Course Schedule

Here is this semester's tentative schedule:

Date Topic Reading Slides
Aug. 25 Introduction 1.1, 1.2 slides
Aug. 30 Analysis of Algs Chap 2. slides
Sep. 1 Greedy Algorithms
  • Scheduling and variations
4.1, 4.2 slides
Sep. 6 Greedy Algorithms
  • Caching
  • Shortest Paths (Dijkstra)
4.3, 4.4 slides
Sep. 8 Greedy Algorithms
  • MST (Prim, Kruskal, "reverse-delete"
Priorty Queue review - Binary Heaps 		4.5, 4.6, 2.5 slides
Sep. 13 MST: Applications
  • Clustering.
  • factor-of-two approximation for Traveling Salesperson problem (misc. notes)
Divide & Conquer Algorithms: Introduction
  • Mergesort
  • Counting Inversions
  • Closest Points,
  • General D & Q Recurrences, recursion tree.

4.7 (clustering)
misc. notes (factor-of-two),
5.1, 5.2, 5.3, 5.4
recurrences handout 		slides
Sep. 15 Divide & Conquer
  • Quicksort
  • Median finding
misc. notes slides
Sep. 20 Divide & Conquer: Arithmetic
  • Integer multiplication (Karatsuba)
  • Matrix multiplication (Strassen)
  • Exponentiation
5.5, misc. notes (exponentiation) slides
Sep. 22 Divide & Conquer
  • Batcher Odd/Even Mergesort
  • Proving correctness for recursive algorithms
misc. notes slides
Sep. 27 Dynamic Programming
  • Introduction
  • Weighted Interval Scheduling
6.1, 6.2 slides
Sep. 29 Dynamic Programming - Two-dimensional tables
  • The Knapsack problem
  • Longest Common Subsequences
6.4 slides
Oct. 4 Exam 1 tonight.
Class Cancelled, but possible open Q&A		 Through 9/22 lecture slides
Oct. 6 Dynamic Programming
  • The Edit Distance problem
  • Matrix Chain Multiplication
misc. notes (Dynamic Programming) slides
Oct. 11 Dynamic Programming
  • Sequence Alignment
  • Segmented Least Squares, etc.
6.6, 6.3 slides
Oct. 13 Flow
  • Introduction
  • The Ford-Fulkerson Algorithm, and Augmenting Paths
7.1 slides
Oct. 18 Flow
  • Maximum-flows and Minimum cuts
  • The Scaling Algorithm
7.2, 7.3 slides
Oct. 20 Flow
  • The Bipartite Matching Problem
  • Applications of Flow
7.5 slides
Oct. 25 Flow Applications
  • Circulations and Lower Bounds on flows
  • Image Segmentation
  • Airline Scheduling, etc.
7.7 - 7.12 slides
Oct. 27 NP Completeness Chap 8 and misc. notes slides
Nov. 1 NP Completeness Chap 8 and misc. notes slides
Nov. 3 NP Completeness Chap 8 and misc. notes slides
Nov. 8 Exam 2 tonight!
Class Cancelled, but possible open Q&A		 Through Oct. 27 lecture slides
Nov. 10 Beyond NP Completeness Chap 8, 9 slides
Nov. 15 Dealing with NPC problems: Special Cases Chap 10 slides
Nov. 17 Dealing with NPC problems: Approximation Algorithms Chap 11 slides
Nov. 22 Thanksgiving Break slides
Nov. 24 Thanksgiving Break slides
Nov. 28 Randomized Algorithms Chap 13 slides
Dec. 1 Randomized Algorithms Chap 13 slides
Dec. 8 Misc. Algorithms, Topics, catch-up misc. notes slides
Dec. 10 Misc. Algorithms, Topics, catch-up misc. notes slides