Algorithms and Data Structures

Summer Semester 2024

Summary

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

Main Textbook

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

Supplementary Reading

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 16, 2024

Introduction; concept of asymptotic analysis, big-Oh notation (GTG 3.3.1 and 3.3.2); typical growth functions (GTG 3.2)

Apr 17, 2024

Basic examples: finding the maximum, prefix averages, three-way disjointness, element uniqueness (GTG 3.3.3); arithmetic progression (GTG, Proposition 3.3); experimental analysis

Apr 23, 2024

Fundamental techniques of proof (GTG 3.4); introduction to recursion (GTG 4.1.1)

Apr 24, 2024

Discusson of Exercise Sheet 1; more recursion (GTG 4.1), remark on interpolation search

Apr 30, 2024

Discusson of Exercise Sheet 2; good and bad recursion (selected parts of GTG 4.3 and 4.4)

May 7, 2024

Discusson of Exercise Sheet 3; Low-level arrays, referential arrays, dynamic arrays; amortization (selected parts of GTG Chapter 5)

May 14, 2024

Stacks and queues (GTG 6.1 and 6.2)

May 15, 2024

Discusson of Exercise Sheet 4; Linked lists (selected parts of GTG Chapter 7)

May 22, 2024

Discusson of Exercise Sheet 5; Trees (begin, GTG 8.1)

May 28, 2024

Trees (ctd.): computing depth and height (GTG 8.1.3), binary trees (GTG 8.2), tree traversals (GTG 8.4.1-3)

Discusson of Exercise Sheet 6; linked-list structure for implementing binary trees (GTG 8.3.1)

June 4, 2024

Final tree topics: Binary search trees, 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 5, 2024

Discusson of Exercise Sheet 7; analysis of bottom-up heap construction (GTG 9.3.6); adaptable priority queues (GTG 9.5.2 without Python implementation)

June 11, 2024

Maps, hash tables and skip lists (selected topics from GTG Chapter 10)

June 12, 2024

Discusson of Exercise Sheet 8

test
June 18, 2024

Review of binary search trees, adding and deleting items from a binary search tree, AVL trees (GTG 11.1, 11.3)

June 19, 2024

Discusson of Exercise Sheet 9; splay trees (GTG 11.4, splay tree interactive visualization)

June 25, 2024

Sorting: strict total order, merge sort, quicksort, \(O(n \log n)\) lower bound on general sequences, bucket sort (GTG 12.1-4)

June 26, 2024

Discusson of Exercise Sheet 10, comparison of sorting algorithms

July 2, 2024

Introduction to graphs, data structures for graphs (GTG 14.1, 14.2)

July 3, 2024

Discusson of Exercise Sheet 11, graph traversals (GTG 14.3)

July 9, 2024

Mock Exam, in class

July 10, 2024

Shortest path, Dijkstra’s algorithm (GTG 15.6)

July 16, 2024

Discussion of the mock exam

July 17, 2024

Minimum spanning trees (GTG 14.7), topological sorting of directed acyclic graphs (GTG 14.5)

July 30, 2024

Final Exam, 10:00-11:30, NB-101