Written Homework
Written homework will be assigned each Tuesday and due by 23:59 on the following Monday. You must submit your solutions electronically, via file upload on Canvas.
- Homework 1 on basic analysis and big-O notation.
- Homework 2 on sorting and searching.
- Homework 3 on elementary graph algorithms.
- Homework 4 on divide and conquer algorithms.
- Homework 5 on dynamic programming, shortest paths, and minimum spanning trees.
- Homework 6 on greedy algorithms and randomization.
- Homework 7 on further randomized algorithms and basic amortized analysis.
- Homework 8 on further amortized analysis and max flow.
Best Practices Regarding Homework
- Start early: Some problems will be hard and are not typically solved in one sitting. Start early and let the ideas come to you over the course of a few days.
- Be rigorous: This is a theory course, and so mathematical rigor will be expected in your solutions.
- Be concise: Express your solution at the proper level of detail. Long, verbose answers are strongly discouraged. Give enough details to clearly present your solution, but not so many that the main ideas are obscured. As a general rule, if your grader cannot figure out how/why your solution is correct based on what you have submitted, you stand to lose credit.
- Form a study group: Collaboration on homework sets is encouraged, so take advantage of it. However, don't forget the Honor Principle.
- Come to office hours: Self-explanatory. Note that you will learn the most by first trying out each problem on your own. Make as much progress as possible on your own before you seek help from course staff.
Homework Grading
Several homework problems will be long-answer questions worth 7 points. On such problems, our grading guidelines are as follows.
- 7 points: A mathematically correct and concise solution that is written well. Contains no errors other than perhaps small spelling mistakes and minor grammatical errors.
- 6 points: A basically correct solution but with one of
the following small flaws.
- One or two small typos that makes the solution technically wrong.
- A proof that is missing one or two minor steps of reasoning.
- A mathematically correct solution but with grammatical errors that make parts of it hard to read or confusing. This includes not writing in complete sentences.
- An otherwise correct solution that is a bit longer than necessary and the excess length subtracts from its clarity.
- 5 points: A mostly correct solution with more than a
minor flaw. For example
- Minor flaws in two or three places, as above.
- Mathematically correct solution but with poor grammar throughout.
- A correct solution that is much longer than necessary (e.g., writing two full pages when half a page would have sufficed).
- 4 points: A solution that is on the right track but has a big mistake somewhere. To get this score, the problem must require at least two major ideas and the mistake cannot be in the more/most important idea.
- 3 points: An attempted solution that has some of the important ideas required but with a mistake in the most important idea.
- 2 points: An attempted solution that solves only a easy special case of the problem, where solving the full problem would require much more sophisticated idea(s).
- 1 point: An answer that would qualify for 2 points except that it has typos or small errors.
- 0 points: An answer that does not make useful progress towards a solution, or is a solution to something other than what was asked.
Homework Solutions
Sample solutions will (usually) be posted on Wednesdays in the files section of this course's Canvas page. Where appropriate, we will summarize "common mistakes" found in students' submissions. Our solutions may be quite different from yours and may point out useful insights. For these reasons, please treat all sample solutions as required reading, even if you solved all the homework problems correctly.