Algorithms and Data Structures is a first course on fundamental data structures and algorithms. It covers theoretical analysis as well as implementation in Python. It is currently addressing students of the BWL Master, speciaization Business Analytics and Operations Research. It is further suitable for students in Digital and Data-Driven Business.
Introduction; concept of asymptotic analysis, big-Oh notation (GTG 3.3.1 and 3.3.2); example: searching in a dictionary – linear search vs. binary search vs. interpolation search; typical growth functions (GTG 3.2)
Experimental analysis; arithmetic and geometric progression; finding the maximum: pseudocode and Python implementation
Getting started with Python; example: prefix averages (from GTG 3.3.3)
Further elementary examples: three-way disjointness, element uniqueness (GTG 3.3.3 ctd.); recursion: factorial, English ruler, disk usage, binary search revisited (GTG 4.1), element uniqueness gone bad (GTG 4.3)
Finish off experimental comparison of the three algorithms for computing prefix averages (Sheet 1-2, Exercise 1); Discussion of example algorithms from GTG p. 143 (Sheet 1-2, Exercise 2); Discussion of the “all sheep are black”-paradox; \(O(n^2)\) recursive implementation of element uniqueness problem
Analyzing recursive algorithms (GTG 4.2), further topics on recursion from remainder of GTG Chapter 4
Discussion of Exercise Sheet 3, play the Tower of Hanoi game
Linear vs. binary recursion (GTG 4.4.2); Lists in Python, dynamic arrays and amortization (GTG 5.2, 5.3)
Discussion of Exercise Sheet 4
Dynamic array class implementation (GTG 5.3.1), lower bound on append complexity (GTG Proposition 5.2), efficiency of Python’s list class (GTG 5.4.1)
Discussion of Exercise Sheet 5
Stacks, queues, and deques (GTG Chapter 6)
Discussion of Exercise Sheet 6
Linked lists (basic ideas without implementation details from GTG Chapter 7), linked lists vs. dynamic arrays (GTG 7.7); trees: definition and properties (GTG 8.1.1), depth and height (GTG 8.1.3), binary trees (initial parts of 8.2, 8.2.2)
Implementation of a deque (final problem from Exercise Sheet 6)
Tree traversals: preorder, postorder, in-order, breadth first (GTG 8.4.1, 8.4.2, 8.4.3); priority queues, heaps (GTG 9.1, 9.3)
Implementation details of trees and tree traversals
Heap-sort, comparison with insertion-sort and selection-sort, in-place implementation (GTG 9.4)
Discussion of the mock exam review sheet
Maps, hash tables, and skip lists (GTG 10.1, 10.2, 10.4, 10.4.1 without implementation)
Mock Exam
Binary search trees (GTG 11.1, 11.2 without implementation details), AVL trees (GTG 11.3)
Discussion of mock exam
High-level discussion of splay trees and red-black trees (see GTG 11.4, 11.6 without technical details), high-level discussion of sorting algorithms: review of insertion-sort, selection-sort, heap-sort, compare with merge-sort and quick-sort (GTG 12.5), introduction to graphs (GTG 14.1, definitions only)
Dijkstra’s algorithm for shortest path (GTG 14.6), implementation of in-place quicksort