Transcript COMP9024: Data Structures and Algorithms

COMP9024: Data Structures and
Algorithms
Final Exam
Hui Wu
Session 1, 2014
http://www.cse.unsw.edu.au/~cs9024
1
Final Exam




8:45am – 12:00am Fri 27/06/2014 Law Building 202
3 hours
Closed book
Two parts

Part 1: Basic data structures and algorithms


Part 2: Design and analysis of algorithms


8 problems (40 marks)
5 problems (60 marks)
Descriptions of algorithms

Use pseudo code
2
Topics Not Examinable





Java Programming Language
Red-Black Trees
Amortized time complexity analysis
Design of randomized algorithms
All the topics not in the textbook
3
Sample Problems in Part 1
(1/2)
Draw the frequency array and Huffman
tree for the following string:
"dogs do not spot hot pots or cats"
4
Sample Problems in Part 1
(2/2)
Assuming that T1, T2, T3, and T4 are
AVL trees of height h, alter the
following binary search tree to yield
an AVL tree.
5
Sample Problems in Part 2
(1/2)
An undirected graph G is a bipartite graph
whose vertices can be split into two
disjoint sets U and V such that every edge
connects a vertex in U and a vertex in V.
Describe an algorithm for testing if an
undirected graph G is a bipartite graph,
and analyze its time complexity in Big-O
notation.
6
Sample Problems in Part 2
(2/2)
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.)
7