FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
UNIVERSITY OF EDINBURGH
COLLEGE OF SCIENCE AND ENGINEERING
SCHOOL OF INFORMATICS
INFORMATICS 2: INTRODUCTION TO ALGORITHMS AND
DATA STRUCTURES
Inf2-IADS Sample Exam (2 hours)
(published 30th March 2021, for individual practice)
Thursday 1 st April 2021
INSTRUCTIONS TO CANDIDATES
This is an Open Book exam.
You have 2 hours to complete all questions.
1. Answer all five questions in Part A, and two out of three questions in
Part B. Each question in Part A is worth 10% of the total exam mark;
each question in Part B is worth 25%.
2. Use a single script book for all questions.
3. Calculators may be used in this exam.
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
PART A:
1. (a) Illustrate the application of MergeSort to the list [3,9,8,2,4,1,6,5], by means
of a diagram showing the recursive call structure. You should show both
the argument passed to MergeSort on each call and the result returned by
each call as the lists are recombined. [5 marks ]
(b) Suppose we restrict our use of MergeSort to lists of length 2m for various
natural numbers m. Give Θ-estimates in terms of m for the best-case, worst-
case and average-case number of comparisons performed by MergeSort on
such lists. You need not justify your answers. [3 marks ]
(c) Give a Θ-estimate, again in terms of m, for the amount of memory used by
MergeSort on lists of length 2m, assuming a version of MergeSort that is as
space-efficient as possible. Briefly justify your answer. [2 marks ]
2. Consider functions f1(n) = (lg(n))
lg(n), f2(n) = n
lg(n), f3(n) = n
2 and f4(n) = n.
(a) There is exactly one i ∈ {1, 2, 3, 4} such that
fi(n) ∈ O(fj(n)) for all j = {1, 2, 3, 4}.
(ie, fi is “big-O” of all the other fj).
State which function is fi, giving informal justification of fi(n) ∈ O(fj(n))
for each j 6= i. [5 marks ]
(b) There is also exactly one k ∈ {1, 2, 3, 4} such that
fk(n) ∈ Ω(fj(n)) for all j = {1, 2, 3, 4}.
(ie, fk is “big-Ω” of all the other fj).
State which function is fk, and rigorously justify fk = Ω(fj) for each j 6= k. [5 marks ]
3. (a) Suppose you require a data structure for storing sets of up to 10,000 integers,
supporting membership testing and insertion. You are trying to decide
between two implementation schemes:
• a bucket-array hash table of size 2,000, using chaining to resolve colli-
sions,
• a red-black tree implementation, storing integers at the internal nodes.
Discuss the relative advantages and disadvantages of each scheme. Your
discussion should be as specific as possible, including rough numerical es-
timates of relevant quantities based on your understanding of these data
structures. [6 marks ]
Page 1 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
(b) The following red-black tree is a possible representation of the set {2, 3, 4}.
The letters R and B show whether nodes are red or black. We have omitted
the trivial leaf nodes.
With the help of diagrams, explain the steps that occur when the new ele-
ment 1 is inserted into this set. [4 marks ]
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:
Inc():
i = 0
while iD[i] = 0
i = i+1
if iD[i] = D[i]+1
(a) Give a Θ-estimate for best case runtime of Inc. Give an example, parametric
in n, illustrating best-case behaviour (you need not prove that it does so). [2 marks ]
(b) Give a Θ-estimate for worst case runtime of Inc. Give an example, para-
metric in n, illustrating worst-case behaviour (again without proof). [2 marks ]
(c) Suppose now that we apply the Inc operation 10n times (so that the counter
returns to its starting state). Give a Θ-estimate for the total runtime for
this sequence of operations, and one for the amortized average cost per Inc
operation. Justify your answer by means of a mathematical analysis of the
total runtime. [6 marks ]
Page 2 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
5. In class we gave details of a polynomial-time reduction from the 3-SAT problem
to the Independent Set problem. In this question we consider strategies for
attempting a reduction in the opposite direction (from Independent Set to
3-SAT).
(a) Consider a 2-literal clause C = (`1 ∨ `2) and show how we can design a [2 marks ]
pair of 3-literal clauses C ′ and C ′′ such that C is true under the identical
conditions as C ′ ∧ C ′′.
(you may introduce “dummy variables” if this helps)
(b) Consider a k-literal clause C = (`1 ∨ . . . ∨ `k) for k ≥ 4 and show how we [2 marks ]
can design a sequence of 3-literal clauses C(1), . . . , C(k − 2) such that C is
true under the identical conditions as C(1) ∧ . . . ∧ C(k − 2).
(you may introduce “dummy variables” if this helps)
(c) Suppose now that we are given a graph G = (V,E) and we are interested
in whether G has an Independent Set of size ≥ 4. Show how to construct a
3-CNF formula Φ with a polynomial number of clauses, such that G has an
independent set of size ≥ 4 if and only if Φ is satisfiable. [4 marks ]
[Hint: You will need to add clauses to capture the “no two adjacent vertices”
constraints, and other clauses to encode the “at least 4 vertices” constraint
(for this, you will need to start with a clause for each set of vertices of size
|V | − 3). You may make use of (a) and (b).]
(d) Suppose you were asked to generalise the reduction in (c) to the case where
we were interested in an Independent Set of size ≥ h, for an arbitrary h.
Would the approach of (c) still give a polynomial-time reduction? [2 marks ]
Page 3 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
PART B:
1. (a) Consider the Heap below, and suppose that we carry out the following oper-
ations in sequence: Heap-Extract-Max(), Max-Heap-Insert(17), Heap-Extract-
Max(), Max-Heap-Insert(7), Max-Heap-Insert(19).
What is the order of the (remaining) elements in the Heap array after this [5 marks ]
sequence of operations has been performed?
(b) We will now consider Priority Queues and their implementation. Recall
that Priority Queues support the operations maxElement, removeMax and
insertItem(k, e). These can be directly implemented by a Heap, via the
methods Heap-Maximum, Heap-Extract-Max, and Max-Heap-Insert (under the
assumption that Heap cells now contain an element e as well as a key k).
Suppose that we would like to implement an data structure Extended Queue
which offers the extra method findElement(k) (for a given key value k), as
well as the standard operations MaxElement, removeMax, insertItem(k, e).
i. Describe an algorithm for implementing findElement(k) on a Heap data
structure. State the worst-case running time of your algorithm as a Θ(·)
expression, giving justification. [5 marks ]
ii. Explain briefly how you could implement maxElement and removeMax
on a Red-Black tree. State the worst-case running time you expect to
get for these methods in Θ(·), justifying your answer. [5 marks ]
iii. Compare and contrast the advantages of using a Heap for the Extended
Queue implementation against using a Red-Black tree. [5 marks ]
(c) Finally, reconsider the Heap realisation of Extended Queue, and a new
method called UpdateKey(o, k′), where the required action is to update the
key value of object o to become k′, maintaining the Heap property. Note o
is an object reference to some existing Heap cell (k, e).
Give details of how UpdateKey(o, k′) can be implemented in O(lg(n)) time [5 marks ]
on a Heap, with reference to known Heap methods if this is helpful.
Page 4 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
2. In English, there are two common ways of forming a list of items. One is to insert
and between all adjacent items. The other is to insert a comma between adjacent
items, except for the last two where and is inserted:
cows and pigs and goats and sheep
cows , pigs , goats and sheep
The following context-free grammar generates lists of both these kinds. The start
symbol is L. The non-terminals AL, CAL, CL respectively stand for ‘and-list’,
‘comma-and-list’, ‘comma-list’.
L → AL | CAL
AL → I | I and AL
AL → CL and I
CL → I | I , CL
I → cows | pigs | goats | sheep | · · ·
(a) Even though our grammar is not in Chomsky Normal Form, it is still possible
to construct CYK-style parse charts for it. Draw up and fill out a CYK-style
chart for the following phrase as a 5× 5 matrix:
cows , goats and sheep
For all possible substrings, your chart should record all non-terminals that
can generate the substring — not only the ones that contribute to a parse
of the complete phrase. (On this occasion, please do not include pointers or
other information showing the origin of table entries.) [7 marks ]
(b) Is the above context-free grammar ambiguous? Justify your answer. [2 marks ]
For the remainder of this question, we shall discard the lexical rules with left-
hand-side I, and treat I simply as a terminal symbol along with , and and.
(c) Explain why our grammar is not LL(1). Your explanation should present a
specific example of an input string and identify the point at which the LL(1)
parsing algorithm is bound to fail. [4 marks ]
(d) The following is a parse table for an LL(1) grammar equivalent to the one
above. The start symbol is again L, and the terminals, non-terminals and
productions can be read from the table. (For example, the top left entry
tells us that there is a production L → I Rest.)
I and , $
L I Rest
Rest and I ATail , I CTail and I
ATail and I ATail
CTail , I ATail
Page 5 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
Show the execution of the LL(1) parsing algorithm on the input string:
I , I and I
Present your solution as a table with a row for each step of the computation,
as in lectures. The three columns should be ‘Operation applied’, ‘Remaining
input’ and ‘Stack state’. [10 marks ]
(e) Briefly discuss whether LL(1) grammars are in general an appropriate tech-
nology for natural language processing. [2 marks ]
Page 6 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
3. (a) Hamiltonian Cycle: Given an undirected input graph G = (V,E), de-
termine whether there is some cycle of length n in G (a cycle which visits
each vertex exactly once).
Consider the brute-force approach to finding a Hamiltonian Cycle, where we
choose some specific starting vertex s, and iteratively build a path p = s . . . v
from that point: at each step, we consider the most recent vertex v and add
any (v, v′) ∈ E such that v′ is not yet an element of the path, updating
p′ ← p, v′. If at any point the path includes all vertices of V , we check that
(v, s) ∈ E, and if this succeeds, then we have found a Hamiltonian cycle;
otherwise we need to backtrack.
When following this na¨ıve process, it is likely that we arrive at a situation
where we cannot find any (v, v′) ∈ E such that v′ /∈ p; then we need to
backtrack and undo the prior edge added to the current path.
Assume we explore the feasible next vertices in order of increasing index.
Adapt the depth-first search algorithm to develop pseudocode for this brute- [7 marks ]
force search for a Hamiltonian cycle.
(b) Consider an unweighted input graph G = (V,E) where V = {0, . . . , n − 1}
with edge set E defined by a complete graph on the nodes {0, 1, . . . , n
2
− 1},
plus a linear path connecting the nodes n
2
, n
2
+ 1, . . . , n− 1, 0, and the extra
edge (1, n
2
).
This graph CLEARLY does contain a Hamiltonian cycle. Show that the [8 marks ]
brute-force search described in (a), started from node 0, and with the feasible
next vertices explored in order of increasing index, will take at least Ω(2n/2)
time before finding a Hamiltonian cycle.
0
1
2
3
n
2 − 1
n
2
n− 1
n− 2
n
2 + 1
(c) Now we consider a related decision problem on graphs, the Travelling
Salesman problem (TSP), this problem defined on weighted complete
graphs.
Page 7 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
Travelling Salesman: Given a natural number k, and an undirected
input graph G = (V,E) such that (u, v) ∈ E for every u, v 6= u ∈ V
(complete graph) with a weight function w : E → R+ on the edges of G,
determine whether there is a simple cycle containing every vertex (exactly
once), with total weight at most k.
We will consider the undirected graph G = (V,E) from part (b), and expand
this to a complete graph G′ = (V,E ′) with weight function w by setting
w(i, j) =
{
1 for every edge (i, j) ∈ E,
n for every (i, j) such that i 6= j, (i, j) /∈ E
i. Specify a value of k such that a tour of G′ of value ≤ k corresponds to [2 marks ]
a Hamiltonian cycle of G. You do not need to justify your answer.
ii. Suppose we run the Greedy algorithm for TSP on the weighted graph G′ [4 marks ]
starting from 0, “breaking ties” between adjacent edges of equal weight
in favour of lower-indexed vertices. Will the tour constructed correspond
to a Hamiltonian cycle of G or not? Justify your answer.
iii. Suppose that we start with the identity permutation (pi(i) = i) as our
initial tour of G′, and then we run the SwapHeuristic method. What
will be the consequence of running this method? Justify your answer. [4 marks ]
Page 8 of 8



































































D[i] = 0
i = i+1
if iD[i] = D[i]+1
(a) Give a Θ-estimate for best case runtime of Inc. Give an example, parametric
in n, illustrating best-case behaviour (you need not prove that it does so). [2 marks ]
(b) Give a Θ-estimate for worst case runtime of Inc. Give an example, para-
metric in n, illustrating worst-case behaviour (again without proof). [2 marks ]
(c) Suppose now that we apply the Inc operation 10n times (so that the counter
returns to its starting state). Give a Θ-estimate for the total runtime for
this sequence of operations, and one for the amortized average cost per Inc
operation. Justify your answer by means of a mathematical analysis of the
total runtime. [6 marks ]
Page 2 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
5. In class we gave details of a polynomial-time reduction from the 3-SAT problem
to the Independent Set problem. In this question we consider strategies for
attempting a reduction in the opposite direction (from Independent Set to
3-SAT).
(a) Consider a 2-literal clause C = (`1 ∨ `2) and show how we can design a [2 marks ]
pair of 3-literal clauses C ′ and C ′′ such that C is true under the identical
conditions as C ′ ∧ C ′′.
(you may introduce “dummy variables” if this helps)
(b) Consider a k-literal clause C = (`1 ∨ . . . ∨ `k) for k ≥ 4 and show how we [2 marks ]
can design a sequence of 3-literal clauses C(1), . . . , C(k − 2) such that C is
true under the identical conditions as C(1) ∧ . . . ∧ C(k − 2).
(you may introduce “dummy variables” if this helps)
(c) Suppose now that we are given a graph G = (V,E) and we are interested
in whether G has an Independent Set of size ≥ 4. Show how to construct a
3-CNF formula Φ with a polynomial number of clauses, such that G has an
independent set of size ≥ 4 if and only if Φ is satisfiable. [4 marks ]
[Hint: You will need to add clauses to capture the “no two adjacent vertices”
constraints, and other clauses to encode the “at least 4 vertices” constraint
(for this, you will need to start with a clause for each set of vertices of size
|V | − 3). You may make use of (a) and (b).]
(d) Suppose you were asked to generalise the reduction in (c) to the case where
we were interested in an Independent Set of size ≥ h, for an arbitrary h.
Would the approach of (c) still give a polynomial-time reduction? [2 marks ]
Page 3 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
PART B:
1. (a) Consider the Heap below, and suppose that we carry out the following oper-
ations in sequence: Heap-Extract-Max(), Max-Heap-Insert(17), Heap-Extract-
Max(), Max-Heap-Insert(7), Max-Heap-Insert(19).
What is the order of the (remaining) elements in the Heap array after this [5 marks ]
sequence of operations has been performed?
(b) We will now consider Priority Queues and their implementation. Recall
that Priority Queues support the operations maxElement, removeMax and
insertItem(k, e). These can be directly implemented by a Heap, via the
methods Heap-Maximum, Heap-Extract-Max, and Max-Heap-Insert (under the
assumption that Heap cells now contain an element e as well as a key k).
Suppose that we would like to implement an data structure Extended Queue
which offers the extra method findElement(k) (for a given key value k), as
well as the standard operations MaxElement, removeMax, insertItem(k, e).
i. Describe an algorithm for implementing findElement(k) on a Heap data
structure. State the worst-case running time of your algorithm as a Θ(·)
expression, giving justification. [5 marks ]
ii. Explain briefly how you could implement maxElement and removeMax
on a Red-Black tree. State the worst-case running time you expect to
get for these methods in Θ(·), justifying your answer. [5 marks ]
iii. Compare and contrast the advantages of using a Heap for the Extended
Queue implementation against using a Red-Black tree. [5 marks ]
(c) Finally, reconsider the Heap realisation of Extended Queue, and a new
method called UpdateKey(o, k′), where the required action is to update the
key value of object o to become k′, maintaining the Heap property. Note o
is an object reference to some existing Heap cell (k, e).
Give details of how UpdateKey(o, k′) can be implemented in O(lg(n)) time [5 marks ]
on a Heap, with reference to known Heap methods if this is helpful.
Page 4 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
2. In English, there are two common ways of forming a list of items. One is to insert
and between all adjacent items. The other is to insert a comma between adjacent
items, except for the last two where and is inserted:
cows and pigs and goats and sheep
cows , pigs , goats and sheep
The following context-free grammar generates lists of both these kinds. The start
symbol is L. The non-terminals AL, CAL, CL respectively stand for ‘and-list’,
‘comma-and-list’, ‘comma-list’.
L → AL | CAL
AL → I | I and AL
AL → CL and I
CL → I | I , CL
I → cows | pigs | goats | sheep | · · ·
(a) Even though our grammar is not in Chomsky Normal Form, it is still possible
to construct CYK-style parse charts for it. Draw up and fill out a CYK-style
chart for the following phrase as a 5× 5 matrix:
cows , goats and sheep
For all possible substrings, your chart should record all non-terminals that
can generate the substring — not only the ones that contribute to a parse
of the complete phrase. (On this occasion, please do not include pointers or
other information showing the origin of table entries.) [7 marks ]
(b) Is the above context-free grammar ambiguous? Justify your answer. [2 marks ]
For the remainder of this question, we shall discard the lexical rules with left-
hand-side I, and treat I simply as a terminal symbol along with , and and.
(c) Explain why our grammar is not LL(1). Your explanation should present a
specific example of an input string and identify the point at which the LL(1)
parsing algorithm is bound to fail. [4 marks ]
(d) The following is a parse table for an LL(1) grammar equivalent to the one
above. The start symbol is again L, and the terminals, non-terminals and
productions can be read from the table. (For example, the top left entry
tells us that there is a production L → I Rest.)
I and , $
L I Rest
Rest and I ATail , I CTail and I
ATail and I ATail
CTail , I ATail
Page 5 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
Show the execution of the LL(1) parsing algorithm on the input string:
I , I and I
Present your solution as a table with a row for each step of the computation,
as in lectures. The three columns should be ‘Operation applied’, ‘Remaining
input’ and ‘Stack state’. [10 marks ]
(e) Briefly discuss whether LL(1) grammars are in general an appropriate tech-
nology for natural language processing. [2 marks ]
Page 6 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
3. (a) Hamiltonian Cycle: Given an undirected input graph G = (V,E), de-
termine whether there is some cycle of length n in G (a cycle which visits
each vertex exactly once).
Consider the brute-force approach to finding a Hamiltonian Cycle, where we
choose some specific starting vertex s, and iteratively build a path p = s . . . v
from that point: at each step, we consider the most recent vertex v and add
any (v, v′) ∈ E such that v′ is not yet an element of the path, updating
p′ ← p, v′. If at any point the path includes all vertices of V , we check that
(v, s) ∈ E, and if this succeeds, then we have found a Hamiltonian cycle;
otherwise we need to backtrack.
When following this na¨ıve process, it is likely that we arrive at a situation
where we cannot find any (v, v′) ∈ E such that v′ /∈ p; then we need to
backtrack and undo the prior edge added to the current path.
Assume we explore the feasible next vertices in order of increasing index.
Adapt the depth-first search algorithm to develop pseudocode for this brute- [7 marks ]
force search for a Hamiltonian cycle.
(b) Consider an unweighted input graph G = (V,E) where V = {0, . . . , n − 1}
with edge set E defined by a complete graph on the nodes {0, 1, . . . , n
2
− 1},
plus a linear path connecting the nodes n
2
, n
2
+ 1, . . . , n− 1, 0, and the extra
edge (1, n
2
).
This graph CLEARLY does contain a Hamiltonian cycle. Show that the [8 marks ]
brute-force search described in (a), started from node 0, and with the feasible
next vertices explored in order of increasing index, will take at least Ω(2n/2)
time before finding a Hamiltonian cycle.
0
1
2
3
n
2 − 1
n
2
n− 1
n− 2
n
2 + 1
(c) Now we consider a related decision problem on graphs, the Travelling
Salesman problem (TSP), this problem defined on weighted complete
graphs.
Page 7 of 8
FOR INTERNAL SCRUTINY (date of this version: 1/4/2021)
Travelling Salesman: Given a natural number k, and an undirected
input graph G = (V,E) such that (u, v) ∈ E for every u, v 6= u ∈ V
(complete graph) with a weight function w : E → R+ on the edges of G,
determine whether there is a simple cycle containing every vertex (exactly
once), with total weight at most k.
We will consider the undirected graph G = (V,E) from part (b), and expand
this to a complete graph G′ = (V,E ′) with weight function w by setting
w(i, j) =
{
1 for every edge (i, j) ∈ E,
n for every (i, j) such that i 6= j, (i, j) /∈ E
i. Specify a value of k such that a tour of G′ of value ≤ k corresponds to [2 marks ]
a Hamiltonian cycle of G. You do not need to justify your answer.
ii. Suppose we run the Greedy algorithm for TSP on the weighted graph G′ [4 marks ]
starting from 0, “breaking ties” between adjacent edges of equal weight
in favour of lower-indexed vertices. Will the tour constructed correspond
to a Hamiltonian cycle of G or not? Justify your answer.
iii. Suppose that we start with the identity permutation (pi(i) = i) as our
initial tour of G′, and then we run the SwapHeuristic method. What
will be the consequence of running this method? Justify your answer. [4 marks ]
Page 8 of 8

学霸联盟