Fundamental Algorithms - Winter 14

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 at end of semester

Semesterwochenstunden / ECTS Credits

2 SWS (2V) / 3 ECTS

TUMonline

https://campus.tum.de/tumonline/lv.detail?clvnr=950160214 (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.

Lecture Notes and Material

will be made available during the course.

Lecture Slides

Introduction - Algorithms, Fibonacci example, Asymptotics (Oct 13, 20)

slides

Sorting - InsertSort, MergeSort, QuickSort (Oct 20, 27)

slides

Worksheets

O-notation, etc. (Oct 13)

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