Fundamental Algorithms - Winter 14

From Sccswiki
Jump to navigation Jump to search
Winter 14
Prof. Dr. Michael Bader
Time and Place
Mon 8.30-10.00, lecture hall MI HS 3 (first lecture on Oct 13, 8.30)
Computational Science and Engineering; Biomedical Computing (elective)
written exam, repeat on Wed, Apr 15, 2015 at 16.30 in lecture room MI 02.07.23 (see details below)
Semesterwochenstunden / ECTS Credits
2 SWS (2V) / 3 ECTS
TUMonline (lecture), (module description)


The course will provide an overview on the analysis of fundamental 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
  • Algorithms on (weighted) graphs: traversals, shortest paths, etc.

Lecture Notes and Material

Lecture Slides

Introduction - Algorithms, Fibonacci example, Asymptotics (Oct 13, 20)
Sorting - InsertSort, MergeSort, QuickSort, BucketSort (Oct 20, 27; Nov 3)
(corrected partitioning algorithm, now fully according to Hoare's algorithm; the previous partitioning algorithm only worked, if all elements of A have distinct size)
Recurrences (Nov 3)
Searching (Nov 10, 17)
AVL trees(Nov 10, 17)
Hash Tables (Nov 24)
Parallel Algorithms and PRAM (Dec 1, 8)
Parallel Sorting, Odd-Even MergeSort (Dec 8, 15)
Graphs (Dec 15, Jan 12)
Weighted Graphs (Jan 12, Jan 19)
Exam (Jan 26)
Due to the exam on Jan 26, there will be no lecture on that day


O-notation, etc. (Oct 13)
worksheet and solution
Complexity and Sorting (Oct 20)
worksheet and solution (corrected Ex. 1)
MergeSort (Oct 27)
worksheet and solution
Recurrences(Nov 3)
worksheet and solution
Sequential and Binary Search (Nov 10)
worksheet and solution
AVL trees (Nov 17)
worksheet and solution
Hashing (Nov 24)
worksheet and solution
PRAM - Linear Algebra and Prefix Problem (Dec 1)
worksheet and solution
PRAM - Prefix Problem and BucketSort (Dec 8)
worksheet and solution
Graphs (Dec 15)
worksheet and solution
Hypergraphs and Bipartite Graphs (Jan 19, optional)
worksheet and solution


  • a repeat exam will be offered on Wed, Apr 15, 16.30 (MI 02.07.023)
    • the exam will be written
    • all rules (helping material, etc.) are identical to the first exam
  • please by at the lecture hall in time (16.15) - the exam will start precisely at 16.30 and there will be announcements before starting
  • Working time will be 90 minutes.
  • Helping material: you are allowed to use one sheet (size A4) of paper with hand-written(!) notes (on both sides) during the exam. Any further helping material (books, calculators, etc.) is forbidden!
  • Please use only blue or black ink during the exam.
  • Exam topics are all topics covered during the lectures; see, in particular, the worksheets for this course
    • Dijkstra and Prim Algorithm from Chapter 9 (Weighted Graphs) are excluded from the exam


  • 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