Fundamental Algorithms - Winter 10

From Sccswiki
Jump to navigation Jump to search
Winter 10
Dr. Dirk Pflüger
Time and Place
Tuesday, 9:00-10:30, lecture hall MI 02.07.023; first lecture November 2
Computational Science and Engineering, 1st semester (Module IN2157); Biomedical Computing
repeat exam (date: May 02, 2011; 16:30-18:00 in room MI 02.07.023
Semesterwochenstunden / ECTS Credits
2 SWS (2V) / 3 Credits


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

  • Master Thesis? Student project? We're always looking for you! See Student Projects and/or ask me!
  • See the updates on corrections.
  • Exam details below.

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. - corrected partitioning algorithm, Python implementations available at [1], [2], call with "Python", 3.2.)
Nov 30
slides (corrected prerequisites for Master Theorem, 6.12.)
More Sorting 
Dec 7, 14
Dec 14, 21
Random Access Machines 
Dec 21
slides (introduced Vector x, 21.12.) - NEW: RAM Simulator online!
The PRAM Model 
Jan 11
slides (Update of three slides, 12.01.)
Jan 18
slides (update assumptions on slide 4, 18.01.)
AVL Trees 
Jan 25
Feb 1
slides (update formula multiplication method, numbers on slide 19, 1.2.)


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
Nov 30
worksheet, solution (27.1. corrected error in solution 2a, third loop)
Dec 07
worksheet, solution
Dec 14
worksheet, solution (27.1. corrected solution for exercise 2: call to larger partition)
Dec 21
worksheet, solution (31.1. corrected line 16 RAM program: "=" -> ">"; 7.2. corrected resulting line 15, R6-R7 -> R7-R6 (thanks for both comments); 9.2. sorry, changed everything back again: the original version was correct, I included a full list of all RAM states for reference, note the definition of the subtraction!)
Jan 8
worksheet, solution (1.2. corrected typeos in ScalarProductPar and MatrixVectorProductEREW)
Jan 18
worksheet, solution
AVL trees 
Jan 25
worksheet (28.1. corrected typeo: first "TreeInsert(5)" should be "TreeDelete(5)", solution
Feb 1
worksheet, solution


  • Date of repeat exam: Moday, May 02, 16:30-18:30 in room MI 02.07.023, see TUMonline
  • Helping material: you are allowed to use one sheet (size A4) of paper with hand-written(!) notes during the exam. Any further helping material (books, calculators, etc.) is forbidden!
  • Exam topics are all topics covered during the lectures; see, in particular, the worksheets for this course



  • 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