CSC373 – Problem Set 2
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources (people, print, electronic) outside of your group, the course notes, and the course staff, that you consulted.
Problem Set: due October 15, 2016 22:00
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity.
Answers that are technically correct that are hard to understand will not receive full marks. Mark values for each question are contained in the [square brackets].
You may work in groups of up to THREE to complete these questions.
1 MST, Extra Edge
We have the following inputs:
• G = (V, E), a connected, undirected graph,
• w : a weight function that assigns a non-negative weight to each edge in E, • T ⊆ E, a minimum spanning tree of G,
• e1 = {u, v} ∈/ E (for u, v ∈ V ), an edge not in E,
• w1, a non-negative weight for e1
[2 marks] First, write an algorithm that outputs a minimum spanning tree T1 for the graph G1 = (V, E∪{e1}) with w(e1) = w1. Of course, you could just generate an MST for G1 from scratch, but that would be very inefficient (and, like, worth 0 marks!). Your algorithm must be more efficient than that.
[1 mark] Second, convince us that your algorithm is efficient by analyzing its worst-case running time. [2 marks] Finally, write a detailed proof that your algorithm is correct.
2 Back to Before…
OK. So the algorithm I gave you in question 3 on PS1 is incorrect. Just so everyone’s on the same page, here’s a simple counterexample for why the algorithm is wrong. Take L = 12, k = 2, and road damage at 2, 4, 5, and 8. The algorithm fixes 4 and then 2, yielding a minimum of 3. But the optimal is to fix 2 and 5, yielding a minimum of 4.
[5 marks] Write a correct, efficient algorithm for this problem, and give a formal proof of correctness. Hint: part of the solution is a greedy algorithm. But there’s more to it than that. The proof structure may involve loop invariants from CSC236 too. Also state and prove the worst-case running time for your algorithm.
3 Building Houses
Along a linear street of length M km, you would like to build houses. You are allowed to build houses at the given positions x1, x2, . . . , xn (each of these positions is between 0 and M inclusive). If you build a house at position xi, you get ri of revenue.
Your goal is to maximize your revenue from building houses. However, you are not allowed to build two houses within less than 5km of each other. For example, if you build a house at position 10, then you cannot build another house to its right until at least position 15.
[5 marks] Follow the five steps to design a dynamic-programming algorithm to solve this problem. Include and clearly label each step in your submission.
Here’s an example. Let M = 15,x1 = 4,x2 = 7,x3 = 10,x4 = 11,r1 = 3,r2 = 4,r3 = 1,r4 = 2. Then the optimal solution is tobuildhousesatx1 =4andx4 =11,foraprofitof5.