Revision as of 19:41, 7 February 2012

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: t.b.a. (no compulsory tutorials; there might be a few extra lessons on a voluntary basis)
Exam: written exam
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

Announcements

Change of time: Lecture was moved from 9.00-10.30 to 9.30-11.00 (starting on Dec 20)
Exam: the final exam will be on Thu, Feb 23, 2012 (14.00-16.00)

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): worksheetand 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

@@ Line 46: / Line 46: @@
 : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg08.pdf slides]
 ; Weighted Graphs (Jan 31)
-: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg09.pdf slides]
+: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/fundalg09.pdf slides] (as the lecture on Feb 7 was cancelled, this module will not be part of the exam)
 == Worksheets ==
@@ Line 64: / Line 64: @@
 : [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg7.pdf worksheet] and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg7sol.pdf solution]
 ; Graphs (Jan 31)
-: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg8.pdf worksheet]
+: [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg8.pdf worksheet]and [http://www5.in.tum.de/lehre/vorlesungen/fundalg/WS11/worksheets/fundalg8sol.pdf solution]
 == Literature ==