The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions and answers in Algorithms
+48
votes
9
answers
1
GATE200654
Given two arrays of numbers $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$ where each number is $0$ or $1$, the fastest algorithm to find the largest span $(i, j)$ such that $ a_{i}+a_{i+1}+\dots+a_{j}=b_{i}+b_{i+1}+\dots+b_{j}$ or report that ... $\Theta (n)$ time and space Takes $O(\sqrt n)$ time only if the sum of the $2n$ elements is an even number
answered
7 hours
ago
in
Algorithms
by
Zaman3027

7.9k
views
gate2006
algorithms
normal
algorithmdesign
timecomplexity
+25
votes
6
answers
2
GATE200751
Consider the following C program segment: int IsPrime (n) { int i, n; for (i=2; i<=sqrt(n);i++) if(n%i == 0) {printf("Not Prime \n"); return 0;} return 1; } Let $T(n)$ denote number of times the $for$ loop is executed by the program on input $n$. Which of the following ... $T(n) = O(n) \: \text{ and } T(n) = \Omega(\sqrt{n})$ None of the above
answered
1 day
ago
in
Algorithms
by
manikantsharma

4.7k
views
gate2007
algorithms
timecomplexity
normal
+4
votes
4
answers
3
TIFR2019A5
Asha and Lata play a game in which Lata first thinks of a natural number between $1$ and $1000$. Asha must find out that number by asking Lata questions, but Lata can only reply by saying Yes or no . Assume that Lata always tells the truth. What is the least ... within which she can always find out the number Lata has thought of? $10$ $32$ $100$ $999$ $\text{None of the above}$
answered
2 days
ago
in
Algorithms
by
arks

921
views
tifr2019
algorithmdesign
binarysearch
+43
votes
8
answers
4
GATE200651, ISRO201634
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)$
answered
3 days
ago
in
Algorithms
by
Jhaiyam

11.2k
views
algorithms
recurrence
isro2016
gate2006
+38
votes
5
answers
5
GATE200617
An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array solves it in linear time using a left to right pass of the array solves it in linear time using a right to left pass of the array solves it using divide and conquer in time $\Theta (n\log n)$ solves it in time $\Theta( n^2)$
answered
4 days
ago
in
Algorithms
by
Jhaiyam

4.9k
views
gate2006
algorithms
normal
algorithmdesign
+53
votes
6
answers
6
GATE200840
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)$
answered
5 days
ago
in
Algorithms
by
Asim Siddiqui 4

9.7k
views
gate2008
normal
algorithms
timecomplexity
+26
votes
6
answers
7
GATE19938.7
$\displaystyle \sum_{1\leq k\leq n} O(n)$, where $O(n)$ stands for order $n$ is: $O(n)$ $O(n^2)$ $O(n^3)$ $O(3n^2)$ $O(1.5n^2)$
answered
6 days
ago
in
Algorithms
by
Jahanvi Pritam

2.5k
views
gate1993
algorithms
timecomplexity
easy
+1
vote
3
answers
8
ISRO202065
Of the following sort algorithms, which has execution time that is least dependant on initial ordering of the input? Insertion sort Quick sort Merge sort Selection sort
answered
6 days
ago
in
Algorithms
by
immanujs

286
views
isro2020
algorithms
sorting
normal
+31
votes
3
answers
9
GATE2014313
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
answered
Jul 2
in
Algorithms
by
Abhishek_123

3.8k
views
gate20143
algorithms
graphalgorithms
numericalanswers
normal
+20
votes
7
answers
10
GATE201847
Consider the following undirected graph $G$: Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $G$ for this value of $x$ is ____.
answered
Jun 27
in
Algorithms
by
TheAnteamatter

6.1k
views
gate2018
algorithms
graphalgorithms
minimumspanningtrees
numericalanswers
+17
votes
3
answers
11
GATE2008IT45
For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree? $\text{(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)}$ ... $\text{(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)}$
answered
Jun 27
in
Algorithms
by
TheAnteamatter

3.9k
views
gate2008it
algorithms
graphalgorithms
spanningtree
normal
+17
votes
5
answers
12
GATE2014210
Consider the function func shown below: int func(int num) { int count = 0; while (num) { count++; num>>= 1; } return (count); } The value returned by func($435$) is ________
answered
Jun 26
in
Algorithms
by
Nandita Gautam

3.9k
views
gate20142
algorithms
identifyfunction
numericalanswers
easy
0
votes
4
answers
13
The maximum number of nodes on level i of a binary tree
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^i1 b)2^i c)2^i+1 d)2^(i+1/2)
answered
Jun 25
in
Algorithms
by
Musa

15.3k
views
binarytree
datastructures
+16
votes
7
answers
14
GATE199201,ix
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______
answered
Jun 25
in
Algorithms
by
TheAnteamatter

5.8k
views
gate1992
spanningtree
algorithms
timecomplexity
easy
+38
votes
8
answers
15
GATE2014314
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)$
answered
Jun 25
in
Algorithms
by
TheAnteamatter

11.1k
views
gate20143
algorithms
sorting
easy
+34
votes
5
answers
16
GATE2015245
Suppose you are provided with the following function declaration in the C programming language. int partition(int a[], int n); The function treats the first element of $a[\:]$ as a pivot and rearranges the array so that all elements less than or equal to the pivot is in the left part of the ... $(a, $ left_end$, k)$ $(a, n$left_end$1, k$left_end$1)$ and $(a, $left_end$, k)$
answered
Jun 25
in
Algorithms
by
TheAnteamatter

5.2k
views
gate20152
algorithms
normal
sorting
+2
votes
9
answers
17
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.
answered
Jun 18
in
Algorithms
by
vivekkumar11112

297
views
nielit2016marscientistb
0
votes
2
answers
18
Cormen Edition 3 Exercise 9.1 Question 1 (Page No. 215)
Show that the second smallest of $n$ elements can be found with $n+\lceil lg\ n \rceil 2$ comparisons in the worst case. (Hint: Also find the smallest element.)
answered
Jun 18
in
Algorithms
by
debasish paramanik

50
views
cormen
algorithms
descriptive
+1
vote
4
answers
19
Binary Search
There are two sorted list each of length n. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons required using binary search and find its time complexity?
answered
Jun 17
in
Algorithms
by
Ameena667

326
views
datastructures
binarysearch
+37
votes
8
answers
20
GATE2017148
Let $A$ be an array of $31$ numbers consisting of a sequence of $0$'s followed by a sequence of $1$'s. The problem is to find the smallest index $i$ such that $A\left [i \right ]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is ____________.
answered
Jun 17
in
Algorithms
by
TheAnteamatter

6.6k
views
gate20171
algorithms
normal
numericalanswers
searching
+33
votes
10
answers
21
GATE2017238
Consider the following C function int fun(int n) { int i, j; for(i=1; i<=n; i++) { for (j=1; j<n; j+=i) { printf("%d %d", i, j); } } } Time complexity of $fun$ in terms of $\Theta$ notation is $\Theta(n \sqrt{n})$ $\Theta(n^2)$ $\Theta(n \: \log n)$ $\Theta(n^2 \log n)$
answered
Jun 17
in
Algorithms
by
TheAnteamatter

6.4k
views
gate20172
algorithms
timecomplexity
+5
votes
3
answers
22
Selfdoubt
Which of the following is exact recurrence relation for binary search (in terms of number of comparisons) ? 1. T(n) = 2T(n/2) + 1 2. T(n) = 2T(n/2) + 2 Please specify relevant reasons.
answered
Jun 15
in
Algorithms
by
Kirti11

544
views
binarysearch
+3
votes
2
answers
23
Algorithms : Binary search vs ternary search
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both
answered
Jun 15
in
Algorithms
by
Kirti11

730
views
binarysearch
datastructures
algorithms
+2
votes
6
answers
24
Searching
Q) Consider a sorted array of n numbers. What would be the time complexity of the best known algorithm to find a pair a and b such that ab = k , k being a positive integer. a) O(logn) b) O(n) c)O(nlogn) d)O(n^2) Which of the option is Correct And Why?
answered
Jun 15
in
Algorithms
by
Kirti11

1.5k
views
algorithms
sorting
timecomplexity
binarysearch
+6
votes
3
answers
25
GATE2020CS23
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_____________.
answered
Jun 14
in
Algorithms
by
Kirti11

2k
views
gate2020cs
numericalanswers
algorithms
hashing
0
votes
2
answers
26
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)$
answered
Jun 10
in
Algorithms
by
rahul_6

129
views
nielit2017julyscientistbit
timecomplexity
algorithms
0
votes
1
answer
27
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)
answered
Jun 10
in
Algorithms
by
Ollie

56
views
nielit2016decscientistbcs
+25
votes
3
answers
28
GATE200584a
We are given $9$ tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before the end ... maximum profit? All tasks are completed $T_1$ and $T_6$ are left out $T_1$ and $T_8$ are left out $T_4$ and $T_6$ are left out
answered
Jun 8
in
Algorithms
by
Gaurav Yadav

3.5k
views
gate2005
algorithms
greedyalgorithm
processschedule
normal
+34
votes
10
answers
29
GATE200369
The following are the starting and ending times of activities $A, B, C, D, E, F, G$ and $H$ ... in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required? $3$ $4$ $5$ $6$
answered
Jun 8
in
Algorithms
by
Gaurav Yadav

4.1k
views
gate2003
algorithms
normal
greedyalgorithm
+40
votes
7
answers
30
GATE200845
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to only vertex $a$ only vertices $a, e, f, g, h$ only vertices $a, b, c, d$ all the vertices
answered
Jun 7
in
Algorithms
by
Gaurav Yadav

7.6k
views
gate2008
algorithms
graphalgorithms
normal
+1
vote
2
answers
31
Made Easy Test Series
What is worst case time complexity to delete middle element from the min heap of n distinct elements? O(logn) O(n) O(nlogn) O($n^{2}$)
answered
Jun 6
in
Algorithms
by
aritraforgate

436
views
+30
votes
4
answers
32
GATE201137
Which of the given options provides the increasing order of asymptotic complexity of functions $f_1, f_2, f_3$ and $f_4$? $f_1(n) = 2^n$ $f_2(n) = n^{3/2}$ $f_3(n) = n \log_2 n$ $f_4(n) = n^{\log_2 n}$ $f_3, f_2, f_4, f_1$ $f_3, f_2, f_1, f_4$ $f_2, f_3, f_1, f_4$ $f_2, f_3, f_4, f_1$
answered
Jun 2
in
Algorithms
by
Gaurav Yadav

3.2k
views
gate2011
algorithms
asymptoticnotations
normal
0
votes
1
answer
33
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 using adjacency matrix? $O(n)$ $O(m+n)$ $O(n^2)$ $O(mn)$
answered
Jun 1
in
Algorithms
by
Mohit Kumar 6

53
views
nielit2017julyscientistbcs
0
votes
3
answers
34
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}{ll}T(n) & =T(n1)+1/n, \text{ if }n>1\\ & =1, \text{ otherwise} \end{array}$ The order of this algorithm is $\log n$ $n$ $n^2$ $n^n$
answered
May 30
in
Algorithms
by
Anup dogrial

119
views
nielit2016marscientistb
0
votes
1
answer
35
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)$
answered
May 29
in
Algorithms
by
Mohit Kumar 6

61
views
nielit2016decscientistbit
0
votes
1
answer
36
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 $10 n \log 10n$ 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$
answered
May 29
in
Algorithms
by
Mohit Kumar 6

66
views
nielit2016decscientistbit
+1
vote
1
answer
37
Cormen Edition 3 Exercise 22.2 Question 7 (Page No. 539)
There are two types of professional wrestlers: babyfaces ( good guys ) and heels ( bad guys ). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we ... between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it.
answered
May 28
in
Algorithms
by
satya753

124
views
cormen
graphalgorithms
bfs
descriptive
0
votes
1
answer
38
NIELIT 2016 DEC Scientist B (IT)  Section B: 52
Find the odd one out Merge Sort TVSP Problem Knapsack Problem OBST Problem
answered
May 28
in
Algorithms
by
Mohit Kumar 6

62
views
nielit2016decscientistbit
0
votes
1
answer
39
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
answered
May 27
in
Algorithms
by
Mohit Kumar 6

58
views
nielit2016decscientistbit
0
votes
1
answer
40
NIELIT 2016 MAR Scientist B  Section C: 19
If there is in NPComplete 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
answered
May 26
in
Algorithms
by
Mohit Kumar 6

100
views
nielit2016marscientistb
To see more, click for all the
questions in this category
.
Quick search syntax
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
Recent Posts
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
2k
Engineering Mathematics
8.2k
Digital Logic
2.9k
Programming and DS
5k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.2k
Operating System
4.6k
Databases
4.2k
CO and Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.2k
Others
1.5k
Admissions
595
Exam Queries
562
Tier 1 Placement Questions
23
Job Queries
71
Projects
19
Unknown Category
1k
Recent questions and answers in Algorithms
Recent Blog Comments
@toxicdesire I don't remember the exact...
Will you please tell what they answered to your...
@commenter max marks for part A was 75. They did...
Hope you get selected bhaiya
Can someone tell me how to check part B marks?...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,501
answers
201,879
comments
95,329
users