- May 15, 2020

Computer Science C73 September 16, 2019Scarborough Campus University of TorontoHomework Assignment #2(worth 6% of the course grade)Due: September 23, 2019, by 10 am• You must submit your assignment as a PDF file through the MarkUs system by logging in with yourUTORid at markus.utsc.utoronto.ca/cscc73f17. To work with a partner, you and your partner mustform a group on MarkUs.• It is your responsibility to ensure that the PDF file you submit is legible. To this end, I encourage youto learn and use the LaTex typesetting system, which is designed to produce high-quality documents thatcontain mathematical notation. You are not required to produce the PDF file you submit using LaTex;you may produce it any way you wish, as long as the resulting document is legible.• By virtue of submitting this assignment you (and your partner, if you have one) acknowledge that youare aware of the policy on homework collaboration for this course.a• For any question, you may use data structures and algorithms previously described in class, or inprerequisites of this course, without describing them. You may also use any result that we covered inclass, or is in the assigned sections of the official course textbooks, by referring to it.• Unless we explicitly state otherwise, you may describe algorithms in high-level pseudocode or point-formEnglish, whichever leads to a clearer and simpler description.• Unless we explicitly state otherwise, you should justify your answers. Your paper will be graded basedon the correctness and efficiency of your answers, and the clarity, precision, and conciseness of yourpresentation.a“In each homework assignment you may collaborate with at most one other student who is currently taking CSCC73. Ifyou collaborate with another student on an assignment, you and your partner must submit only one copy of your solution,with both of your names. The solution will be graded in the usual way and both partners will receive the same mark.Collaboration involving more than two students is not allowed. For help with your homework you may consult onlythe instructor, TAs, your homework partner (if you have one), your textbook, and your class notes. Youmay not consult any other source.”Question 1. (15 marks) A summer camp has n campers, labeled 1, 2, . . . , n, and wants to organize acanoe trip. Camper i weighs wi. Each canoe must have exactly two campers, whose combined weightmust not exceed C; naturally, no camper can be in two canoes! Our job is to pair-up as many campers aspossible subject to the weight constraint.More precisely, a set of (unordered) pairs of campers is feasible if (a) no camper belongs to two differentpairs in the set; and (b) for any pair {i, j} in the set, wi + wj ≤ C. A feasible set of pairs of campers isoptimal if there is no feasible set with greater cardinality. Given w1, . . . , wn and C, we want to find anoptimal set of pairs of campers.a. Prove that the following greedy algorithm does not necessarily find an optimal set: If n < 2, returnthe empty set. Otherwise, let p and q be two lightest campers (ties broken arbitrarily). If wp + wq ≤ C,return the set of pairs obtained by adding the pair {p, q} to the set returned by recursively applying thealgorithm to the remaining campers; otherwise, return the empty set.b. Prove that the following greedy algorithm always finds an optimal set: If n < 2, return the empty set.Otherwise, let p be a lightest camper and q be a heaviest camper (ties broken arbitrarily). If wp +wq ≤ C,return the set of pairs obtained by adding the pair {p, q} to the set returned by recursively applyingthe algorithm to the remaining campers; otherwise, discard q and return the set returned by recursivelyapplying the algorithm to the remaining campers. The recursion ends when the number of remaining1campers is less than two. (Hint. Prove that if the combined weight of a lightest and heaviest camper doesnot exceed C, there is an optimal set that contains a pair consisting of these two campers.)c. Suppose the camp has only four-person canoes; i.e., each canoe must carry exactly four campers.Consider the following greedy algorithm for this case: Take the two lightest and two heaviest campers(ties broken arbitrarily). If the combined weight of these four campers is at most C add this group of fourcampers to the set returned by recursively applying the algorithm to the remaining campers; otherwisediscard the heaviest of the four campers and return the set returned by recursively applying the algorithmto the remaining campers. The recursion ends when the number of remaining campers is less than four.Does this algorithm work? Justify your answerQuestion 2. (10 marks) Consider Huffman’s algorithm.a. (2 marks) Give an example of a (small) set of symbols and their associated frequencies so that thereis exactly one symbol with frequency 1/3, all other symbols have frequency (strictly) less than 1/3, andHuffman’s algorithm may produce a codeword of length 1.b. (8 marks) Prove that for any set of symbols, if every symbol has frequency (strictly) less than 1/3,Huffman’s algorithm cannot produce a codeword of length 1.Question 3. (10 marks)a. (8 marks) Modify Dijkstra’s algorithm to compute the number of minimum-weight paths from thestart node s to every node, assuming that all edges have (strictly) positive weights. Your modificationshould have the same running time (asymptotically) as Dijkstra’s algorithm. You need not prove that youralgorithm is correct — but it should be! (To convince yourself that it does, I suggest that you revisit theinvariants that we used in the proof correctness of Dijkstra’s algorithm and that you consider how theyshould be strengthened to prove the correctness of your algorithm. You should not include this in youranswer, however.)b. (2 marks) Does your algorithm work if edges have non-negative (as opposed to strictly positive)weights — i.e., if some edges may have zero weight? Justify your answer.2