主观题代写-2-IADS
时间:2021-05-11
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

学霸联盟


essay、essay代写