Fundamental Algorithms - Winter 09

Term

Winter 09

Lecturer

Dr. Michael Bader

Time and Place

Friday, 9-11, lecture hall MI 03.07.023 (!room change!)

Audience

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

Tutorials

-

Exam

written exam (t.b.a.)

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.
• Artithmetic Problems: parallel prefix computation, parallel matrix and vector operations
• Graph Algorithms: Transitive Closure, Shortest Path Problems, Minimum Spanning Trees (if time allows)

Lecture Notes and Material

Slides from the Lecture

Introduction - Algorithms, Fibonacci example, growth of functions

Oct 30, Nov 6

slides

Sorting Algorithms

Nov 6, Nov 13

slides

More Sorting

Nov 20, Nov 27

slides

Worksheets

Growth of functions

Oct 30

worksheet, solution

Complexity of Algorithms, Sorting on Matrices

Nov 6

worksheet, solution

Recurrences - Complexity of MergeSort and QuickSort

Nov 13

worksheet, solution

CountingSort

Nov 20

worksheet

Further Material

• Lecture notes (on CSE Teaching Centre)

Literature

• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, MIT Press
• Heun: Grundlegende Algorithmen, Vieweg 2000
• Sedgewick: Algorithms, Pearson Education
• Shackleford, Computing and Algorithms, Addison Wesley Longman
• Kleinberg, Tardos: Algorithm Design, Pearson Education