Term: Winter 11
Lecturer: Prof. Dr. Michael Bader
Time and Place: Tuesday, 9:30-11:00 (MI 02.07.023); first lecture: Oct 25
Audience: Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing (elective)
Tutorials: ---
Exam: written exam, Thu, Feb 23, 2012 at 14.00 in room MW 0350; repeat exam (written) on Thu, Apr 12, 2012, at 13.00 in room MI 02.07.02
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
Foundations of parallel algorithms and simple models of parallel computation
Algorithms on (weighted) graphs: traversals, shortest paths, etc.

Announcements

Exam Review: on Mon, Mar 19, 2012 from 15.30-17.00, you can look into your exam (for corrections and grading, e.g.); further opportunities for exam review will be offered, if there is respective demand.
Change of time: Lecture was moved from 9.00-10.30 to 9.30-11.00 (starting on Dec 20)

Repeat Exam

the repeat exam will be on Thu, Apr 12, 2012 at 13.00 in room MI 02.07.023; the repeat exam will again be a written exam
Working time will be 90 minutes.
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!
Please use only blue or black ink during the exam.
Exam topics are all topics covered during the lectures except Chapter 9 (Weighted Graphs); see, in particular, the worksheets for this course

Introduction - Algorithms, Fibonacci example (Oct 25): slides
Sorting (Nov 8, Nov 15, Nov 22): slides (lecture on Nov 15 from 9.00 to 9.45, because of Student General Assembly)
Recurrences (Nov 22, Nov 29): slides
More Sorting (Nov 29): slides
Parallel Algorithms and PRAM (Dec 6): slides
Parallel Sorting, Odd-Even MergeSort (Dec 13): slides
Searching (Dec 20): slides
AVL trees(Jan 10): slides
Hash Tables (Jan 17): slides
Graphs (Jan 24): slides
Weighted Graphs (Jan 31): slides (as the lecture on Feb 7 was cancelled, this module will not be part of the exam)

O-notation, etc. (Nov 8): worksheet and solution
Complexity and Sorting (Nov 15): worksheet and solution
MergeSort and Recurrences (Nov 22): worksheet and solution
Parallel Scalar Product and Matrix-Vector Multiplication (Dec 6): worksheet and solution
Sequential and Binary Search (Dec 20): worksheet and solution
AVL trees (Jan 10): worksheet and solution
Hashing (Jan 17): worksheet and solution
Graphs (Jan 31): worksheet and solution

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