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 | Project4 Design Experience |
|
Nov 01 | 18. Linear Programming (Introduction) |
Chapter 7 | pp. 188-198 | HW14 |
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 |