Description
Make best use of picture in Latex: If you think some part of your answer is too difficult to type using Latex, you may write that part on paper and scan it as a picture, and then insert that part into Latex as a picture, and finally Latex will compile the picture into the final PDF output. This will make things easier. For instructions of how to insert pictures in Latex, you may refer to the Latex file of our homework 1, which includes several examples of inserting pictures in Latex.
Discussion Group (People with whom you discussed ideas used in your answers if any): Xudong Jiang
I acknowledge and accept the Honor Code. Please type your initials below:
Signed: (YC)
- Warm up with BST. (20 points) Beginning with an empty binary search tree, what binary search tree is formed when you insert the following values in the order given? (Values are compared in alphabet order, e.g., A < B)
- W, T, N, J, E, B, A
- W, T, N, A, B, E, J
- A, B, W, J, N, T, E
- N, A, T, E, B, W, J
Answer:
Figure 1: Question1 Answer.
- Red, black, or neither? (20 points) For each of the unlabeled binary trees, state whether or not it can be the structure of a red-black tree. If so, color the vertices red or black. If not, state which of the red-black tree invariants (1 to 5) cannot be satisfied and provide an explanation.
[We are expecting a YES/NO, and either (1) a valid coloring or (2) a set of violated invariants and a brief explanation. For the colorings, feel free to
redraw the trees by hand and insert the image.]
- (5 point) No (c) (5 point) Yes
- (5 point) Yes (d) (5 point) Yes
Answer:
Figure 2: Question2.
(a) No. Assume it can be the structure of a red-black tree. Noted The root node is black.
Let the left child be red. since the invariant 5, every path from a root node to a NULL node has the same number of black nodes. The right path has 0 black nodes. therefore, all of its descendants are red. But, it violated the invariant 4. So, the left child cannot be red.
Let the left child be black. Since the invariant 5, we can know that the other two of its descendants must be red to maintain the invariant 5, because, the right path has 0 black nodes. But, it violated the invariant 4. So, the left child cannot be black. The same logistics for the right child.
In sum, there is a contradiction. Thus, it cannot be the structure of a red-black tree. (b) Yes. (c) Yes. (d) Yes.
- Binary search tree with equal keys. (30 points + 10 bonus points) In the class, we assumed that all the keys in a BST are different from each other. However, the BST can still store keys of the same value, in this case, we put a key that is less than a node to its left, and put a key that is greater than or equal to a node to its right. Here is the algorithm for inserting a new key z in to a binary search tree T:
Algorithm 1: Tree-Insert(T,z)
- y = NIL;
- x = T.root;
- while x 6= NIL
- y=x;
- if key<x.key
- x = x.left;
- else x = x.right
- parent = y;
- if y==NIL
- root = z; //tree T was empty
- elseif key<y.key
- left=z;
- else right=z;
- (10 points) To better understand the algorithm, draw the tree generated by inserting the numbers 5, 3, 10, 8, 12, 12, 8, 8, 6, 6, 7, 5, 8 in this given order into an initially empty binary search tree using the above algorithm.
- (10 points) What is the asymptotic runtime of Tree-Insert when used to insert n items with identical keys into an initially empty binary search tree?
We propose to improve Tree-Insert by testing before line 5 to determine whether z.key==x.key and by testing before line 11 to determine whether z.key==y.key. If equality holds, we implement one of the following strategies. For each strategy, find the asymptotic runtime of inserting n items with identical keys into an initially empty binary search tree. (The strategies are described for line 5, in which we compare the keys of z and x, and substitute y for x to arrive at the strategies for line 11.)
Figure 3: Question3 (a).
Question3 (b) Answer:
Acording to the Algorithm 1, we know that TREE-INSERT is always FALSE on line 5, then the right child will be chosen. For the line 11, the TREE-INSERT is also FALSE, the new element will be inserted to the right of the rightmost leaf. As we know, there are total n items, so the height of tree is n, and increases at every insertion and new element is inserted as a new leaf node. Therefore, the runtime of TREE-INSERT is
- (10 points) Keep a list of nodes with equal keys at x, and insert z into the list.
Answer:
When we keep a list of nodes with equal keys at x, and insert z into the list, which means the height of the tree is 0, so we only take linear time. It is a single insertion into a list, so runtime is O(1).
- (10 bonus points) Randomly set x to either x.left or x.right. (Give the worst-case runtime and informally derive the expected runtime.) Answer:
The worst-case: it would set all x to left or all x to right.So it is same as the part (b), the runtime is O(n2).
The expected: we expect the tree is a balance tree, like half-half, set half x to x.left, half to x.right. Therefore, the height of the tree is logn, the total runtime is
[Note: for (b) (c) and (d), we are expecting the runtime represented as a function of n].
- Hat-check problem. (10 bonus points) Use indicator random variables to solve the following problem, which is known as the hat-check problem. Each of n customers gives
a hat to a hat-check person at a restaurant. The hat-check person gives the hats back to the customers in a random order. What is the expected number of customers who get back their own hat?
Answer: Using indicator random variables let ith customers get back their own hat back.
Xi = I (for 1 ≤ i ≤ n )
Let X be a random variable denoting the total number of customers who get their own hat back.
Then, we are going to compute the E[X].
We know that the hat-check person gives the hats back to the customers in a random order, so each of n customers has the probability 1/n to get their own hat back.
So,E[Xi] = 1/n
E[X] = E[Pni=1 Xi]
E[X] = Pni=1 E[Xi]
E[X] = Pni=1(1/n)
E[X] = 1
Thus, the expected number of customers which get their own hat back is 1.
- Quicksort with equal element values. (30 points) The analysis of the expected running time of randomized Quicksort in class (corresponding to Section 7.4.2 in textbook) assumes that all element values are distinct. In this problem, we examine what happens when they are not, i.e., there exist same-valued elements in the array to be sorted.
The Quicksort algorithm relies on the following partition algorithm, which finds a pivot randomly, and then put all the numbers less than or equal to the pivot in the left, and put all the numbers greater than the pivot in the right, and then return the pivot location, as well as the left and right sublists for recursive calls.
Algorithm 2: Partition(A,p,r)
- q=Random(p,r); //generate a random number in the range of [p,r]
- L=empty list, R=empty list; 3 for each element a in A except A[q]:
- if a≤A[q]:
- append a to L;
- else append a to R;
- A=append(L,A[q],R);
- returen A, q;
In this algorithm, the list to be sorted is A, and we use p and r to denote the left-most and right-most indices of the currently processing subarray, respectively. For example, in the initial call of the Quicksort algorithm, we will let p = 0 and r = n−1, which correspond to the whole original array. The Partition(A,p,r) procedure returns an index q such that each element of A[p : q − 1] is less than or equal to A[q] and each element of A[q + 1 : r] is greater than A[q].
- (10 points) Suppose there are n elements and all element values are equal. What would be randomized Quicksort’s running time in this case?
Answer:
Noted there are n elements and all the element values are equal. Therefore, the random value p and r are always equal.According to the Algorithm 2, we know that all the element will go to the L (left empty list). the total runtime is
- (10 points) Modify the Partition procedure to produce a procedure Partition0(A,p,r), which permutes the elements of A[p : r] and returns two indices q and t, where p ≤ q ≤ t ≤ r, such that:
- all elements of A[q : t] are equal,
- each element of A[p : q − 1] is less than A[q], and
- each element of A[t + 1 : r] is greater than A[q]
Like Partition, your Partiton0 procedure should take O(r − p) time.
Answer:
PARTITION’(A, p, r) x = A[p] low = p, high = p for(j = p + 1,j <= r,j + +) if A[j] < x y = A[j]; A[j] = A[high + 1];
A[high + 1] = A[low]; A[low] = y; low++, high++; END IF
else if (A[j] == x) exchange A[high + 1] with A[j]; high++;
END IF
END FOR;
return (low, high);
(c) (10 points) Now you have a Partition0(A,p,r) algorithm, based on this algorithm, provide the pseudocode of a Quicksort0(A) algorithm which calls Partition0(A,p,r) as a subroutine, so that it recurses only on partitions of elements not known to be equal to each other. [Hint: it will looks very similar to our Quicksort pseudocode in the lecture slides, you only need to make minor modifications to recurse on the partitions produced by Partition0(A,p,r).] Answer:
QUICKSORT’(A, p, r) if (p < r)
(low, high) = RANDOMIZED-PARTITION’(A, p, r);
QUICKSORT’(A, p, low – 1);
QUICKSORT’(A, high + 1, r);
END IF;
