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:
(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.
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.
(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 13For 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.
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.