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

Highest voted questions in Algorithms

1 votes
2 answers
2371
asymtotic notations
Q). Consider the following functions $f_1 = n^{\frac{4}{3}}$ $f_2=2^{2^n}$ $f_3= 2^{n^2}$ $f_4= n!$ $f_5=2^n$ Which of the following is true? A). $f_1$ is $\Omega(f_2)$ B). $f_2$ is $O(f_3)$ C). $f_1<f_5<f_4<f_2<f_3$ D). $f_4$ is $O(f_3)$
Q). Consider the following functions$f_1 = n^{\frac{4}{3}}$$f_2=2^{2^n}$$f_3= 2^{n^2}$$f_4= n!$$f_5=2^n$Which of the following is true?A). $f_1$ is $\Omega(f_2)$B). $f_2$...
User Avatar
1 votes
2 answers
2373
inverion pairs
assume that A be an array of 16 elements.What is the difference between maximum and minimum number of inversion pairs in worst case?
assume that A be an array of 16 elements.What is the difference between maximum and minimum number of inversion pairs in worst case?
User Avatar
1 votes
0 answers
2375
Asymptotic notations
Let f(n)= Ω(n), g(n)= O(n) and h(n)= Ѳ(n). Then [f(n). g(n)] + h(n) is: (a) Ω (n) (b) O (n) (c) Ѳ (n) (d) None of these explain it
Let f(n)= Ω(n), g(n)= O(n) and h(n)= Ѳ(n).Then [f(n). g(n)] + h(n) is:(a) Ω (n) (b) O (n)(c) Ѳ (n) (d) None of theseexplain it
User Avatar
1 votes
2 answers
2376
time complexity
$\sum\limits_{i=0}^n i^{3} = X$ and following choices for X 1.$\Theta(n^4)$ 2.$\Theta(n^5)$ 3. $O(n^5)$ 4.$\Omega(n^3)$ possible values of $X$
$\sum\limits_{i=0}^n i^{3} = X$and following choices for X1.$\Theta(n^4)$2.$\Theta(n^5)$3. $O(n^5)$4.$\Omega(n^3)$possible values of $X$
User Avatar
1 votes
1 answer
2377
Recurrence
How to build Recurrence relation for Time complexity double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += foo(i); } return sum; } }
How to build Recurrence relation for Time complexity double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += f...
User Avatar
1 votes
1 answer
2378
Dijkatra algorithm for unweighted graph
hi all , Please tell me how much does dijkastra algoritm would take for unwaited and martix implementation
hi all ,Please tell me how much does dijkastra algoritm would take for unwaited and martix implementation
User Avatar
1 votes
0 answers
2379
Max Heap
Extract Min from Max heap 1. search at last level = O(n) 2.Replace element with last element and decrese heap size by 1 = O(1) 3. Apply max heapify on replaced element = O(log n) Total Time = O(n)+O(1)+O(log n) = O(n) is it correct ?
Extract Min from Max heap1. search at last level = O(n)2.Replace element with last element and decrese heap size by 1 = O(1)3. Apply max heapify on replaced element = O(l...
User Avatar
1 votes
1 answer
2380
Recurrence relation
Recurrence relation T(1)=1 T(n)=2T(n-1)+n n>=2 evaluates to .. Pls explain with detailed steps..
Recurrence relation T(1)=1 T(n)=2T(n-1)+n n>=2 evaluates to ..Pls explain with detailed steps..
User Avatar
1 votes
1 answer
2381
Recurrence relation
How to solve the Recurrence relation T(n)=T(n/4)+T(3n/4)+n
How to solve the Recurrence relation T(n)=T(n/4)+T(3n/4)+n
User Avatar
1 votes
1 answer
2382
Hashing function
Consider a hashing function that resolves collision by quadratic probing. Assume the address space is indexed from 1 to 8.If a collision occurs at position 4, then the location which will never be probed is..
Consider a hashing function that resolves collision by quadratic probing. Assume the address space is indexed from 1 to 8.If a collision occurs at position 4, then the lo...
User Avatar
1 votes
2 answers
2383
Hash table
A hash table can store a max of 10 records, currently, there are records in locations 1,3,4,7,8,9,10. The probability of a new record going into location 2,with a hash function resolving collisions by linear probing is..
A hash table can store a max of 10 records, currently, there are records in locations 1,3,4,7,8,9,10. The probability of a new record going into location 2,with a hash fu...
User Avatar
1 votes
1 answer
2384
order of the algorithm
T(n) = T(n-1)+ 1/n if n>1 =1 otherwise The order of the algorithm is
T(n) = T(n-1)+ 1/n if n>1 =1 otherwiseThe order of the algorithm is
User Avatar
1 votes
1 answer
2385
Algorithm
When s be a sorted array of n integers , and t(n) s the time taken for the most efficient algorithm to determine if there are 2 elements with sum less than 1000 in s, then which of the following statements is true? t(n) is O(1) n<=t(n)<= n logn n logn<= t(n) <(n/2) t(n) =(n/2)
When s be a sorted array of n integers , and t(n) s the time taken for the most efficient algorithm to determine if there are 2 elements with sum less than 1000 in s, the...
User Avatar
1 votes
1 answer
2386
Calculate the time complexity
Let f(n) = Ω(n), g(n) = O(n) and h(n) = θ(n). Then [f(n) ⋅ g(n)] + h(n) is _______.
Let f(n) = Ω(n), g(n) = O(n) and h(n) = θ(n). Then [f(n) ⋅ g(n)] + h(n) is _______.
User Avatar
1 votes
2 answers
2387
Recurrence Relation
T(n) = T(n-1) + T(n-2) + c i want solve it using substitution method.. T(n) <= 2 T(n-1) + c is this a correct way ?? plz explain ... if its wrong then what is correct way
T(n) = T(n-1) + T(n-2) + c i want solve it using substitution method..T(n) <= 2 T(n-1) + c is this a correct way ??plz explain ...if its wrong then what is correct w...
User Avatar
1 votes
0 answers
2389
dynamic programming
https://gateoverflow.in/?qa=blob&qa_blobid=11412484315430083479
https://gateoverflow.in/?qa=blob&qa_blobid=11412484315430083479
User Avatar
1 votes
1 answer
2390
Finding time complexity of Dynamic programming problem
The answer to the above problem is A but I am expecting it to be D as constant amount of work is required to solve each subproblem.
The answer to the above problem is A but I am expecting it to be D as constant amount of work is required to solve each subproblem.
User Avatar
Page: