Question 1
As an Author, Harry Potter needs to commute from his home at Number 12, Grimmauld
Place to the ministry of magic. In order not to be seen by muggles, he can only use
the portkeys and the muggle way of driving cars through the London road network,
instead of flying on the broom. The portkeys are everyday objects that are enchanted
with a fixed destination and just by touching them, one gets instantaneously
teleported to the destination location. Harry has the road network with associated
edge weights that capture the driving distance. He also knows of the location of the
various portkeys, where they are and their destination. However, he can only use two
portkeys in a single commute as otherwise he runs the risk of decomposing himself.
Give an time algorithm to compute the shortest path from his home to
the ministry that uses at most two portkeys. Here, is the number of locations/
intersections in the London road network (including the portkey locations) and is the
number of roads between those locations/intersections. Argue its correctness as well
as its asymptotic complexity. [25 marks]
[Hint: Transform the graph instead of designing increasingly complex algorithms]
Question 2
Define k-Clique to be the problem that considers a graph and an integer ,
and determines if there is a set of nodes, such that between any two nodes in ,
there is an edge in .
(a) Show that -clique problem is in NP. [5 marks]
(b) The independent set problem is to determine if there is an independent set of size
. For a graph , we say is an independent set in G if there are no edges
O(n log n + m)
n
m
G = (V, E ) k
S k S
G
k
k G = (V, E ) S ⊆ V
Page 1 of 3
between any two nodes in . We have shown that the problem of independent set is
NP-hard. Reduce the independent set problem to the -Clique problem in order to
show that -Clique is NP-hard. [15 marks]
Question 3
Consider the following algorithm for computing the second shortest path between
vertices and in an undirected graph . Either give a counter-example to show that
this algorithm is incorrect or prove its correctness. [15 marks]
Algorithm SecondShortestPath( )
Compute the first shortest path between and in
Remove all edges in from to form
Compute the shortest path between and in
Return
Question 4
The distance between two nodes in an unweighted graph is the number of edges in a
shortest path connecting them. This is also known as the geodesic distance. The
eccentricity of a node v is the maximum distance between v and any other node. The
diameter of a graph is the maximum eccentricity of any node in the graph. Give a
algorithm for this problem that returns a value that is between D/2 and D, if
the actual diameter is D? [15 marks]
Question 5
Here’s yet another minimum spanning tree algorithm:
Algorithm 1 MST(G)
1: T := G
2: while T contains a cycle do
3: Choose an arbitrary cycle C in T
4: Remove the heaviest edge in C from T
5: end while
6: return T
(a) Prove that this algorithm does indeed produce a minimum spanning tree of G. You
may assume that G is connected and that there are no two edges in G that have the
same weight. [15 marks]
Note that this question is asking for a mathematically rigorous formal proof, similar to
what you have been given in “Tutorial Solution: Question 2a Formal proof” part in the
Brightspace section on Minimum spanning trees
(b) Give an efficient way to implement this algorithm and argue its asymptotic
complexity [10marks]
S
k
k
s t G
G,s, t
P1 s t G
P1 G G′
P2 s t G′
P2
Θ(n + m)
Page 2 of 3
Bonus Question
You are a farmer and are considering purchasing an electric tractor. You have farms
at different locations in the Irish countryside, roads connecting those farms and
you want to be able to visit the farms to survey the ongoing agriculture work. On a
full charge, the electric vehicle can go km. Since you can quickly charge at any of
your farm, you are only concerned about the length of the longest road you have to
traverse and whether or not it is smaller than km. If needed, you are willing to
backtrack over a road in order to minimise the length of the longest road you will have
to traverse. Of course, you can take longer detours through your farms to go from one
farm to another as long as the maximum length of the road that you have to traverse
is less than kms. Give an time algorithm to determine if it is possible to
visit your farms in this way. Argue the correctness of your algorithm as well as its
asymptotic complexity. [20 marks]
Update: You can assume that and that the endpoints of the roads are the
farms that you have.
