1a For a worst case input of size N, Algorithm X has Θ(N) time complexity.
i) Give a full explanation of the statement above.
ii) What can you deduce about the time complexity of Algorithm X for any
input?
iii) Using the formal definition of Big Theta, show whether
7N + 5 = Θ(2N)
is true or not.
b Describe the space complexity of Quicksort, Merge Sort and Counting Sort.
c Given an array A of integers, the maximum sub-array sum problem, is to find the
value of the greatest sum
Ai + · · ·+ Aj
where [Ai, . . . , Aj] can be any (contiguous) sub-array of A. The problem can be
decomposed into subproblems as follows. If Sk is defined to be the maximum
sum of those sub-arrays that end at index k, then Sk is the greater of:
Ak
Sk−1 + Ak
Write a Θ(N) algorithm which, given an array A of N integers, calculates the
maximum sub-array sum of A. You can use either pseudocode or Java.
The three parts carry, respectively, 40%, 20%, and 40% of the marks.
c© Imperial College London 2017 Paper C580 Page 1 of 4
2a An application needs to be able to search for a given object x in a set S.
i) The average time to search the set for an object should be constant (i.e.
independent of the size of S). What type of data structure would you use to
store S? Explain your answer.
ii) Describe the insert procedure, including any steps required to ensure the
average time for search remains constant. What would be the (time)
performance of insert?
iii) Suppose the objects in S are strings, and a search should return all strings
in S that are anagrams of a string x. Describe how you would store the
data in this case, and what changes you would need to make to the search
and insert procedures.
b The following set of linear programming equations, where x1 and x4 are basic
variables and x2 and x3 are non-basic variables, represent a stage of the Simplex
algorithm. The objective of the problem is to find a solution that maximizes z.
z = 12000 − 25×2 + 350×3
x1 = 40 − 112 x2 −
1
2 x3
x4 = 250 − 512 x2 −
25
2 x3
i) What is the basic solution given by these equations?
ii) Which of the non-basic variables x2 and x3 should be selected for the next
pivot of the algorithm? Justify your answer.
iii) Which of the basic variables x1 and x4 should be selected for the next pivot
of the algorithm? Justify your answer.
The two parts carry, respectively, 70% and 30% of the marks.
c© Imperial College London 2017 Paper C580 Page 2 of 4
3a The following keys are added to an empty binary search tree in order:
4, 6, 23, 7, 2,−8, 46, 36, 5. Draw the resulting tree.
b You are implementing a binary search tree that allows duplicate keys. In such a
tree both the left and the right subtree of a node may contain other nodes with the
same key. A tree is composed of node objects that have public fields left, right
(subtrees) and key (an integer). The tree has a public field root (the root node).
i) Write a procedure ADD that adds a new node x to such a binary search tree
T. You can use either pseudocode or Java.
ii) Describe the (runtime) performance of your ADD procedure given inputs
with and without duplicate keys.
c An application searches English language “texts” (strings) for occurrences of
certain “patterns” (also strings) using the Knuth–Morris–Pratt algorithm.
i) Write out a table containing the Knuth–Morris–Pratt π function for the
pattern “amanadamanages”.
ii) How will the input text and input pattern affect the running time?
iii) If the same application was used with texts and patterns both composed
from the alphabet A = {0, 1}, how would this affect your answer to (ii)?
iv) How would the input pattern and the input text affect the running time of
the application if it used the Boyer–Moore algorithm instead? Compare the
English language and the A = {0, 1} cases.
The three parts carry, respectively, 15%, 40%, and 45% of the marks.
c© Imperial College London 2017 Paper C580 Page 3 of 4
4a Write a O(V + E) algorithm to find the number of paths from a vertex s to a
vertex t in a directed acyclic graph G = (V, E). HINT — the number of paths
from vertex u to t is the sum of:
• 1 for each edge (u, t), plus
• the number of paths from v to t for each other edge (u, v).
Your algorithm can be in pseudocode or Java. You can assume the existence of a
function G.adj(u) that returns the list of vertices adjacent to vertex u.
b i) Use Kruskal’s algorithm to find a minimum spanning tree (MST) for the
graph below. List the edges that are added, in the order they are added, and
give the total weight of the MST. If you have a choice of which edge to
add, choose the edge (u, v) with the (alphabetically) lowest value for u.
ii) Consider this statement: if a graph G contains a cycle C, and C contains
an edge e whose weight is less than the weight of all other edges in C, then
e is in an MST for G. Is this true or false? HINT — consider how Kruskal’s
algorithm would contruct the MST for relevant examples.
c To find the shortest paths containing at most Q edges from a vertex s to all other
vertices of a directed graph G with positively weighted edges, you are told to
modify either the Dijkstra or the Bellman–Ford algorithm. You limit the main
loop to run exactly Q times. In iteration i, your modified RELAX procedure:
1: procedure RELAX((u, v), i)
2: if dist[u][i− 1] + w(u, v) < dist[v][i] then
3: dist[v][i] = dist[u][i− 1] + w(u, v)
where (u, v) is an edge in G, is used to update dist[v][i], the distance to vertex v
using at most i edges, after initialising this to dist[v][i− 1]. Would you choose
the Dijkstra or the Bellman–Ford algorithm to adapt, and why?
The three parts carry, respectively, 40%, 35%, and 25% of the marks.
c© Imperial College London 2017 Paper C580 Page 4 of 4
C580-1516
C580-201516-questions