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
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
2
Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
3
RADIX-SORT(A, d) 1 for i = 1 to d 2 use a stable sort to sort array A on digit i illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.
4
Describe an algorithm that, given $n$ integers in the range $0$ to $k$ preprocesses its input and then answers any query about how many of the $n$ integers fall into the range $[a..b]$ in $O(1)$ time.Your algorithm should use $\Theta(n+k)$ preprocessing time.
5
Suppose that we were to rewrite the for loop header in line $10$ of the COUNTINGSORT as 10 for j = 1 to A.length Show that the algorithm still works properly. Is the modified algorithm stable?
6
Prove that COUNTING-SORT is stable.
7
COUNTING-SORT(A, B, k) 1 let C[0, ,k] be a new array 2 for i = 0 to k 3 C[i] = 0 4 for j = 1 to A.length 5 C[A[j]] = C[A[j]] + 1 6 // C[i] now contains the number of elements equal to i . 7 for i =1 to k 8 C[i] = C[i] + C[i-1] 9 // C[i] now contains the ... [C[A[j]]] = A[j] 12 C[A[j]] = C[A[j]] - 1 illustrate the operation of COUNTING-SORT on the array $A=\langle 6,0,2,0,1,3,4,6,1,3,2 \rangle$
8
Suppose that you are given a sequence of $n$ elements to sort.The input sequence consists of $n/k$ subsequences, each containing $k$ elements.The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the ... this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
9
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$.What about a fraction of $1/n$ inputs of length $n$? What about a fraction $1/2^n$?
10
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.
11
What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
12
Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst a $\alpha$-to-$(1-\alpha)$ split, as a function of $\alpha$ in the range $0<\alpha<1$.
13
We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is nearly sorted. Upon calling quicksort on a subarray with fewer than $k$ elements, let it simply return without sorting the subarray. After the top-level ... runs in $O(nk+n\ lg\ (n/k))$ expected time. How should we pick $k$, both in theory and in practice?
14
Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.
15
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.
16
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.
17
Show that in the recurrence $T(n)=\max_{0<q\leq n-1} (T(q)+T(n-q-1))+\Theta(n)$ $T(n)=\Omega(n^2)$
18
RANDOMIZED-QUICKSORT(A, p, r) 1 if p < r 2 q = RANDOMIZED-PARTITION(A, p, r) 3 RANDOMIZED-QUICKSORT(A, p, q - 1) 4 RANDOMIZED-QUICKSORT(A, q + 1, r) RANDOMIZED-PARTITION(A, p, r) 1 i = RANDOM(p, r) 2 exchange A[r] with A[i] 3 return ... how many calls are made to the random number generator RANDOM in the worst case? How about in the best case? Give your answer in terms of $\Theta$ notation.
19
Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?
Argue that for any constant $0<\alpha\leq 1/2$, the probability is approximately $1-2\alpha$ that on a random input array, PARTITION produces a split more balanced than $1-\alpha$ to $\alpha$.