This page is primarily to serve and document my homework solutions for the spring 2018 version of cs374 with Jeff Erickson, as well as to serve as a guide for anyone seeking an A in the class, which is something many consider to be difficult and something I achieved.

I worked with a homework group for this class, although it was less of a homework group and more of a solution conference group, where everyone discussed their solutions rather than solving the problems. I ultimately submitted a different set of solution files than them on all occasions, except one, where I did not have time to typeset my own. While not having a study group is very doable for this class, having one is highly beneficial when you are short on time, like I was for that one week. I highly urge that people using this page as a resource try solving all the problems by themselves first before meeting with their group, as this will improve everyone's understanding of the material as well as challenging your ability to do mechanical work and improving your test scores.

Jeff is stubborn in his beliefs and if you would like to obtain good homework scores, you should adhere to his guidelines and argue back homework points through regrade requests whenever possible, because the graders hired for this class are incredibly incapable of reading English. On several occasions I have had points taken off for "not writing X, which was mentioned in the rubric", but it's in the first or second or last paragraph, or "you did DP, but didn't explain how you memoized" when I in fact did not do DP.

In general though, when you get back your homework scores, you should grade via my guidelines (on a scale of 10.0) to get a somewhat better understanding of how well you did. Please note that these are just guidelines and you should be strict with yourself when grading your own work.

1. If your solution contains major mathematical mistakes (this does not include hand-waving something true, because sometimes that's just out of scope), automatic 0 points.
   Note this does not include minor calculation mistakes unless it is the crux of the problem.
2. If your solution is correct, start at 10.0 points.
3. If your solution contains minor mathematical mistakes, take away 1.0 points.
4. If your running time is in an inferior class (e.g. linear instead of constant, exp instead of poly), take away 5.0 points for every class. You should apply this to every free variable in the running time.
   As an example, reporting $O(EV)$ instead of $O(E \log^2 V)$, it means you missed a major simplification somewhere regarding $V$, and this nets -5.0 points.
5. For every exponent you are inferior by, take away 2.0 points. These lapses of judgement are less important and usually come from not caching some oftenly computed values or not reusing facts you have previously learned.
6. Finally, take away points based on your perceived clarity of your solution. Did you write claims you never used? Is your solution needlessly long? Mathematical writing is about clarity and conciseness, and writing two pages when one paragraph should suffice is a huge sin.

You may wonder why I don't use a rubric like grading scale. It's simply because for induction like problems or anything mathematically based, I don't want to give out any points just because you have written down the hypothesis and the base case. You need to actually solve the problem to get points.

scores