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{2024-1} & \textbf{2024-2} & \textbf{2023} & \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} & 1&2&2& 2 &3&2&1&2&3
\\\hline\textbf{2 Marks Count} &4&2&2& 2 &3&4&2&2.83&4
\\\hline\textbf{Total Marks} &9&6&6& 6 &9&10&\bf{6} & \bf{7.67}&\bf{10}\\\hline
\end{array}}}$$

Filter

Recent questions in Algorithms

#3621
1.8k
views
1 answers
0 votes
median of 5 elements
how to find median of 5 distinct values with only 6 comparisons?
User Avatar
#3622
13.1k
views
2 answers
3 votes
Complexity of T(sqrt(N)) + log N
User Avatar
#3623
341
views
0 answers
0 votes
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?
User Avatar
#3624
797
views
4 answers
3 votes
ISI2011-PCB-CS-3a
Solve the following recurrence ($n$ is a natural number):$T(n) = \begin{cases} 7T(n\div3)+n^2 & ;n>2 \\ 1 & ;n \leq 2. \end{cases}$
User Avatar
#3625
926
views
2 answers
2 votes
ISI2011-PCB-CS-2
You are given $k$ sorted lists, each containing $m$ integers in ascending order. Assume that (i) the lists are stored as singly-linked lists with one ... storage?Analyse the time complexity of your algorithm for each of the above two cases.
User Avatar
#3626
846
views
2 answers
3 votes
ISI2011-PCB-CS-1b
There are $n$ students of a class standing in a line. The students have to arrange themselves in ascending order on the basis of their roll numbers. This ... an expression for the number of swaps needed by your algorithm in the worst case.
User Avatar
#3627
462
views
0 answers
2 votes
ISI2011-PCB-A-4b
Consider the following intervals on the real line: $A_1 = (13.3, 18.3) \: A_3 = (8.3, 23.3) − A_1 \cup A_2$ ... ., your pseudo-code should calculate $i \in \{1, 2, 3, 4\}$ such that $x \in A_i$.
User Avatar
#3628
744
views
1 answers
1 votes
Time Complexity of iterative series
What should be the time complexity of : k=1; while (k<=n) do j=1; while (j<=k) do sum=sum+1; j=j+1; k=k*2;According to me:For K=1, j= 1 timefor K=2, j=2 ... on...Thus sum= 1+2+4+8....nThis is I think 2n+1-1So should the answer be O(2n) ?
User Avatar
#3629
1.6k
views
2 answers
10 votes
ISI2011-PCB-A-2a
Give a strategy to sort four given distinct integers $a, b, c, d$ in increasing order that minimizes the number of pairwise comparisons needed to sort any permutation of $a, b, c, d$.
User Avatar
#3630
492
views
0 answers
1 votes
ISI2012-PCB-CS-5a
Suppose you have the following three subroutines:$\text{max}(A, i, j)$: returns the index of the maximum among the set of consecutive elements $A[i, \dots, j]$ of the ... where $k = j − i$, and that for the third subroutine is $O(1)$.
User Avatar
#3631
2.1k
views
2 answers
0 votes
Find the Space complexity of following Code [Ace Gate Practice Booklet Vol-1 Page 127]
Find the time and Space complexity of code below : void fun(n) { if (n==1) then call A(); else { fun(n/2); fun(n/2); call B(n); } } Please note that B(n) takes ... $O(nlog(n))$But What will be space complexity ?
User Avatar
#3632
539
views
1 answers
1 votes
ISI2012-PCB-A-3
Given an array $A = \{a_1, a_2, \dots, a_n\}$ of unsorted distinct integers, write a program in pseudo-code for the following problem: given an integer $u$, ... of the array. You may use at most 5 extra variables apart from the array $A$.
User Avatar
#3633
547
views
1 answers
1 votes
State the true and False (Beautiful Problem)
I was surfing internet and I got this beautiful Problem, I thought i should post here.
User Avatar
#3634
3.1k
views
2 answers
1 votes
Analysis of code fragment to find time complexity [ACE Gate Practice Booklet Volume 1 Page 127 Question 32]
Consider the following c fragment : void DAA(n) { int i,j,k,x=0; for (i=1 ; i <=n ; i++) for (j=1 ; j <= i * i ; j++) { if ( j mod i == 0 ) for ... ; k <= j ; k++) x=x+10; } }Find the time complexity of above code in terms of input size n.
User Avatar
#3635
563
views
0 answers
1 votes
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$, ... .]
User Avatar
#3636
522
views
0 answers
1 votes
ISI2013-PCB-CS-3
Let $M$ be an $(n \times n)$ matrix where each element is a distinct positive integer. Construct another matrix $M'$ by permuting the rows and/or ... how much additional storage, other than the matrix itself, is required in your algorithm.
User Avatar
#3637
520
views
0 answers
2 votes
ISI2013-PCB-CS-2a
Draw a complete binary tree $T$ with $(N − 1)$ nodes where $N = 2^n$. Suppose each node in $T$ is a processor and each edge of $T$ is a physical link between two processors ... $i$ in $O(\log N + M)$ time.
User Avatar
#3638
1.1k
views
2 answers
0 votes
This statement is true or false about minimum spanning tree?
If average weight of a minimum spanning tree is Aavg.Then minimum spanning tree will have weight almost (n-1)Aavg, where n is no of vertices in the graph. It is true or false?why?
User Avatar
#3639
516
views
1 answers
0 votes
Asymptotics notations
It is true or false..(log n)! and (log log n)! are polynomially bounded?What does polynomially bounded means?
User Avatar
#3640
2.0k
views
2 answers
1 votes
What is the time complexity of the function?
void fun(int n, int k) { for (int i=1; i<=n; i++) { int p = pow(i, k); for (int j=1; j<=p; j++) { // Some O(1) work } }}
User Avatar
Page: