links
cs374
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.
notes
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.

If your solution contains major mathematical mistakes (this does not include
handwaving 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.

If your solution is correct, start at 10.0 points.

If your solution contains minor mathematical mistakes, take away 1.0 points.

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.

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.

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

hw0
(sol)
 effectively 30.0/30.0
 1.5 points were taken off due to "not declaring variables", which is pretty
stupid.

hw1
(sol)
 effectively 30.0/30.0
 2.0 points were taken off due to "not describing every state of the dfa in
english", which is pretty stupid.

hw2
(sol)

hw3
(sol)

hw4
(sol)
 29.5/30.0
 2.5 points were taken off for $O(n^2)$ for problem 2 and 2.0 points were
given for $O(n)$ for problem 1a.

hw5
(sol)

hw6
(sol)
 30.0/30.0
 this was submitted by my homework group, so the solution link will 404.

hw7
(sol)
 effectively 30.0/30.0
 2.0 points were taken off for not solving the "reachability problem" for
problem 1, 2.0 points were taken off for not solving the "reachability problem"
for problem 2, and 0.5 points were taken off for "using DFS or BFS instead of
WFS", all of which are bogus because shortest path $\implies$ reachability and
DFS and BFS return the correct result (wrt reachability, DFS does not give the
shortest path) with the same runtime.

hw8
(sol)
 29.0/30.0
 1.0 points were taken off for $O(E \log V)$ runtime on problem 1a.

hw9
(sol)

hw10
(sol)

hw11
(sol)
 /30.0
 this was optional, so I didn't do it and the solution link will 404.
If you believe any of my solutions are wrong, please contact me at
[email protected] and I will add a
note to that particular homework.