Assignment 1 Solution

Suppose the Canadian Armed Forces is conducting a training exercise for n soldiers in an elite unit. Each soldier must first climb up an down a 10 meter rope and then run a kilometer on a track with n lanes. There is only one rope (due to budget cuts) so only one soldier can be on the rope at any time, whereas it does not matter how many soldiers are on the track. Suppose we know the time ci 0 for soldier i to climb the rope (ci is the total time to climb both up and down) and the time ri 0 for soldier i to complete a kilometer run. The goal is to minimize the overall completion time (the moment when all soldiers have completed the exercise, assuming that the exercise begins at time 0).



Suppose we perform a greedy algorithm by sorting the order in which the soldiers will climb the rope so that ri + ci ri+1 + ci+1. Show that this algorithm will not always produce an optimal schedule.



Design a greedy scheduling algorithm so as to produce an optimal schedule for the order in which the soldiers will climb the rope.



Prove that your scheduling algorithm is optimal by using an exchange argument.



Give an efficient algorithm that takes the following inputs:



a positive integer n 2 Z+;
a sequence with n integers, a1; a2; : : : ; an (note that each ai can be either positive or negative);
and that outputs two integers j and k such that aj ; : : : ; ak is the maximum subsequence of a1; : : : ; an.

Specifically, j and k satisfy:




• 1 6 j 6 k 6 n;

• for any j0 and k0 such that 1 6 j0 6 k0 6 n,


k0
ai 6


k
ai .








i=j0


i=j
(


). Write a detailed proof that


time complexity
n
For full marks, your algorithm must have theP




P




O


your algorithm is correct and justify your algorithm’s time complexity. (Note that this argument of correctness will be worth significantly more than the algorithm itself.)










Dept. of Computer Science, University of Toronto, St. George Campus page 1 of 2
CSC 373 H1 Assignment # 1







Consider the following inputs:



G = (V ; E), a connected undirected graph,



w : E ! Z+, a weight function for the edges of G.



Also assume the minimum spanning tree (MST) of G, T , is unique, i.e., there is no other spanning tree has the same total weight as T . Design an algorithm that outputs a second-minimum spanning

ˆ

tree for G, i.e., a spanning tree T of G such that:




ˆ

• w(T ) w(T )—remember that T is the unique MST of G,

ˆ

• w(T ) 6 w(T ) for all spanning trees T of G that are not T




(where w(T ) is the sum of the weights of the edges of T , for any spanning tree T ). If there is no




ˆ

spanning tree T that satisfies these conditions, your algorithm should output the special value nil.




For full marks, your algorithm must have asymptotic time complexity no worse than computing a MST for G from scratch. Prove that your algorithm is correct and justify your algorithm’s time complexity. (Note that this argument of correctness will be worth more than the algorithm itself).




Hint: One possible efficient algorithm is to compute the minimum spanning tree T first and then modify T to obtain the second minimum spanning tree. In this case, simply make a call to the appropriate algorithm from class and please do not repeat its proof of correctness in your solution: you can just use the fact that the algorithm is known to be correct.




Note: Your algorithm is likely to be different from a pure Greedy algorithm. Keep this in mind when writing your proof!
















































































































Dept. of Computer Science, University of Toronto, St. George Campus page 2 of 2