CS 381 - Homework 5

• 2024-09-23 (Mon)
• 2-minute read

Update

Now that the Homework 5 submission period is over, this page has now been archived. The forms below will not work.

See the code for the backend that used to power this page here: https://github.com/ericswpark/purdue_cs381-hw5

Question 2

Question 3a

Explanation for the two forms below:

Form 1 assumes that the cost of adding dunes together is the intermediate sum (as explained in 3b and in the lecture). Use this when finding a counterexample in n3b.

Form 2 lets you arbitrarily define the cost of merging dunes together, as the actual handout specifies for problem 3a.

Form 1 (constant cost)

Update (2024-09-23 20:11) - A bug due to IDE autocomplete was fixed which caused wrong outputs for some inputs. Thanks to Meet Patel for emailing in about this! Again, here be dragons, answers may be wrong, etc.

Note: this question assumes a constant cost like 4b and the one described in the lecture instead of the 3D cost matrix because the author is an idiot and misunderstood the handout. The revised verifier is available below:

Form 2 (arbitrary cost)

Question 3b

This is the greedy implementation that should be wrong (on purpose) with certain inputs.

Update (2024-09-23 21:39) - Caching bug caused 3a outputs to be shown. Please force-refresh with Ctrl+Shift+R.

Question 4

Update (2024-09-27 01:22) - Fixed a bug where the penalty value shown would be lower than the expected value. Thanks to an anonymous poster on Edstem for the report.

Warning: while care has been taken to verify the algorithm, the answer this page gives may be incorrect. Do not use this as the sole verification for your answers. I am not responsible for any lost points on your homework.