Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CompSci 260P Algorithms Problem Set 3: Greedy Algorithms (Optimal and Approximate)
There are fewer problems in this set, as each requires a fair bit of work, and you may want to attempt the problem, discuss with your study group, and then revise your solution.
1. I am teaching a class that has n teaching assistants, each of whom hold office hours outside, at JavaCity. The ith TA holds office hours starting at time Si and ending at time Ei . Each TA holds exactly one office hour (which may last any amount of time, not necessarily one hour, and different TAs may have different interval lengths, which may overlap with one another). Attendance has been low because students, being Computer Science majors, are afraid of the sun, so the department announces that all TAs who do not have a student visit them this week will be fired1 . Because all of our teaching assistants are awesome2 , we want to ensure that none get fired. However, due to student fears of the sun, we want to minimize the total number of visits made to TAs.
For purposes of this problem, assume each TA’s office hour time is one continuous interval with no breaks, and that a student visiting the sundeck at time t counts as visiting all TAs whose office hours interval contains t. Also assume that student visits are “instantaneous,” in the sense that the amount of time a student stays in the sun is negligible – formally, each student visits the deck at a single point in time. This also helps to avoid exposing a student to the sun unnecessarily.
You propose the following: first, we sort all of the intervals by end time. We send a student to attend office hours at the moment immediately prior to the end of the first ending interval. We remove from our input all TAs who overlap with this time, and if the remaining set is non-empty, we repeat.
Prove that the greedy algorithm in the previous statement minimizes the number of students we need to send to visit TAs. You may be as informal as the proof from lecture.
2. If you struggle on this problem, consider trying problems C-10.8 and C-10.9 in the Goodrich/Tamassia textbook, or Chapter 4 problem 17, and then coming back to this problem We’re asked to help the captain of the UCI’s tennis team to arrange a series of matches against Long Beach State’s team3 . Both teams have n players; the tennis rating (a positive number, where a higher number can be interpreted to mean a better player) of the ith member of UCI’s team is ai and the tennis rating for the kth member of LBSU’s team is sk. We would like to set up a competition in which each person plays one match against a player from the opposite school. Because we get to select who plays against whom, our goal is to make sure that in as many matches as possible, the UCI player has a higher tennis rating than their opponent.
(a) One proposal has been to sort both rosters by tennis rating, and then pair our best player agaisnt their best player, our second best against their second best, and so on in that fashion. Give a complete counter-example to demonstrate that this does not solve the problem stated here.
(b) Give an efficient greedy algorithm for this problem and prove that it is correct (maximizes the number of matches in which our team has the player with the higher tennis rating). Note that “sort both rosters and pair up the top players, the second-best, etc” is not the correct answer to this problem. For CompSci 260P this quarter, for the proof, it is sufficient to demonstrate that the repair of an arbitrary inversion in any alternate ordering, compared to yours, produces an ordering that is no worse. You may use the fact from lecture that any permutation that differs from yours has a consecutive pair of elements that are inverted relative to yours, however for this particular problem, the proof may not need the fact that they are adjacent.
3. The Steiner Tree problem is as follows. Given an undirected graph G = (V, E) with nonnegative edge costs and whose vertices are partitioned into two sets, R and S, find a tree T ⊆ G such that for every v ∈ R, v ∈ T with total cost at most C. That is, the tree that contains every vertex in R (and possibly some in S) with a total edge cost of at most C. This is similar to a Minimum Spanning Tree with some vertices not being required to be part of the output graph.
(a) The difficulty in the Steiner tree problem is determining which set S ′ ⊆ S should be included in T. Give a polynomial time algorithm to find the Steiner tree of minimum cost for the case where the optimal S ′ is also provided.
(b) This problem, when S ′ is not given is N P-complete. If we want to solve this problem anyway, we will need to abandon correctness and get an efficient, approximate solution. We are solving the problem of finding a minimum-cost Steiner tree from a complete graph (a simple graph with n vertices and all n 2 possible edges). We are not given the optimal S ′ ⊆ S. You may assume that the edge costs obey the triangle inequality if you would like to do so, although that isn’t strictly necessary to obtain the correct answer. Suppose we compute a minimum spanning tree on R, treating S ′ = ∅ (which might not be true in the optimal solution). Show that this approximation algorithm has cost at most twice the optimal.
4. Suppose we are given a graph G = (V, E) and want to color the vertices from amongst k distinct colors. Give a polynomial-time algorithm that guarantees that the number of monochromatic edges is at most |E| k . Explain why your algorithm makes this guarantee and why it is polynomial time.
Hint: For any arbitrary coloring, how many monochromatic edges do you have? If you have more than the required amount, can you adjust the solution?
In addition, the two textbooks for the class have some great on-topic practice problems. I suggest these problems if you are looking for more.
In the G/T textbook, R-10.4, R-10.5, R-10.6, R-10.7, R-10.8, R-10.9, R-10.10, R-10.4, R-10.5, R-10.6, R-10.7, R-10.8, A-10.4, A-10.5, A-10.7, A-15.1, A-15.2, A-15.3, A-15.4, A-15.5, A-15.6, A-15.7
In the textbook of Erickson, Chapter 4, questions 1 (be sure to prove the three correct algorithms to be correct), 3, 4, 5, 6, 14, 15, 16, 17, 20, 21 (a,b for sure; c is good too), 22, 23, 24.