Fundamental Algorithms (CSE)



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.


  • Introduction – Algorithms, Fibonacci Example, Asymptotic Notation: pdf
  • Sorting: pdf
  • Recurrences: pdf
  • Searching: pdf
  • AVL-Trees: pdf
  • Hashing: pdf
  • PRAM, Introduction to Parallel Algorithms: pdf
  • Parallel Sorting: pdf
  • Graphs: pdf, pptx
  • Weighted Graphs: pdf pdf


  • The exam will take place on Friday, 26th Feb, in room 5101.EG.501.
  • You are allowed to bring a cheat sheet, which must adhere to the following requirements:
    • size DIN A4 or smaller
    • it must be hand-written, on one side only (copies are not allowed)
    • it must carry your name and your student ID number in legible(!) writing
  • no further materials (book, calculate etc.) is allowed