COMP90038 Algorithms and Complexity
Reading Time: 15 minutes Exam Duration: 3 hours
This paper has 11 pages, including this front page.
Examiners’ use:
Enrolment number (student number):
Authorised Materials:
None. This is a closed book exam. Electronic devices, including calculators and laptop computers are not permitted.
Instructions to Invigilators:
Students will provide answers in the exam paper itself. The exam paper must remain in the exam venue and must be returned to the examiner.
Instructions to Students:
This is not an actual exam paper. It is a practice paper which has been put together to show you the format that you can expect in the exam. Many aspects of this paper’s contents do not necessarily reflect the contents of the actual exam paper: The selection of topics, the number of questions or sub-questions, the perceived difficulty of individual questions, and the distribution of weights are all aspects that may be different. When preparing for the exam, you should cover the entire syllabus and not focus only on topics or question types used in this practice paper. If anything, the exam paper can be expected to be harder than this practice paper.
There are 12 questions. As in the exam, you should attempt them all. Of course your answers must be readable. Any unreadable parts will be considered wrong. You will find some questions easier than others; in the actual exam you should allocate your time accordingly. Marks are indicated for each question, adding to a total of 70.
The actual exam paper will be printed single-sided, so you will have plenty of space for rough work on the flip sides. Only what you write inside the allocated boxes will be marked. Page 11 is overflow space, in case you need more writing space for some question.
1 2 3 4 5 6 7 8 9 10 11 12
Page 2 of 11
Question 1
A. Give the names of two stable sorting algorithms, together with their worst-case time
complexities. Write the names and complexities in the box:
B. Give the names of two unstable sorting algorithms, together with their worst-case time complexities. Write the names and complexities in the box:
Question 2 (4 marks)
We are given an array A holding n integers, for some large n. The array is sorted, and the values in A range from -2147483648 to 2147483647, evenly distributed. Give Θ expressions for the following tasks:
A. Running the insertion sort algorithm on the array A:
B. Running the selection sort algorithm on the array A:
C. Performing binary search for integer k which is not in A: D. Performing interpolation search for integer k not in A:
[COMP90038]
[please turn over . . . ]
(4 marks)
Question 3
(4 marks)
Page 3 of 11
For the directed graph below, list the order in which the nine nodes are visited during a depth-first (DFS) traversal, as well as the order in which they are visited during a breadth- first (BFS) traversal. As always, assume that any ties are resolved by taking nodes in alphabetical order. Write the answers in the boxes given.
bcd
axe
hgf
DFS sequence: BFS sequence:
Question 4
Given the pattern A T G A and the text TCATCATCCATGCACAATGACTTT
(4 marks)
how many character comparisons will Horspool’s algorithm make before locating the pattern in the text? Write the number in the box:
[COMP90038] [please turn over . . . ]
Question 5
(4 marks)
In the following table, for each about the function’s rate of growth:
Page 4 of 11
Assume the array A holds the keys 77, 64, 15, 43, 28, 91, 80, 32, 56 in index positions 1 to 9. Show the heap that results after application of the linear-time bottom-up heap construction algorithm. You may show the heap as a tree or as an array.
Question 6
The functions A–D are defined integer):
A(n) = B(n) = C(n) = D(n) =
(4 marks)
recursively as follows (all divisions round down, to the closest
2A(n/3)+2, B(n/2) + n/2, 512 C(n/8) + 4n2, 4D(n/2)+n2,
withA(1)=1 with B(1) = 1 with C(1) = 4 withD(1)=2
of the four functions, tick the most precise correct statement
O(n)
Θ(n)
O(n log n)
Θ(n2)
O(n2 log n)
Θ(n2√
n)
O(n3)
A
B
C
D
[COMP90038] [please turn over . . . ]
Question 7
(4 marks)
Page 5 of 11
For each of A–D below, answer yes or no, and, in each case, briefly explain your reasoning (just a justification of your answer, rather than detailed calculations). A yes/no answer that is not justified will not attract marks, even if correct.
Question Answer/explanation
A.
Is √
n ∈ Ω(n)?
B.
Isn2logn ∈O(nlogn)?
C.
Is Θ(log(n2 log n)) = Θ(log(nlog n))?
D.
Is Θ(log(2n)) = Θ(log(3n))?
[COMP90038]
[please turn over . . . ]
Question 8
(6 marks)
Page 6 of 11
A. The box below contains a weighted undirected graph with eight nodes. Give a minimum spanning tree for the graph. You may do that either by outlining a minimum spanning tree on the graph itself, or by drawing the tree in the empty space next to the graph.
a5b 647
h9c 864
g
5d 437
fe
8
B. Given a weighted graph G = ⟨V, E⟩, a subgraph ⟨V, E′⟩ (that is, E′ ⊆ E) which is a tree with minimal weight is a maximum spanning tree for G.
We want a transformation of the graph G so that we can run Prim’s algorithm on the transformed graph G′, and the algorithm will find a maximum spanning tree for G.
Describe such a (systematic) transformation from G to G′.
[COMP90038] [please turn over . . . ]
Question 9
(6 marks)
Page 7 of 11
Consider the function F below. The function takes as input an integer array A, and the size n of A. The array indices run from 1 to n. The division used is integer division, that it, it rounds down to the closest smaller (or equal) integer value.
In the box, give a Θ expression for the function’s time complexity.
function F(A[·], n) s←0
m←n
while m>0 do
for i ← 1 to m do s ← s + A[i]
m ← m/2
[COMP90038]
Question 10
(10 marks)
Page 8 of 11
Using pseudo-code, give an algorithm for deleting the smallest element of a binary search tree (a BST). Assume a non-empty binary tree T has attributes T.left, T.right, and T.root which denote T’s left sub-tree, right sub-tree, and the key of T’s root node, respectively. You can use these tests if they seem useful: IsLeaf(T) tests whether the binary tree T is a leaf, and IsEmpty(T ) tests whether it is empty.
[COMP90038] [please turn over . . . ]
Question 11
(10 marks)
Page 9 of 11
Consider an array A of n distinct integers (that is, all elements are different). It is known that A was originally sorted in ascending order, but A was then right-rotated r places, where 0 < r < n. In other words, the last r elements were moved from the end of the array to the beginning, with all other elements being pushed r positions to the right. For example, for n = 7 and r = 3, the result may look like this:
[43, 46, 58, 12, 20, 29, 34]
For r = 5, the result, based on the same original array, would be
[29, 34, 43, 46, 58, 12, 20]
You know that the given A[0..n−1] has this particular form, that is, for some r, the sequence A[r],…,A[n − 1],A[0],…A[r − 1] is in ascending order, but you do not know what r is. Design an algorithm to find the largest integer in A. Full marks are given for an algorithm that works in time O(logn); half marks are given for a solution that is correct, but less efficient.
[COMP90038] [please turn over . . . ]
Question 12
(10 marks)
Page 10 of 11
Two programmers face the following problem. Given an array containing n random integers in random order, find the largest integer. The integers are placed in cells A[1] . . . A[n].
Programmer X has come up with the code shown below, on the left. (In the programming language used, arrays are indexed from 0, but X’s method does not use A[0].)
function X(A[·], n) max ← A[1]
i←2
while i≤n do
if A[i]>max then max ← A[i]
i←i+1 return max
function Y(A[·], n) i ← n
while i>0 do A[0]←A[i]
i←i−1
while A[0] > A[i] do
i←i−1 return A[0]
Programmer Y has solved the same problem differently, as shown above on the right. Compare the two solutions using three criteria: Correctness, time complexity class, and the
number of comparisons performed. Write your analysis in the box:
[COMP90038] [end of exam]
Overflow space
Page 11 of 11
Use this page if you ran out of writing space in some question. Make sure to leave a pointer to this page from the relevant question.