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

0 votes
1 answer
1981
Asymtotic notation
How to prove these type of questions???
How to prove these type of questions???
User Avatar
2 votes
1 answer
1982
Merge sort
Given "log n" sorted lists each of size "n/log n",what is the total time required to merge them into one single list.
Given "log n" sorted lists each of size "n/log n",what is the total time required to merge them into one single list.
User Avatar
0 votes
1 answer
1983
time complexity
int Dosomething(int n) { if(n>=2) return 1; else return (floor(sqrt(n)))+n; } time complexity of the program?
int Dosomething(int n){if(n>=2)return 1;elsereturn (floor(sqrt(n)))+n;}time complexity of the program?
User Avatar
0 votes
1 answer
1984
time complexity
let n>=m int gcd(n,m) { if(n%m==0) return ml; n=n%m; return gcd(m,n); } how many recursive calls are made by this function?
let n>=mint gcd(n,m){if(n%m==0)return ml;n=n%m;return gcd(m,n);}how many recursive calls are made by this function?
User Avatar
0 votes
1 answer
1986
algo self doubt
consider the following c program A(n) { if(n<=1) return(n2 +n+1) else return(5A(n/2)+3A(n/2)+MA(n)) } where MA(n) has complexity O(n2). 1.what is the recurrence relation for value.? 2.what is the the recurrence relation for time complexity?
consider the following c program A(n){if(n<=1)return(n2 +n+1)elsereturn(5A(n/2)+3A(n/2)+MA(n))}where MA(n) has complexity O(n2).1.what is the recurrence relation for valu...
User Avatar
0 votes
1 answer
1987
Binary search
Find the average number of comparisons in a binary search on a sorted array of 10 consecutive integers starting from 1. 1) 2.6 2)2.7 3)2.8 4)2.9
Find the average number of comparisons in a binary search on a sorted array of 10 consecutive integers starting from 1.1) 2.62)2.73)2.84)2.9
User Avatar
0 votes
1 answer
1989
Self-Doubt
What will be the time-complexity of the following ? for(i=1;i<=n;i=i*2) { for(j=0;j<i;j++) { count++; } }
What will be the time-complexity of the following ? for(i=1;i<=n;i=i*2) { for(j=0;j<i;j++) { count++; } }
User Avatar
0 votes
1 answer
1990
Made easy workbook
We've been given an unordered list having n distinct elements,the no. Of comparison to find an element that is neither the 2nd minimum nor the 2nd maximum is?
We've been given an unordered list having n distinct elements,the no. Of comparison to find an element that is neither the 2nd minimum nor the 2nd maximum is?
User Avatar
0 votes
1 answer
1991
#Algorithms Can Heapsort be applied on Min Heap Data Structure?
I've read and been told that Heapsort can only be applied on Max heap, but this article for G4G states otherwise - https://www.geeksforgeeks.org/heap-sort-for-decreasing-order-using-min-heap/ So, is it true that HS can be applied also on Min heap?
I've read and been told that Heapsort can only be applied on Max heap, but this article for G4G states otherwise - https://www.geeksforgeeks.org/heap-sort-for-decreasing-...
User Avatar
1 votes
1 answer
1992
cormen 3rd edition Q. 16.2-6
Show how to solve the fractional knapsack problem in O(n) time. The solution include that we can find the median in O(n) time and then solving the fractional knapsack problem on input of size n/2, but the pi/wi is not sorted, so how do we have the equation T(n) = T(n/2) + cn?
Show how to solve the fractional knapsack problem in O(n) time.The solution include that we can find the median in O(n) time and then solving the fractional knapsack prob...
User Avatar
0 votes
1 answer
1994
Heap Sort
Would it be possible to implement a variant of heapsort based on a perfectly balanced ternary structure in which the children of node $i$ are at positions $3i - 1, 3i$, and $3i + 1$, and if so what would be the advantages and disadvantages of the new method?
Would it be possible to implement a variant of heapsort based on a perfectly balanced ternary structure in which the children of node $i$ are at positions $3i - 1, 3i$, a...
User Avatar
2 votes
1 answer
1995
Algorithm
Which of the given options provides the increasing order of asymptotic complexity of functions $f1$, $f2$, $f3$ and $f4$? $f1(n) = 2^n \\ f2(n) = n^{(3/2)} \\ f3(n) = nlogn \\ f4(n) = n^{(logn)}$ How $n^{3/2}$ is greater than $n^{logn}$
Which of the given options provides the increasing order of asymptotic complexity of functions $f1$, $f2$, $f3$ and $f4$? $f1(n) = 2^n \\ f2(n) = n^{(3/2)} \\ f3(n) = nl...
User Avatar
0 votes
1 answer
1996
time complexity
what is the time complexity of the $pow(m,n)$ ?
what is the time complexity of the $pow(m,n)$ ?
User Avatar
0 votes
1 answer
1997
Time complexity
$T(n) = T(n-2) + 2logn, \text{ if } n>1 \\ =1, \text{ if } n=1$ Find the Time Complexity.
$T(n) = T(n-2) + 2logn, \text{ if } n>1 \\ =1, \text{ if } n=1$Find the Time Complexity.
User Avatar
0 votes
1 answer
1998
Time complexity
What is the time complexity of the following recursive function : int DoSomething(int n) { if (n <= 2) return 1; else return DoSomething(floor(sqrt(n)))+ n; } $\theta(n^2)$ $\theta(n \log_2 n)$ $\theta(\log_2 n)$ $\theta(\log_2 \log_2 n)$
What is the time complexity of the following recursive function :int DoSomething(int n) { if (n <= 2) return 1; else return DoSomething(floor(sqrt(n)))+ n; }$\theta(n^2)$...
User Avatar
0 votes
1 answer
1999
me wk book
let T be a minimum cost spanning tree of G. suppose that ewe decreased the weight of one of the edge in T.then to check modified T is MST or not how much tym will take??? O(1) or O(n)?????
let T be a minimum cost spanning tree of G. suppose that ewe decreased the weight of one of the edge in T.then to check modified T is MST or not how much tym will take???...
User Avatar
0 votes
1 answer
2000
self doubt
Suppose that average edge weight for a graph G is Aavg. Then the minimum spanning tree of G will have weight at most (n-1) Aavg. Where n is number of vertices in graph G. i think think is false but in a solution mannul it is given as true please check it.
Suppose that average edge weight for a graph G is Aavg. Then the minimum spanning tree of G will have weight at most(n-1) Aavg. Where n is number of vertices in graph G.i...
User Avatar
Page: