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 15, 2010)
Semesterwochenstunden / ECTS Credits: 2 SWS (2V) / 3 Credits
TUMonline: {{{tumonline}}}

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

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