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

#3681
534
views
1 answers
1 votes
CMI2014-B-03
$\text{Air CMI }$operates direct flights between different cities. For any pair of cities $A$ and $B$, there is at most one flight in a day ... all connections are feasible within the same day. Analyze the complexity of your algorithm.
User Avatar
#3682
710
views
1 answers
1 votes
CMI2014-A-04
Alan's task is to design an algorithm for a decision problem $P$. He knows that there is an algorithm $A$ that transforms instances of $P$ to instances of the ... there is an algorithm for $P$.The Halting Problem can be solved using $A$.
User Avatar
#3683
990
views
3 answers
3 votes
CMI2014-A-03
In the code fragment on the right, start and end are integer values and $\text{prime}(x)$ is a function that returns true if $x$ is a prime number and $\text{false}$ otherwise ... $k > i+j$Depends on $\text{start}$ and $\text{end}$
User Avatar
#3684
2.2k
views
2 answers
3 votes
Difference between Depth first traversal and Depth first search
DFS is done for a graph.So we need a visited array to keep track of cycles.Do we need visited array for DFT of a tree?What is the basic difference between traversal and search ?
User Avatar
#3685
1.1k
views
1 answers
1 votes
Order statistics problem
Does this question makes sense to you? Its asked in algorithms section. Though quick googling says its all about statistics. Or I am making mistake and it is indeed part of Algorithms? Is it ... ) (C) O(n log n) (D) None of these
User Avatar
#3686
19.1k
views
1 answers
4 votes
T(n)=2T(floor(sqrt(n))+log n
the solution of recurrence relationT(n)=2T(floor(sqrt(n))+log n
User Avatar
#3687
2.2k
views
1 answers
0 votes
T(n)=mT(n/2)+an^2
User Avatar
#3688
1.2k
views
3 answers
1 votes
why the time complexity is O(n) not O(nlogn)?
int fun(int n){ int count = 0; for (int i = n; i > 0; i /= 2) for (int j = 0; j < i; j++) count += 1; return count; }then this function should give O(nlogn).since outer loop run O(logn) timeinner loop O(n) time
User Avatar
#3689
2.9k
views
2 answers
3 votes
what is the time complexity ?
sum=0; for(i=0;i<n;i++) for(j=0;j<i*i;j++) for(k=0;k<j;k++) sum++;
User Avatar
#3690
1.2k
views
3 answers
4 votes
CMI2013-B-07
Consider the code below, defining the function $\text{mystery}:$mystery(a,b){ if (a < 0 or b < 0) return 0; else if (a == 0) return b+1; else if (b == 0) ... a function of $n$.Compute $\text{mystery}(3, \:2)$ and $\text{mystery}(3, 3)$.
User Avatar
#3691
1.0k
views
2 answers
1 votes
CMI2013-B-06a
Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world ... time of the current match? Analyze the worse-case complexity of your algorithm.
User Avatar
#3692
448
views
1 answers
3 votes
CMI2013-B-05
You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you ... algorithm for the problem and analyze the worst-case complexity of your algorithm.
User Avatar
#3693
987
views
1 answers
7 votes
CMI2013-B-04
You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$-th smallest element in the union of the two lists in time $O(\log m + \log n)$.
User Avatar
#3694
1.4k
views
3 answers
6 votes
CMI2013-A-10
The below question is based on following program:procedure mystery (A : array [1..100] of int) int i,j,position,tmp; begin for j := 1 to 100 do position := ... $100$5050$10000$Depends on contents of $A$
User Avatar
#3695
1.2k
views
3 answers
9 votes
CMI2013-A-09
The below question is based on the following program.procedure mystery (A : array [1..100] of int) int i,j,position,tmp; begin for ... , the array A has been:ReversedLeft unalteredSorted in descending orderSorted in ascending order
User Avatar
#3696
7.0k
views
5 answers
32 votes
CMI2013-A-05
You have $n$ lists, each consisting of $m$ integers sorted in ascending order. Merging these lists into a single sorted list will take time:$O(nm \log m)$O(mn \log n)$O(m + n)$O(mn)$
User Avatar
#3697
2.8k
views
1 answers
1 votes
What is the time complexity of Binary Knapsack?
I was reading some of the notes (made easy and ACE) and noticed that some teacher have taught that time complexity for Binary Knapsack O(2^(n/2)) ... something. Should I stop seeing those notes which people have posted over the internet.
User Avatar
#3698
1.5k
views
0 answers
1 votes
CMI2012-B-06
A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes ... are in the interior of the string so each split is non-trivial.
User Avatar
#3699
511
views
1 answers
1 votes
CMI2012-B-05a
Given an undirected weighted graph $G = (V, E)$ with non-negative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also ... if the statement is false.$T$ is still a minimum cost spanning tree of $G$.
User Avatar
#3700
1.2k
views
1 answers
1 votes
CMI2012-B-04
You have an array $A$ with $n$ objects, some of which are identical. You can check if two objects are equal but you cannot compare them in any other way - i.e., ... with an $O(n \log n)$ algorithm to determine if $A$ has a majority element.
User Avatar
Page: