Semester Two Final Examinations, 2019 COMP3506/COMP7505 Algorithms and Data Structures
Page 1 of 6



This exam paper must not be removed from the venue


School of Information Technology and Electrical Engineering
EXAMINATION
Semester Two Final Examinations, 2019
COMP3506/COMP7505 Algorithms and Data Structures
This paper is for St Lucia Campus students.
Examination Duration: 120 minutes
Reading Time: 10 minutes
Exam Conditions:
This is a Central Examination
This is a Closed Book Examination - specified materials permitted
During reading time - write only on the rough paper provided
This examination paper will be released to the Library
Materials Permitted In The Exam Venue:
(No electronic aids are permitted e.g. laptops, phones)
Calculators - Casio FX82 series or UQ approved (labelled)
One A4 sheet of handwritten or typed notes double sided is permitted
Materials To Be Supplied To Students:
1 x 14-Page Answer Booklet
Instructions To Students:
Additional exam materials (eg. answer booklets, rough paper) will be
provided upon request.

All questions are to be answered in the provided answer booklet.
Venue ____________________
Seat Number ________
Student Number |__|__|__|__|__|__|__|__|
Family Name _____________________
First Name _____________________
For Examiner Use Only
Question Mark





















Total ________
Semester Two Final Examinations, 2019 COMP3506/COMP7505 Algorithms and Data Structures
Page 2 of 6
Question 1 (10 marks)
a) Describe the running time (in big-O notation) of the following algorithm in terms
of input parameter n. The given bound should be as tight and as simple as
possible. Briefly explain your answer.
Algorithm: getStuffDone(n)
i ← 1
m ← 1
while i < n do
i ← i + 1
m ← m + m
for j ← 1 to m do
... // These statements run in constant time
return
(2 marks)
b) Describe the worst-case time complexity (in big-O notation) of the following
algorithm, assuming that the parameter list is (well) implemented using an array.
The given bound should be as tight and as simple as possible. Briefly explain your
answer.
Algorithm: removeEven(list, n)
Input: a list containing n integer elements
Output: removes all of the even integers from the given list
i ← 0
while i < list.size() do
if (list.get(i) % 2) = 0 then
list.remove(i)
else
i ← i + 1
return
(2 marks)
c) During her routine maintenance of a large software system, Karen notices that a
Θ(n2) algorithm is being used in a place where an Θ(n log n) algorithm could be
used instead. Will replacing the existing algorithm with the Θ(n log n) make the
system run faster? Why or why not? What should Karen consider before she
invests her time in updating the code?
(2 marks)

d) Determine whether the following statements are true or false for all possible
functions f(n), g(n), and h(n). If true, explain why using the mathematical
definitions of big-Ω and big-Θ. If false, provide a counterexample.

i) If f(n) is Ω(g(n)) and g(n) is Ω(h(n)), then f(n) is Ω(h(n))
(2 marks)
ii) If f(n) is Ω(g(n)) and g(n) is Ω(f(n)), then f(n) is Θ(g(n))
(2 marks)
Semester Two Final Examinations, 2019 COMP3506/COMP7505 Algorithms and Data Structures
Page 3 of 6
Question 2 (8 marks)
Consider a Point class (shown below), representing an (x, y, z) coordinate tuple on a
three-dimensional Cartesian plane. Assume x, y, and z are all 64-bit long integers and
have public getter methods.
public class Point implements Comparable {
private long x;
private long y;
private long z;
public Point(long x, long y, long z) {
this.x = x;
this.y = y;
this.z = z;
}

public int compareTo(Point other) {
if (this.x == other.x && this.y == other.y) {
return Long.compare(this.z, other.z);
} else if (this.x == other.x) {
return Long.compare(this.y, other.y);
} else {
return Long.compare(this.x, other.x);
}
}
}

a) What is the best-case run-time performance of sorting n points using any
comparison sort? Explain how this can be determined.
(2 marks)

b) An alternative approach to a comparison sort would be to represent points as the
concatenation of the bits of the x, y, and z coordinates (that is, each point is a
single 192-bit cell in memory). We would then be able to use radix-sort on the
binary representation of the point (which has O(n) time complexity). Explain why
this approach to sorting may not be a good idea.
(2 marks)

c) Design an algorithm that takes two large arrays of Point objects and determines if
the first array contains a point that is also in the second array. Your solution
should be as fast as possible. You should write the pseudocode of your solution
and explain what changes need to be made to the Point class (if any are required).
Briefly explain the worst-case time and memory complexity of your solution.
(4 marks)
Semester Two Final Examinations, 2019 COMP3506/COMP7505 Algorithms and Data Structures
Page 4 of 6
Question 3 (6 marks)
a) Provide an example scenario where it would be appropriate to use a hash table as the
implementation for a map. Explain why a hash table would be the most appropriate
implementation for the scenario.
(2 marks)
b) Provide an example scenario where it would be appropriate to use a splay tree as the
implementation for a map. Explain why a splay tree would be the most appropriate
implementation for the scenario.
(2 marks)
c) Provide an example scenario where it would be appropriate to use a B-tree as the
implementation for a map. Explain why a B-tree would be the most appropriate
implementation for the scenario.
(2 marks)

Question 4 (7 marks)
a) Draw the 2-4 tree below after inserting the key 10. Draw all intermediate states of
the tree.

(3 marks)
b) James has a sorted map implemented as a red-black tree. Henry claims that
reimplementing the data structure as an AVL tree would make retrieving keys of the
map faster. However, James thinks that there would be no performance benefit as
both implementations have O(log n) runtime efficiency for searching. Who is
correct? Explain your answer.
(2 marks)
c) During lectures and tutorials, it was mentioned that heaps can be stored as arrays to
save space. Explain why we don't do the same for binary search trees.
(2 marks)
Semester Two Final Examinations, 2019 COMP3506/COMP7505 Algorithms and Data Structures
Page 5 of 6
Question 5 (9 marks)
a) Draw a Standard Trie for the following set of strings: {ab, bb, bab, baa, cab}
(2 marks)
b) Give an accurate description of the worst-case time complexity of searching for a
word of m characters in a Standard Trie containing a set S of r strings of total size
n, from an alphabet of size d. Assume that the children of each node in the
Standard Trie are stored as a linked list. Express your answer in asymptotic
notation using an appropriate combination of the parameters m, r, n and d. Make
the bounds as tight as possible and simplify your answer as much as possible.
Briefly explain your answer.
(2 marks)
c) The Knuth-Morris-Pratt algorithm pre-processes a pattern P to build a failure
function F. Compute the table of the failure function F for the pattern
P=”KOKKOLA”.
(2 marks)

d) Use Huffman’s algorithm to construct a Huffman tree that minimises the size of
the encoding of the word “KOKKOLA”. Show all intermediate states of the
priority queue. What is the number of bits needed to encode the string
“KOKKOLA” using the Huffman tree that you constructed?
(3 marks)
Question 6 (10 marks)
Consider the following DAG:


a) List the order that nodes would be visited in a breadth-first traversal of this graph
starting at vertex H.
(1 mark)
b) Give a topological ordering of this graph, or explain why no ordering exists.
(1 mark)
Semester Two Final Examinations, 2019 COMP3506/COMP7505 Algorithms and Data Structures
Page 6 of 6
c) Consider two vertices in an arbitrary undirected and weighted graph. Is the
shortest path between two vertices guaranteed to be a part of the graph's MST? If
so, explain why. If not, provide a counterexample.
(2 marks)

d) Consider the following variation of Dijkstra's algorithm, where the relaxation step
is performed twice (instead of once) per vertex in the priority queue.

Algorithm: shortestPath(n)
PQ ← new heap-based priority queue
{ initialize all distances to infinity }
while !PQ.isEmpty() do
v ← PQ.removeMin()
for all e in G.incidentEdges(v) do
{ relax e }
for all e in G.incidentEdges(v) do
{ relax e }

Does the additional relaxation step affect the behavior of the algorithm? Explain
why/why not.
(3 marks)
e) Suppose you have a graph like the one below. The dots signify some part of the
graph that you don’t know exactly, not a straight link. You know however, that
there are many paths from the start to the goal. You also know that they tend to be
rather long. Suppose that you want to implement a program that searches for a
path and returns the first one it can find. You have no need for finding the optimal
path in any sense, just any path will do.

Would you want to use BFS or DFS as the basis for your program? Justify your
answer. Describe a tradeoff of using your chosen algorithm for this specific
scenario.

(3 marks)


END OF EXAMINATION


欢迎咨询51作业君