Fundamental Algorithms - Winter 13

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)

---

Contents

The course will provide an overview on the analysis of fundamental algorithms. Topics will be:

• 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

• the lectures will start on Monday, Oct 21 (no lecture on Oct 14, due to semester opening)

Lecture Notes and Material

will be made available here throughout the lecture ...

Lecture Slides

Introduction - Algorithms, Fibonacci example, Asymptotics (Oct 21, Oct 28)

slides

Sorting - InsertSort, MergeSort, QuickSort (Oct 28, Nov 4)

slides (with corrected proof for InsertionSort)

Worksheets

O-notation, etc. (Oct 21)

worksheet and solution

Complexity and Sorting (Oct 28)

worksheet

Literature

• 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