Fundamental Algorithms - Winter 11

Term

Winter 11

Lecturer

Prof. Dr. Michael Bader

Time and Place

Tuesday, 9:00-10:30, (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}}}

---

Contents

The course will provide an overview of fundamental algorithms and an introduction to the analysis of 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

Lecture Notes and Material

Slides from the Lecture

Introduction - Algorithms, Fibonacci example (Oct 25)

slides

Sorting (Nov 8, Nov 15)

slides (lecture on Nov 15 from 9.00 to 9.45, because of Student General Assembly)

Worksheets

O-notation, etc. (Nov 8)

worksheet and solution

Complexity and Sorting (Nov 15)

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