[SOLVED] CS algorithm CSE4101/5101 Solutions to Mid-Term Test Winter 2008

CSE4101/5101 Solutions to Mid-Term Test Winter 2008
Problem 1.
(a) 2n + log (C + 1). [The second term is a bound on the initial potential (i.e., # of 1-bits in the counter).]
(b) Expand by factor 10/9 if the table is full just before an insertion. Contract by factor 8/9 if the table load fac-
tor is 0.8 just before a deletion. [The load factor just after an expansion/contraction is 0.9.]
(c) False. [Even for the static case, counter-example was given in class.]
(d) O(n). [By an adaptation of inorder traversal on multi-way search trees.]
(e) Is 2. This happens when at the end of the Fix-Up, a 3-node cluster is turned into a zig-zag 4-node cluster. 2 rotations are needed to turn it into a balanced 4-node cluster.
(f) (T ) = v T rankT (v), where rankT (v) = log weightT (v). (The running time of each operation is domi- nated by its number of rotations.) Amortized # rotations in an insertion is 4 log n + 1 = O( log n).
(g) Added field per node: size (i.e., # descendants of the node). New operations: OS Rank and OS -Select . Amortized time: O( log n) per operation.
(h) False. [See T1 in Figure 1, LN4].
(i) False. [Length of rightmost path could vary between (1) and (n).]
(j) False. [Potential could go up.]
Problem 2.
1, 2
Problem 3.
Only final results are shown below. Nodes labeled R in T2 are red (the rest are black).
5, 16, 22
10, 12
T1
16
12R
1
2
12
5R
2 10
22R
45
18
30, 45, 50
18
T2
18, 5
14, 53
45
50
10
5 16 30
18
1R
30R
50R
T3
22
a
4 , 23
16, 7
24, 15
12, 31
Let P = {p1 , p2 , , pn}. Assume no two points of P have equal x coordinate or equal y coordinate. We prove the existence and uniqueness of SHT (P) by induction on n.
Basis (n = 0): The empty tree is the unique SHT.
Induction Step (n 1): Sort the points in P in increasing order of their x coordinates. Without loss of generality assume the sorted sequence is (p1 , p2 , , pn). Since x coordinates are distinct, this sorted sequence is unique. Among these n points select the unique one with minimum y coordinate. Let that be yi. Then because of the heap property on y coordinates, point pi is the unique point that can form the root of SHT (P). Furthermore, because of the binary search property on x coordinates, the unique x-sorted sequence of points (p1 , p2 , , pi1) must form the left subtree of the root, which by the induction hypothesis must exist and be unique; and the unique x-sorted sequence of points (pi+1 , pi+2 , , pn) must form the right subtree of the root, which by the induction hypothesis must exist and be unique. This completes the inductive proof.
b

-2-
What happens if the x or y coordinates of points in P are non-distinct? If two or more points have equal x coordi- nates, by the standard definition of binary search trees, SHT(P) does not exist. However, if we relax this condi- tion and allow some x coordinates to be equal, then the x-sorted sequence mentioned above exists but is not unique. Furthermore, if y coordinates are not distinct, then the selection of the root of the tree (or inductively the subtrees) may not be unique. Hence, SHT (P) may not be unique.
SHT(P) was defined to satisfy properties (i), (ii), and (iii). We know that rotation preserves the inorder sequence of nodes. So if we perform a rotation on any link of SHT, properties (i) and (ii) will be preserved. How about property (iii)?
Notation: point(v) = ( x(v) , y(v) ) indicates the point stored at node v of the SHT.
T was a valid SHT(P). Then the point p = (x, y) at node v of T changed to p = (x, ynew), with ynew < y. If v is the root of T , then we still have a valid SHT. Otherwise, suppose node u is parent of v. The subtree T rooted at u was SHT before the change. Now we lower y(v) to ynew. If we still have y(u) y(v), we have a valid SHT. Oth- erwise, we rotate the link (u,v), now v becomes the root of T and T is a valid SHT. Why? For every proper descendant w of the old v we had y(u) y(w). So, any subtree of the old v that becomes a subtree of the new u does still satisfy the heap ordering property. Such rotations may need to be repeated several levels up the tree. But by the same reasoning, if u was any proper ancestor of the old v and w was any proper descendant of the old v, we had y(u) y(w). So, the rotations that cause node v to go up the tree cannot violate the heap property within the subtree of v. Eventually either v becomes the root, or y(v) y(parent(v)) and we get a valid SHT.Assuming P is given in x-sorted order, SHT(P) can be constructed in O(n) time as follows. Using the idea in part (c), we employ an Incremental Construction of SHT. Without loss of generality assume the x-sorted sequence of the point set P is (p1 , p2 ,…, pn). Let Pi =(p1 , p2 ,…, pi), i.e., the first i points in the x-sorted sequence. We incrementally construct SHT(P1), then SHT(P2), SHT(P3), … SHT(Pn). Obviously SHT(P1) is just a single node containing point p1. The main question is how to go from SHT(Pi1) to SHT(Pi), for each i = 2 .. n? We want to insert point pi = (xi , yi) into T = SHT(Pi1). The changes take place on the rightmost path of the SHT. Instead of pi, imagine we momentarily insert point p = (xi , ). Point p can clearly be added to the rightmost external node v of T . The three properties (i)-(iii) are satisfied. Now, using part (c), we change p to pi at node v of T , i.e., we lower its y coordinate from to yi . This requires several rotations starting at node v up the rightmost path until property (iii) is established. To have access to the nodes of the rightmost path upwards without using parent pointers, we will put them on a stack in order of depth, with the root at the bottom of the stack and node v at the top. We can add a dummy root r with point ( , ), and the true SHT will be the right subtree of r. (Why do we add the dummy root?) The algorithm appears below.Algorithm ConstructSHT(P) {* P = {p1 , … , pn} is x-sorted *}1. r a new node; point[r] (, ); right[r] nil {* dummy root *} 2. MakeEmptyStack(S);Push(r,S)3. for i1..n do{* v is right-child of Top(S) which is right-child of second-top of S *}Time Analysis: The while-loop of lines 6-9 is a MultiPop on S. n such MultiPops are done within the for-loop. There are n + 1 pushes at lines 2 and 10. Hence all the stack operations take O(n) time, and that dominates the entire process. So, the algorithm takes O(n) time. c dv a new node; point[v] pi; left[v] right[v] nil right[Top(S)] v {* make v right child of rightmost node *} while y[Top(S)] > y[v] do
4.
5.
6.
7.
8.
9.
10.
11. endfor
12. return right[r] {* root of SHT (P) *} end
Push(v, S)
LeftRotate(Top(S))
Pop(S) endwhile