Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Inf2-IADS Sample Exam
PART A: 1. (a) The diagram is essentially [3,9,8,2,4,1,6,5] [3,9,8,2] [4,1,6,5] [3,9] [8,2] [4,1] [6,5] [3] [9] [8] [2] [4] [1] [6] [5] [3,9] [2,8] [1,4] [5,6] [2,3,8,9] [1,4,5,6] [1,2,3,4,5,6,8,9] with the obvious arrows added. [5 marks; roughly 2 for the splittings and 3 for the mergings.] (b) Best, worst and average case times are all Θ(m ∗ 2m). [1 mark each.] (c) To mergesort a list of length 2m we only need an array of size 2 ∗ 2m (proof is an easy induction). So space needed is Θ(2m). [1 mark for the answer; 1 mark for any reasonable supporting point.] 2. This is the question about the different fi; we have f1(n) = (lg(n)) lg(n), f2(n) = nlg(n), f3(n) = n 2 and f4(n) = n. note: this is an example of where it’s important to know the “rules of logs”. (a) We are asked to identify the i ∈ {1, 2, 3, 4} such that fi(n) ∈ O(fj(n)) for all j = {1, 2, 3, 4}. Basically we want the fi that is “asymptotically slowest”. This function is f4 = n. The (informal) justification for this . . . • n certainly grows slower than f3 = n2. • Also n certainly grows slower than f2 = nlgn (lg n ≥ 2 for every n ≥ 4) • To consider relative growth of f4 against f1, we will take the lg of both functions: then lg(f1(n)) = lg(lg(n) lg(n)) which is equal to lg(n) · lg lg(n) by “rules of logs” and lg(f4(n)) = lg(n). Hence lg(f1(n)) = lg(n) · lg(f4(n)) so lg(f1(n))) grows asymptotically faster than lg(f4(n)), and f1(n) grows much much faster than f4(n). Hence f4 = O(f1). [5 marks: 2 for identifying the correct i as 4, 1 mark each for the justification wrt each j 6= 4]. Page 1 of 9 (b) We have to identify the k ∈ {1, 2, 3, 4} such that fk(n) ∈ Ω(fj(n)) for all j = {1, 2, 3, 4}, and formally justify this. The function fk is f2 = n lg(n). To prove the fk = Ω(fj) for another j we need to find a n0 ∈ N, c ∈ R>0 such that nlg(n) ≥ c · fj for all n ≥ n0. • For j = 1, we can set c = 1, n0 = 2, then n ≥ lg(n) for n ≥ 2 and hence nlg(n) ≥ lg(n)lg(n) (as the exponent lg(n) is a positive value > 1 for n ≥ 2) • For j = 3, we set c = 1, n0 = 4, then for n ≥ 4 we have lg(n) ≥ 2 and hence f3(n) = n lg(n) ≥ n2. • For j = 3, we set c = 1, n0 = 2, then for n ≥ 2 we have lg(n) ≥ 1 and hence f3(n) = n lg(n) ≥ n. [5 marks: 2 for identifying the correct i as 4, 1 mark each for the formal justification wrt each j 6= 4]. 3. (a) The hash table will have better average case performance. If 10,000 integers are stored, the average bucket size will be 5, so on average, 5 key comparisons will be required for an insertion or unsuccessful lookup, and fewer for a successful lookup. A binary tree storing 10,000 integers, even if perfectly balanced, will have depth around lg 10, 000 ' 13, so a lookup will involve 12 comparisons on average. However, the hash table has terrible worst case performance: if all 10,000 integers hash to the same value, a lookup might require 10,000 comparisons. For red-black trees, the depth (hence the number of comparisons) will be bounded by something around 2 lg 10, 000 ' 26. [3 marks for discussion of average case, 3 marks for worst case. Ballpark figures are acceptable, as in the above answer. Any other reasonable points are acceptable.] (b) The 1 is first added as the left child of 2, and initially coloured R [1 mark]. We then apply the ‘red uncle’ rule, turning 2 and 4 B and 3 R [2 marks]. Finally, since 3 is the root, we turn it B [1 mark]. So in the end, 2,3,4 are B and 1 is R. 4. A decimal counter of length n consists of an array D indexed by 0, . . . , n− 1, in which each cell contains one of the decimal digits 0, . . . , 9. The value v(D) of such a counter is the sum ∑n−1 i=0 D[i] ∗ 10i. The following operation increments the current value of the counter modulo 10n: Page 2 of 9 Inc(): i = 0 while iD[i] = 0 i = i+1 if iD[i] = D[i]+1 (a) Best case time is Θ(1) [1 mark]. This is illustrated by any scenario where D[0] 6= 9 [1 mark]. (b) Worst case time is Θ(n) [1 mark]. Illustrated by the case where D[i] = 9 for all i [1 mark]. (c) Suppose we gauge runtime cost by the number of times the while-test is evaluated (the total number of line executions will be within a factor of 6 of this). Each of the 10n Inc’s will do this test at least once; a tenth of them will do it at least twice; a hundredth at least three times, etc. So total runtime cost will be 10n(1 + 1 10 + 1 100 + · · ·+ 1 10n ) < 10n ∗ ∞∑ i=0 10−i = 10n ∗ 1.1111 · · · Thus total cost is between 10n and 10n ∗ 10/9, and so is Θ(n). Amortized average cost per operation is thus between 1 and 10/9, hence Θ(1). [1 mark for each of the answers; 4 marks for the justification.] 5. Trying to reduce Independent Set to 3-SAT. (a) Given C = (`1 ∨ `2), we can replicate the exact conditions under which C is true by introducing any logical variable xC and replacing C by the con- junction of the following two 3-CNF clauses: C ′ = (`1 ∨ `2 ∨ xC) and C ′′ = (`1 ∨ `2 ∨ ¬xC) [2 marks for the correct construction] (b) For a k-literal clause C = (`1 ∨ . . . ∨ `k) for k ≥ 4, we define k − 2 vari- ables xC,2, . . . , xC,k−2 and replace C by the conjunction of the following clauses: C(2) = (`1 ∨ `2 ∨ ¬xC,2) C(3) = (xC,2 ∨ `3 ∨ ¬xC,3) . . . . . . . . . . . . . . . C(k − 1) = (xC,k−2 ∨ `k−1 ∨ `k) [2 marks for the correct construction] Page 3 of 9 (c) The graph G = (V,E) (n = |V |,m = |E|) will have an Independent Set of size ≥ 4 if and only if for every subset V ′ ⊆ V, |I| = n − 3, V ′ has at least one vertex in I. Using the boolean variable xv to indicate “v is in I” (xv = 1 in this case), we can represent “V ′ has at least one vertex in I” as the length-(n− 3) clause ∨v∈V ′ xv. We need to consider every subset of size (n − 3), so we have (n 3 ) of these length-(n−3) clauses, joined by a ∧. By (b) we know any one of the length- (n− 3) clauses can be re-cast as (n− 5) 3-CNF clauses. Doing this for each of the big clauses gives a 3-CNF Φ which has (n− 5)(n 3 ) clauses in total. To ensure adjacent vertices can’t belong to I, we add (¬xu ∨¬xv) for every e = (u, v) ∈ E. By (a), these can be coded as 2 3-CNF clauses, giving 2m extra clauses. [4 marks - 1 for the length-(n−3) clause, 1 for the characterisation as 3-CNF, 1 for the counting of all big clauses, 1 for the “non-adjacent” clauses.] (d) If we consider generalising the reduction in (c) to the case where we were interested in an Independent Set of size ≥ h, for an arbitrary h, we would find ourselves considering taking ( n h−1 ) different subsets of V , and adding a “big clause” (eventually realised as the ∧ of a number of 3-CNF clauses) for each of these. If h is variable, then the number of “big clauses” is no longer polynomially-sized. So no, this approach doesn’t work. [2 marks for a decent explanation.] Page 4 of 9 FOR PART B: 1. (a) After the first Heap-Extract-Max, the array has 18, 11, 8, 1, 6, 5. After calling Max-Heap-Insert(17), the array then has 18, 11, 17, 1, 6, 5, 8 After calling Heap-Extract-Max again, the array then has 17, 11, 8, 1, 6, 5 After calling Max-Heap-Insert(7), the array then has 17, 11, 8, 1, 6, 5, 7 After calling Max-Heap-Insert(19), the array then has 19, 17, 8, 11, 6, 5, 7, 1 [5 marks for the right answer] (b) We are considering the implementation of ExtendedQueue. i. There is not really any intelligent way to implement findElement on a Heap. If we try to search from the root, then whenever we are exploring a node v, if we find that v.key < k, we are allowed to ignore all nodes below v. However, if v.key > k then we must search in both of the subtrees below v, since the Heap structure does not tell us anything more about where k might be. We can however implement an algorithm which does a traversal of the Heap, and which stops exploring when v.key < k. In the worst-case this has a running time of Θ(n). Consider the case where k lies is the lowest level of the Heap... In this case k is no more likely to be in any spot (on this level) than another. However the lowest level of the Heap may contain n/2 elements in total (if the total size of the Heap is n). [3 marks for a correct findElement and 2 marks for justifying the Θ(n) (1 for each of O(n) and Ω(n)).] ii. To implement maxElement on a Red-Black tree, we observe that the element with the Maximum key in a R-B tree is the rightmost “near- leaf”, giving the following algorithm for maxElement: I. Start at the root of the R-B tree and keep walking to the right-hand child of the current node, until the next right child is a trivial leaf. II. Return the element stored in this position. This little algorithm has worst-case running-time Θ(h) = Θ(lg(n)), given what we know about the height of R-B trees. For removeMax, we initially perform the same steps as for maxElement. Then we delete the node we arrived at - this will potentially require the re-colouring of nodes up to the root of the tree (in the case that we deleted a previously-black node). There are a number of cases to patch-up the tree, but all can be executed in time proportional to the height which is Θ(lg(n)). [1 mark for removeMax and 1 for its running time, 2 marks for remove- Max and 1 for its running time.] iii. The operations removeMax and insertItem both have worst-case running time Θ(lg(n)) on a Heap, and on a R-B tree. The operations findElement and maxElement have different asymptotics on the different structures. Page 5 of 9 If we are implementing an Extended Queue on a Heap, then the Θ(n) running-time of findElement on a Heap might be prohibitive. If we expect findElement to be used relatively frequently for a particular ap- plication of ExtendedQueue, then we should use the Red-Black imple- mentation. However, the R-B implementation of maxElement is less efficient than the Θ(1) implementation of the Heap. So if findElement calls are infre- quent, we might choose to work with the Heap implementation. [5 marks, awarded based on the quality of the arguments.] (c) To implement UpdateKey(o, k′), we assume that o is a direct reference to the object o = (e, k), so we don’t need to carry out findElement. We want to update the key value of o to become k′, but doing this may violate the Max-Heap property. There are two cases: • If k′ > k, then k′ may be larger than the parent of o. This scenario is very similar to the situation in Max-Heap-Insert after the new key gets inserted at the available leaf - the solution is to “swap with the parent” until o sits at a position where k′ is less than the parent’s key. This is O(h) = O(lg(n)) time.