Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMS20010 — 2020–21 Exam
This exam was actually given as a Blackboard test in a slightly different format to the one used this year
(hence “Section 1” and “Section 2”). This means this isn’t quite the final version, and since it hadn’t gone
through the final round of checking at that point there might still be one or two errors lurking in the model
answers, but it should be a good guide as to what to expect.
Section 1
1. (5 marks) (Short question.) Mark each of the following statements true or false:
(a) (1 mark) n2 ∈ O(5n).
Solution: False, n2 ∈ ω(5n).
(b) (1 mark) 10n2 + n ∈ O(n2).
Solution: True, 10n2 + n ∈ O(n2).
(c) (1 mark) log n ∈ O(n1/5).
Solution: True, log n ∈ O(n1/5).
(d) (1 mark) n65 ∈ O(n!).
Solution: True, n65 ∈ O(n!).
(e) (1 mark) 2n
2 ∈ O(2n).
Solution: False, 2n
2 ∈ ω(2n).
2. (5 marks) (Short question.) Consider the following graph G and the indicated vertex w.
w
Mark each of the following statements true or false:
(a) (1 mark) G is weakly connected.
Solution: True, G is weakly connected.
(b) (1 mark) G is strongly connected.
Solution: False, there is no path from the right triangle to the left triangle.
(c) (1 mark) G has an Euler walk.
Solution: True, starting at v, walking round the left triangle, crossing to the right triangle,
walking round the right triangle.
(d) (1 mark) G contains a directed cycle as an induced subgraph.
Solution: True, both triangles are induced directed cycles.
(e) (1 mark) d−(w) = 2.
Solution: False, d−(w) = 1.
3. (5 marks) (Short question.) Consider the following flow network and flow, with source s and sink t.
5/
8
2/2
4/6
1/4 5/
5
2/2
6/7
3/4
4/
8
s
a b
c d
t
List all augmenting paths of the network under the given flow.
Solution: The augmenting paths are sabt, sabdt, sabcdt, sacdt, and sacdbt.
4. (5 marks) (Short question.) The strategy game Civilization VI is played on a hexagonal map as shown
below. The map is effectively a cylinder, with the left and right boundaries are joined together, and
the top and bottom boundaries are impassable — thus in the picture below, tile a appears twice, and is
adjacent to both tile b and tile c. Units can move between any pair of adjacent tiles, and this is stored
in memory as a graph in which there is an edge between two tiles if they are adjacent in the map.
ab
a
c
If the map is 90 tiles wide and 56 tiles high, how many edges does the graph have? (Hint: Use the
handshaking lemma.)
A. 13440.
B. 14829.
C. 14940.
D. 29658.
E. None of the above.
Solution: By the handshaking lemma, the total number of edges is half the total degree of the
graph. There are 90 tiles of degree 5 and 90 tiles of degree 3, with 45 of each along the top edge
and 45 of each along the bottom edge. The remaining 90 · 56 − 90 · 2 tiles all have degree 6. Thus
the total number of edges is
90 · 54 · 6 + 90 · 5 + 90 · 3
2
= 14940.
A is the number of edges in the standard Civilization VI map size of 84× 54, just in case someone
manages to Google it. B is what you get if you forget the horizontal boundaries wrap. D is what
you get if you forget the horizontal boundaries wrap and forget to divide by 2.
5. (5 marks) (Short question.) Consider the weighted graph below.
20
5
10
3
3
7
6
1
5 10
2
6
13
u v
What is the distance from u to v?
A. 1.
B. 16.
C. 18.
D. 20.
E. None of the above.
Solution: E — None of the above. The correct answer is 17. A shortest-path tree is drawn
below.
20
5
10
3
3
7
6
1
5 10
2
6
13
u v
6. (5 marks) (Short question.) Consider the 11-vertex weighted graph G below.
32
2
1
3
3
2
1
2
2
2
1 2
2
2
1
3 2
What is the weight of a minimum spanning tree of G?
A. 12.
B. 13.
C. 14.
D. G doesn’t have a minimum spanning tree.
E. None of the above.
Solution: D— G is disconnected, so it doesn’t have any spanning trees at all. A minimum spanning
tree of the left component has total weight 8, and a minimum spanning tree of the right component
has total weight 6.
7. (5 marks) (Short question.) Which of the following are valid 2-3-4 trees?
(a) (1 mark)
3
1 5
2 4 6
Solution: Invalid. This tree breaks perfect balance, because 1 is a non-leaf 2-node with fewer
than 2 children.
(b) (1 mark)
2 4 6 8
1 3 5 7 9
Solution: Invalid. The root is neither a 2-node, nor a 3-node, nor a 4-node.
(c) (1 mark)
3
1 2 5 7
4 6 8
Solution: Invalid. This tree breaks perfect balance, because (1, 2) is a leaf not on the bottom
level of the tree.
(d) (1 mark)
1 2 3 5 7 9 11 14 20
4 8 13 17
6 10
Solution: Valid. The values in a 2-3-4 tree don’t have to be consecutive.
(e) (1 mark)
1 2
Solution: Valid. A 2-3-4 tree can have any number of levels, even one.
8. (5 marks) (Short question.) Consider the unoptimised version of the union-find data structure, in which
a sequence of n operations takes O(n log n) time rather than O(nα(n)) time. Suppose the current state
of the data structure is as follows:
1 2 3
4
5
6
7
8
9
1011
12 13
(a) (1 mark) What is the result of Find(13)?
Solution: 13.
(b) (1 mark) What is the result of Find(9)?
Solution: 12, the root of the component containing 9.
(c) (2 marks) Suppose we now apply the operations Union(6,8), Union(1,7) and Union(10,4) to the
data structure, in this order. How many components does the data structure now have?
Solution: 2. Each Union operation reduces the number of components by one.
(d) (1 mark) Again after applying the Union operations above, what is the maximum depth of any
component of the data structure? (The answer does not depend on how ties are broken.)
Solution: 3. The exact structure will depend on how ties are broken, but the first Union
will always merge the middle two components into a depth-2 component, the second Union
will always merge the first component with this depth-2 component without increasing its
depth, and the third Union will always merge two depth-2 components to produce a depth-3
component.
9. (5 marks) (Short question.) EvilCo Incorporated designs dastardly mazes for enterprising B-movie vil-
lains. In their marketing material, they say that their mazes are so complicated that if you want to get
from one point to another without retracing your steps, there’s only ever one way to do it. If one of
their mazes has j junctions, how many corridors between junctions does it have, and why?
(Note this does not include e.g. dead ends, or the entrance and exit — only corridors between two
junctions count. Your answer should be short.)
...
...
...
...
Junction Junction
Solution: We can view the maze as a graph, where the vertices are junctions, and two junctions are
joined by an edge if there is a direct corridor between them. In this context, the marketing material
says that there is a unique path between any two vertices. Hence by the Fundamental Lemma of
Trees, the graph must be a tree and contain j − 1 edges.
10. (5 marks) (Medium question.) You are the CEO of a sprawling corporation, which contains many
overlapping product teams. You wish to set up a representative meeting — a meeting containing at least
one representative from each product team — which is as small as possible, using the fact that a single
person can act as a representative for all of the teams they’re a member of. By reducing from vertex
cover or otherwise, prove that it is NP-complete (under Karp reductions) to decide whether or not a
k-person representative meeting exists, given a list of the teams and the value of k.
Solution: Given a proposed meeting, we can verify that it contains at least one person from each
team in polynomial time, so the problem is in NP. It remains to show that the problem is NP-hard
under Karp reductions.
Let (G, k) be an instance of vertex cover. Then we take our employees to be the vertices of G, and
our teams to be the edges of G. Thus a set S of k people forms a representative meeting if and only
if every edge contains a person in S — that is, if and only if S is a size-k vertex cover of G. We
have therefore created an instance of the representative meeting problem in polynomial time whose
answer is Yes if and only if (G, k) is a Yes instance of vertex cover, as required.
11. (5 marks) (Medium question.) Consider the 2-3-4 tree below:
8 16
12
3 6 10 14 18 20 22
1 2 4 5 7 9 11 13 15 17 19 21 23 24 25
After deleting the value 8 and inserting the value 30:
(a) (1 mark) What is the depth of the resulting tree?
Solution: 3. Deleting 8 involves fusing the root, transferring 5 from (4, 5) to (7), deleting 7
and overwriting 8 with 7. The result looks like this:
7 12 16
3 5 10 14 18 20 22
1 2 4 6 9 11 13 15 17 19 21 23 24 25
Inserting 30 then involves splitting the root, splitting (18, 20, 22), splitting (23, 24, 25) and
inserting 30 into the newly formed (25) node. The result looks like this:
7 16 20
12
3 5 10 14 18 22 24
1 2 4 6 9 11 13 15 17 19 21 23 25 30
(b) (2 marks) How many 3-nodes does the resulting tree have?
Solution: 5. See above.
(c) (2 marks) While deleting 8 and inserting 30, how many fuse, transfer and split operations were
performed in total?
Solution: 5. See above.
12. (5 marks) (Short question.) Consider the following flow network (G, c, s, t):
42
5
2
3
1
3
5
6
2
s a b
c
d
t
Let A = {s, b} and B = {a, c, d, t}. What is the capacity c+(A) of the cut (A,B)?
A. 8.
B. 13.
C. 21.
D. (A,B) is not a cut.
E. None of the above.
Solution: B — 13. Cuts do not have to form connected induced subgraphs, and the capacity is
the sum of the capacities of all edges leaving A.
13. (5 marks) (Short question.) Consider the following circulation network.
3
2 1 2
4
-4
a
0
b
1
c
3
d
Which of the following is a valid circulation f?
A. f(a, b) = 2; f(a, c) = 0; f(a, d) = 1; f(b, d) = 2; f(c, d) = 0.
B. f(a, b) = 2; f(a, c) = 2; f(a, d) = 0; f(b, d) = 1; f(c, d) = 1.
C. f(a, b) = 3; f(a, c) = 1; f(a, d) = 0; f(b, d) = 3; f(c, d) = 0.
D. f(a, b) = 1; f(a, c) = 2; f(a, d) = 1; f(b, d) = 1; f(c, d) = 1.
E. None of the above, or more than one of the above.
Solution: D is a valid circulation. A violates the demand constraints at a and c. B violates the
demand constraints at b and d. C violates the capacity constraint at (b, d).
14. (5 marks) (Short question.) Mark each of the following statements true or false.
(a) (1 mark) The problem of outputting a size-k vertex cover in a graph G if one exists or No cover
otherwise, given G and k as inputs, is NP-hard.
Solution: True. There is an immediate reduction from (the decision version of) vertex cover,
the NP-completeness of which was proved in lectures..
(b) (1 mark) The problem of outputting a size-k vertex cover in a graph G if one exists or No cover
otherwise, given G and k as inputs, is in NP.
Solution: False. This is not a decision problem, so it is not a member of NP.
(c) (1 mark) Because SAT is an NP-complete problem, it is never practical to solve a 1,000-variable
instance of SAT.
Solution: False. Discussed highly-efficient industrial SAT-solvers in lectures, and the 1,000-
variable instance could just be e.g. x1 ∧ x2 ∧ · · · ∧ x1000.
(d) (1 mark) If we had working quantum computers, we know how to use them to solve NP-complete
problems in polynomial time.
Solution: False. Explicitly discussed limitations of quantum computers in lectures.
(e) (1 mark) If a problem has instance size n and parameter k, then an algorithm with running time
O(n
√
k) shows that the problem is fixed-parameter tractable.
Solution: False. FPT time requires running time O(g(k)nC) for some computable function g
and some constant C.
15. (5 marks) (Short question.) Consider an instance of weighted interval scheduling with interval set R =
[(1, 5), (4, 6), (2, 11), (6, 13), (11, 16), (14, 19), (14, 21), (18, 21), (20, 25)] and weight function w given by
w(1, 5) = 3, w(4, 6) = 5, w(2, 11) = 7, w(6, 13) = 3, w(11, 16) = 3,
w(14, 19) = 4, w(14, 21) = 6, w(18, 21) = 5, w(20, 25) = 3.
What is the maximum possible weight of a compatible set?
A. 13.
B. 14.
C. 15.
D. 16.
E. None of the above.
Solution: C – 15. An optimal set is {(2, 11), (11, 16), (18, 21)}. In more detail, writing OPT(i)
for the weight of an optimal solution on the first i intervals in ascending order of finish time, we
have:
OPT(1) = 3, OPT(2) = 5, OPT(3) = 7, OPT(4) = 8, OPT(5) = 10,
OPT(6) = 12, OPT(7) = 15, OPT(8) = 15, OPT(9) = 15.
The two compatible sets with weight 15 are {(4, 6), (6, 13), (14, 19), (20, 25) and {(2, 11), (11, 16), (18, 12)}.