Material will be added gradually during the course.

The course will primarily be based on excerpts from the following books:

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 4th eds., MIT Press, 2022. ISBN 9780262046305. [CLRS]
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd eds., MIT Press, 2009. ISBN 9780262033848. [CLRS3rd]
  (via the 4th edition home page, click "Resources" and then "Materials Removed from 3e" to download a zip file containing, among many other things, the section on perfect hashing)
• Jon Kleinberg, Eva Tardos, Algorithm Design, Pearson, 2005. ISBN 9780321295354. [KT]
  (parts of chapter 13 - only available in Itslearning due to copyright rules)
• Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th eds., McGraw-Hill Educations, 2019. [Rosen]

Some parts may be made available on the learning platform. Which parts we will use will be announced later. Thus, if you have been enrolled at SDU from the beginning of your education, you may not need to buy any new books.

My (supplementary) errata to the books by

• Kleinberg & Tardos

Lecture Slides

• Online Algorithms

Exercise Solutions by TA Mads Anker Nielsen

1. Introduction. Network Flows.
2. Network Flows: Edmonds-Karp and Examples.
3. Randomized Algorithms: Contention Resolution, Global Minimum Cut.
4. Randomized Algorithms: Waiting Times, MAX 3-SAT Approximation.
5. Randomized Quicksort and Selection.
6. Amortized Analysis: Stack, Counter, Dynamic Tables.
7. Amortized Analysis: Stack, Counter, Dynamic Tables (2).
8. String Matching: Naive, Rabin-Karp, Finite Automata.
9. String Matching: Finite Automata, Knuth-Morris-Pratt.

• Red-black trees rebalancing operations

Further material related to lectures will be listed here as soon as relevant.

 

---