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. (Links for future homeworks and solutions are placeholders.) Don't forget to read the homework policies!
- Homework 0, due September 3 — Solutions — LaTeX solution template
- Homework 1, due September 10 — Solutions
- Homework 2, due September 17 — Solutions
- Homework 3, due September 24 — Solutions
- No homework due October 1 — Midterm 1
- Homework 4, due October 8 — Solutions
- Homework 5, due October 15 — Solutions
- Homework 6, due October 22 — Solutions
- Homework 7, due October 29 — Solutions
- Homework 8, due November 5 — Solutions
- No homework due November 12 — Midterm 2
- Homework 9, due November 17 — Solutions
- No homework due November 26 or December 3 — Thanksgiving break
- Homework 10, due December 10 — Solutions
All quizzes are available on the course Moodle site.
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 detailed solutions; that would miss the point. However, we strongly encourage everyone to discuss the head-banging problems on Piazza, and even post solutions for feedback. Students who post correct solutions on Piazza will get some extra credit.
- August 27–28 — Induction
- September 3–4 — Divide and conquer
- September 10–11 — Dynamic programming
- September 17–18 — More dynamic programming
- September 24–25 — Midterm 1 review
- October 1–2 — Randomized algorithms
- October 8–9 — Amortized analysis
- October 15–16 — More amortized analysis
- October 22–23 — Graphs, topological sort, dynamic programming in dags
- October 29–30 — Minimum spanning trees and shortest paths
- November 5–6 — Midterm 2 review
- November 12–13 — Maximum flows and minimum cuts
- November 19–20 — NP-hardness
- No head-banging November 26–27 — Thanksgiving break
- December 3–4 — More NP-hardness
- December 10–11 — Final review
- Midterm 1 — September 26, 7:00-9:00 pm — location TBA
- Midterm 2 — November 7, 7:00-9:00 pm — location TBA
- Final exam — December 18, 1:30-4:30 pm — 1404 Siebel
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 |