Fundamental Algorithms - Winter 10

Term

Winter 10

Lecturer

Dr. rer. nat. Dirk Pflüger

Time and Place

Tuesday, 9:00-10:30, lecture hall MI 02.07.023; first lecture November 2

Audience

Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing

Tutorials

-

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
• Graph Algorithms: Transitive Closure, Shortest Path Problems, Minimum Spanning Trees (if time allows)

Current News

In the hope that the file system problems will eventually be resolved, a few announcements:

• On Tuesday, Nov. 16, we will have only 45 minutes lecture due to SVV (Studentische Vollversammlung [1] in MW2001)
• Yes, we're in the seminar room 02.07.023
• The slides are online
• Literature recommendations are listed below

Lecture Notes and Material

Slides from the Lecture

Introduction - Algorithms, Fibonacci example, growth of functions

Nov 2

slides (Update loop invariants, 08.11.2010)

Sorting Algorithms

Nov 9

slides

Worksheets

Growth of functions

Nov 9

worksheet, solution

Complexity of Algorithms, Sorting on Matrices

Nov 16

worksheet

Literature

Recommended:

• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press

Also helpful:

• Heun: Grundlegende Algorithmen, Vieweg 2000
• Sedgewick: Algorithms, Pearson Education
• Shackleford, Computing and Algorithms, Addison Wesley Longman
• Kleinberg, Tardos: Algorithm Design, Pearson Education