COMP20007 Design of Algorithms Semester 1, 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP20007 Design of Algorithms
Semester 1, 2022
Sample Exam
Question 1 [10 Marks]
(a) Perform mergesort on the array ┌ 25.23.17.29.7.16.33.21┐, showing the result after each
recursive call. Indicate which range of elements are being considered during each recursive call by outlining those elements.
[2 marks]
(b) Which two operations must a queue implement? Give the name and a brief description of
these two operations.
[2 marks]
(c) Describe how you would implement a queue using a singly linked list to ensure that both of these operations run in ò(1) time.
[1 mark]
(d) Insert the characters C, O, M, P, L, E, X, I, T, Y into an initially empty 2-3 tree. You must show the state of the 2-3 tree after every insertion.
[2 marks]
(e) Describe which two rotations must be done to balance the following tree? Give the node and
the direction of the rotation (left or right).
[1 mark]
I
C M
A D Y
N
(f) Describe how performing a right rotation of the tree above would change the in-order traversal
of the tree. You should give the resultant in-order traversal as part of your answer.
[2 marks]
Question 2 [9 Marks]
(a) Demonstrate how to search for the pattern EAR in the text STRINGSEARCH using Horspool’s
algorithm. How many comparisons were made?
[1 mark]
(b) A pair of strings are anagrams of each other if they contain the exact same letters, for example
"DESSERTS" and "STRESSED" are anagrams.
Write an algorithm which takes as input two strings, 夺 and ╱ , and determines whether or not they are anagrams. Your algorithm should run in ò(n) time where n := max●(夺(.(╱ (e. You may assume that all characters in 夺 and ╱ are uppercase alphabetic characters.
[4 marks]
(c) Write an algorithm which takes as input an array of n strings, of length no longer than m characters long, and outputs the largest set of strings which are all anagrams of each other.
For example, given the array ┌ "ABC", "ABBA", "CAB", "BABA", "CBA", "BAC", "BAD" ┐ your algorithm would output "ABC", "CAB", "CBA", "BAC" (not necessarily in that order).
Your algorithm must run in ò(mn log n) time. You may again assume that all characters are uppercase alphabetic characters.
[4 marks]
Question 3 [8 Marks]
(a) For each of the following, explain whether f (n) · ò(g(n)), f (n) · Ω(g(n)), or f (n) ·
Θ(g(n)). Only solutions with sufficient justification will be awarded marks.
(i) f (n) = log(n) and g(n) = log(log(n))
(ii) f (n) = log3 (n) and g(n) = log2 (n2 )
(iii) f (n) = 100}n + 0.01n2 + 0.001n3 and g(n) = n
(iv) f (n) = log n + n2 and g(n) = n
[4 marks]
(b) Solve, using the method of repeated substitutions, the following recurrence relation. You
must give a closed form expression and a Big-Theta bound for ╱ (n).
╱ (n) = 2╱ (n - 1) + 7. ╱ (2) = 0
[2 marks]
(c) Consider the following sorting algorithm:
function CHuNKSoRT(![0...n - 1])
if n == 2 and ![0] 女 ![1] then
swap ![0] and ![1]
else
CHuNKSoRT(![0... - 1])
CHuNKSoRT(![...n - 1])
CHuNKSoRT(![... - 1])
CHuNKSoRT(![0... - 1])
CHuNKSoRT(![...n - 1])
CHuNKSoRT(![... - 1])
Write the recurrence relation (including the base case) for the number of comparisons of CHuNK-SoRT.
[1 mark]
(d) Recall, the master theorem states that if ╱ is a recurrence relation such that ╱ (n) = α╱ ()+ Θ(nc ) and ╱ (1) = constant then,
,.Θ (nc ) ╱ (n) · .Θ (nc log n)
..Θ ╱nlogb(a)、
if c 女 logb (α)
if c = logb (α).
if c ! logb (α)
Use the master theorem to find the time complexity of CHuNKSoRT.
[1 mark]
Question 4 [10 Marks]
(a) Consider a hash table with 8 slots and a hash function h(k) = k mod 8, which uses open
addressing with a step size of 1. Show the contents of the table after inserting 16, 23, 7, 10 and 12.
[2 marks]
(b) How many comparisons are required to lookup the key 7? Indicate which comparisons
are performed. You can assume that we can check if a slot is empty without making any comparisons.
[1 mark]
(c) How many comparisons are required to lookup the key 15? Indicate which comparisons are performed. You can assume that we can check if a slot is empty without making any comparisons.
[1 mark]
(d) Consider again a hash table with 8 slots and a hash function h1 (k) = k mod 8. This time, the hash table uses separate chaining. Show the state of the hash table after inserting 9, 17, 4, 11 and 1 into an empty hash table.
[1 mark]
(e) Now consider the same hash table (with separate chaining) but with a different hash function
h1 (k) = k mod 5. Explain why this hash function is not ideal for this hash table.
[1 mark] (f) Use Huffman’s algorithm to construct a Huffman tree for the string "free-coffee".
[2 marks]
(g) What is the encoded version of this string, using your Huffman tree? Let each left child be
0 and each right child be 1. Give the total length of the encoding in bits.
[1 mark]
(h) Using the following Huffman tree (again, using 0 for left and 1 for right), give the codes for
f, o, t, and y and decode 0111001000.
o
f
t
[1 mark]
Question 5 [10 Marks]
(a) A string of parentheses ("(" and ")") is valid if no pair of parentheses is “closed” before it
is “opened”. For example, "(())()" is valid while "())(" is not.
The 5 valid strings of 6 parentheses are: "()()()", "(())()", "()(())", "(()())" and "((()))".
Give 3 (three) examples of valid strings of parentheses containing 8 (eight) parentheses.
[1 mark]
(b) Write a recursive formula and base case(s) for the subproblem 女i , where 女i is defined as the
number of different valid strings containing exactly i parentheses.
[4 marks]
(c) Using the recursive formula you derived in Part (b) write pseudocode for an algorithm which computes the number of different valid strings containing n parentheses.
[3 marks]
(d) What is the space complexity of your algorithm? Give an answer in Big-Theta notation and justify your answer.
[1 mark]
(e) What is the time complexity of your algorithm? Give an answer in Big-Theta notation and
justify your answer.
[1 mark]
(a) Show how we interpret the array ┌null.8.4.3.5.2.13.6.4┐ as a tree with the indexing scheme
used for heaps.
[1 mark]
(b) Run the bottom-up construct heap algorithm to convert this array into a max-heap. Show
the state of the heap (in tree form) after each step, indicating exactly which operations are being performed.
[2 marks]
(c) Now show the state of the heap after one REMovEMAx operation. Which element is returned after this operation is performed?
[1 mark]
(d) Give the weights matrix for the following graph.
[1 mark]
(e) Run Floyd’s algorithm to find the shortest paths between each pair of vertices in the graph
from part d. Write the matrices after each step of the algorithm
[3 marks]
(f) Describe what the time complexity of Floyd’s algorithm is (assume the graph has n vertices
and m edges).
[1 mark]
(g) Using DIJKsTRA(ψ.u.w) as a helper function which returns the cost of the shortest path
between u and w in a graph ψ, write an algorithm in pseudocode for computing the all pairs shortest paths in a graph ψ with non-negative edge weights. The graph ψ has n vertices and m edges and is sparse, i.e., m · ò(n).
Your algorithm must have a time complexity better (i.e., smaller) than Floyd’s algorithm. [3 marks]
2022-06-10