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

May 20, 2025

Deques (GTG 6.3); linked lists (GTG Chapter 7)

May 21, 2025

Discusson of Exercise Sheet 3 - solutions and Exercise Sheet 4 - solutions

May 27, 2025

Trees, including basic definitions from graph theory (GTG 8.1; also see lecture notes from Foundations of Information Systems on foundations of graph theory); computing depth and height (GTG 8.1.3), binary trees (GTG 8.2), tree traversals (GTG 8.4.1-3)

May 28, 2025

Discusson of Exercise Sheet 5 - solutions

June 3, 2025

Linked-list structure for implementing binary trees (GTG 8.3.1), array-based implementation of a tree (parts of GTG 8.4.3, GTG 8.3.2); priority queues, heaps, heap sort (GTG Chapter 9, without implementation details)

June 4, 2025

Discusson of Exercise Sheet 6 - solutions; Review of heap sort, bottom-up heap construction (GTG 9.3.6)

June 11, 2025

Discusson of Exercise Sheet 7 - solutions; Maps and hash tables (GTG 10.1 and 10.2)

June 17, 2025

Sorted maps, maxima sets, skip lists (selected topics from GTG 10.3 and 10.4)

June 18, 2025

Discusson of Exercise Sheet 8 - solutions; Binary search trees (GTG 11.1), AVL trees (start)

June 24, 2025

AVL trees (GTG 11.2, 11.3), splay trees (start)

June 25, 2025

No class

July 1, 2025

Splay trees, sorting (start)