

Announcements
Course Description
This course is an indepth study of the design and analysis of advanced algorithms, including the performance tradeoffs and resources required by various algorithmic implementations. Major classes of computational problems will be identified and explored. Advanced data structures and approximation heuristics are introduced as required for solution design. Topics will include the Master Theorem, dynamic programming, divideandconquer and greedy algorithms.
Book, Course Information, and Prerequisites
Course Instructor
Schedule 
Date  Lecture Topic(s)  Recommended Reading  Homework 
WAugust 21  Introduction/Course Overview pdf  Chapter 1  FirstDay Survey due 8/23 
FAugust 23  Stable Matching Algorithm  Section 1.1  Homework 1 
MAugust 26  Analyzing Algorithms pdf  Sections 2.1, 2.32.4  
WAugust 28  Asymptotic Forms pdf  Section 2.2  
FAugust 30  Master Theorem pdf  CLRS Chapter 4  Homework 2 hw2input.txt 
MSeptember 2  Holiday No Class  
WSeptember 4  Sorting and Selection pdf  
FSeptember 6  Greedy Algorithms for Scheduling pdf  Ch. 4 Intro, Sections 4.14.2 (KT)  Homework 3 PS3_input.txt 
MSeptember 9  More on Greedy Algorithms Notes from Dr. Sanders 
Section 4.8  
WSeptember 11  Minimizing Lateness & Huffman Encoding pdf  Section 4.8  
FSeptember 13  Graphs: Definitions, Representations, and Traversals  Chapter 3  Homework 4 
MSeptember 16  Graphs: Topological Sort pdf  Section 4.5  
WSeptember 18  Minimum Spanning Trees pdf  Section 4.5  
FSeptember 20  Dijkstra's Algorithm for Shortest Paths pdf  Section 4.4  
MSeptember 23  Midterm Review Practice Problems 

WSeptember 25  Midterm 1  
FSeptember 27  DivideandConquer: Inversion Counting pdf  Section 5.15.3  Homework 5 
MSeptember 30  DivideandConquer: Closest Pairs pdf  Section 5.4  
WOctober 2  DivideandConquer: Selection pdf  
FOctober 4  Intro to Dynamic Programming  Section 6 intro, 6.16.2  Homework 6 
MOctober 7  Dynamic Programming: Knapsack & LCS pdf  Section 6.4  
WOctober 9  Dynamic Programming: Finish LCS & Edit Distance/Sequence Alignment pdf  Section 6.66.7  
FOctober 11  Space Efficient Sequence Alignment pdf Dynamic Programming Practice 
Homework 7  
MOctober 14  Fall Break  No Class  
W October 16  BellmanFord Algorithm for Shortest Paths pdf  Section 6.8/CLRS Section 25.2  
FOctober 18  AllPairs Shortest Paths & Intro to Network Flows pdf  Section 7.17.3  
MOctober 21  More on Network Flows pdf  Section 7.57.6  Homework 8 
WOctober 23  Extensions to Network Flow pdf Network Flow Practice 
Section 7.77.12  
FOctober 25  No Class Practice Problems  
MOctober 28  Midterm Review  
WOctober 30  Midterm 2  
FNovember 1  NPCompleteness: Definitions pdf  Chapter 8 intro  Homework 9 
MNovember 4  NPCompleteness: Reductions pdf  Chapter 8 (KT) 34.234.3 (CLRS) 

WNovember 6  Cook's Theorem, 3SAT, Independent Set pdf  Ch. 8 (KT) 34.434.5 (CLRS) 

FNovember 8  Clique, Vertex Cover, and Independent Set pdf  Ch. 8 (KT) 34.5 (CLRS) 
Homework 10 
MNovember 11  Dominating Set pdf  Ch. 8 (KT) 34.5 (CLRS) 

WNovember 13  NPComplete Practice Problems  
FNovember 15  Approximation Algorithms: VC & TSP pdf  Chapter 11 (KT)  Homework 11 
MNovember 18  Approximation Algorithms: Set Cover and the Greedy Heuristic pdf  Chapter 11 (KT) 35.3 (CLRS) 

WNovember 20  Subset Sum pdf  Section 6.4 & 8.8 (KT) Section 35.5 (CLRS) 

FNovember 22  Subset Sum Approximation pdf  Section 6.4 & 8.8 (KT) Section 35.5 (CLRS) 

MNovember 25  Practice Problems  
WNovember 27  Holiday No Class  
FNovember 29  Holiday No Class  
MDecember 2  Practice Problems  
WDecember 4  WrapUp/Evals  
TuesDecember 10  Final Exam,Time: 5:308pm 
*Special thanks to Dave Mount for the use of his excellent notes and class materials.