Date  Class Period & Lecture Topic  Reading  Assignment  

Aug 30  1. What is the class about and how will it work? (Syllabus, policies, business, motivation) 
Read and understand the course website and get on Slack  
Sep 01  2. Algorithm Essentials (BigO and basic arithmetic) 
Chapters 0, 1  pp. 115  Install Python and start playing around. 
Sep 06  3. Algorithm Essentials (Modular arithmetic and Primality) 
Chapter 1  pp. 1630  HW1 
Sep 08  4. Algorithm Essentials
(Cryptography and Euclid) 
pp. 3038  HW2 Project1 Design Experience 

Sep 13  5. Divide and Conquer (Multiplication, Recurrence Relations, Merge Sort) 
Chapter 2  pp. 4550  HW3 Project1: Primality Tester 
Sep 15  6. Divide and Conquer (Medians, Matrix Multiplication, Convex Hull) 
pp. 5057  HW4 

Sep 20  7. Graphs (Depthfirst Search) 
Chapter 3  pp. 8087  HW5 Project2 Design Experience 
Sep 22  8. Graphs (Directed Graphs and Strong Connectedness) 
pp. 8795  HW6  
Sep 27  9. Graphs (Shortest Paths) 
Chapter 4  pp. 104113  HW7 
Sep 29  10. Graphs (Priority Queues and Variations on Shortest Path) 
pp. 113120  HW8 Project2: Convex Hull 

Oct 04  11. Greedy Algorithms (Minimum Spanning Trees) 
Chapter 5  pp. 127138  HW9 
Oct 06  12. Greedy Algorithms (Huffman Encoding) 
pp. 138143  HW10 Project3 Design Experience 

Oct 11  13. Greedy Algorithms (Horn Formulas and Set Cover) 
pp. 144147  HW11  
Midterm (October 12[8am]14[9pm; late fee after 2pm] in the testing center) Study Guide  
Oct 13  14. No lecture (Midterm)  
Oct 18  15. Dynamic Programming (Longest Increasing Subsequence and Edit Distance) 
Chapter 6  pp. 156164  HW12 
Oct 19  Project3: Network Routing  
Oct 20  16. Dynamic Programming (Knapsack and Chain Matrix Multiplication) 
pp. 164171  HW13  
Oct 25  17. Dynamic Programming (Shortest Paths and Independent Sets) 
pp. 171177  Project4 Design Experience 

Oct 27  18. Linear Programming (Introduction) 
Chapter 7  pp. 188198 
HW14 
Nov 01  19. Linear Programming (Duality and Zerosum Games) 
pp. 206213  HW16  
Nov 03  20. Intelligent Search (Backtracking and Branch & Bound) 
Chapter 9  pp. 271276 + extra B&B TSP material  HW17 Project4: Gene Sequencing 
Nov 08  21. Intelligent Search (More Branch & Bound) 
Chapter 9  pp. 271276 + extra B&B TSP material  no homework assignment 
Nov 10  22. Intelligent Search (NPcompleteness) 
Chapter 8  pp. 232247 + "Unsolvable Problems" box on page 263  HW18 Project5 Design Experience 
Nov 15  23. Intelligent Search (Approximation and Local Search) 
Chapter 9  pp. 276293  HW19 
Nov 17  24. Advanced Algorithms (Randomized Algorithms) Why Consider Grad School? 
Sec 2.4  Boxes on pp. 29, 56, 140  HW20 
Nov 22  Friday Instruction 

Nov 24  Thanksgiving 

Nov 29  25. Advanced Algorithms (Evolutionary Computation) 
Project5: TSP with Branch and Bound  
Dec 01  26. Advanced Algorithms (Neural Networks) 

Dec 06  27. Advanced Algorithms (Quantum Computation) 
Chapter 10  pp. 297302  
Dec 08  28. Group Project Presentations 
Project6: Group TSP  
Dec 09  Reading Day  
Dec 12  Sec. 2 Final (7:00am–10:00am in class) Study Guide  
Dec 12  Sec. 4 Final (2:30pm5:30pm in class) Study Guide  
Dec 15  Sec. 3 Final (3:00pm6:00pm in class) Study Guide  
Dec 16  Sec. 1 Final (7:00am–10:00am in class) Study Guide 