Spelman College — Spring 2026
This course builds on the first data structures course, focusing on algorithm analysis, advanced data structures, and core algorithm design paradigms. We emphasize rigorous complexity analysis while implementing concepts in C++. Topics include asymptotic notation, balanced trees, graphs, greedy algorithms, dynamic programming, and an introduction to complexity theory.
| Week | Topics | Weiss / CLRS | Materials | Assignment |
|---|---|---|---|---|
| 1 | Course Overview | Ch. 1 / Ch. 1 | Slides | |
| 2 | Empirical Analysis & Timing Code Why analysis matters, timing experiments, growth rates |
Ch. 2.1–2.3 / Ch. 2 | Slides | HW1: Growth Rates |
| 2 | Big-O Notation Asymptotic notation (O, Ω, Θ), formal definitions, proving bounds |
Ch. 2.4 / Ch. 3 | Slides | HW2: Asymptotic Analysis |
| 3 | Analyzing Iterative Code Loops, nested loops, common patterns |
Ch. 2.4 / Ch. 2–3 | Slides Practice | HW3: Code Complexity HW4: Analyzing Code |
| 4 | Mathematical Foundations Logarithms, exponents, summations, proof techniques |
Ch. 1.4–1.7, App. / Ch. A | Slides | HW5: Proof by Induction |
| 5 | Divide and Conquer, Recursion & Recurrences Recursive algorithms, Three-Case Recurrence Theorem, unrolling |
Ch. 2.4 / Ch. 4 | Slides Strassen's Algorithm | HW6: Recurrences [Sol] |
| 6 | Midterm Review | Practice Midterm Solutions Extra Practice Solutions | ||
| 7 | Searching & Sorting Binary search, merge sort, quick sort, complexity analysis |
Ch. 7 / Ch. 6–7 | Slides | |
| 8 | Data Structures Review Arrays, lists, stacks, queues, trees, heaps, hash tables |
Ch. 3–5 / Ch. 10–11 | Slides Applied Problems | HW7: Data Structures [Sol] |
| 9 | Amortized Analysis Dynamic arrays, aggregate method, accounting & potential methods |
Ch. 3.5 / Ch. 17 | Slides | |
| 10 | Balanced Trees (AVL) Why balancing matters, rotations (LL, RR, LR, RL), O(log n) guarantee |
Ch. 4.4 / Ch. 13 | Slides | |
| 11 | Graphs Representations (matrix vs. list), BFS & DFS, applications |
Ch. 9 / Ch. 20–22 | Slides | |
| 12–13 | Project Presentations | Ω(n log n) Lower Bound Counting Inversions Euclid's Algorithm & RSA Stern-Brocot Tree Three-Case Recurrence Quicksort Average Case | ||
| 14 | Greedy Algorithms & Dynamic Programming | Slides | ||
| 15 | Complexity Theory Problem classes (P, NP), NP-completeness, decidability overview |
Ch. 9.7 / Ch. 34 | Slides | |
| 15 | Review & Integration | Practice Final Solutions Extra Practice Solutions | ||
| 16 | Final Exam |