search
Log In

Recent questions tagged searching

1 vote
2 answers
1
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$
asked Mar 30 in Algorithms Lakshman Patel RJIT 123 views
0 votes
1 answer
2
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)$?
asked Jun 26, 2019 in Algorithms akash.dinkar12 47 views
0 votes
0 answers
3
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 search algorithm repeats this procedure, ... iterative or recursive, for binary search. Argue that the worst-case running time of binary search is $\Theta (lg\ n)$.
asked Jun 26, 2019 in Algorithms akash.dinkar12 49 views
0 votes
1 answer
4
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? How about in the worst case? What are the average-case and worst-case running times of linear search in ‚-notation? Justify your answers.
asked Jun 25, 2019 in Algorithms akash.dinkar12 122 views
0 votes
0 answers
5
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 not appear in $A$. Write ... sequence, looking for $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 akash.dinkar12 54 views
2 votes
1 answer
6
.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 Hirak 368 views
0 votes
1 answer
7
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==A[i] ... What should 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 Ruturaj Mohanty 142 views
2 votes
0 answers
8
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 faster than on the 1-GHz 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 Vaishnavi01 107 views
0 votes
0 answers
9
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 LDAP systems which contain users and ... said format. The 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 Arunav Khare 104 views
0 votes
1 answer
10
Which of the following search method takes less memory ? Depth-first search Breadth-first search Linear search None of the above
asked Mar 2, 2018 in Unknown Category gatecse 106 views
43 votes
8 answers
12
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 Arjun 7.4k views
0 votes
0 answers
13
3 votes
3 answers
14
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 to a goal node through each of ... all 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 makhdoom ghaya 901 views
17 votes
3 answers
15
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) && (i < j)) ; 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 jothee 2.5k views
18 votes
3 answers
16
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 := N ... correct 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 makhdoom ghaya 884 views
24 votes
1 answer
17
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, that ... binary 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 makhdoom ghaya 1.7k views
16 votes
2 answers
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:= 1; j:= n; repeat k: ... x) or (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 Kathleen 1.3k views
34 votes
6 answers
19
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
asked Oct 9, 2014 in Algorithms Kathleen 12.3k views
45 votes
8 answers
20
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}$
asked Sep 16, 2014 in Algorithms Kathleen 8.7k views
32 votes
5 answers
21
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) && (i < j)) ; if(Y[k] ... $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 Kathleen 8.1k views
To see more, click for the full list of questions or popular tags.
...