Algorithms and Data Structures

Summer Semester 2025

Summary

Algorithms and Data Structures is a first course on fundamental data structures and algorithms. It covers theoretical analysis based on implementations in Python.

Quick Links

• Module on KU.Campus
• Lecture instance on KU.Campus
• Tutorial instance on KU.Campus
• Python code
• Exercises
• Exams
• Repository with all Python codes from GTG
• Old class web page from Summer 2024

Main Textbook

• M.T. Goodrich, R. Tamassia, and M.H. Goldwasser, Data Structures and Algorithms in Python, Wiley, 2013

Supplementary Reading

• J. Erickson, Algorithms, 2019
• K.D. Lee and S. Hubbard, Data Structures and Algorithms with Python, Springer, 2015
• B. Miller and D. Ranum, Problem Solving with Algorithms and Data Structures, 2013
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2009

Grading

• Weekly exercise assignments, not to be turned in, not graded. However, you are strongly encouraged to work on them before they are discussed in the exercise session on Wednesday
• The grade for this class is determined by one final exam
• There will be a “mock exam” 3-4 weeks before the final exam. Passing the mock exam will add a grade bonus of 1/3 of a grade step to your final grade. Note that the pass/fail decision is not affected by the bonus, and the top grade can be achieved without the bonus.

Topics

Apr 22, 2025

Introduction; concept of asymptotic analysis, big-Oh notation (GTG 3.3.1 and 3.3.2); typical growth functions (GTG 3.2); Basic examples: finding the maximum, prefix averages, three-way disjointness, element uniqueness (GTG 3.3.3); arithmetic progression (GTG, Proposition 3.3)

Apr 23, 2025

No class due to university function

Apr 29, 2025

Basic examples (ctd.); geometric and arithmetic progression revisited; fundamental techniques of proof (GTG 3.4), experimental analysis

Apr 30, 2025

Discusson of Exercise Sheet 1 - solutions; Recursion (GTG Chapter 4)

May 6, 2025

Recursion: using induction to prove operation counts; Low-level arrays, referential arrays, dynamic arrays; amortization (selected parts of GTG Chapter 5)

May 7, 2025

Discusson of Exercise Sheet 2 - solutions; Amortization revisited - shrinking dynamic arrays; further properties of array operations (GTG Chapter 5 ctd.)

May 13, 2024

Stacks and queues (GTG 6.1 and 6.2)

May 14, 2025

No class