Final Exam
1
COMP9024: Data Structures and
Algorithms
Final Exam
Hui Wu
Term 1, 2021
http://www.cse.unsw.edu.au/~cs9024
2
Final Exam (1/3)
Time: 1pm-5pm Wednesday 12 May
Venue: Online
Not invigilated
Exam paper will be available at 1pm on
Moodle course website
https://moodle.telt.unsw.edu.au/course/v
iew.php?id=57053
Click on Final Exam below MyExperience
to download the exam paper
Submit your solutions in one or more PDF
files with a sequence number at the end
of each file name by 5pm
https://moodle.telt.unsw.edu.au/course/view.php?id=57053
3
Final Exam (2/3)
Each file cannot exceed 200MB
We use our MS Teams site for Q&A. There
is a separate channel named Final Exam on
our MS Teams site used for the exam only.
If you have any questions, raise your
questions via chat on the Final Exam
channel or talk to me directly via audio
call or video call.
Plagiarism will be checked for all
submissions.
4
Final Exam (3/3)
Two parts
Part 1: Basic data structures and algorithms
8 questions (40 marks)
Part 2: Design and analysis of algorithms
5 questions (60 marks)
Descriptions of algorithms
Use pseudo code
5
Topics Not Examinable
C Programming Language
Red-Black Trees
Floyd-Warshall algorithm for
transitive closure problem
Randomized algorithms (skip lists,
quick select, quicksort)
6
Sample Questions in Part 1 (1/6)
Consider the following algorithm which
takes an array A of n integers as input
and uses an initially-empty queue Q as a
local variable:
7
Sample Questions in Part 1 (2/6)
Algorithm Unknown(A, n)
Input: A one-dimensional integer array A of size n
Output: To be determined
{ create an empty queue Q;
enqueue(Q, A[0]); // adds A[0] to the end of Q
for ( i = 1; i<= n – 1; i++ ) { if ( A[i] >=A[i-1] )
enqueue(Q, A[i]);
else
{ t=0;
while ( Q is not empty )
t = t + dequeue(Q);
output t;
enqueue(Q, A[i]);}}
if ( Q is not empty)
{ t=0;
while ( Q is not empty )
t = t + dequeue(Q);
output t; // print t on the standard output
}
}
8
Sample Questions in Part 1 (3/6)
Please answer each of the following
questions concerning this algorithm:
(a) What are printed on the standard
output when this algorithm terminates
for the array A = {1, 9, 12, 12, 14,
5, 6, 8, 13, 3, 12, 5, 5}?
(b) Use one sentence to explain what this
algorithm does.
(c) Characterize, using the big-O
notation, the running time of the
above algorithm in terms of n, the
size of array A.
9
Sample Questions in Part 1 (4/6)
What does a splay tree look like if its
entries are accessed in increasing order
of their keys?
10
Sample Questions in Part 1 (5/6)
Draw the frequency array and Huffman
tree for the following string:
“dogs do not spot hot pots or cats”
Sample Questions in Part 1 (6/6)
Given a (2,4) tree shown below, draw the
resultant (2,4) trees after deleting key
12 and inserting key 30, and the
intermediate tree after each step
(splitting, or fusion or transfer).
27 32 35
10 15 24
2 8 12 18
12
Sample Questions in Part 2
(1/4)
Given a binary tree with n nodes where
each node stores an entry (key, value),
design an algorithm with the time
complexity O(n)for testing if the tree is
a search tree, and explain why your
algorithm has O(n) time complexity.
13
Sample Questions in Part 2
(2/4)
In an edge-weighted DAG (directed acyclic
graph),each edge has a weight. The length of
a path from a vertex u to a vertex v is the
sum of all the edge weights of the path. A
shortest path from a vertex u to a vertex v
is the path with the minimum length. Describe
an algorithm with O(m+n)time complexity for
finding a shorted path from a vertex u to a
vertex v in an edge-weighted DAG G,and show
why your algorithm takes O(m+n) time, where n
and m are the number of vertices and the
number of edges, respectively, of the graph.
14
Sample Questions in Part 2
(3/4)
For example, in the edge-weighted DAG
shown below, the shortest path length from
vertex 1 to vertex 5 is 4.
2
26
1
3
4
14
3 1
5 2
3 5
5
1
15
Sample Questions in Part 2
(4/4)
Show how to modify the KPM pattern
matching algorithm so as to find
every occurrence of a pattern string
P that appears as a substring in T,
while still running in O(n+m) time.
(Be sure to catch even those matches
that overlap.)
COMP9024: Data Structures and Algorithms
Final Exam (1/3)
Final Exam (2/3)
Final Exam (3/3)
Topics Not Examinable
Sample Questions in Part 1 (1/6)
Sample Questions in Part 1 (2/6)
Sample Questions in Part 1 (3/6)
Sample Questions in Part 1 (4/6)
Sample Questions in Part 1 (5/6)
Sample Questions in Part 1 (6/6)
Sample Questions in Part 2 (1/4)
Sample Questions in Part 2 (2/4)
Sample Questions in Part 2 (3/4)
Sample Questions in Part 2 (4/4)