Wk 
Day 
Date 
Topic  Resources  Events 

1  Mon  Jan 13  Introduction to the Course  Course Website  


 Wed  Jan 15  Analysis of Quicksort  CLRS Chapter 7.4
Quicksort Analysis notes  


 Fri  Jan 17  Lower bounds for Sorting  CLRS Chapter 8.1
Comparison Sort Lower Bound Lecture Notes  Pretest 

2  Mon  Jan 20  Martin Luther King Day   No Class 


 Wed  Jan 22  Finding
Minimum
Maximum
ith item  CLRS Chapter 9.19.2
Medians and Order Statistics Lecture Notes  


 Fri  Jan 24  ith order statistic:
A better algorithm  CLRS Chapter 9.3  

3  Mon  Jan 27  Finish Order Statistics
Start Dynamic Programming
Dynamic Programming
The Elements of Dynamic Programming
Example: MCM   


 Wed  Jan 29  Dynamic Programming
Example: MCM
Example: 01 Knapsack  CLRS Chapter 15.115.3
An Introduction to Dynamic Programming Lecture Notes  


 Fri  Jan 31  More Dynamic Programming
LCS   

4  Mon  Feb 03  LCS
 CLRS Chapter 15.415.5
Dynamic Programming Lecture Notes  HW1 Due 


 Wed  Feb 05  Optimal Polygon Triangulation
  


 Fri  Feb 07  Greedy Algorithms:
Activity Selection Problem  Introduction to Greedy Algorithms (review)
Minimum Spanning Trees (review)
Greedy Algorithms
CLRS Sections 16.116.3
 

5  Mon  Feb 10  Review of Homework 1   


 Wed  Feb 12  Minimum Spanning Trees 
Greedy Algorithms Lecture Notes  


 Fri  Feb 14  Huffman Encoding 
Huffman Encoding Info and Applet  

6  Mon  Feb 17  Optimal Binary Search Trees   


 Wed  Feb 19  Amortized Analysis  CLRS Chapter 17
Amortized Analysis Lecture Notes  


 Fri  Feb 21  Amortized Analysis   HW 2 due 

7  Mon  Feb 24  Amortized Analysis   


 Wed  Feb 26  Network Flow  CLRS Sections 26.126.3
Maximum Flow Lecture Notes  


 Fri  Feb 28  Network Flow Problems   

8  Mon  Mar 03  Residual Networks and Augmenting Paths   


 Wed  Mar 05  Maxflow mincut theorem   


 Fri  Mar 07  Ford Fulkerson Method 
Ford Fulkerson Algorithm Applet
 

9  Mon  Mar 10  P, NP, NPComplete  P, NP, and
NPComplete (review)
 HW 3 due 


 Wed  Mar 12  Review for Midterm   


 Fri  Mar 14  Searching, Sorting, and Bounds
Greedy Algorithms
Dynamic Programming
Amortized Analysis
Network Flow  Pencil, Paper  Midterm Exam 

Spring Break Week 

10  Mon  Mar 24  Introduction to P, NP, NPC  CLRS Section 34.1
NPCompleteness Lecture Notes  


 Wed  Mar 26  Verification and NP  CLRS section 34.2  


 Fri  Mar 28  NPC and Reductions  CLRS 34.3  

11  Mon  Mar 31  NPC Proofs  CLRS 34.4  


 Wed  Apr 02  NPC Proofs  34.434.5  


 Fri  Apr 04  NPC Proofs   

12  Mon  Apr 07  Approximation Algorithms  CLRS Chapter 35  


 Wed  Apr 09  Approximation Algorithm:
Travelling Salesman Problem   


 Fri  Apr 11  CSE Day   No Class
HW4 Due 

13  Mon  Apr 14  Approximation Algorithm:
Set Covering   


 Wed  Apr 16  Approximation Algorithm:
SubsetSum   


 Fri  Apr 18    

14  Mon  Apr 21    


 Wed  Apr 23    


 Fri  Apr 25    

15  Mon  Apr 28    HW 5 due 


 Wed  Apr 30    


 Fri  May 02    

Ex  Fri  May 09    Final Exam 7:30am 