search
Log In

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{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&0&2&2&3&3&0&2&3
\\\hline\textbf{2 Marks Count}&2&4&2&3&2&3&2&2.7&4
\\\hline\textbf{Total Marks}&6&8&6&8&7&9&\bf{6}&\bf{7.3}&\bf{9}\\\hline
\end{array}}}$$

Most viewed questions in Algorithms

0 votes
5 answers
1
Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i of a binary tree is In the following answers, the operator '^' indicates power a) 2^i-1 b)2^i c)2^i+1 d)2^(i+1/2)
asked Jan 16, 2016 in Algorithms Akanksha Kesarwani 21.4k views
56 votes
14 answers
2
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
asked Sep 28, 2014 in Algorithms jothee 20.1k views
7 votes
1 answer
3
1. The number of swappings needed to sort the numbers: 8, 22, 7, 9, 31, 19, 5, 13 in ascending order using bubble sort is— (a) 11 (b) 12 (c) 13 (d) 14 I know how to solve it using straightforward method. What I did was to write every pass and check the swappings. But , it takes too much time. Is there any shortcut possible ?
asked Aug 2, 2015 in Algorithms worst_engineer 16.1k views
59 votes
15 answers
4
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________
asked Feb 12, 2016 in Algorithms Sandeep Singh 14.6k views
40 votes
8 answers
5
You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is $O(n^2)$ $O(n \log n)$ $\Theta(n\log n)$ $O(n^3)$
asked Sep 28, 2014 in Algorithms jothee 13.3k views
34 votes
13 answers
6
The number of possible min-heaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
asked Feb 14, 2018 in Algorithms gatecse 13k views
41 votes
15 answers
7
Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$
asked Jul 6, 2016 in Algorithms Arjun 13k views
11 votes
5 answers
8
Please tell me the complete steps how to solve this problem. $\Large T(n) = T ( \sqrt n )+ 1$
asked Jun 10, 2015 in Algorithms Jonathan Decosta 13k views
53 votes
10 answers
9
Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3 Half of the product of the $3$ consecutive integers. One-third of the product of the $3$ consecutive integers. One-sixth of the product of the $3$ consecutive integers. None of the above.
asked Sep 28, 2014 in Algorithms jothee 12.8k views
34 votes
6 answers
10
The average number of key comparisons required for a successful search for sequential search on $n$ items is $\frac{n}{2}$ $\frac{n-1}{2}$ $\frac{n+1}{2}$ None of the above
asked Oct 9, 2014 in Algorithms Kathleen 12.2k views
44 votes
8 answers
11
Consider the following recurrence: $ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$ Which one of the following is true? $ T(n)=\Theta (\log\log n)$ $ T(n)=\Theta (\log n)$ $ T(n)=\Theta (\sqrt{n})$ $ T(n)=\Theta (n)$
asked Sep 26, 2014 in Algorithms Rucha Shelke 12.2k views
50 votes
4 answers
12
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of $n$ $n^2$ $n \log n$ $n \log^2n$
asked Sep 19, 2014 in Algorithms Kathleen 11.8k views
68 votes
5 answers
13
The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is $\Theta(1)$ $\Theta(\sqrt{\log} n)$ $\Theta(\frac{\log n}{\log \log n})$ $\Theta(\log n)$
asked Sep 24, 2014 in Algorithms Arjun 11.6k views
80 votes
7 answers
14
$G=(V, E)$ is an undirected simple graph in which each edge has a distinct weight, and $e$ is a particular edge of $G$. Which of the following statements about the minimum spanning trees $(MSTs)$ of $G$ is/are TRUE? If $e$ is the lightest edge of some cycle in $G$, then ... heaviest edge of some cycle in $G$, then every MST of $G$ excludes $e$. I only. II only. Both I and II. Neither I nor II.
asked Feb 12, 2016 in Algorithms Sandeep Singh 11k views
54 votes
6 answers
15
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is $\Theta(n)$ $\Theta(\log n)$ $\Theta(\log^*n)$ $\Theta(1)$
asked Sep 12, 2014 in Algorithms Kathleen 10.9k views
40 votes
10 answers
16
A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is $O (n \log n) $ $ O(n^{2} \log n) $ $ O(n^{2} + \log n) $ $ O(n^{2}) $
asked Sep 26, 2014 in Algorithms gatecse 10.8k views
40 votes
4 answers
17
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
asked Feb 12, 2016 in Algorithms Sandeep Singh 10.7k views
63 votes
6 answers
18
The cube root of a natural number $n$ is defined as the largest natural number $m$ such that $(m^3 \leq n)$ . The complexity of computing the cube root of $n$ ($n$ is represented by binary notation) is $O(n)$ but not $O(n^{0.5})$ $O(n^{0.5})$ but not $O((\log n)^k)$ for any constant ... $m>0$ $O( (\log \log n)^k )$ for some constant $k > 0.5$, but not $O( (\log \log n)^{0.5} )$
asked Sep 2, 2014 in Algorithms Nishant T-rex 10.3k views
45 votes
6 answers
19
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap B-Tree
asked Sep 16, 2014 in Algorithms Rucha Shelke 10.3k views
47 votes
14 answers
20
Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure) $O(n \log \log n)$ $\Theta(n \log n)$ $\Omega(n \log n)$ $\Omega\left(n^{3/2}\right)$
asked Sep 15, 2014 in Algorithms gatecse 10.2k views
...