Exams
Quiz 1, on Mon 10/5
Quiz 2, on Mon 11/2
Quiz 3, on Mon 12/7

Homeworks
H1 LaTeX, out 09/09, due 09/16
H2 LaTeX, out 09/16, due 09/23
H3 LaTeX, out 09/23, due 09/30
H4 LaTeX, out 10/12, due 10/21
H5 LaTeX, out 10/21, due 10/28
H6 LaTeX, out 11/09, due 11/16
H7 LaTeX, out 11/16, due 11/23

Lecture Topics and Readings
Part 1: Foundations
 Lecture 1 (Wed Sep 02): Introduction. Insertion sort and analysis.
  CLRS: 1, 2.1, 2.2
 Lecture 2 (Mon Sep 07): Labor Day.
 No class today, enjoy the holiday.
 Lecture 3 (Wed Sep 09): A better way to sort: Merge sort and analysis. Asymptotic notation.
  CLRS: 2.3, 3
 Lecture 4 (Mon Sep 14): Recurrences I.
  CLRS: 4
 Lecture 5 (Wed Sep 16): Recurrences II. Intro to probabilistic analysis.
  CLRS: 4
 Lecture 6 (Mon Sep 21): Probabilistic Analysis. Randomized algorithms.
  CLRS: 5
Part 2: Sorting and Order Statistics
 Lecture 7 (Wed Sep 23): Quicksort. Randomized Quicksort.
  CLRS: 7
 Lecture 8 (Mon Sep 28): Medians and order statistics.
  CLRS: 9.
 Lecture 9 (Wed Sep 30): Lower bounds for comparisonbased sorting.
Beating the lower bound: counting sort.
  CLRS: 8.1, 8.2, 8.3, 8.4.
 Lecture 10 (Mon Oct 05): Quiz #1
  CLRS: everything covered so far.
Part 3: Advanced Design and Analysis Techniques
 Lecture 11 (Wed Oct 07): Dynamic Programming I. Rod Cutting.
  CLRS: 15.1, 15.2.
 Lecture 12 (Mon Oct 12): Dynamic Programming II. Longest Common Subsequence.
  CLRS: 15.3, 15.4.
 Lecture 13 (Wed Oct 14): Greedy Algorithms. Activity selection. Huffman Codes.
  CLRS: 16.1, 16.2, 16.3.
 Lecture 14 (Mon Oct 19): Algorithms Fall Break Day.
  No class today, enjoy the fall weather.
 Lecture 15 (Wed Oct 21): Amortized Analysis.
  CLRS: 17.1.
Part 4: Graph Algorithms
 Lecture 16 (Mon Oct 26): Graphs and their representations. BFS.
  CLRS: 22.1, 22.2.
 Lecture 17 (Wed Oct 28): DFS.
  CLRS: 22.3.
 Lecture 18 (Mon Nov 02): Quiz #2.
  CLRS: everything so far, emphasis on material since Quiz #1.
 Lecture 19 (Wed Nov 04): Topological sort. Minimum spanning trees. Kruskal and Prim's algorithms.
  CLRS: 22.4, 23.
 Lecture 20 (Mon Nov 09): Singlesource shortest paths. The BellmanFord algorithm.
  CLRS: 24 (before 24.1), 24.1.
 Lecture 21 (Wed Nov 11): Dijkstra's algorithm.
  CLRS: 24.3.
 Lecture 22 (Mon Nov 16): Allpairs shortest paths.
  CLRS: 25.2, 25.3.
 Lecture 23 (Wed Nov 18): Maximum Flow. The FordFulkerson algorithm.
  CLRS: 26.1, 26.2.
Part 5: Selected Topics
 Lecture 24 (Mon Nov 23): Introduction to the P vs. NP problem. NPCompleteness.
  CLRS: 34 (selections)
  slides: PDF
 Lecture 25 (Wed Nov 25): Thanksgiving Break.
  No class today, enjoy the holiday
 Lecture 26 (Mon Nov 30): Introduction to number theory and cryptography.
  CLRS: 31 (selections)
  slides: PDF
 Lecture 27 (Wed Dec 02): Interactive Proofs and ZeroKnowledge.
 Lecture 28 (Mon Dec 07): Quiz #3.
  CRLS: all material so far, emphasis on material since Quiz #2.
  This is the last day of classes.
