Schedule

Table 1
Week Date Content
1 Tue Aug 26
Wed Aug 27
Thu Aug 28
2 Mon Sep 1 Labor Day observed (no class)
Tue Sep 2
Thu Sep 4
3 Tue Sep 9
Wed Sep 10
Thu Sep 11
  • Checkpoint 1: Running Time and Invariants
    • Loop Invariants
    • Total Running Time
    • Asymptotic Running Time Proofs
4 Tue Sep 16
Thu Sep 18
5 Tue Sep 23
Wed Sep 24
Thu Sep 25
  • 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 Sep 30
Thu Oct 2
7 Tue Oct 7
Wed Oct 8
Thu Oct 9
  • Checkpoint 3: Graph Theory
    • Connectivity
    • BFS and DFS
    • Topological Orderings
    • Graph Representations
    • Kosaraju’s Algorithm (and SCCs)
    • Dijkstra’s Algorithm (and SSSP)
8 Mon Oct 13 Fall break (no class)
Tue Oct 14 Fall break (no class)
Thu Oct 16
9 Tue Oct 21
Wed Oct 22
Thu Oct 23
  • Checkpoint 4: Data Structures and Memory
    • Heaps
    • Binary Search Trees
    • Red-Black Trees
    • Hash Tables
    • Universal Hashing
10 Tue Oct 28
Thu Oct 30
11 Tue Nov 4
Wed Nov 5
Thu Nov 6
  • Checkpoint 5: Greedy Algorithms
    • Greedy scheduling
    • Minimum spanning trees (Prim’s and Kruskal’s)
    • Exchange Arguments
12 Tue Nov 11
Thu Nov 13
  • To be determined! (maybe memory and dynamic programming)
13 Tue Nov 18
Wed Nov 19
Thu Nov 20
  • Checkpoint 6: Dynamic Programming
    • Dynamic Programming Properties
    • The Knapsack Problem
    • The Bellman-Ford Algorithm
    • The Floyd-Warshall Algorithm
    • Sequence Alignment
    • Jump-It
14 Tue Nov 25
Wed Nov 26 Thanksgiving recess (no class)
Thu Nov 27 Thanksgiving recess (no class)
Fri Nov 28 Thanksgiving recess (no class)
15 Tue Dec 2
Wed Dec 3
  • All grading must be complete
Thu Dec 4 Reading day (no class)
Fri Dec 5 Reading day (no class)
16 Fri Dec 12
  • 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