Fundamental Algorithms - Winter 09: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
| audience = Computational Science and Engineering, 1st semester (Module [http://drehscheibe.in.tum.de/myintum/kurs_verwaltung/cm.html?id=IN2157 IN2157]); Biomedical Computing | | audience = Computational Science and Engineering, 1st semester (Module [http://drehscheibe.in.tum.de/myintum/kurs_verwaltung/cm.html?id=IN2157 IN2157]); Biomedical Computing | ||
| tutorials = - | | tutorials = - | ||
| exam = written exam (date: Feb | | exam = written exam (date: Feb 12, 2010; 10-12 in room MI 02.07.23) | ||
}} | }} | ||
| Line 61: | Line 61: | ||
; Searching : Jan 22 | ; Searching : Jan 22 | ||
: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg10.pdf worksheet] | : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/worksheets/fundalg10.pdf worksheet] | ||
= Exam = | |||
* Date of final exam: Friday, Feb 12, 10-12 in room MI 02.07.023 | |||
* Helping material: you are allowed to use '''one sheet (size A4) of paper''' with '''hand-written(!) notes''' during the exam. Any further helping material (books, calculators, etc.) is forbidden! | |||
* Exam topics are all topics covered during the lectures; see, in particular, the worksheets for this course | |||
* Repeat exam: a repeat exam will offered (only for students who failed the regular exam) in April 2010. The exam will be written or oral, depending on the number of participants. | |||
== Further Material == | == Further Material == | ||
Revision as of 12:11, 22 January 2010
- Term
- Winter 09
- Lecturer
- Jun.-Prof. Dr. Michael Bader
- Time and Place
- Friday, 9-11, lecture hall MI 03.07.023 (!room change!)
- Audience
- Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing
- Tutorials
- -
- Exam
- written exam (date: Feb 12, 2010; 10-12 in room MI 02.07.23)
- Semesterwochenstunden / ECTS Credits
- 2 SWS (2V) / 3 Credits
- TUMonline
- {{{tumonline}}}
Contents
The course will provide an overview of fundamental algorithms and an introduction to the analysis of algorithms. Topics will be:
- Fundamentals: Models of Computation, Complexity Measures
- Sorting: Bubble-Sort, Merge-Sort, Quick-Sort, Median-Algorithms, Lower Bounds, etc.: sorting in parallel
- Searching: Hashing, Search Tress, etc.
- Arithmetic Problems: parallel prefix computation, parallel matrix and vector operations
- Graph Algorithms: Transitive Closure, Shortest Path Problems, Minimum Spanning Trees (if time allows)
Lecture Notes and Material
Slides from the Lecture
- Introduction - Algorithms, Fibonacci example, growth of functions
- Oct 30, Nov 6
- slides
- Sorting Algorithms
- Nov 6, Nov 13
- slides
- More Sorting
- Nov 20, Nov 27
- slides
- Selecting
- Dec 04
- slides
- Random Access Machines
- Dec 11
- slides
- Recurrences
- Dec 18
- slides
- The PRAM Model
- Jan 8
- slides
- Searching
- Jan 15
- slides
- AVL Trees
- Jan 22
- slides
Worksheets
- Growth of functions
- Oct 30
- worksheet, solution
- Complexity of Algorithms, Sorting on Matrices
- Nov 6
- worksheet, solution
- Recurrences - Complexity of MergeSort and QuickSort
- Nov 13
- worksheet, solution
- CountingSort
- Nov 20
- worksheet, solution
- Selecting
- Dec 4
- worksheet, solution
- RAM
- Dec 11
- worksheet, solution
- PRAM
- Jan 8
- worksheet
- Searching
- Jan 15
- worksheet; for solution, see skript on virtual teaching centre (sections on searching on binary search trees)
- Searching
- Jan 22
- worksheet
Exam
- Date of final exam: Friday, Feb 12, 10-12 in room MI 02.07.023
- Helping material: you are allowed to use one sheet (size A4) of paper with hand-written(!) notes during the exam. Any further helping material (books, calculators, etc.) is forbidden!
- Exam topics are all topics covered during the lectures; see, in particular, the worksheets for this course
- Repeat exam: a repeat exam will offered (only for students who failed the regular exam) in April 2010. The exam will be written or oral, depending on the number of participants.
Further Material
Literature
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press
- Heun: Grundlegende Algorithmen, Vieweg 2000
- Sedgewick: Algorithms, Pearson Education
- Shackleford, Computing and Algorithms, Addison Wesley Longman
- Kleinberg, Tardos: Algorithm Design, Pearson Education