(a) [20 points] Your friend gives you the following pseudocode for a sorting algorithm.
1. Read the input sequence into an array X 2. Initialize a singly linked list L to X[0] 3. for i = 1 to n-1 do 4. Do a binary search on L to find where X[i] should be inserted in L 5. Insert X[i] at this locationThen your friend tries to convince you that the above algorithm takes O(n log(n)) time, where n is the number of elements in the input sequence. Her explanation is the following. Step 1 takes O(n) time. Step 2 takes O(1) time. The for-loop is executed n-1 times and inside the for-loop we do O(log(n)) work for binary search in Step 4 and O(1) work for insertion into a linked list in Step 5. Therefore we do a total of O(log(n)) inside the for-loop during each iteration. Thus the total running time of Steps 3, 4, and 5 is O(n log(n)). Therefore, the entire algorithm runs in O(n log(n)).
As you might be suspecting, this argument is nonsense because there is one step in the above pseudocode that cannot be implemented in the claimed running time. Identify what this step is and explain in one sentence why it cannot be implemented to run in the time your friend claims.
(b) [30 points] A natural operation to add to the CircularList class is a rotate operation that rotates the circular list by the given amount. For example, consider the circular list in Figure 8.10, page 195. The list consists of 3 nodes, "muffins", "donuts", and "bagels", with "muffins" being the first node of the list and "bagels" being the last. If we rotate this list by 1 unit, then we get the list "donuts", "bagels", "muffins" with "donuts" being the first node and "muffins" being the last.
Implement a method of the CircularList class with the following header:
void rotate(int r)Here, the argument r stands for the number of units we want the list to be rotated by.
Notes:
- The function is no more than 4-5 lines long.
- Assume that r is a non-negative integer, but it could be larger than the number of nodes in the circular list.
(a) [20 points] Recall that the remove operation on a queue removes the element at the front of the queue. Bailey provides 3 implementations of queues: QueueList, QueueVector, and QueueArray. For each of these implementations, write down the running time of the remove() method, in Big-Oh notation, as a function of n, where n is the number of elements in the queue.
(b) [30 points] The main drawback of Bailey's array based implementation of the queue data structure is that when the queue is first instantiated we need to provide a size and the total number of elements present in the queue simultaneously can never exceed this size. For example, consider the following code fragment:
QueueArray Q; Q = new QueueArray(2);Because of above instantiation, the queue Q can never contain more than 2 elements at one time. Now suppose that we use Q to do breadth-first search in a graph. Knowing the fact that Q can never simultaneously hold more than 2 elements, let us suppose that we modify our code for breadth-first search so that whenever it is time to enqueue a neighbor into the queue, we first check if the queue is full and only if it is not full do you enqueue the new element. If the queue is full, then we skip the step of enqueing the neighbor and we also skip the step of marking the neighbor as having been visited.
Run this modified code for breadth-first search on the following graph and show the breadth-first
search tree that is obtained.
As usual, assume that the neighbors of each vertex are processed in alphabetical order.
Recall that in a breadth-first search tree, if node x is the parent of node y, then it must be
the case that vertex y was first marked visited when the algorithm was processing vertex x and
and it encountered y as a neighbor of x.
(a) [30 points] Some students have seen "stack overflow" errors while implementing recursive depth-first search for Project 2. This is because each time a recursive call is made, the current "state" of the function is bundled together into a data structure called an activation record and this is saved on a stack called the run time stack. When the call to the function is completed, then its activation record is popped from the stack. Consider the following recursive function:
int foo(int n)
{
if(n <= 1)
return 1;
else
{
int temp;
temp = foo(n/2) + foo(n/2) + 1;
return temp;
}
}
Suppose that for a call foo(n) to the function, an activation record of size 100 n bytes is created and
pushed on to the run time stack.
Suppose you want to make the function call foo(100).
How much memory would the Java run-time environment need to have set aside for the run time stack, for
the function call foo(100) to successfully complete?
Justify your answer by showing your calculations.
(b) [20 points] We had two implementations depth-first search. One was recursive and the other explicitly used the stack data structure. The problem with the implementation that used the stack data structure was that it was inefficient as compared to recursive depth-first search.
Explain in one sentence what the reason for this inefficiency was. In a second sentence explain how you would fix this problem so that the modified function runs in O(n+m) time.
(a) [20 points] Let Vector H contain a binary heap of 20 elements. It is clear that the element with highest priority can only occupy slot 0 in H. However, there is some flexibility in where the element with second highest priority could go. In particular, the element with second highest priority could be in slot 1 or in slot 2. What about the element with lowest priority? Specifically, list all possible slots, in the range 0 through 19, that the element with lowest priority could be in?
Hint: Recall that the element with lowest priority has can have no children.
(b) [30 points] A natural extension of a binary heap is a ternary heap in which each element has a maximum of 3 children (rather than 2). For example, consider sequence
5 11 10 18 12 15 13would correspond to the ternary heap
5
/ | \
11 10 18
/ | \
12 15 13
For an element in slot i, write down the locations of its 3 children.
For an element in slot i, write down the location of its parent.
(a) [20 points] Write a new method to the BinarySearchTree class called max that returns a reference to the largest node in the binary search tree. Use the following function header:
BinaryTree max()
(b) [30 points] Determine whether the following two binary search trees
can be red-black colored or not.
If a tree can be red-black colored show such a coloring (which should
satisfy all 5 properties of red-black trees).
If a tree cannot be red-black colored, explain in 1-2 sentences why it cannot
be done.
Make sure your explanation is as precise as possible; it is not enough to
say I tried lots of colorings and none of them worked.
