CSE431/531 Homework 4 - Algorithms: Design and Analysis

CSE 431/531, Algorithms: Design and Analysis 

 Homework 4

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.

https://open.kattis.com/problems?show_solved=on&show_tried=off&show_untried=off

https://open.kattis.com/problems?show_solved=on&show_tried=off&show_untried=off

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?

https://open.kattis.com/problems/blockcrusher

https://open.kattis.com/problems/blockcrusher

https://open.kattis.com/problems/continuousmedian

https://open.kattis.com/problems/continuousmedian

 

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.