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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged searching
0
votes
1
answer
1
Cormen Edition 3 Exercise 2.3 Question 6 (Page No. 39)
Observe that the while loop of the INSERTIONSORT procedure uses a linear search to scan (backward) through the sorted subarray $A[i\dots j1]$ Can we use a binary search (see Exercise 2.35) instead to improve the overall worstcase running time of insertion sort to $\Theta(n\ lg\ n)$?
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

14
views
algorithms
cormen
searching
descriptive
0
votes
0
answers
2
Cormen Edition 3 Exercise 2.3 Question 5 (Page No. 39)
Referring back to the searching problem (see Exercise 2.13), observe that if the sequence $A$ is sorted, we can check the midpoint of the sequence against $v$ and eliminate half of the sequence from further consideration. The binary ... recursive, for binary search. Argue that the worstcase running time of binary search is $\Theta (lg\ n)$.
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

7
views
cormen
algorithms
searching
descriptive
0
votes
1
answer
3
Cormen Edition 3 Exercise 2.2 Question 3 (Page No. 29)
Consider the linear search again (see Exercise 2.13). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? ... case? What are the averagecase and worstcase running times of linear search in notation? Justify your answers.
asked
Jun 25
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

19
views
cormen
algorithms
searching
descriptive
0
votes
0
answers
4
Cormen Edition 3 Exercise 2.1 Question 3 (Page No. 22)
Consider the searching problem: Input: A sequence of $n$ numbers $A = \langle a_1, a_2,\dots a_n \rangle$ and a value $v$ Output: An index $i$ such that $v=A[i]$ or the special value NIL if $v$ does ... $v$. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
asked
Jun 25
in
Algorithms
by
akash.dinkar12
Boss
(
41.7k
points)

12
views
cormen
algorithms
searching
descriptive
+2
votes
1
answer
5
Vani Qs Bank Algorithms
.Given an array of distinct integers A[1, 2,…n]. Find the tightest upper bound to check the existence of any index i for which A[i]=i. Ans should be O(log n) right by doing binary search ??
asked
May 21
in
Algorithms
by
Hirak
Active
(
3.5k
points)

173
views
algorithms
datastructure
arrays
searching
+2
votes
0
answers
6
Algorithm Searching
Which is faster and by how much, a linear search of only 1000 elements on a 5GHz computer or a binary search of 1 million elements on a 1GHz computer. Assume that the execution of each instruction on the 5GHz computer is five times ... 1GHz computer and that each iteration of the linear search algorithm is twice as fast as each iteration of the binary search algorithm.
asked
Sep 23, 2018
in
Algorithms
by
Vaishnavi01
(
143
points)

38
views
algorithms
searching
0
votes
0
answers
7
Better Algorithm for aggregating data from LDAP Systems
This question is not related to GATE, but certainly would help you to grill your mind to come up with a better approach.. Feel free to comment if you think, this is not a right forum for this question. I have 10 ... format cannot be changed as there is dependency with other downstream systems. Is there a better approach to achieve the same ?
asked
May 14, 2018
in
Programming
by
Arunav Khare
Loyal
(
5.5k
points)

87
views
algorithms
searching
0
votes
1
answer
8
Uttrakhand Asst. Professor Exam19
Which of the following search method takes less memory ? Depthfirst search Breadthfirst search Linear search None of the above
asked
Mar 2, 2018
in
Others
by
gatecse
Boss
(
16.3k
points)

61
views
uttarakhandasstprof2018
datastructure
searching
+3
votes
1
answer
9
Ace Test Series: Algorithms  Searching
asked
Nov 23, 2017
in
Algorithms
by
saxena0612
Boss
(
11.7k
points)

467
views
binarysearch
algorithms
acetestseries
searching
+32
votes
6
answers
10
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 ____________.
asked
Feb 14, 2017
in
Algorithms
by
Arjun
Veteran
(
421k
points)

5.2k
views
gate20171
algorithms
normal
numericalanswers
searching
0
votes
0
answers
11
MadeEasy Advance Test Series: Algorithm  Searching
can someone provide me the detailed description for this answer?
asked
Feb 1, 2017
in
Algorithms
by
S Ram
Active
(
1.7k
points)

67
views
madeeasytestseries
algorithms
searching
+2
votes
3
answers
12
UGCNETDec2014III56
An $A^{*}$ algorithm is a heuristic search technique which Is like a depthfirst search where most promising child is selected for expansion Generates all successor nodes and computes an estimate of distance (cost) from start node to a goal node ... path lengths (costs) from start node to all generated nodes and chooses shortest path for further expansion. None of the above
asked
Jul 30, 2016
in
Others
by
makhdoom ghaya
Boss
(
29.8k
points)

655
views
ugcnetdec2014iii
artificialintelligence
searching
+16
votes
3
answers
13
GATE200885
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int u, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) & ... to: if $(Y[k] < x) i = k$; else $j = k$; Change line 7 to: } while $((Y[k] == x) \&\& (i < j))$ ;
asked
Apr 23, 2016
in
Algorithms
by
jothee
Veteran
(
103k
points)

1.7k
views
gate2008
algorithms
searching
normal
+15
votes
3
answers
14
TIFR2012B11
Consider the following three version of the binary search program. Assume that the elements of type $T$ can be compared with each other; also assume that the array is sorted. i, j, k : integer; a : array [1....N] of T; x : T; Program 1 : i := 1; j ... Only Program $2$ is correct Only Program $1$ and $2$ are correct. Both Program $2$ and $3$ are correct All the three programs are wrong
asked
Nov 1, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
29.8k
points)

554
views
tifr2012
algorithms
searching
+20
votes
1
answer
15
TIFR2010B29
Suppose you are given an array $A$ with $2n$ numbers. The numbers in odd positions are sorted in ascending order, that is, $A[1] \leq A[3] \leq \ldots \leq A[2n  1]$. The numbers in even positions are sorted in descending order, ... search on the entire array. Perform separate binary searches on the odd positions and the even positions. Search sequentially from the end of the array.
asked
Oct 6, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
29.8k
points)

893
views
tifr2010
searching
+14
votes
2
answers
16
GATE199618
Consider the following program that attempts to locate an element $x$ in an array $a[ ]$ using binary search. Assume $N > 1$. The program is erroneous. Under what conditions does the program fail? var i,j,k: integer; x: integer; a: array; [1..N] of integer; begin i:= 1; j:= ... (i >= j); if (a[k] = x) then writeln ('x is in the array') else writeln ('x is not in the array') end;
asked
Oct 10, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.1k
points)

912
views
gate1996
algorithms
searching
normal
+30
votes
6
answers
17
GATE19962.13, ISRO201628
The average number of key comparisons required for a successful search for sequential search on $n$ items is $\frac{n}{2}$ $\frac{n1}{2}$ $\frac{n+1}{2}$ None of the above
asked
Oct 9, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.1k
points)

8.5k
views
gate1996
algorithms
easy
isro2016
searching
+34
votes
7
answers
18
GATE20022.10
Consider the following algorithm for searching for a given number $x$ in an unsorted array $A[1..n]$ having $n$ distinct values: Choose an $i$ at random from $1..n$ If $A[i] = x$, then Stop else Goto 1; Assuming that $x$ is present in $A$, what is the expected number of comparisons made by the algorithm before it terminates? $n$ $n1$ $2n$ $\frac{n}{2}$
asked
Sep 16, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.1k
points)

5.9k
views
gate2002
searching
normal
+30
votes
4
answers
19
GATE200884
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int u, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x) && ... $x > 2$ $Y$ is $[2 \ 4 \ 6 \ 8 \ 10 \ 12 \ 14 \ 16 \ 18 \ 20]$ and $ 2 < x < 20$ and $x$ is even
asked
Sep 11, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.1k
points)

5.7k
views
gate2008
algorithms
searching
normal
To see more, click for the
full list of questions
or
popular tags
.
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
Standard Book Exercise Questions for Computer Science
Resource to Learn Graph Theory Interactively
Recruitment to the post of Scientist/Engineer 'SC' (Electronics, Mechanical and Computer Science)
Standard Videos for Calculus
Standard Videos for Linear Algebra
Follow @csegate
Recent questions tagged searching
Recent Blog Comments
Are the answers also present ?
@Arjun sir , Is there any page or something where...
@arjun sir but u called about providing the pdfs...
But anyhow I appreciate this. The questions of...
All these PYQ blogs and standard videos blogs...
50,407
questions
55,862
answers
192,660
comments
91,653
users