search
Log In

Web Page

Searching, Sorting, Hashing, Asymptotic worst case time and Space complexity, Algorithm design techniques: Greedy, Dynamic programming, and Divide‐and‐conquer, Graph search, Minimum spanning trees, Shortest paths.

$$\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}}}$$

Questions without answers in Algorithms

0 votes
0 answers
1
The running time of an algorithm is $O(g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n)) \cdot (O= \textit{ big }O)$ its worst-case running time is $\Omega (g(n))$ ... , $(o = \textit{ small } o)$ Choose the correct answer from the options given below: $(a)$ only $(b)$ only $(c)$ only $(d)$ only
asked Nov 20, 2020 in Algorithms jothee 94 views
0 votes
0 answers
2
Given below are two statements: If two variables $V_1$ and $V_2$ are used for clustering, then consider the following statements for $k$ means clustering with $k=3$: Statement $I$: If $V_1$ and $V_2$ have correlation of $1$ the cluster centroid will be in straight ... Statement $II$ are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true
asked Nov 20, 2020 in Algorithms jothee 46 views
1 vote
0 answers
4
A college professor gives several quizzes during the semester, with negative marking. He has become bored of the usual "Best $M$ out of $N$ quizzes" formula to award marks for internal assessment. Instead, each student will be evaluated based on the ... programming, the score the professor needs to award each student. Describe the space and time complexity of your dynamic programming algorithm.
asked Sep 13, 2019 in Algorithms gatecse 233 views
0 votes
0 answers
5
The running time of an algorithm of n interdependent operations is computed with both the asymptotic & amortized analyses. The most accurate running time obtained by Asymptotic analysis Amortized analysis Both analyses None of these
asked Aug 4, 2019 in Algorithms gatecse 31 views
0 votes
0 answers
6
The comparison of algorithm types divide-and-conquer (DAC) and dynamic programming (DP) indicates that DP is bottom-up approach and DAC is top-down approach. DP is top-down approach and DAC is bottom-up approach. Both DP and DAC are bottom-up approaches. Both DP and DAC are top-down approaches.
asked Aug 4, 2019 in Algorithms gatecse 21 views
0 votes
0 answers
7
Explain how to implement doubly linked lists using only one pointer value $x.np$ per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as $k$-bit integers, and define $x.np$ to be $x.np=x.next$ $XOR$ $x.prev$, the $k$- ... to implement the $SEARCH$, $INSERT$, and $DELETE$ operations on such a list. Also, show how to reverse such a list in $O(1)$ time.
asked Jun 30, 2019 in Algorithms akash.dinkar12 240 views
0 votes
0 answers
8
LIST-SEARCH’(L, k) 1 x = L.nil.next 2 while x != L.nil and x.key != k 3 x = x.next 4 return x As written, each loop iteration in the LIST-SEARCH’ procedure requires two tests: one for $x\neq L.nil$ and one for $x.key\neq k$. Show how to eliminate the test for $x\neq L.nil$ in each iteration.
asked Jun 30, 2019 in Algorithms akash.dinkar12 69 views
0 votes
0 answers
9
0 votes
0 answers
10
A probability distribution function $P(x)$ for a random variable $X$ is defined by $P(x) =Pr\{X\leq x\}$.Suppose that we draw a list of $n$ random variables $X_1,X_2,…,X_n$ from a continuous probability distribution function $P$ that is computable in $O(1)$ time. Give an algorithm that sorts these numbers in linear averagecase time.
asked Jun 28, 2019 in Algorithms akash.dinkar12 191 views
0 votes
0 answers
11
We are given $n$ points in the unit circle, $P_i=(x_i,y_i)$, such that $0<x_i^2+y_i^2<1$ for $i=1,2, .,n$.Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the ... from the origin. (Hint: Design the bucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)
asked Jun 28, 2019 in Algorithms akash.dinkar12 159 views
0 votes
0 answers
12
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
asked Jun 28, 2019 in Algorithms akash.dinkar12 135 views
0 votes
0 answers
13
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?
asked Jun 28, 2019 in Algorithms akash.dinkar12 113 views
0 votes
0 answers
14
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 $
asked Jun 28, 2019 in Algorithms akash.dinkar12 113 views
0 votes
0 answers
15
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.)
asked Jun 28, 2019 in Algorithms akash.dinkar12 98 views
0 votes
0 answers
16
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$?
asked Jun 28, 2019 in Algorithms akash.dinkar12 68 views
0 votes
0 answers
17
0 votes
0 answers
18
Suppose that the splits at every level of quicksort are in the proportion $1-\alpha$ to $\alpha$, where $0<\alpha\leq1/2$ is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately $-lg\ n /lg\ \alpha$ and the maximum depth is approximately $-lg\ n / lg\ (1-\alpha)$.(Don’t worry about integer round-off.)
asked Jun 27, 2019 in Algorithms akash.dinkar12 59 views
0 votes
0 answers
19
Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants ... problem of sorting almost-sorted input. Argue that the procedure INSERTION-SORT would tend to beat the procedure QUICKSORT on this problem.
asked Jun 27, 2019 in Algorithms akash.dinkar12 101 views
0 votes
0 answers
20
Give an $O(n\lg\ k)$- time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a minheap for $k$-way merging.)
asked Jun 27, 2019 in Algorithms akash.dinkar12 67 views
0 votes
0 answers
21
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
asked Jun 27, 2019 in Algorithms akash.dinkar12 60 views
0 votes
0 answers
22
Each exchange operation on line $5$ of HEAP-INCREASE-KEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the three assignments down to just one assignment.
asked Jun 27, 2019 in Algorithms akash.dinkar12 60 views
0 votes
0 answers
23
Argue the correctness of HEAP-INCREASE-KEY using the following loop invariant: At the start of each iteration of the while loop of lines $4-6$, the subarray $A[1..A.heapsize]$ satisfies the max-heap property, except that there may be one violation$::$ $A[i]$ may be ... $A[a..heapsize]$ satisfies the max-heap property at the time HEAP-INCREASE-KEY is called.
asked Jun 27, 2019 in Algorithms akash.dinkar12 39 views
0 votes
0 answers
24
Why do we bother setting the key of the inserted node to $-\infty$ in line $2$ of MAX-HEAP-INSERT when the next thing we do is increase its key to the desired value?
asked Jun 27, 2019 in Algorithms akash.dinkar12 87 views
0 votes
0 answers
25
Write pseudo code for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.
asked Jun 27, 2019 in Algorithms akash.dinkar12 40 views
0 votes
0 answers
26
HEAP-INCREASE-KEY(A,i,key) 1 if key < A[i] 2 error new key is smaller than current key 3 A[i] = key 4 while i > 1 and A[parent(i)] < A[i] 5 exchange A[i] with A[parent(i)] 6 i=parent(i) MAX-HEAP-INSERT(A,key) 1 A.heapsize = A.heapsize + 1 2 A[A.heapsize] ... -KEY(A,A.heapsize,key) Illustrate the operation of MAX-HEAP-INSERT$(A,10)$ on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
asked Jun 27, 2019 in Algorithms akash.dinkar12 90 views
0 votes
0 answers
27
HEAP-EXTRACT-MAX(A) 1 if A.heap-size < 1 2 error “heap underflow” 3 max=A[1] 4 A[1]=A[A.heapsize] 5 A.heapsize=A.heapsize-1 6 MAX-HEAPIFY(A,1) 7 return max Illustrate the operation of HEAP-EXTRACT-MAX on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
asked Jun 27, 2019 in Algorithms akash.dinkar12 44 views
0 votes
0 answers
28
0 votes
0 answers
29
0 votes
0 answers
30
What is the running time of HEAPSORT on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?
asked Jun 27, 2019 in Algorithms akash.dinkar12 49 views
To see more, click for the full list of questions or popular tags.
...