Register

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{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{2020}&\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 &3&2&3&2&0&2&2&3&3&0&2.2&3
\\\hline\textbf{2 Marks Count} & 2 &3&4&4&2&4&2&3&2&3&2&2.9&4
\\\hline\textbf{Total Marks} & 6 &9&10&11&6&8&6&8&7&9&\bf{6}&\bf{8}&\bf{11}\\\hline
\end{array}}}$$

Filter

Most answered questions in Algorithms

2 votes
0 answers
4351
insertion sort
In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion sort algorithm, if the inputs are restricted to permutations of 1.....n with at most n inversions?
In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai aj. What would be the worst case time complexity of the Inserti...
User Avatar
1 votes
0 answers
4352
heapsort
I have read that for heapify, t(n) = t(2n/3) +o(1) and i know the no. of nodes in the subtree will be 2n/3(worst case) but the algo actually be applied to logn elements down the subtree so isn't it should be t(log n) instead of t(2n/3)? if anybody know then plz clear my doubt
I have read that for heapify, t(n) = t(2n/3) +o(1) and i know the no. of nodes in the subtree will be 2n/3(worst case) but the algo actually be applied to logn elements d...
User Avatar
1 votes
0 answers
4353
Ace Practice booklet
T(n)=sqrt(2T(n/2))+logn
T(n)=sqrt(2T(n/2))+logn
User Avatar
1 votes
0 answers
4354
Solve the recurrence equation
Consider the recurrence T(n)=2T(n/2)+nlogn Find complexity
Consider the recurrence T(n)=2T(n/2)+nlogn Find complexity
User Avatar
1 votes
0 answers
4358
Heap Sort
Why is the space complexity of heap sort O(1) and not O(log n) even if Heap sort internally calls max_heapify whose space complexity is O(log n) due to the stack (recursion)? And if it is O(log n), it should not be an in-place sorting algorithm.
Why is the space complexity of heap sort O(1) and not O(log n) even if Heap sort internally calls max_heapify whose space complexity is O(log n) due to the stack (recursi...
User Avatar
2 votes
0 answers
4359
What is the complexity of a generate-and test algorithm?
In the absence of a comparator, the time complexity of a generate-and test type of algorithm to sort n numbers would be of the order : (A) log n (B) n2 (C) n (D) n!
In the absence of a comparator, the time complexity of a generate-and test type of algorithm to sort n numbers would be of the order : (A) log n(B) n2(C) n(D) n!
User Avatar
0 votes
0 answers
4362
Complexity
In the max heap where the smallest element reside i)if all element are distinct? ii) if all element are not distinct? What is the time complexity in both the cases? If any space complexity required ?
In the max heap where the smallest element residei)if all element are distinct?ii) if all element are not distinct?What is the time complexity in both the cases?If any sp...
User Avatar
0 votes
0 answers
4364
ISRO-2008-29
User Avatar
0 votes
0 answers
4366
Binary Search time -ISRO2014
User Avatar
0 votes
0 answers
4367
what is the tight bound for this expression?
1^k+2^k+3^k+..........n^k =n^k+n^k+n^k+........n^k(n times) =n^(k+1)=O(nk+1) But this is the actual tight bound or it can further be minimized?
1^k+2^k+3^k+..........n^k=n^k+n^k+n^k+........n^k(n times)=n^(k+1)=O(nk+1)But this is the actual tight bound or it can further be minimized?
User Avatar
1 votes
0 answers
4370
ISI2013-PCB-CS-7
A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source vertex $s$ and a designated destination vertex $t$. Let $P(v)$ ... .]
A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source...
User Avatar
Page: