Term: Winter 14
Lecturer: Prof. Dr. Michael Bader
Time and Place: Mon 8.30-10.00, lecture hall MI HS 3 (first lecture on Oct 13, 8.30)
Audience: Computational Science and Engineering; Biomedical Computing (elective)
Tutorials: ---
Exam: written exam, repeat on Wed, Apr 15, 2015 at 16.30 in lecture room MI 02.07.23 (see details below)
Semesterwochenstunden / ECTS Credits: 2 SWS (2V) / 3 ECTS
TUMonline: https://campus.tum.de/tumonline/lv.detail?clvnr=950160214 (lecture),
https://campus.tum.de/tumonline/WBMODHB.wbShowMHBReadOnly?pKnotenNr=458187&pOrgNr=14189 (module description)

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
Foundations of parallel algorithms and simple models of parallel computation
Algorithms on (weighted) graphs: traversals, shortest paths, etc.

Lecture Notes and Material

Lecture Slides

Introduction - Algorithms, Fibonacci example, Asymptotics (Oct 13, 20): slides
Sorting - InsertSort, MergeSort, QuickSort, BucketSort (Oct 20, 27; Nov 3): slides; (corrected partitioning algorithm, now fully according to Hoare's algorithm; the previous partitioning algorithm only worked, if all elements of A have distinct size)
Recurrences (Nov 3): slides
Searching (Nov 10, 17): slides
AVL trees(Nov 10, 17): slides
Hash Tables (Nov 24): slides
Parallel Algorithms and PRAM (Dec 1, 8): slides
Parallel Sorting, Odd-Even MergeSort (Dec 8, 15): slides
Graphs (Dec 15, Jan 12): slides
Weighted Graphs (Jan 12, Jan 19): slides
Exam (Jan 26): Due to the exam on Jan 26, there will be no lecture on that day

a repeat exam will be offered on Wed, Apr 15, 16.30 (MI 02.07.023)
- the exam will be written
- all rules (helping material, etc.) are identical to the first exam
please by at the lecture hall in time (16.15) - the exam will start precisely at 16.30 and there will be announcements before starting
Working time will be 90 minutes.
Helping material: you are allowed to use one sheet (size A4) of paper with hand-written(!) notes (on both sides) during the exam. Any further helping material (books, calculators, etc.) is forbidden!
Please use only blue or black ink during the exam.
Exam topics are all topics covered during the lectures; see, in particular, the worksheets for this course
- Dijkstra and Prim Algorithm from Chapter 9 (Weighted Graphs) are excluded from the exam

Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms; MIT Press
Berman, Paul: Algorithms: Sequential, Parallel, and Distributed; Cengage Learning Emea 2004
Heun: Grundlegende Algorithmen; Vieweg 2000
Sedgewick: Algorithms; Pearson Education
Shackleford, Computing and Algorithms; Addison Wesley Longman
Kleinberg, Tardos: Algorithm Design; Pearson Education