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

• Sara Baase, Allen Van Gelder Computer Algorithms: Introduction to Design and Analysis, 3rd eds. Pearson, 1999. [BG]
  (chapter 5 and Algorithm 1.3 in the back of the notes - only available in Itslearning due to copyright rules)
• 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. In earlier courses, we have used some of these textbooks already [CLRS, Rosen]. 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
• Meldable Priority Queues

Extra Material for Exercises

• Red-black trees rebalancing operations

Exercise Solutions by the TAs

The TAs have prepared exercise sheets. These are sheets containing the problem formulation together with illustrations or other parts from the textbook that may be referred to in a particular exercise. This may be easier than moving back and forth in the book.

After the exercises, the TAs have offered to upload the solutions. However, I cannot stress enough how important it is that you work with the exercises yourself until the point where you cannot get further. Then go to the exercises or read the solutions if you're prevented from attending the exercises. You learn the material much better that way than if you just read the solution immediately. This is especially true if you want to get better at proofs.

Topic	Exercise Sheet	Solution Sheet
Introduction. Network Flows.	pdf	pdf
Discrete Probability Theory.	pdf	pdf
Network Flows: Edmonds-Karp and Examples.	pdf	pdf
Randomized Algorithms: Contention Resolution, Global Minimum Cut.	pdf	pdf
Randomized Algorithms: Waiting Times, MAX 3-SAT Approximation.	pdf	pdf
Randomized Quicksort and Selection.	pdf	pdf
Amortized Analysis: Stack, Counter, Dynamic Tables.	pdf	pdf
Amortized Analysis: Stack, Counter, Dynamic Tables (2).	pdf	pdf
String Matching: Naive, Rabin-Karp, Finite Automata.	pdf	pdf
String Matching: Finite Automata, Knuth-Morris-Pratt.	pdf	pdf
Online Algorithms.	pdf	pdf
Deterministic Selection. Adversarial Lower Bound Techniques.	pdf	pdf

 

---