Web Page

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline \textbf{Year}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum} \\\hline\textbf{1 Mark Count}&2&0&2&2&3&3&0&2&3 \\\hline\textbf{2 Marks Count}&2&4&2&3&2&3&2&2.7&4 \\\hline\textbf{Total Marks}&6&8&6&8&7&9&\bf{6}&\bf{7.3}&\bf{9}\\\hline \end{array}}}$$

# Recent questions in Algorithms

1
Why do we want the loop index $i$ in line $2$ of BUILD-MAX-HEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor A.length/2 \rfloor$?
2
BUILD-MAX-HEAP(A) 1 A.heapsize=A.length 2 for i=A.length/2 downto 1 3 MAX-HEAPIFY(A,i) Using Figure $6.3$ as a model, illustrate the operation of BUILD-MAX-HEAP on the array $A=\langle 5,3,17,10,84,19,6,22,9 \rangle$
3
Show that the worst-case running time of MAX-HEAPIFY on a heap of size $n$ is $\Omega(lg\ n)$.(Hint: For a heap with $n$ nodes, give node values that cause MAXHEAPIFY to be called recursively at every node on a simple path from the root down to a leaf).
4
The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an iterative control construct (a loop) instead of recursion.
5
What is the effect of calling MAX-HEAPIFY$(A,i)$ for $i > A.heapsize/2$.
6
What is the effect of calling MAX-HEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?
7
Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY$(A, i )$, which performs the corresponding manipulation on a minheap. How does the running time of MIN-HEAPIFY compare to that of MAXHEAPIFY?
8
MAX-HEAPIFY(A,i) 1 l=Left(i) 2 r=Right(i) 3 if l <= A.heapsize and A[l] > A[i] 4 largest=l 5 else largest = i 6 if r <= A.heapsize and A[r] > A[largest] 7 largest=r 8 if largest!=i 9 exchange A[i] with A[largest] 10 MAX-HEAPIFY(A,largest) Using Figure 6.2 as a model, illustrate the operation of MAX-HEAPIFY(A,3) on the array $A=\langle 27,17,3,16,13,10, 1,5,7,12,4,8,9,0 \rangle$
9
Prove that $n!=\omega(2^n)$ and $n!=o(n^n)$.
10
Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $\Theta (n\ lg\ n)$ worst-case time. (Hint: Modify merge sort.)
11
What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
12
What array with elements from the set $\{1,2,\dots n\}$ has the most inversions? How many does it have?
13
List the five inversions of the array $\langle 2,3,8,6,1\rangle$
14
Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence $T(n) = \begin{cases} 2 \text{, if n=2, } \\2T(n/2)+n \text{, if n=$2^k$,for k >1} \end{cases}$ is $T(n) = n\ lg\ n$.
15
Describe a $\Theta(n\ lg\ n)$ time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whose sum is exactly $x$.
16
Observe that the while loop of the INSERTION-SORT procedure uses a linear search to scan (backward) through the sorted subarray $A[i\dots j-1]$ Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to $\Theta(n\ lg\ n)$?
17
Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence $A$ is sorted, we can check the midpoint of the sequence against $v$ and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, ... iterative or recursive, for binary search. Argue that the worst-case running time of binary search is $\Theta (lg\ n)$.
We can express the insertion sort as a recursive procedure as follows.In order to sort $A[1\dots n]$, we recursively sort $A[1 \dots n-1]$ and then insert $A[n]$ into the sorted array $A[1 \dots n-1]$. Write a recurrence for the running time of this recursive version of insertion sort.
Rewrite the MERGE procedure so that it does not use sentinels, instead of stopping once either array $L$ or $R$ has had all its elements copied back to $A$ and then copying the remainder of the other array back into $A$.
Using Figure $2.4$ as a model, illustrate the operation of merge sort on the array $A=\langle 3,41,52,26,38,57,9,49 \rangle$