CSE 431/531, Algorithms: Design and Analysis, Fall

2022, Homework 4

Due Sunday, December 4, 2022, 11:59pm

General Instructions: For this homework, you will have a mix of theory and programming
problems. Instructions for each follow the same guidelines as the previous assignments.

For the “Pseudocode” question, your answer should have three parts: algorithm descrip-
tion and pseudocode, proof of correctness, and time analysis.

For the programming questions, you should submit your source code, as well as a screen-
shot showing that you submitted it on Kattis, and that it passes all the tests there.

Further details about the programming part:

• You may code in your choice of {C, C++, Java, Python}. It is up to you to ensure that
your code will compile using the corresponding compiler on Kattis. (If you want to
use one of the other languages Kattis supports, you need to clear it with the instructor
and TAs first.)

• Kattis will test your answer for efficiency and correctness. It uses two sets of test
inputs: a public one that you have access to while coding and debugging, and a private
one that you don’t get to see, but also need to pass. It would be a good idea to make
your own test inputs as well, and you are welcome to share these with your classmates
on piazza. Each time you submit your code on Kattis, it will check whether it compiles
correctly and passes the test inputs (without timing out).

• There is no limit on how many times you submit on Kattis. You just need to pass the
tests in the end.

• Important: Kattis requires that you read the input from stdin, and write only the
required output to stdout. You are encouraged to produce more verbose output that
goes to stderr (Kattis will ignore this).

• For the problem submission on Gradescope, upload your full, commented code, followed
by a proof that Kattis accepted it (such as a screenshot from Kattis showing your
username and the Accepted status of the problem). You should be able to use this
webpage: https://open.kattis.com/problems?show_solved=on&show_tried=off&
show_untried=off

• Follow good programming practices such as carefully naming variables and functions,
organizing your code, commenting, and making your code a joy to read (not an em-
barassing mess!)

• As always, the code you submit must be your own. You must acknowledge
any sources who made a significant contribution to your successful solution, such as
classmates, textbooks, websites, etc. Upon request, you must be prepared to meet
with the instructor and/or TA and explain, in detail, how your code works.

1

There are 4 problems, worth 10 points each. Start each problem on a new page!
Include a cover sheet with your name, but do not put your name on the problem solution

pages.
Submit your solution on GradeScope, using its interface to tell it which pages correspond

to each problem.
Unsolicited hints have been provided for problem 4. If you would like a hint on any of

the other problems, ask on Piazza!

Problem 1: Knapsack Variant (Pseudocode)

Consider the following version of Knapsack. Given are two weight limits W1 and W2, where
W1 ≤ W2. Given are also n items (w1, c1), (w2, c2), . . . , (wn, cn), where wi is the weight and ci
the cost of the i-th item. We want to find a subset of these items of the highest cost, where
the subset weights at least W1 and at most W2. Give an O(nW2) algorithm for this problem.
(Recall that the cost (respectively weight) of a subset is the sum of the costs (respectively
weights) of the items in the subset.)

Problem 2: Minimum Spanning Tree with Repeated Costs (Proof)

Consider the Minimum Cost Spanning Tree problem on an undirected graph G = (V,E)
with a cost ce ≥ 0 on each edge, where the costs may not all be different. If the costs are
not all distinct, there can in general be many distinct minimum-cost solutions. Suppose we
are given a spanning tree T ⊆ E with the guarantee that, for every e ∈ T , e belongs to some
minimum-cost spanning tree in G. Can we conclude that T itself must be a minimum-cost
spanning tree in G? Give a proof or counterexample with explanation.

Problem 3: Block Crusher (Kattis)

Solve the “Block Crusher”, which you can find at this web address: https://open.kattis.
com/problems/blockcrusher This is a coding problem; be sure to follow the relevant in-
structions for testing and submitting.

Problem 4: Continuous Median (Kattis)

Solve the “Continuous Median” problem, which you can find at this web address: https:

//open.kattis.com/problems/continuousmedian This is a coding problem; be sure to
follow the relevant instructions for testing and submitting.

An O(n2) algorithm will not be fast enough to pass all the tests, and will receive at most
3 points out of 10. You need to get the running time down to o(n2), and ideally, O(n log n).
Hint 1: Suppose “median” in the problem statement were replaced by “min” (or “max”).
How would you solve that problem? Suppose we added the additional condition that, after
even-numbered inputs, you must return the min value, and thereafter treat it as having been
deleted from the data set. How would you solve it now?

2

Hint 2: Notice that the median element is (ignoring rounding for now) the maximum element
of the bottom half of the input, and the minimum element of the top half of the input. How
can you make use of that fact?
Hint 3: Choosing the right data structure is essential.

3