Question 1: Most people did not understand how to solve this question (almost no one did). The most popular solution was to take an avg between min and max and choose edges with minimum distance to this avg. This solution has a counterexample. Some people proposed strange ways of selecting the initial value from which they try to minimize distance of all edges chosen. All these solutions have counterexamples. Example 1: v1 - v2 : cost 9999 v2 - v4 : cost 1 v4 - v3 : cost 9000 v3 - v1 : cost 9000 v1 - v4 : cost 3000 The avg between max and min is 5000. Choosing the first closest edge to it is 3000. However, the opt is to take 9xxx edges. Example 2: v1 - v2 : cost 1000 v1 - v3 : cost 5 v2 - v3 : cost 10 Taking from max to min (reverse of Prim's) results in 1000, 10, which is not opt. Example 3: v1 - v2 : cost 15 v2 - v3 : cost 10 v3 - v4 : cost 10 v4 - v5 : cost 2 v4 - v1 : cost 4 v2 - v5 : cost 1 This example shows that starting from any initial edge and then choosing edges with min distance to this initial edges doesn't work. Example 5: v1 - v2 : cost 9999 v1 - v3 : cost 9000 v2 - v4 : cost 1 v1 - v4 : cost 3000 v3 - v4 : cost 9000 v4 - v5 : cost 5000 v4 - v6 : cost 5000 v4 - v7 : cost 5000 This example shows that if you sort edges in increasing order, and take the mid edge in this sorted order and then choose edges with min distance to it, you won't get opt. Example 6: v1 - v2 : cost 1000 v1 - v3 : cost 5 v3 - v2 : cost 10 v2 - v4 : cost 800 v2 - v5 : cost 800 v2 - v6 : cost 800 This example shows that if you take the mean of all edges (~569) and then choose edges closest to the mean, it doesn't produce the optimum solution. Question 2: Most people just rewrote the solution from the assignment. This does not work. The whole point of the question was that you needed to figure out where to start the initial flight from. You cannot start from an arbitrary interval (most just started from a1). Restating the assignment algorithm could give you AT MOST 4 points (depending on how clear it was written, proof, etc..). Example 1: given (a1=1,b1=2); (a2=19, b2=20) Say c = 21 and t = 6. Then, if you start at a2, you cover everything at once. However, if you start at a1, you will need another flight. Example 2: given (a1=0, b1 = 1), (a2=3, b2=5). Say c = 21, and t = 6. This shows that you cannot start at the longest interval. Question 3: Most people understood that a modification of the assignment algorithm works here. Marks awarded for this question were high.