Blog

Solutions for Inf2-IADS Sample Exam 2020/21 (prepared April 2021):
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.
If k′ < k, then k′ may be smaller than the key(s) at o’s child nodes. This can be resolved by making the call Max-Heapify at o, and again this will run in O(lg(n) time. [5 marks, with 3 going for a correct solution to either of the two cases, and the other 2 for the second case.] Page 6 of 9 2. (a) The CYK chart is: cows , goats and sheep cows I,AL,CL CL CAL,L , goats I,AL,CL AL,CAL,L and sheep I,AL,CL [7 marks. Approximately 0.5 per correct entry.] (b) The grammar is ambiguous [1 mark]. For instance, goats and sheep can be parsed as either AL or CAL(this example is encountered in the course of constructing the CYK chart above). [1 mark for any example.] (c) The LL(1) parsing algorithm will fail at the very first step. We wish to expand the start symbol L. Suppose the first input token is cows. We cannot tell whether to expand L to AL or to CAL, as both are consistent with this input information (e.g. the string could be cows and goats and sheep or cows, goats and sheep. [2 marks for identifying the point of failure, 2 marks for an explanation showing clear understanding.] (d) The parser executes as follows: Operation applied Remaining input Stack state I , I and I L Lookup L, I I , I and I I Rest Match I , I and I Rest Lookup Rest, , , I and I , I CTail and I Match , I and I I CTail and I Match I and I CTail and I Lookup CTail, and and I and I Match and I I Match I end of input empty stack [10 marks; roughly 1 mark per line.] (e) In general, LL(1) grammars aren’t appropriate for NLP. Even in cases where an NL grammar can be made LL(1), doing so may artificially eradicate gen- uine ambiguities: a single interpretation will be selected and others ignored, and the ambiguity won’t even be flagged up. [2 marks; any reasonable point accepted.] Page 7 of 9 3. (a) Algorithm hamilton(G = (V,E)) 1. len← 1 2. Initialize visited array of length |V | to False in every cell. 3. visited[v1]← True 4. return hamiltonFromVertex(G = (V,E), v1) Algorithm hamiltonFromVertex(G = (V,E), w) 1. if ((len = |V |) and(w, v1) ∈ E) 2. then return True 3. else if ((len = |V |) and(w, v1) /∈ E) 4. then return False 5. else 6. len← len + 1 7. for all (x ∈ Adj(w) such that visited[x] = False) do 8. visited[x]← True 9. if hamiltonFromVertex(G = (V,E), x) 10. return true 11. visited[x]← False 12. len← len 1 There are two main differences from depth-first search. The first is the lack of a loop in the “top-level” method iterating over all vertices (for a HC in a undirected graph it makes no difference where we start, since we require a single connected component). The second difference that when we meet a new vertex x, we mark it visited, and we subsequently continue out exploration from there, but if this fails to generate a HC, we will revert the “visited” status of x as we backtrack. [The 7 marks are divided as 2 for the top-level method, and up to 5 marks for accurate details for the recursive method. Their structure approach may be slightly different, marks will be awarded fairly.] (b) We assume that competing adjacent nodes are explored in order of increasing index. If we start our exploration at node 0, then the lowest-indexed adjacent edge is (0, 1), and we continue our exploration from 1. Note that {1, . . . , n 2 1} is a complete graph, so hamiltonFromVertex(G, 1) (with 0 already visited), will explore every permutation of {2, . . . , n 2 1} ((n 2 2)! of these) before returning to 0. All are guaranteed to be explored, as we know there is no HC with 0 adjacent to 1, there is a unique HC which contains (0, n 1) and (0, n 2 1). (note we can show a similar result for exploring the other edges (0, i), i = 2, . . . , n 2 2 from 0, but we don’t need this for the result.) Page 8 of 9 It is well-known that k! ≥ 2k for k ≥ 4, therefore (n 2 2)! ≥ 2n2 2. And using c = 1 4 for the 2 2, and n0 = 4, clearly 2 n 2 2 = (2 n 2 ). [3 marks for noticing the exploration of the complete graph on the top needs to be done in full, and explaining why wrt the indices, 2 marks for relating this to the unique HC and adjacencies of the 0 vertex, 2 marks for working out a lower bound wrt (n 2 2)!, 1 mark for relating this to power of 2.] (c) i. We can set k = n and then a tour of value ≤ k (for this graph) can only be achieved with a tour where every edge has weight 1, as appropriate (note we require n ≥ 2 for this!) [2 marks for a correct answer] ii. The constructed tour will not correspond to a HC of the original graph. This is because the first step of Greedy (breaking ties for lower indices) will be to add (0, 1) to the tour, and commit to that edge. We already know there is no HC with the edge (0, 1) in it. [2 marks for the answer, 2 marks for justifying] iii. The initial tour 0, 1, . . . , n 2 1, n 2 , . . . , n 1 consists of (n 1) edges of weight 1 (this includes the “wraparound” edge (n 1, 0)) plus the weight n for edge (n 2 1, n 2 ). The only “swap” moves which have the potential to change the status of the weight-n edge are i = n 2 2, i = n 2 1 and i = n 2 . In the first case vertex (n 2 2) will end up adjacent to n 2 , and this also has weight n, so no improvement is made. For i = (n 2 1), the swap would bring n 2 adjacent to (n 2 2) and also (n 2 1) adjacent to (n 2 + 1), two edges of weight n, so strictly worse . . . and again for i = n 2 the proposed change would result in two edges of weight n. None of these options has (strictly) lower tourValue than our original tour, so no changes will be made. [2 marks for the answer, 2 marks for justifying] Page 9 of 9 D[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.
If k′ < k, then k′ may be smaller than the key(s) at o’s child nodes. This can be resolved by making the call Max-Heapify at o, and again this will run in O(lg(n) time. [5 marks, with 3 going for a correct solution to either of the two cases, and the other 2 for the second case.] Page 6 of 9 2. (a) The CYK chart is: cows , goats and sheep cows I,AL,CL CL CAL,L , goats I,AL,CL AL,CAL,L and sheep I,AL,CL [7 marks. Approximately 0.5 per correct entry.] (b) The grammar is ambiguous [1 mark]. For instance, goats and sheep can be parsed as either AL or CAL(this example is encountered in the course of constructing the CYK chart above). [1 mark for any example.] (c) The LL(1) parsing algorithm will fail at the very first step. We wish to expand the start symbol L. Suppose the first input token is cows. We cannot tell whether to expand L to AL or to CAL, as both are consistent with this input information (e.g. the string could be cows and goats and sheep or cows, goats and sheep. [2 marks for identifying the point of failure, 2 marks for an explanation showing clear understanding.] (d) The parser executes as follows: Operation applied Remaining input Stack state I , I and I L Lookup L, I I , I and I I Rest Match I , I and I Rest Lookup Rest, , , I and I , I CTail and I Match , I and I I CTail and I Match I and I CTail and I Lookup CTail, and and I and I Match and I I Match I end of input empty stack [10 marks; roughly 1 mark per line.] (e) In general, LL(1) grammars aren’t appropriate for NLP. Even in cases where an NL grammar can be made LL(1), doing so may artificially eradicate gen- uine ambiguities: a single interpretation will be selected and others ignored, and the ambiguity won’t even be flagged up. [2 marks; any reasonable point accepted.] Page 7 of 9 3. (a) Algorithm hamilton(G = (V,E)) 1. len← 1 2. Initialize visited array of length |V | to False in every cell. 3. visited[v1]← True 4. return hamiltonFromVertex(G = (V,E), v1) Algorithm hamiltonFromVertex(G = (V,E), w) 1. if ((len = |V |) and(w, v1) ∈ E) 2. then return True 3. else if ((len = |V |) and(w, v1) /∈ E) 4. then return False 5. else 6. len← len + 1 7. for all (x ∈ Adj(w) such that visited[x] = False) do 8. visited[x]← True 9. if hamiltonFromVertex(G = (V,E), x) 10. return true 11. visited[x]← False 12. len← len 1 There are two main differences from depth-first search. The first is the lack of a loop in the “top-level” method iterating over all vertices (for a HC in a undirected graph it makes no difference where we start, since we require a single connected component). The second difference that when we meet a new vertex x, we mark it visited, and we subsequently continue out exploration from there, but if this fails to generate a HC, we will revert the “visited” status of x as we backtrack. [The 7 marks are divided as 2 for the top-level method, and up to 5 marks for accurate details for the recursive method. Their structure approach may be slightly different, marks will be awarded fairly.] (b) We assume that competing adjacent nodes are explored in order of increasing index. If we start our exploration at node 0, then the lowest-indexed adjacent edge is (0, 1), and we continue our exploration from 1. Note that {1, . . . , n 2 1} is a complete graph, so hamiltonFromVertex(G, 1) (with 0 already visited), will explore every permutation of {2, . . . , n 2 1} ((n 2 2)! of these) before returning to 0. All are guaranteed to be explored, as we know there is no HC with 0 adjacent to 1, there is a unique HC which contains (0, n 1) and (0, n 2 1). (note we can show a similar result for exploring the other edges (0, i), i = 2, . . . , n 2 2 from 0, but we don’t need this for the result.) Page 8 of 9 It is well-known that k! ≥ 2k for k ≥ 4, therefore (n 2 2)! ≥ 2n2 2. And using c = 1 4 for the 2 2, and n0 = 4, clearly 2 n 2 2 = (2 n 2 ). [3 marks for noticing the exploration of the complete graph on the top needs to be done in full, and explaining why wrt the indices, 2 marks for relating this to the unique HC and adjacencies of the 0 vertex, 2 marks for working out a lower bound wrt (n 2 2)!, 1 mark for relating this to power of 2.] (c) i. We can set k = n and then a tour of value ≤ k (for this graph) can only be achieved with a tour where every edge has weight 1, as appropriate (note we require n ≥ 2 for this!) [2 marks for a correct answer] ii. The constructed tour will not correspond to a HC of the original graph. This is because the first step of Greedy (breaking ties for lower indices) will be to add (0, 1) to the tour, and commit to that edge. We already know there is no HC with the edge (0, 1) in it. [2 marks for the answer, 2 marks for justifying] iii. The initial tour 0, 1, . . . , n 2 1, n 2 , . . . , n 1 consists of (n 1) edges of weight 1 (this includes the “wraparound” edge (n 1, 0)) plus the weight n for edge (n 2 1, n 2 ). The only “swap” moves which have the potential to change the status of the weight-n edge are i = n 2 2, i = n 2 1 and i = n 2 . In the first case vertex (n 2 2) will end up adjacent to n 2 , and this also has weight n, so no improvement is made. For i = (n 2 1), the swap would bring n 2 adjacent to (n 2 2) and also (n 2 1) adjacent to (n 2 + 1), two edges of weight n, so strictly worse . . . and again for i = n 2 the proposed change would result in two edges of weight n. None of these options has (strictly) lower tourValue than our original tour, so no changes will be made. [2 marks for the answer, 2 marks for justifying] Page 9 of 9 Inc(): i = 0 while i