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
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

19
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

14
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

24
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, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.4k
points)

21
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, 2019
in
Algorithms
by
Hirak
Active
(
3.6k
points)

193
views
algorithms
datastructures
arrays
searching
0
votes
1
answer
6
GO2019FLT132
A sequential search operation is performed on an array $A$ for the key value of $'x'$ (ignore quotes). Consider the following piece of assembly language code that uses back patching to perform the sequential search. i=0; P: if (i<A.length) goto ____; Q: goto ____; R: if (x ... be the correct values in the blanks provided ordered from top to bottom? R T U P R U T P P U T R P T U R
asked
Dec 27, 2018
in
Algorithms
by
Ruturaj Mohanty
Active
(
2.7k
points)

100
views
go2019flt1
algorithms
searching
+2
votes
0
answers
7
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
(
153
points)

49
views
algorithms
searching
0
votes
0
answers
8
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)

88
views
algorithms
searching
0
votes
1
answer
9
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
(
17.5k
points)

66
views
uttarakhandasstprof2018
datastructures
searching
+3
votes
1
answer
10
Ace Test Series: Algorithms  Searching
asked
Nov 23, 2017
in
Algorithms
by
saxena0612
Boss
(
11.9k
points)

496
views
binarysearch
algorithms
acetestseries
searching
+34
votes
7
answers
11
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
(
430k
points)

5.7k
views
gate20171
algorithms
normal
numericalanswers
searching
0
votes
0
answers
12
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)

70
views
madeeasytestseries
algorithms
searching
+2
votes
3
answers
13
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
(
30.7k
points)

685
views
ugcnetdec2014iii
artificialintelligence
searching
+16
votes
3
answers
14
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
(
105k
points)

1.9k
views
gate2008
algorithms
searching
normal
+16
votes
3
answers
15
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
(
30.7k
points)

621
views
tifr2012
algorithms
searching
+21
votes
1
answer
16
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
(
30.7k
points)

975
views
tifr2010
searching
+14
votes
2
answers
17
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.2k
points)

1k
views
gate1996
algorithms
searching
normal
+31
votes
6
answers
18
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.2k
points)

9.1k
views
gate1996
algorithms
easy
isro2016
searching
+38
votes
8
answers
19
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.2k
points)

6.6k
views
gate2002
searching
normal
+30
votes
4
answers
20
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.2k
points)

6.1k
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Management Trainee Recruitment COAL INDIA 2020
ECIL Interview Experience
Follow @csegate
Recent questions tagged searching
Recent Blog Comments
Q42 C option is correct for C set as it is an...
@ smsubham The SQL query question No...
Are SQL query and that case 1, case 2 answer in...
@ Debapaul Correct answer should be...
Question No. 42 (BIG ENDIAN QUESTION) in Set 'C'...
50,737
questions
57,271
answers
198,137
comments
104,779
users