Schedule

Week Date Content
1 Mon Jan 20 (Holiday) Martin Luther King, Jr. Day
Tue Jan 21
Wed Jan 22
Thu Jan 23
2 Tue Jan 28
Thu Jan 30
3 Tue Feb 4
Wed Feb 5
Thu Feb 6
  • Checkpoint 1: Running Time and Invariants
    • Loop Invariants
    • Total Running Time
    • Asymptotic Running Time Proofs
4 Tue Feb 11
Thu Feb 13
5 Tue Feb 18
Wed Feb 19
Thu Feb 20
  • Checkpoint 2: Recursion and Probability
    • Recurrences and Recursion Trees
    • Divide and Conquer Algorithms
      • Merge Sort
      • Closest Pair
      • Quicksort
      • Randomized Selection
      • Deterministic Selection
    • Master Method
    • Expected Values
    • Linearity of Expectation
6 Tue Feb 25
Thu Feb 27
7 Tue Mar 4
Wed Mar 5
Thu Mar 6
  • Checkpoint 3: Graph Theory
    • Connectivity
    • BFS and DFS
    • Topological Orderings
    • Graph Representations
    • Kosaraju’s Algorithm (and SCCs)
    • Dijkstra’s Algorithm (and SSSP)
8 Tue Mar 11
Thu Mar 13
9 Tue Mar 18 Spring break
Thu Mar 20 Spring break
10 Tue Mar 25
Wed Mar 26
Thu Mar 27
  • Checkpoint 4: Data Structures and Memory
    • Heaps
    • Binary Search Trees
    • Red-Black Trees
    • Hash Tables
    • Universal Hashing
Fri Mar 28 (Holiday) César Chávez Day
11 Tue Apr 1
Thu Apr 3
12 Tue Apr 8
Wed Apr 9
Thu Apr 10
  • Checkpoint 5: Greedy Algorithms
    • Greedy scheduling
    • Minimum spanning trees (Prim’s and Kruskal’s)
    • Exchange Arguments
13 Tue Apr 15
Thu Apr 17
14 Tue Apr 22
Wed Apr 23
Thu Apr 24
  • Checkpoint 6: Dynamic Programming
    • Dynamic Programming Properties
    • The Knapsack Problem
    • The Bellman-Ford Algorithm
    • The Floyd-Warshall Algorithm
    • Sequence Alignment
    • Jump-It
15 Tue Apr 29
Thu May 1
16 Tue May 6
Wed May 7
  • All grading walk-throughs must be complete
Thu May 8 Reading day
Fri May 9 Reading day
17 Thu May 15
  • 2:00 - 5:00 p.m.
  • Checkpoint 7: Complexity and Reductions
    • Complexity Classifications
    • Reductions
    • Approximation Algorithms

Modules

Module 1: Introduction

In this first module we will focus on the language of algorithms and how we will conduct proofs and time complexity analysis.

  • Administrivia
  • Terminology
  • Insertion Sort
  • Loop Invariant Proofs
  • Asymptotic Notation
  • Running Times
  • Sorting Algorithms

Module 2: Divide-and-Conquer Algorithms and Randomized Algorithms

Next we will discuss algorithms that work by repeatedly “simplifying” the problem and combining solutions to simplified problems. We will then transition from divide-and-conquer algorithms into algorithms that leverage randomness to have provably “good” average performance.

  • Recurrences
  • Merge Sort
  • The Closest Pair Problem
  • The Master Method and Recursion Trees
  • Probability Review
  • QuickSort
  • Randomized and Deterministic Selection
  • Order Statistics
  • Sorting Lower Bound

Module 3: Graph Theory

Our next module will cover graph theory. These algorithms and data structures have a surprisingly large number of practical applications.

  • Graph Connectivity
  • Breadth-First Search
  • Depth-First Search
  • Topological Sort
  • Graph Representations
  • Dijkstra’s Algorithm
  • A* Search
  • Kosaraju’s Algorithm

Module 4: Advanced Data Structures

Related to graphs, we will next discuss binary trees, which are typically an ordered data structure. After BSTs we will discuss one of the most widely used data structures: hash tables. When in doubt, use an array or a hash table.

  • Heaps
  • Fibonacci Heap Data Structure
  • Amortized Analysis
  • Binary Search Trees (BSTs)
  • Balanced BSTs (e.g., Red-Black Trees)
  • Hash Tables
  • Universal Hashing
  • Memory and Locality

Module 5: Greedy Algorithms

We’ll wrap up the course discussing two types of algorithm design paradigms. First, we’ll discuss greedy algorithms, which focus on repeatedly making simple decisions and never going back to look for better results.

  • Greedy Scheduling
  • Minimum Spanning Trees (Prim’s and Kruskal’s)
  • Huffman Codes
  • Max-Spacing k-Clustering
  • The Knapsack Problem
  • Exchange Arguments

Module 6: Dynamic Programming

Contrasted to greedy algorithms, dynamic programming algorithms (effectively) look at many possible solutions by leveraging overlapping sub-problems and optimal substructure.

  • The Knapsack Problem
  • Sequence Alignment
  • The Bellman-Ford Algorithm
  • All-Pairs Shortest Paths (e.g., Floyd-Warshall)

Module 7: Complexity

Finally, we’ll look at some of our known algorithms and classify them in terms of space and time complexity.

  • Complexity Classes, P, and NP
  • The Traveling Salesperson Problem
  • Reductions
  • Approximation Algorithms