Date Class Period & Lecture Topic Reading Assignment
Sep 04 1. What is the class about and how will it work?
(Syllabus, policies, business, motivation)
     
Sep 06 2. Algorithm Essentials
(Big-O and basic arithmetic)
Chapters 0, 1 pp. 1-15 Install Visual Studio and get started on Project1
Sep 11 3. Algorithm Essentials
(Modular arithmetic and Primality)
Chapter 1 pp. 16-30 HW1
Sep 13 4. Algorithm Essentials
(Cryptography and Euclid)
pp. 30-38 HW2
Project1 Design Experience
Sep 18 5. Divide and Conquer
(Multiplication, Recurrence Relations, Convex Hull)
Chapter 2 pp. 45-50 HW3
Project1: Primality Tester
Sep 20 6. Divide and Conquer
(Merge Sort, Medians, Matrix Multiplication)
  pp. 50-57 HW4
Sep 25 7. Graphs
(Depth-first Search)
Chapter 3 pp. 80-87 HW5
Project2 Design Experience
Sep 27 8. Graphs
(Directed Graphs and Strong Connectedness)
  pp. 87-95 HW6
Oct 02 9. Graphs
(Shortest Paths)
Chapter 4 pp. 104-113 HW7
Oct 04 10. Graphs
(Priority Queues and Variations on Shortest Path)
  pp. 113-120 HW8
Project2: Convex Hull
Oct 09 11. Greedy Algorithms
(Minimum Spanning Trees)
Chapter 5 pp. 127-138 HW9
Oct 11 12. Greedy Algorithms
(Huffman Encoding)
  pp. 138-143 HW10
Project3 Design Experience
Oct 16 13. Greedy Algorithms
(Horn Formulas and Set Cover)
  pp. 144-147 HW11
  Midterm (October 16[12pm]-19[9pm; late fee] in the testing center) Study Guide
Oct 18 14. No lecture (Midterm)  
Oct 23 15. Dynamic Programming
(Longest Increasing Subsequence and Edit Distance)
Chapter 6 pp. 156-164 HW12
Oct 24 Project3: Network Routing
Oct 25 16. Dynamic Programming
(Knapsack and Chain Matrix Multiplication)
  pp. 164-171 HW13
Oct 30 17. Dynamic Programming
(Shortest Paths and Independent Sets)
  pp. 171-177 HW14 (postponed)
Project4 Design Experience
Nov 01 18. Linear Programming
(Introduction)
Chapter 7 pp. 188-198 HW14
HW15 CANCELED ☹
Nov 06 19. Linear Programming
(Duality and Zero-sum Games)
  pp. 206-213 HW16
Nov 08 20. Intelligent Search
(Backtracking and Branch & Bound)
Chapter 9 pp. 271-276 + extra B&B TSP material HW17
Project4: Gene Sequencing
Nov 13 21. Intelligent Search
(More Branch & Bound)
Chapter 9 pp. 271-276 + extra B&B TSP material no homework assignment
Nov 15 22. Intelligent Search
(NP-completeness)
Chapter 8 pp. 232-247 HW19
Project5 Design Experience
Nov 20 Friday Instruction
 
Nov 22 Thanksgiving
 
Nov 27 23. Intelligent Search
(Approximation and Local Search)
Chapter 9 pp. 276-293 HW20
Nov 29 24. Advanced Algorithms
(Randomized Algorithms)
Why Consider Grad School?
Boxes on pp. 29, 53, 56, 140 HW21
Dec 04 25. Advanced Algorithms
(Quantum Computation)
Chapter 10 pp. 297-302 Project5: TSP with Branch and Bound
Dec 06 26. Advanced Algorithms
(Evolutionary Computation)
 
Dec 11 27. Advanced Algorithms
(Neural Networks)
 
Dec 13 28. Group Project Presentations
  Project6: Group TSP
Dec 14 Reading Day      
Dec 15 Sec. 2 Final (7:00am–10:00am in class) Study Guide
Dec 19 Sec. 1 Final (7:00am–10:00am in class) Study Guide

TA Schedule

(TA office is 1152 TMCB)

  Monday Tuesday Wednesday Thursday Friday
  8:00 -   9:00 Reed Reed Reed
  9:00 - 10:00 Reed Reed Reed
10:00 - 11:00 Reed Reed Reed
11:00 - 12:00 Robert Robert Robert
12:00 -   1:00 Robert Reed Robert Reed Robert
  1:00 -   2:00 Robert Mike Robert Mike Robert
  2:00 -   3:00 Robert Mike Robert Mike Robert
  3:00 -   4:00 Mike Mike
  4:00 -   5:00 Nathan Mike Mike
  5:00 -   6:00 Nathan Nathan
  6:00 -   7:00 Nathan Nathan
  7:00 -   8:00 Nathan Nathan