Fundamental Algorithms - Winter 09
- 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
- Hashing
- Jan 29
- 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)
- AVL trees
- Jan 22
- worksheet, solution
- Hashing
- Jan 29
- worksheet, solution
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