All homeworks are due Tuesday at noon in the drop-boxes outside 1404 Siebel Center. We will post each week's homework at least one week before the due date; we will solutions at most a day after the due date. Don't forget to read the homework policies!
- Homework 0, due September 4 — LaTeX solution template — Solutions
- Homework 1, due September 11 — Solutions
- Homework 2, due September 18 — Solutions
- Homework 3, due September 25 — Solutions
- No homework due October 2 — Midterm 1
- Homework 4, due October 9 — Solutions
- Homework 5, due October 16 — Solutions
- Homework 6, due October 23 — Solutions
- Homework 7, due October 30 — Solutions
- No homework due November 6 — Midterm 2
- Homework 8, due November 13 — Solutions
- No homework due November 20 or 27 — Thanksgiving break
- Homework 9, due December 4 — Solutions
- Homework 10, due December 11 — Solutions
All quizzes are available on the course Moodle site. Each week's quiz will be available at least a week before its due date.
We will post each week's head-banging problems here on Thursday, after everyone has had a chance to solve them from scratch. We will not post solutions; that would miss the point. However, we strongly encourage everyone to discuss the head-banging problems, and even post solutions for feedback, on Piazza. If any student posts a correct solution, we will certify it, and the student will get some extra credit.
- August 28-29 — Induction
- September 4-5 — Divide and conquer
- September 11-12 — Dynamic programming
- September 18-19 — Greedy algorithms
- September 25-26 — Proof practice
- October 2-3 — Probability and randomized algorithms
- October 9-10 — Amortization
- October 16-17 — More amortization
- October 23-24 — Graph traversal
- October 30-31 — More graph traversal
- November 6-7 — Minimum spanning trees and shortest paths
- November 13-14 — Flows and cuts
- No head-banging November 20-21 — Thanksgiving break
- November 27-28 — Applications of maxflow
- December 4-6 — NP-hardness
- Midterm 1 — September 27 — Solutions
- Midterm 2 — November 1 — Solutions
- Final exam — December 18, 8-11 am
| The problem is that we attempt to solve the simplest questions cleverly, thereby rendering them unusually complex. One should seek the simple solution. |
| — Anton Pavlovich Chekhov (c. 1890) |
| Thus you see, most noble Sir, how this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle. Because of this, I do not know why even questions which bear so little relationship to mathematics are solved more quickly by mathematicians than by others. |
|
—Leonhard Euler, describing the Königsburg bridge problem in a letter to Carl Leonhard Gottlieb Ehler, April 3, 1736 |