Date 
Topic 
Reading (in the book/handout) 
Sep 1 
General overview; Stable marriage problem 
Chapter 1 
Sep 6 
Stable marriage problem, proof of optimality; Graphs, Representation of graphs 
Chapter 1 
Sep 8 
DFS, Order notation, BFS, Top sort 
Chapter 23 
Sep 13 
Top sort, Directed DFS 
Chapter 23 
Sep 15 
Cut nodes 
Biconnected Components
Biconnected Components Algorithm 
Sep 20 
Strong connectivity and strong components 
Chapter 22.5 from CLRS 
Sep 22 
Minimum Spanning Tree, basic MST proofs of correctness
Kruscal algorithm for MST 
Chapter 4 
Sep 27 
MST finished
Heaps
Prim's algoritm
Finding maximum collection of disjoint intervals 
Section 4.1

Sep 29 
Amortized analysis
UNIONFIND data structure
Interval graph coloring 
Chapter 17 from CLRS
Chapter 4.1 
Oct 4 
Huffman coding 
Chapter 4 
Oct 6 
QUIZ: 45 minutes in class; closed notes, books, etc.
AVERAGE: 64.84 

Oct 11 
Dijkestra Algorithm
BellmanFord Algorithm 
Chapter 4.4
from CLRS

Oct 13 
Solving quiz problems
Dynamic Programming algorithm for KNAPSACK 

Oct 18 
Toothpick game
 Chapter 6.1
Toothpick game

Oct 20 
Practice problems for midterm exam
Singly connected graphs 
Singly connected graphs

Oct 25 
MIDTERM
AVERAGE: 60.33 

Oct 27 
Midterm discussion

Chapter 6.3

Nov 1 
Dynamic Programming
Exercise 1 and 2 (solved exercises from book)
Line fitting problem

Chapter 6.3

Nov 3 
Homework 5 discussion
Dynamic Programming
Sequence alignment

Chapter 6.6

Nov 8 
2 algorithms for all pairs shortest paths:
First one from the book;
Second one Floyd Warshall 
Chapter 6

Nov 10 
Divide and conquer closest pair algorithm 
Chapter 5

Nov 15 
Randomized and deterministic SELECTION (median finding) algorithms 

Nov 17 
Devide and Conquer:
Long number multiplication;
Counting inversions

Chapter 5 
Nov 22 
NPCompleteness 
NPCompleteness

Nov 29 
Review of NPCompleteness
Reduction from Independent Set to Vertex Cover problem
Reduction from 3SAT to Independent Set problem
Introduction to Dominating Set problem 
Chapter 8

Dec 1 
Reduction from 3SAT to SUBSET SUM problem

Section 34.5.5 from CLRS

Dec 6 
Reduction from SUBSET SUM to PARTITION problem
Reduction from PARTITION to Scheduling with release time/deadline
Reduction from Hamiltonian Cycle to Hamiltonian Path problem


Dec 8 
Reduction from Vertex Cover to Dominating Set problem

