COMPSCI 220
2020 S2 EXAM SOLUTIONS
1 D is the correct answer. Note that g(n) = 0 < n if n is odd and g(n) = 2n2 > n
if n is even. So you cannot fix a constant n0 for which that the inequality of the
asymptotic notation can hold.
2 We have a cubic time algorithm (Θ(n3)) so we can assume the number of elementary
operations can be calculated as cn3 for some constant c. When n = 10, c103 = 20
so c = 150 . And
1
501000
3 = 20000000.
3 Interesting question. We can use the same approach as the previous question
(calculate the constants and then work out the new time with the new input size)
but it will require more time since we have two different algorithms to look at here.
Let’s take a different approach. An algorithm with running time Θ(2n) will need
to double its running time if the input size is increased by 1 (obviously true since
2n+1
2n =2). Similarly, an algorithm with running time Θ(3
n) will need to triple its
running time if the input size is increased by 1. Here, the input size has increased
by 1005 − 1000 = 5. So Algorithm A will need 25 = 32 mins to process the input
and algorithm B will need 35 = 243 mins to calculate the answer. So we save
243− 32 = 211 mins which is about 3.5 hours.
4 A is the correct answer. There is a useful table of summary on the growth rate of
different type of functions in the lecture notes (you can find the same table in the
textbook as well, note that the numbers are different since the table in the book
uses different constants). Note that fastest growth rate means the algorithm itself
will run slower (i.e. the amount of time you need grows faster and hence it will take
longer for the algorithm to run). If you are unsure about the asymptotic relation
between two particular functions, you can always use the limit rule (i.e. calculate
limn→∞
f(n)
g(n) ) to determine the answer.
5 Mergesort, Heapsort and Quicksort (at least in the average case) all have optimal
running time (Θ(n log n)). Mergesort and Quicksort are not in-place and Heapsort
is not stable so B is the correct answer.
6 We have two nested-loops and the loop-counter variables (i and k) are independent.
The outer-loop runs for n2 iterations and the inner-loop runs for lg n2 = 2 lg n
iterations. Since the number of operations inside the main-body ranges from 1 to
1000, the total number of operations (let’s call it x) is bounded by 2n2 lg n ≤ x ≤
(1000)2n2 lg n. Ignore all the constants and we see that f(n) = n2 log n.
7 We are looking at sorting algorithms where the running time between its best, worst
and average case are very similar (at least asymptotically). Selection sort runs in
Θ(n2) time in all cases. Heapsort and Mergesort run in time Θ(n log n) in all cases
and so the answer is C.
1
2 COMPSCI 220 2020 S2 EXAM SOLUTIONS
8 A is the correct answer. This was briefly discussed when we talked about priority
queues in the Heapsort lecture (whether to use an ordered or unordered list to
implement the priority queue).
9 We have solved several similar recurrence in this form. With telescoping, we obtain
T (2m) = T (2m−1) + 2 = T (2m−2) + 2 + 2 = T (2m−3) + 2 + 2 + 2 and eventually we
get to T (2m = T (2m−m) + 2×m) = T (1) + 2m = 2m where m = lg n and so C is
the correct answer.
10 B is the correct answer assuming we want to build a min-heap (not specified in
the question, I think it was a typo). Doing the linear time heapifying algorithm
shows that in every iteration, the node has to be bubble downed all the way to a
leaf (max comparison in every iteration).
11 B is false since you can start from any node. C is false as each NULL element
corresponds to the root of a search tree and could have many search trees. D is
false since nodes only turn black when it has no out neighbours. E is TRUE. So E
is the correct answer.
12 All the statements are correct. Once we realize this tree satisfies the AVL tree
balance condition, we know that at least two statements have to be true.
13 A is true as to find the underlying graph just need to ignore the direction of the
arrows and notice that the arcs (0, 1) and (1, 0) collapse into the single edge {0, 1}.
B is also true. So C must be TRUE (easy to check that D and E are also true if
you like).
14 A is true because 6 and 5 are in different search trees so there is no ancestral
relationship between them, so (6,5) is a cross arc. B is false since 1 is a descendent
of 0 in the search tree so (1,0) is a back arc. Thus A must be the correct answer
(easy to check that (2,3) is a forward arc and (5,1) is a cross arc, making D and E
false).
15 Probably would start this one by drawing the graph - easy to see distances by eye
in a small digraph. Without drawing out the digraph can see that B is false since
0 has out-neighbours 1 and 2 (not just 1 as in the adjacency list). C is false since a
tree has no cycles but 010 is a cycle. D is false since since the in-degree is just the
sum of column 0 which is 1, E is false since adjacency matrices are symmetric for
graphs but M is not symmetric (eg M [0, 2] = 1 6= 0 = M [2, 0]. So check that A is
true: starting from 1 can only folow arc to 0, then to 2 where we can get to 3. So
Shortest path to 3 is 1023 which is of length 3, so A is true.
16 Notice this is about search on a graph, not a digraph. A is false since if there
were an edge from T3 to T2 they wold be the same search tree (as everything in
T3 would be reachable from T2). C is false as w may not be reachable from v in
which case it would be in a different search tree (eg, if w were an isolated vertex
with no neighbours). D is false since each tree is explored with all vertices in the
tree turning from grey to black in the call to the subroutine Visit. E is false from
the same reason that A was false. So B is true.
17 We first ‘remove’ (we want a sorted list at the end so we can’t really just delete a
node and throw it away) the root by swapping it to the end of the array so we get
COMPSCI 220 2020 S2 EXAM SOLUTIONS 3
[1, 10, 9, 8, 7, 6, 5, 4, 2, 11]. And then we bubble down the new root 1 to the correct
place while ignoring 11 and we get [10, 8, 9, 4, 7, 6, 5, 1, 2, 11] at the end.
18 A is correct. Following standard BST insertion procedure we reach node 8. Since
7 < 8, we insert 7 as the left child of 8.
19 D is the correct answer. You can only use binary search in an ordered list.
20 A is false since 3 is a sink so the distance to 6 is undefined or infinite. B is false
since node 5 has out-neighbours and is thus not a sink. C is false since it has only
one out-neighbour, so out-degree is 1. D is false as for A. E is true and is the correct
answer - there is no path to 5 from 3 (or from any other node as 5 is a source).
22 A is false since 3 is a descendant of 2 in the search tree so 3 turned grey before 2.
B is false since the search forest has three trees. C is false since 2 is a root node of
a tree and if it was chosen (turned grey) before 0 then 0, 1, and 5 would be in the
same search tree as node 2 sinc they are all reachable from 2 - hence 0 turned grey
before 2 did. So E must be true and the correct answer - check it using the same
type of argument that demonstrated C was false.
23 A spanning subgraph is a subgraph that includes all vertices of the original graph.
So need to keep all vertices in, and can amke different subgraphs by leaving edges
out. There are 3 + 2 + 1 = 6 edges in K4 and each can be left in or taken out to
form a subgraph so there are 26 possible subgraphs. So E is the correct answer.
24 First let’s find the underlying graph either draw it or go through lists finding all in
and all out neighbours. Get:
0 1 2
1 0 2 6
2 0 6
3 4 5 6
4 3 5
5 3 4 6
6 1 2 3 5
Now start DFS at 0 (as that is the lowest index). Order in which nodes are
visited is 0, 1,2, 6,3,4,5. Thus 5 is the last vertex added to the stack and the the
correct answer is D.
25 The order that nodes are visited (added to the queue) is 2,5,0 (since that is the
white node with lowest index), 1,3,4,6,7, 8. So the answer is C.
26 A is false since the serach forest could have as few as 0 arcs (to see this consider
the case where there no edges in the graph). So A is the correct answer. (easy to
check that the other options are all true)
27 A is true since can use any traversal to find connected components of a graph. B is
true, explanation given in notes. C is false, the result being refered to here is that
G is acyclic if and only if there are no back arcs. Thus C is the correct answer.
(check D and E are true by examples given in notes).
28 A is false since is a topological order must end with a sink but 2 is not a sink. So
A is the correct answer. (check that other answers are true).
4 COMPSCI 220 2020 S2 EXAM SOLUTIONS
29 The algroithm to find the shortest directed cycle in a digraph is given in the notes.
It uses BFS starting from v and stops when a back arc to v is found. This is option
B which is the correct answer here.
30 By eye can see that {7, 8, 14}, {15, 16}, and {9, 10, 17} form three mutually reach-
able sets of nodes so are the strong components of the digraph. Thus E is the
correct answer.
31 The diameter of a graph is the maximum distance between the pair of vertices.
One can easily check that the distance between every pair of vertices in the given
graph is either 1 or 2. Hence, the diameter is 2. Option D
32 We saw in lectures that G does not contain an odd length cycle iff G is bipartite
iff G has a two colouring. That means A is true and D is true. Note that if G has
a 2-colouring it trivially has a k-colouring for 2 ≤ k ≤ n where n is the order of G.
Here n ≥ 10 so C and E are true. So only left with B which must be false. Easy
to see it is false by considering the graph G with no edges. So the correct answer
is B.
33 This problem is solved in the last lecture and the correct answer is A.
BLACK dist[x]
s,1,2,3,4,5
s 0, 1, 3, 6,∞,∞
s,1 0, 1, 3, 6, 4,∞
s,1,2 0, 1, 3, 5, 4, 7
s,1,2,4 0, 1, 3, 5, 4, 6
s,1,2,4,3 0, 1, 3, 5, 4, 6
s,1,2,4,3,5 0, 1, 3, 5, 4, 6
34 The weight ({u, v}) cannot be less than 5 because if it is, then there is a shorter
path from s to u with weight less than 40. It is also possible that there is only one
path from s to u in the graph. In this scenario, weight ({u, v}) cannot be any of
the options A, B, or E as the weight of the shortest path from s to u is given to be
40. Thus, the correct option is D.
35 We can apply Dijkstra’s algorithm with starting node as ‘a’.
BLACK dist[x]
a,b,c,d,e,f
a 0,∞, 7, 2,∞, 6
a,d 0, 3, 7, 2,∞, 6
a,d,b 0, 3, 7, 2,∞, 6
a,d,b,f 0, 3, 7, 2, 8, 6
a,d,b,f,c 0, 3, 7, 2, 8, 6
a,d,b,f,c,e 0, 3, 7, 2, 8, 6
The answer is option E, that is, node c, which is the second farthest from the
source.
36 The weighted graph described is a complete graph of n vertices which each edge
having an edge weight of 2. Definitely, in a complete graph, MST is not unique.
COMPSCI 220 2020 S2 EXAM SOLUTIONS 5
And since a spanning tree on n vertices has exactly n− 1 edges and each edge has
weight 2. A MST in G has weight 2(n− 1). Thus, option E is correct.
37 In Kruskal’s algorithm, edges in increasing order of their weight are considered one
by one and are added to MST as long as it does not create a cycle in the forest
of trees created so far.In the first iteration, the edge {a, b} with weight 1 is added;
in the second iteration, the edge {d, f} with weight 2 is added. In the third and
fourth iteration, edges {c, f} and {g, i} are added, each of weight 3. Thus. option
E is correct.
38 Option D is correct as Prim’s, Kruskal’s, and Dijkstra’s are greedy algorithms
whereas Floyd’s and Bellman-Ford are based on dynamic programming.
39 Option D is correct. Look at the pseudocode for Floyd’s algorithm, it should be
clear. We are checking if there is a shorter path from x to y that passes through v.
40 Option C is correct. This question is discussed in the last lecture. Since V =
{0, 2, 4} is a subset of the vertex set, option A and D can’t be true as spanning
tree and Hamiltonian cycle must contain all vertices of the graph. Option B is
also incorrect as the vertices do not have any edges connecting them. Option E is
incorrect as {1, 3, 5} will form another independent set. Please check lecture notes
for definition of independent set.

欢迎咨询51作业君