[SOLVED] CS data structure algorithm YORK UNIVERSITY Dept. of Computer Science and Engineering

YORK UNIVERSITY Dept. of Computer Science and Engineering
Faculty of Science and Engineering
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:
February 29, 2008
Problem
Points Received
Points 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.
12, 26
20, 15
24, 72
37, 35
7 , 42
15, 81
28, 58
(a) [5%] Show the SHT of the following set of points: P = {(12, 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-