Revision as of 13:42, 8 November 2013

Term: Winter 13
Lecturer: Prof. Dr. Michael Bader
Time and Place: Mon 8.30-10.00, lecture hall MI HS 3 (first lecture on Oct 21, 8.30)
Audience: Computational Science and Engineering; Biomedical Computing (elective)
Tutorials: ---
Exam: written exam at end of semester
Semesterwochenstunden / ECTS Credits: 2 SWS (2V) / 3 ECTS
TUMonline: https://campus.tum.de/tumonline/lv.detail?clvnr=950121698 (lecture),
https://campus.tum.de/tumonline/wbStpModHB.detailPage?&pKnotenNr=458187 (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.

Announcements

in the slot on Dec 23, we will do a short (40min) test exam, with discussion of solutions afterwards;
participation is entirely optional (questions and solutions will be made available towards the end of the Christmas holidays)
the lectures will start on Monday, Oct 21 (no lecture on Oct 14, due to semester opening)

will be made available here throughout the lecture ...

Introduction - Algorithms, Fibonacci example, Asymptotics (Oct 21, Oct 28): slides
Sorting - InsertSort, MergeSort, QuickSort (Oct 28, Nov 4, Nov 11): slides (with corrected proof for InsertionSort)
Recurrences (Nov 11): slides

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

@@ Line 33: / Line 33: @@
 ; Sorting - InsertSort, MergeSort, QuickSort (Oct 28, Nov 4, Nov 11)
 : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/fundalg02.pdf slides] (with corrected proof for InsertionSort)
+; Recurrences (Nov 11)
+: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS13/fundalg02b.pdf slides]
 <!--
-; Recurrences (Nov 22, Nov 29)
-: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg02b.pdf slides]
 ; More Sorting (Nov 29)
 : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg03.pdf slides]