Recent questions in Algorithms

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.

$$\small{\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}}}$$

Recent questions in Algorithms

+2 votes

5 answers

1

126 views

NIELIT 2016 MAR Scientist B - Section C: 12
Which of the following sorting algorithms does not have a worst case running time of $O(n^2)$ ? Insertion sort. Merge sort. Quick sort. Bubble sort.

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 126 views

0 votes

0 answers

2

43 views

NIELIT 2016 MAR Scientist B - Section C: 19
If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is in P NP both (A) and (B) None of these

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 43 views

0 votes

2 answers

3

56 views

NIELIT 2016 MAR Scientist B - Section C: 22
Time complexity of an algorithm $T(n)$, where n is the input size is given by $\begin{array}{}&\text{T(n)}&=T(n-1)+1/n, \text{if n>1}\\ & & =1, otherwise \end{array}$ The order of this algorithm is $\log n$ $n$ $n^2$ $n^n$

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 56 views

0 votes

0 answers

4

25 views

NIELIT 2016 DEC Scientist B (IT) - Section B: 5
Two alternative packages A and B are available for processing a database having $10k$ records. Package A requires $0.0001n2$ time units and package B requires $10nlog10n$ time units to process $n$ records. What is the smallest value of $k$ for which package B will be preferred over A? $12$ $10$ $6$ $5$

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 25 views

0 votes

1 answer

5

32 views

NIELIT 2016 DEC Scientist B (IT) - Section B: 7
What is the type of the algorithm used in solving the $4$ Queens problem? Greedy Branch and bound Dynamic Programming Backtracking

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 32 views

0 votes

2 answers

6

27 views

NIELIT 2016 DEC Scientist B (IT) - Section B: 8
Selection sort,quick sort is a stable sorting method True,True False,False True,False False,True

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 27 views

0 votes

0 answers

7

19 views

NIELIT 2016 DEC Scientist B (IT) - Section B: 12
Which of the following sorting procedures is the slowest? Quick Sort Merge Sort Shell Sort Bubble Sort

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 19 views

0 votes

1 answer

8

26 views

NIELIT 2016 DEC Scientist B (IT) - Section B: 16
The recurrence relation capturing the optimal execution time of the towers of Hanoi problem with n discs is: T(n)=2T(n-2)+2 T(n)=2T(n/2)+1 T(n)=2T(n-1)+n T(n)=2T(n-1)+1

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 26 views

0 votes

0 answers

9

21 views

NIELIT 2016 DEC Scientist B (IT) - Section B: 27
Complexity of Kruskal's algorithm for finding minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is: $O(mn)$ $O(m)$ $O(m+n)$ $O(n)$

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 21 views

0 votes

0 answers

10

24 views

NIELIT 2016 DEC Scientist B (IT) - Section B: 52
Find the odd one out Merge Sort TVSP Problem Knapsack Problem OBST Problem

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 24 views

0 votes

1 answer

11

24 views

NIELIT 2016 DEC Scientist B (CS) - Section B: 7
The Knapsack problem belongs to which domain of problems? Optimization. NP complete. Linear Solution. Sorting.

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 24 views

0 votes

1 answer

12

30 views

NIELIT 2016 DEC Scientist B (CS) - Section B: 12
The running time of quick sort algorithm depends heavily on the selection of: No. of inputs. Arrangement of elements in an array. Size of elements. Pivot element.

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 30 views

0 votes

1 answer

13

27 views

NIELIT 2016 DEC Scientist B (CS) - Section B: 16
Two main measures for the efficiency of an algorithm are: Processor and Memory. Complexity and Capacity. Time and Space. Data and Space.

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 27 views

0 votes

1 answer

14

34 views

NIELIT 2016 DEC Scientist B (CS) - Section B: 27
What is the solution to the recurrence $T(n)=T(\frac{n}{2})+n$? $O(\log n)$ $O(n)$ $O(n\log n)$ None of these

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 34 views

0 votes

0 answers

15

18 views

NIELIT 2016 DEC Scientist B (CS) - Section B: 52
The concept of order Big O is important because: It can be used to decide the best algorithm that solves a given problem It is the lower bound of the growth rate of algorithm It determines the maximum size of a problem that can be solved in a given amount of time Both (A) and (B)

asked Mar 31 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 18 views

0 votes

1 answer

16

18 views

NIELIT 2017 July Scientist B (IT) - Section B: 59
What is the running time of the following function(specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$

asked Mar 30 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 18 views

0 votes

1 answer

17

17 views

NIELIT 2017 July Scientist B (IT) - Section B: 60
$0/1$-Knapsack is a well known problem where, it is desired to get the maximum total profit by placing n items(each item is having some weight and associated profit) into a knapsack of capacity $W$. The table given below shows the weights and ... \text{11}\\\hline\text{5}&\text{8}&\text{18} \\\hline\end{array}$$ $19$ $18$ $17$ $20$

asked Mar 30 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 17 views

0 votes

1 answer

18

25 views

NIELIT 2017 July Scientist B (CS) - Section B: 9
The worst case running times of insertion sort, merge sort and quick sort respectively are $\Theta(nlogn),\Theta(nlogn)\:and\:\Theta(n^2)$ $\Theta(n^2),\Theta(n^2)\:and\:\Theta(nlogn)$ $\Theta(n^2),\Theta(nlogn)\:and\:\Theta(nlogn)$ $\Theta(n^2),\Theta(nlogn)\:and\:\Theta(n^2)$

asked Mar 30 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 25 views

0 votes

1 answer

19

20 views

NIELIT 2017 July Scientist B (CS) - Section B: 39
Which of the following standard algorithms is not Dynamic Programming based? Bellman-Ford Algorithm for single source shortest path Floyd Warshall Algorithm for all pairs shortest paths $0-1$ Knapsack problem Prim’s Minimum Spanning Tree

asked Mar 30 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 20 views

0 votes

0 answers

20

18 views

NIELIT 2017 July Scientist B (CS) - Section B: 41
Four Matrices $M_1, M_2, M_3$ and $M_4$ of dimensions $ p \times q, \:\:q \times r, \:\:r \times s$ and $s \times t$ respectively can be multiplied in several ways with different number of total scalar multiplications. For ... 10, q=100, r=20, s=5$ and $t=80$, then the number of scalar multiplications needed is $248000$ $44000$ $19000$ $25000$

asked Mar 30 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 18 views

0 votes

0 answers

21

19 views

NIELIT 2017 July Scientist B (CS) - Section B: 42
Let $G$ be a graph with $n$ vertices and $m$ edges.What is the tightest upper bound on the running time of Depth First Search of $G$, when $G$ is represented as an adjacency matrix? $O(n)$ $O(m+n)$ $O(n^2)$ $O(mn)$

asked Mar 30 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 19 views

0 votes

0 answers

22

12 views

NIELIT 2017 July Scientist B (CS) - Section B: 55
Suppose $T(n)=2T(n/2)+n$, $T(0)=T(1)=1$ which one of the following is false? $T(n)=O(n^2)$ $T(n)=\Theta(n\log n)$ $T(n)=\Omega(n^2)$ $T(n)=O(n\log n)$

asked Mar 30 in Algorithms by Lakshman Patel RJIT Veteran (63.1k points) 12 views

0 votes

2 answers

23

35 views

UGCNET-Dec2006-II: 21
Which algorithm has same average, worst case and best case time ? Binary search. Maximum of n number. Quick sort. Fibonacci search.

asked Mar 27 in Algorithms by jothee Veteran (109k points) 35 views

0 votes

2 answers

24

39 views

UGCNET-Dec2006-II: 22
Binary search tree is an example of : Divide and conquer technique. Greedy algorithm. Back tracking. Dynamic Programming.

asked Mar 27 in Algorithms by jothee Veteran (109k points) 39 views

0 votes

1 answer

25

36 views

UGCNET-Dec2004-II: 25
How much extra space is used by heapsort ? $O (1)$ $O (\log n)$ $O (n)$ $O (n^2)$

asked Mar 26 in Algorithms by jothee Veteran (109k points) 36 views

+3 votes

4 answers

26

2.2k views

GATE2020-CS-2
For parameters $a$ and $b$, both of which are $\omega(1)$, $T(n) = T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is $\Theta (\log_a \log _b n)$ $\Theta (\log_{ab} n$) $\Theta (\log_{b} \log_{a} \: n$) $\Theta (\log_{2} \log_{2} n$)

asked Feb 12 in Algorithms by Arjun Veteran (436k points) 2.2k views

+1 vote

3 answers

27

1.2k views

GATE2020-CS-6
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially? $\Theta (n^{4})$ $\Theta (n^{2})$ $\Theta (n^{2}\log n)$ $\Theta (n^{3})$

asked Feb 12 in Algorithms by Arjun Veteran (436k points) 1.2k views

+3 votes

2 answers

28

1.5k views

GATE2020-CS-23
Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Assume that the table size is $23$. Then the address returned by probe $1$ in the probe sequence (assume that the probe sequence begins at probe $0$) for key value $k=90$ is_____________.

asked Feb 12 in Algorithms by Arjun Veteran (436k points) 1.5k views

+3 votes

3 answers

29

1.7k views

GATE2020-CS-31
Let $G = (V, G)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighed edge $(u, v) \in V \times V$ is added to $G$. The worst case time complexity of determining if $T$ is still an MST of the resultant ... (\mid E \mid \mid V \mid) \\$ $\Theta(E \mid \log \mid V \mid) \\$ $\Theta( \mid V \mid)$

asked Feb 12 in Algorithms by Arjun Veteran (436k points) 1.7k views

+8 votes

4 answers

30

1.9k views

GATE2020-CS-40
Let $G = (V,E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$. For some function $f: V \rightarrow \mathbb{R}$, for each edge$(u,v)\in E$, define ${w}'(u,v)$ as $w(u,v)+f(u)-f(v)$. Which one of the ... )$ is the distance from $s$ to $u$ in the graph obtained by adding a new vertex $s$ to $G$ and edges of zero weight from $s$ to every vertex of $G$

asked Feb 12 in Algorithms by Arjun Veteran (436k points) 1.9k views

Page:

1
2
3
4
5
6
...
147
next »

...