Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
1

School of Information Technology and Electrical Engineering
EXAMINATION
Semester Two Final Examination, 2020
COMP3506/COMP7505 Algorithms and Data Structures
This paper is for all students.

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
2
Question 1 (2 marks)
What is the maximum possible number of external nodes in a binary tree with height
4? Give a brief description by drawing a resulting tree.

Question 2 (1 mark)
Consider the following Java program, containing a recursive method. When the class
ContainsRecursion is run, the final line of output will be:

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
3
Question 3 (4 marks)
a) Given two algorithms, A with O(n) time complexity, and B with Θ(n logn) time
complexity, testing shows that algorithm B is faster than algorithm A in practice
for all datasets tested. Give two possible reasons why this may be. (2 marks)

b) Given two algorithms for performing a task, is it ever reasonable to use the
algorithm with worse asymptotic performance? Why or why not? (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
4
Question 4 (2 marks)
Consider the following recurrences:
R1(n) = 4 R1(n/2) + O(1)
R2(n) = 2 R2(n/4) + O(1)
Explain which one is asymptotically faster and why? (2 marks)

Question 5 (2 marks)
Draw a table to represent the “last occurrence” function for the pattern P="baccarat",
which is used as part of the Boyer-Moore pattern matching algorithm.

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
5
Question 6 (4 marks)
A splay tree is populated by inserting into an empty tree the keys: 4, 15, 8, 16, 42, and
23, in that order.
a) Draw the final tree. No need to include the external leaves in the drawing. (2
marks)

b) What is the order that nodes are visited during a post-order traversal of the
resulting tree? (1 mark)

c) Draw a different splay tree with the same post order traversal. (1 mark)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
6
Question 7 (2 marks)
We defined a hash function h(s) = s.size(), for a hash table which stores a set of
strings.

a) Explain why h(s) is not a good hash function. Note: size() returns the length of
the string. (1 mark)

b) Suggest an alternative hash function or technique that would perform more
suitably (and why?). (1 mark)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
7
Question 8 (4 marks)
Arrays store a set of values by index using O(n) space, where n is the largest index in
use. In some cases, most indices of the array are null, wasting space; such arrays are
called sparse arrays. In other words, the number of non-default values stored m, is
much smaller than the largest index n.
a) Describe how you would efficiently implement a sparse array using a hash
table. What would be the worst-case time complexity of standard array
operations (insert, delete (moving indices of elements later in the array after
deletion), and search an item) in Big-O notation, if we implement sparse arrays
using hash tables? (2 marks)

b) Describe how you would efficiently implement a sparse array using a linked list.
What would be the worst-case time complexity of standard array operations in
Big-O notation, if we implement sparse arrays using linked lists? (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
8
Question 9 (2 marks)
Below is a Huffman tree generated from the exact frequencies of the text: "this is an
example of a huffman tree"

Using the Huffman tree above, determine the binary code and count the number of
bits required to transmit the text “fill pool” (do not forget the space separating the
words). Note: Left branches represented a 0 bit and right branches represent a 1 bit.
CODE=
#BITS=

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
9
Question 10 (5 marks)
For each of the following scenarios, suggest an efficient and suitable sorting algorithm
(out of the ones we learned in this course), and explain why you chose it. Note: n
potentially is very large.
(a) We have an array consisting of n objects in random order. The objects are
comparable, and not necessarily numbers. (1 mark)


(b) We have an array consisting of n objects. The objects are comparable. Apart from
d items (d< log2n) that are in random positions in this array, all the other items are
in sorted order. (2 marks)

(c) We have an array consisting of n random integers in the range of 0 to d, with d<
log2n. (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
10
Question 11 (4 marks)
a) Given a semi-balanced binary tree with n nodes, where the number of leaves
in the corresponding left and right subtrees differs at most by one. Explain the
worst-case height of the tree. Note: Write the Big-O with respect to the number
of nodes (n). (2 marks)

b) Given a semi-balanced binary tree with n nodes, where the number of nodes in
the left subtree is at most twice the number of nodes in the corresponding right
subtree. Explain the worst-case height of the tree. Note: Write the Big-O with
respect to the number of nodes (n). (2 marks)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
11
Question 12 (4 marks)
Given an unweighted graph G with n vertices and the adjacency matrix A:
a) Given a positive integer k, propose an algorithm (give a pseudo-code or
explain in words) to calculate the number of walks (vertices/edges can
be revisited) consisting of exactly k number of edges between vertices i
and j. Your algorithm should return 0 if there are no walks of length k. (3
marks)

b) What is the worst-case time complexity of your proposed algorithm in terms of
n and k? and explain why. (1 mark)

Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures
12
Question 13 (4 marks)
Work out the most efficient Big-O time complexity of finding pth smallest element in a
BST with m elements. Hint: The Big-O will be in terms of m and p. Describe in words
your proposed algorithm.


End of Examination