Dark Mode

Recent questions tagged searching

1 vote

1 answer

1

NIELIT Scientific Assistant A 2020 November: 65
Finding the location of the element with a given value is : Traversal Search Sort None of the options

gatecse asked in Algorithms Dec 9, 2020

203 views

1 vote

3 answers

2

NIELIT 2017 DEC Scientist B - Section B: 8
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[i]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is $2$ $4$ $3$ $5$

Lakshman Bhaiya asked in Algorithms Mar 30, 2020

by Lakshman Bhaiya

737 views

0 votes

1 answer

3

Cormen Edition 3 Exercise 2.3 Question 6 (Page No. 39)
Observe that the while loop of the INSERTION-SORT procedure uses a linear search to scan (backward) through the sorted subarray $A[i\dots j-1]$ Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to $\Theta(n\ lg\ n)$?

akash.dinkar12 asked in Algorithms Jun 26, 2019

by akash.dinkar12

638 views

0 votes

0 answers

4

Cormen Edition 3 Exercise 2.3 Question 5 (Page No. 39)
Referring back to the searching problem (see Exercise 2.1-3), 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 worst-case running time of binary search is $\Theta (lg\ n)$.

akash.dinkar12 asked in Algorithms Jun 26, 2019

by akash.dinkar12

285 views

0 votes

1 answer

5

Cormen Edition 3 Exercise 2.2 Question 3 (Page No. 29)
Consider the linear search again (see Exercise 2.1-3). 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 average-case and worst-case running times of linear search in -notation? Justify your answers.

akash.dinkar12 asked in Algorithms Jun 25, 2019

by akash.dinkar12

2.8k views

0 votes

0 answers

6

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.

akash.dinkar12 asked in Algorithms Jun 25, 2019

by akash.dinkar12

334 views

2 votes

1 answer

7

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 ??

Hirak asked in Algorithms May 21, 2019

by Hirak

932 views

1 vote

1 answer

8

Applied Course | Mock GATE | Test 1 | Question: 47
In a sorted file structure, let the cost of reading a page be $D=10$ milliseconds, the number of data pages be $B=1024$. Let the average time to process a record is $C=5$ milliseconds. Let the number of records ... the time taken to perform a search with equality selection? $10$ milliseconds $120$ milliseconds $5$ milliseconds $50$ milliseconds

Applied Course asked in Algorithms Jan 16, 2019

by Applied Course

417 views

0 votes

1 answer

9

GATE Overflow | Mock GATE | Test 1 | Question: 32
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: ... 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

Ruturaj Mohanty asked in Algorithms Dec 27, 2018

by Ruturaj Mohanty

479 views

2 votes

0 answers

10

Algorithm Searching
Which is faster and by how much, a linear search of only 1000 elements on a 5-GHz computer or a binary search of 1 million elements on a 1-GHz computer. Assume that the execution of each instruction on the 5-GHz computer is five times ... 1-GHz computer and that each iteration of the linear search algorithm is twice as fast as each iteration of the binary search algorithm.

Vaishnavi01 asked in Algorithms Sep 23, 2018

302 views

1 vote

2 answers

11

what is the expected number of comparisons made before the algorithm terminates ?

radha gogia asked in Algorithms Aug 7, 2018

610 views

1 vote

1 answer

12

Ace Algorithms
Suppose A is a sorted array and some of the elements are duplicates. What is the best upper bound to find out the number of elements that are equal to a given key 'k' a) O(log n) b) O(n) c) O(nlogn) d) O(n2)

Sambhrant Maurya asked in Algorithms Aug 7, 2018

by Sambhrant Maurya

530 views

0 votes

0 answers

13

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 ?

Arunav Khare asked in Programming May 14, 2018

by Arunav Khare

217 views

0 votes

1 answer

14

Uttrakhand Asst. Professor Exam-19
Which of the following search method takes less memory ? Depth-first search Breadth-first search Linear search None of the above

gatecse asked in Unknown Category Mar 2, 2018

974 views

52 votes

8 answers

15

GATE CSE 2017 Set 1 | Question: 48
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 ____________.

Arjun asked in Algorithms Feb 14, 2017

by Arjun

16.4k views

0 votes

0 answers

16

MadeEasy Advance Test Series: Algorithm - Searching
can someone provide me the detailed description for this answer?

S Ram asked in Algorithms Feb 1, 2017

by S Ram

229 views

3 votes

3 answers

17

UGC NET CSE | December 2014 | Part 3 | Question: 56
An $A^{*}$ algorithm is a heuristic search technique which Is like a depth-first search where most promising child is selected for expansion Generates all successor nodes and computes an estimate of distance (cost) from start node ... (costs) from start node to all generated nodes and chooses shortest path for further expansion. None of the above

makhdoom ghaya asked in Others Jul 30, 2016

by makhdoom ghaya

2.5k views

24 votes

3 answers

18

GATE CSE 2008 | Question: 85
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 i, j, k; i= 0; j = 9; do { k = (i + j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] ... if $(Y[k] < x) i = k$; else $j = k$; Change line 7 to: } while $((Y[k] == x) \&\& (i < j))$ ;

go_editor asked in Algorithms Apr 23, 2016

5.4k views

3 votes

2 answers

19

ISRO2011-70
Number of comparisons required for an unsuccessful search of an element in a sequential search organized, fixed length, symbol table of length L is L L/2 (L+1)/2 2L

ajit asked in Algorithms Oct 1, 2015

by ajit

5.8k views

22 votes

2 answers

20

GATE CSE 1996 | Question: 18
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 ... ;= j); if (a[k] = x) then writeln ('x is in the array') else writeln ('x is not in the array') end;

Kathleen asked in Algorithms Oct 10, 2014

2.7k views

49 votes

8 answers

21

GATE CSE 1996 | Question: 2.13, ISRO2016-28
The average number of key comparisons required for a successful search for sequential search on $n$ items is $\frac{n}{2}$ $\frac{n-1}{2}$ $\frac{n+1}{2}$ None of the above

Kathleen asked in Algorithms Oct 9, 2014

27.1k views

63 votes

10 answers

22

GATE CSE 2002 | Question: 2.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$ $n-1$ $2n$ $\frac{n}{2}$

Kathleen asked in Algorithms Sep 16, 2014

18.7k views

44 votes

5 answers

23

GATE CSE 2008 | Question: 84
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 i, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x ... $Y$ is $[2 \ 4 \ 6 \ 8 \ 10 \ 12 \ 14 \ 16 \ 18 \ 20]$ and $ 2 < x < 20$ and $x$ is even

Kathleen asked in Algorithms Sep 11, 2014

17.1k views

To see more, click for the full list of questions or popular tags.

Recent questions tagged searching