Fundamental Algorithms - Winter 09
Jump to navigation
Jump to search
- 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.
- Possibility to view your exam results will be given on March 8, 14-16, in office 02.05.057.
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