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}}}$$

Recent questions in Algorithms

0 votes

1 answer

121

Consider performing QuickSort on an array of n distinct elements. What is the probability that no comparisons will be made between the smallest and largest element?

Consider performing QuickSort on an array of n distinct elements. What is the probability that no comparisons will be made between the smallest and largest element?a. 1/n...

dhruba

449 views

dhruba asked Jun 5, 2023

1 votes

1 answer

122

Suppose a BST is converted into an AVL tree. Which of the following statements is correct?
Suppose a BST is converted into an AVL tree. Which of the following statements is correct? a. The in-order traversal of the AVL tree and the BST will be the same. b. The pre-order traversal of the AVL tree and ... c. The post-order traversal of the AVL tree and the BST will be the same. d. None of the above.

Suppose a BST is converted into an AVL tree. Which of the following statements is correct?a. The in-order traversal of the AVL tree and the BST will be the same.b. The pr...

dhruba

602 views

dhruba asked Jun 5, 2023

0 votes

2 answers

123

Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). How many comparisons are needed in the worst case scenario to determine that the key is not in the array?

Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...

dhruba

1.2k views

dhruba asked Jun 5, 2023

1 votes

1 answer

124

Output Of C Program
#include<stdio.h> int main(){ int x,sum; sum=0; for(x=0;x<=500;x+=10){ sum=sum+x; } printf("%d",sum); return 0; } What is output of above C-program? Actually, Answer when compiled on computer is 12750. But i want explanation about How for loop is running and what is behaviour of sum value ?

#include<stdio.h>int main(){ int x,sum; sum=0; for(x=0;x<=500;x+=10){ sum=sum+x; } printf("%d",sum); return 0;} What is output of above C-program...

ShubhamMeher

471 views

ShubhamMeher asked Jun 1, 2023

0 votes

1 answer

125

Consider a divide and conquer algorithm that divides an input of size n into a subproblems, each of size n/b, and the cost of dividing and merging the problems is given by f(n) = Θ(n^c). The Master Theorem classifies this into different cases based on the value of c in relation to log_b(a). Could you explain the intuition and reasoning behind these classifications?

Consider a divide and conquer algorithm that divides an input of size n into a subproblems, each of size n/b, and the cost of dividing and merging the problems is given b...

dhruba

455 views

dhruba asked May 29, 2023

0 votes

1 answer

126

UGCNET CSE December 2022: 28
Consider the Graph below: How many spanning trees can be found? $10$ $5$ $9$ $8$ (Option $1 [39409]) 1$ (Option $2[39410]) 2$ (Option $3 [39411]) 3$ (Option $4 [39412]) 4$ Answer Given by Candidate : $2$

Consider the Graph below:How many spanning trees can be found?$10$$5$$9$$8$(Option $1 [39409]) 1$(Option $2[39410]) 2$(Option $3 [39411]) 3$(Option $4 [39412]) 4$Answer G...

admin

562 views

admin asked May 20, 2023

0 votes

0 answers

127

Algorithm

Çșȇ ʛấẗẻ

299 views

Çșȇ ʛấẗẻ asked May 11, 2023

0 votes

2 answers

128

Sort the following array using quicksort algorithm. [40,11,4,72,17,2,49]
Sort the following array using quicksort algorithm. [40,11,4,72,17,2,49]

Sort the following array using quicksort algorithm. [40,11,4,72,17,2,49]

Ajink123

565 views

Ajink123 asked May 10, 2023

0 votes

0 answers

129

(x+k)^m=O(x^m) is true or false for x and k being constants?

James_Gosling

242 views

James_Gosling asked Apr 24, 2023

0 votes

1 answer

130

Self Doubt
An adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin ... is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

An adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in th...

Psy Duck

383 views

Psy Duck asked Mar 29, 2023

4 votes

2 answers

131

GO Classes 2023 | IIITH Mock Test 1 | Question: 8
If we have an array of size $\mathrm{N}$ with only $3$ different values for its elements, what is the probability that the first partition results in a completely sorted array? Assume there are an equal number of each element in the array. $1 / 2$ $1 / 3$ $1 / 4$ $2 / 3$

If we have an array of size $\mathrm{N}$ with only $3$ different values for its elements, what is the probability that the first partition results in a completely sorted ...

GO Classes

872 views

GO Classes asked Mar 26, 2023

2 votes

1 answer

132

GO Classes 2023 | IIITH Mock Test 1 | Question: 9
Let $T(n)=4 T(n / 3)+n^{\log _{3} 4}.$ What will be asymptotic bound on $T(n)?$ $T(n)=\Theta\left(n^{\log _{3} 4} \log n\right)$ $T(n)=\Theta(n \log n)$ $T(n)=\Theta\left(4^{\log _{3} n} \log \log n\right)$ None of these

Let $T(n)=4 T(n / 3)+n^{\log _{3} 4}.$ What will be asymptotic bound on $T(n)?$$T(n)=\Theta\left(n^{\log _{3} 4} \log n\right)$$T(n)=\Theta(n \log n)$$T(n)=\Theta\left(4^...

GO Classes

618 views

GO Classes asked Mar 26, 2023

2 votes

1 answer

133

GO Classes 2023 | IIITH Mock Test 1 | Question: 10
$\text{G}$ is a directed graph with negative weight edges but NO negative weight cycles. Which of the following hold for Dijkstra's algorithm on $\text{G}:$ Dijkstra's algo will always give the correct output since there is no ... if we add large positive weight to every edge then it will work. Dijkstra's algo may not terminate in this case.

$\text{G}$ is a directed graph with negative weight edges but NO negative weight cycles. Which of the following hold for Dijkstra’s algorithm on $\text{G}:$Dijkstra’s...

GO Classes

744 views

GO Classes asked Mar 26, 2023

1 votes

2 answers

134

GO Classes 2023 | IIITH Mock Test 1 | Question: 11
Suppose that a MST of the following edge-weighted graph contains the edges with weights $x, y$, and $z$. What will be the maximum value of $x+y+z?$ $200$ $250$ $300$ $350$

Suppose that a MST of the following edge-weighted graph contains the edges with weights $x, y$, and $z$.What will be the maximum value of $x+y+z?$$200$$250$$300$$350$

GO Classes

977 views

GO Classes asked Mar 26, 2023

7 votes

1 answer

135

GO Classes 2023 | IIITH Mock Test 1 | Question: 12
A list of $n$ arrays, each of length $n$, is passed to an algorithm like merge-sort. The algorithm recursively divides a set of arrays into two parts until there are only two arrays. If there are two arrays, then, as a base case, the algorithm combines or merges both in cost of ... $T(n)=2 T(n / 2)+n$ $T(n)=2 T(n / 2)+n^ 3$ None of these

A list of $n$ arrays, each of length $n$, is passed to an algorithm like merge-sort. The algorithm recursively divides a set of arrays into two parts until there are only...

GO Classes

1.2k views

GO Classes asked Mar 26, 2023

3 votes

0 answers

136

GO Classes 2023 | IIITH Mock Test 1 | Question: 13
Arrange the following functions in their increasing order of growth. In options $\log ^{2} n$ means $(\log n)^{2}$ $\log (n !), \log ^{2} n, (\lg n) !, e^{n}$ $\log (n !), \log ^{2} n, e^{n}, (\lg n) !$ $\log ^{2} n, \log (n !), (\lg n) !, e^{n}$ $\log ^{2} n, (\lg n) !, \log (n !), e^{n}$

Arrange the following functions in their increasing order of growth. In options $\log ^{2} n$ means $(\log n)^{2}$$\log (n !), \log ^{2} n, (\lg n) !, e^{n}$$\log (n !)...

GO Classes

705 views

GO Classes asked Mar 26, 2023

2 votes

4 answers

137

GO Classes 2023 | IIITH Mock Test 1 | Question: 16
Consider a hash table of $9$ slots implemented with linear probing. Suppose we insert $2$ elements in a sequence to a hash table with a simple uniform hashing assumption. What is the probability that we end up with $2$ consecutive slots of the hash table filled? ... $1/2$ $1/3$ $1/4$ $2/3$

Consider a hash table of $9$ slots implemented with linear probing. Suppose we insert $2$ elements in a sequence to a hash table with a simple uniform hashing assumption....

GO Classes

956 views

GO Classes asked Mar 26, 2023

1 votes

1 answer

138

GO Classes 2023 | IIITH Mock Test 1 | Question: 43
Recall the Partition subroutine that we used in QuickSort. Suppose that the following array has just been partitioned around some pivot element $: 3,1,2,4,5,8,7,6,9.$ Which of these element(s) could have been the pivot element? $4$ $5$ $2$ $9$

Recall the Partition subroutine that we used in QuickSort. Suppose that the following array has just been partitioned around some pivot element $: 3,1,2,4,5,8,7,6,9.$Whic...

GO Classes

904 views

GO Classes asked Mar 26, 2023

2 votes

1 answer

139

GO Classes 2023 | IIITH Mock Test 1 | Question: 45
Assume you have two positive functions $f$ and $g$ such that $f(n)$ is in $O(g(n))$. For each of the following statements, decide which one(s) is/are always TRUE. $2^{f(n)}$ is $O\left(2^{g(n)}\right)$ $f(n)^{2}$ is $O\left(g(n)^{2}\right)$ $f(n)=O\left((f(n))^{2}\right)$ $g(n)=\Omega(g(n))$

Assume you have two positive functions $f$ and $g$ such that $f(n)$ is in $O(g(n))$. For each of the following statements, decide which one(s) is/are always TRUE.$2^{f(n)...

GO Classes

862 views

GO Classes asked Mar 26, 2023

6 votes

1 answer

140

GO Classes 2023 | IIITH Mock Test 1 | Question: 50
For which of the following functions $f(n)$ and $g(n),$ it holds $:f(n)=O(g(n)).$ Every $\log$ below is base $2.$ $f(n)=2^{k \log n}\;, \quad g(n)=n^k$ $f(n)=2^n\;, \quad g(n)=2^{2 n}$ ... $f(n)=2^{\sqrt{\log n}}\;, \quad g(n)= (\log n)^{100}$

For which of the following functions $f(n)$ and $g(n),$ it holds $:f(n)=O(g(n)).$ Every $\log$ below is base $2.$$f(n)=2^{k \log n}\;, \quad g(n)=n^k$$f(n)=2^n\;, \quad g...

GO Classes

958 views

GO Classes asked Mar 26, 2023

Page:

« prev
1
2
3
4
5
6
7
8
9
10
11
12
...
242
next »

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true