Write the recurrence relation that can arise in relation to the time complexity of the binary search algorithm.
Consider the following postfix expression with single digit operands:

6 2 3 * / 4 2 * + 6 8 * -

The top two elements of the stack after the second * is evaluated, are:

i) 6, 3 ii) 8, 1 iii) 8, 2 iv) 6, 2
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following is/are TRUE?

I. Quicksort runs in time. II. Bubblesort runs in time. III. Merge sort runs in time. IV. Insertion sort runs in time.

(a) I and II only (b) I and III only (c) II and IV only (d) I and IV only
The height of a binary tree is the maximum number of nodes in any root-to-leaf path. The maximum number of nodes in a binary tree of height is:
Let be a perfect binary tree with leaves. Then how many nodes in have degree 2?

Write the recurrence relation that can arise in relation to the time complexity of the following C function. Solve that recurrence relation and compute its time complexity.
```
int recursive(int n)
{
	 if (n == 2)
		  return 1;
	 else
		  return recursive(n/2) + recursive(n/2);
}
```
Given an array of numbers. You are asked to pick a number which is not the second largest. Can you propose an algorithm? If so, write an algorithm; if not, state why.
What type of list implementation (for example, singly linked list, doubly linked list, circular linked list etc.) should be used to perform the concatenation of two lists in time? Justify your answer.
Given two sorted arrays and having numbers of elements and , respectively. Write a pseudo-code of linear time complexity () to merge and into a third array , such that is also sorted and has elements.

Solve the following recurrence relations:

i)

ii) and
A circularly linked list is used to represent a Queue. A single variable is used to access the Queue. To which node (for example front, rear etc.) should point such that both the operations enQueue and deQueue can be performed in constant time? Justify your answer.
We have studied “Binary Search” algorithm in class. Now consider a “Ternary Search” algorithm in which two mid-indices are maintained; and . This divides the array into three parts: left to , to , and to right. Search is conducted recursively in these three parts. Write pseudo code for the ternary search algorithm and compute its time complexity.
Convert the following infix expressions into postfix expressions using the operator stack.

i)

ii)

iii)

iv)

v)
Write an algorithm for level-order traversal of a binary tree. Analyze the time complexity of the algorithm.

Mr. Ram is a chemist who receives ten medicine boxes with batch numbers 35, 33, 42, 10, 14, 19, 27, 44, 26, 31 printed on them. He always arranges the boxes manually and gets frustrated every time. He thought he would have a lot of problems in the future arranging the boxes if the number of boxes of medicine is large. He wants to make this task easier. As you are a good programmer, Mr. Ram is asking for your help. Write an optimal quick sort algorithm to arrange the boxes in increasing order of batch numbers and show each step of the algorithm in detail using the above sequence of batch numbers. Also, write the best case and worst case time complexity of the algorithm?

Solutions

StudyLabs