Samplemidterm1.dvi

[12] 1. Answer each of the questions with either true or false. You must justify each of your
answers; an answer without a justification will be worth at most 1.5 out of 4.
Solution : This is true. Here are two proofs of this fact:
• Using the definition of O: pick c = 32 and n0 = 1. Then 3n+2 +5 = 27·3n−1 + 5 ≤ 27 · 3n−1 + 5 · 3n−1 (for n ≥ 1), and so 3n+2 + 5 ≤ 32 · 3n−1 = c3n−1.
[4] b. Let f, g be two functions from N into R+. Assuming that limn→∞ f (n)/g(n) exists, we can use its value to determine whether or not f is in O(g).
Solution : This is true: if limn→∞ f (n)/g(n) = 0 then f ∈ o(g), and hence f ∈
O(g). If limn→∞ f (n)/g(n) is a positive real number, then f ∈ Θ(g) and so f ∈
O(g). Finally if limn→∞ f (n)/g(n) = +∞ then f ∈ ω(g), and therefore f /
[4] c. In class, we proved an Ω(n log n) lower bound on the worst-case running time of any algorithm that can be used to sort a sequence of n values.
Solution : This is false: we only proved an Ω(n log n) lower bound on the worst-
case running time of any comparison sort. We did not prove that there isn’t some
other type of algorithm that might be able to sort a sequence of n values faster.
[8] 2. Show how to construct an input for which the prefix tree generated by Huffman’s algorithm will have all of its leaves on either the bottom-most level, or the level just above it. Yourconstruction should work for any alphabet size m ≥ 2. Sketch a proof that it results in aprefix tree with the requested property (you do not need to write a complete proof).
Solution : I claim that if all characters have the same frequency f , then the tree will have
the desired property. The simplest proof of this fact is a proof by contradiction. Suppose
that Huffman’s algorithm generated a tree T with depth d, and at least one leaf at depth d′
where d′ < d − 1. Let x and y be the two characters that occupy siblings leaves at depth d,
and z be the character at depth d′.
We build a tree T ′ from T by moving the character z from its current node to the parentof x and y, and by making x and y children of the node that used to contain z. What happens to the length of the code? The code grows by d − 1 − d′ bits for every occurrenceof z, and shrinks by d − d′ bits for every occurrence of x and y. The total change is thusf (d − 1 − d′) − f (d − d′), which after simplification is just −f .
But this means that T ′ gives us a code shorter than the code found by Huffman’s algorithm,which is impossible. Therefore every leaf of T must have been at level d or d − 1.
[8] 3. Show the tree constructed by Kruskal’s minimum spanning tree algorithm for the graph in the following figure. Label each edge of your tree by a number that indicates the order inwhich the edges were added to the tree (so the first edge added will be labeled “1”, thesecond edge added will be labeled “2”, etc).
Solution :
[12] 4. The Vancouver aquarium is undergoing major renovations. For the duration of the renova- tions, only one water tank will be available to the public. The aquarium’s president decidesto put as many different species of fish in that one tank so the public can see as many ofthem as possible. He asks for your help. He provides you with the following information: • A list F1, . . . , Fn of the n types of fish that the aquarium owns, and• A list (Fi, Fj) of pairs of kinds of fish that can not be put in the same water tank as [9] a. Design a greedy algorithm that takes this information as input, and returns a list of species of fish that can cohabit peacefully. Your algorithm should try to maximizethe number of species in the list.
Solution : Here is one possible solution:
// F is the list of species of fish.
// P is the list of pairs of species we can not put together find species f of F that occurs the fewest times in P remove from F every species x such that (f, x) ∈ Premove all occurrences of f from P This is all that you were required to answer on the exam. Let us now analyze the
worst-case running time of the algorithm (this was not required).
A brute-force implementation of this algorithm will loop through P every time itneeds to find the next species of fish, and will run in O(|F ||P |) time. A more carefulimplementation would work as follows: • We count how many times each species f occurs in P . This can be done in O(|F | + |P |) time by initializing a counter to 0 for each element of |F |, and thengoing through the list of pairs once, incrementing the counters for both elementsof each pair. We also store all other species of fish with which a species f isincompatible.
• We then store the elements of |F | in a min-heap.
• The remainder of the algorithm then performs |F | deleteMin and delete This allows the algorithm to run in O(|P | + |F | log |F |) time. Note that, unfortu-nately, this algorithm does not always return the largest possible set of species (it islikely that no greedy algorithm can do it).
[3] b. Explain briefly why your algorithm from part (a) is greedy.
Solution : It is greedy because it always chooses the fish species whose inclusion
forces the exclusion of as few other species as possible.

Source: http://thecube.ca/files/exams/2010/cs320-2010-t1-sample-midterm1-solution.pdf