YORK UNIVERSITY Dept. of Computer Science and Engineering
Faculty of Science and Engineering February 29, 2008
MID TERM TEST
CSE4101/5101: Advanced Data Structures
• This Test is closed book and lasts from 5:30 pm to 7:00 pm.
• Read all questions before deciding in what order to answer them.
• Do not use any electronic/mechanical computation/communication devices.
• This booklet contains 6 pages including this cover page.
• You may use back side of pages for scratch work.
Name:
Student Number:
Problem Points Points
Received Worth
1 30
2 30
3 40
TOTAL 100
- 1 -
-2-
Problem 1. [30%] Fill in the underlined blanks with the most appropriate and simplified answer.
(a) If we perform a sequence of n INCREMENT operations on a binary counter with initial value C (NOT
ZERO), the total number of bit flips is at most _________________ .
(b) Consider maintaining a dynamic table T with expansion and contraction. One such strategy that yields O(1 )
amortized time per insert and delete and keeps the table load factor at least 80% is:
contraction policy: ___________________________________________________________________,
expansion policy: ____________________________________________________________________.
(c) True or False: Among all off-line strategies on sequential linear lists with free/paid exchanges, the decreas-
ing frequency count method is the optimum, i.e., minimum cost strategy. Answer: _________ .
(d) Given a 2-3-4 tree consisting of n keys, we can output those n keys in sorted order in optimal time
Θ(___________).
(e) In an arbitrary n-node Red-Black tree, the (exact, not asymptotic) maximum number of rotations used in a
single bottom-up insertion is __________, and this happens when _________________________________
______________________________________________________________________________________ .
(f) For the amortized analysis of the Splay Trees we defined the potential function to be
______________________________________________________________________________________ .
The amortized cost of an insert operation is ____________________ .
(g) A self-adjusting version of the Dynamic Order Statistic tree can be implemented by augmenting Splay Trees
by the addition of a _____________ field to each node. In addition to the usual dictionary operations, such
a data structure supports the order statistics operations _____________ and _____________ in
________________ amortized time per operation.
(h) True or False: Let x and y be two arbitrary external nodes in a binary tree T , such that x appears before y
in the inorder sequence of (internal/external) nodes of T . If T is leftist, then depth(x) ≥ depth(y).
Answer: ________ .
(i) True or False: Depth of the rightmost external node in an n-node skew heap is O( log n ).
Answer: ________ .
(j) True or False: In a DeleteMin operation on a skew heap, the number of right-heavy nodes of the resulting
skew heap is always less than or equal to the number of right-heavy nodes of the input skew heap.
Answer: ___________ .
- 2 -
-3-
Problem 2. [30%] Consider the following sequence of keys:
(5, 16, 22, 45, 2, 10, 18, 30, 50, 12, 1).
Consider the bottom-up insertion of items with this set of keys, in the order given, into an initially empty:
a) 2-3-4 tree T1.
b) Red-Black Tree T2.
c) Splay Tree T3.
Draw T1 and T2 and T3 after each insertion.
- 3 -
-4-
Problem 3. [40%] We are given a set P = { p1 , p2 , . . . , pn} of n points in the plane. Assume each point is
given by its x and y coordinates, pi = (xi , yi), for i = 1. . n. We wish to store P in an n node binary tree T with
the following properties:
(i) Each node of T holds a distinct point of P,
(ii) T appears as a Binary Search Tree with respect to the x-coordinates of its stored points,
(iii) T appears as a min-heap with respect to the y-coordinates of its stored points.
We call such a data structure a Search-Heap Tree (SHT). The figure below shows an example.
20, 15
12, 26
24, 72
28, 58
37, 35
7 , 42 15, 81
(a) [5%] Show the SHT of the following set of points: P = {(1 2, 31), (24,15), (4, 23), (18, 5), (14, 53), (16, 7)}.
(b) [9%] If all points in P have distinct x coordinates and distinct y coordinates, show that SHT of P exists
and is unique. What happens to the existence or uniqueness of SHT if we remove the coordinate distinct-
ness assumption?
- 4 -
-5-
(c) [9%] Let T represent the SHT of the point set P. Suppose the y-coordinate of a point of P stored at a
given node v of T is decreased to ynew. How would you update this y-coordinate and use rotation to restore
the SHT property of T ?
(d) [17%] The problem is to construct the SHT of P, where P is a set of n points in the plane, given in sorted
order of their x-coordinates. Give a detailed design and analysis of the most efficient algorithm you can for
this problem. [Hint: Use incremental construction and amortized analysis. Less efficient algorithms may
get partial credit.] [You may continue your answer on the next page.]
- 5 -
-6-
[Answer to Problem 3 continued.]
- 6 -