Fundamental Algorithms - Winter 10

Term

Winter 10

Lecturer

Dr. 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)

Lecture Notes and Material

Slides from the Lecture

Introduction - Algorithms, Fibonacci example, growth of functions

Nov 2

slides (Update loop invariants, 08.11.)

Sorting Algorithms

Nov 9, 16, 23

slides (few typos corrected, 15.11., Update last slide, 24.11.2011)

Recurrences

Nov 30

slides (corrected prerequisites for Master Theorem, 6.12.)

More Sorting

Dec 7, 14

slides

Selecting

Dec 14, 21

slides

Random Access Machines

Dec 21

slides

Worksheets

Growth of functions

Nov 9

worksheet, solution

Complexity of Algorithms, Sorting on Matrices

Nov 16

worksheet, solution

Recurrences - Complexity of MergeSort and QuickSort

Nov 23

worksheet, solution

CountingSort

Nov 30

worksheet, solution

Recurrences

Dec 07

worksheet, solution

Selecting

Dec 14

worksheet, solution

RAM

Dec 21

worksheet

Literature

Recommended:

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

For parallel RAM:

• Berman, Paul: Fundamentals of Sequential and Parallel Algorithms

Also helpful:

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