search
Log In

Web Page

Searching, Sorting, Hashing, Asymptotic worst case time and Space complexity, Algorithm design techniques: Greedy, Dynamic programming, and Divide‐and‐conquer, Graph search, Minimum spanning trees, Shortest paths.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count}&2&0&2&2&3&3&0&2&3
\\\hline\textbf{2 Marks Count}&2&4&2&3&2&3&2&2.7&4
\\\hline\textbf{Total Marks}&6&8&6&8&7&9&\bf{6}&\bf{7.3}&\bf{9}\\\hline
\end{array}}}$$

Recent questions in Algorithms

0 votes
0 answers
1
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 68 views
0 votes
1 answer
2
We can express the insertion sort as a recursive procedure as follows.In order to sort $A[1\dots n]$, we recursively sort $A[1 \dots n-1]$ and then insert $A[n]$ into the sorted array $A[1 \dots n-1]$. Write a recurrence for the running time of this recursive version of insertion sort.
asked Jun 26, 2019 in Algorithms akash.dinkar12 129 views
0 votes
0 answers
3
Rewrite the MERGE procedure so that it does not use sentinels, instead of stopping once either array $L$ or $R$ has had all its elements copied back to $A$ and then copying the remainder of the other array back into $A$.
asked Jun 26, 2019 in Algorithms akash.dinkar12 165 views
0 votes
1 answer
4
Using Figure $2.4$ as a model, illustrate the operation of merge sort on the array $A=\langle 3,41,52,26,38,57,9,49 \rangle $
asked Jun 26, 2019 in Algorithms akash.dinkar12 500 views
0 votes
1 answer
5
0 votes
1 answer
6
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 236 views
0 votes
1 answer
7
Consider sorting $n$ numbers stored in an array $A$ by first finding the smallest element of $A$ and exchanging it with the element in $A[1]$. Then find the second smallest element of $A$, and exchange it with $A[2] $. Continue in this manner for the first ... $n-1$ elements, rather than for all n elements? Give the best-case and worst-case running times of selection sort in $\Theta$-notation
asked Jun 25, 2019 in Algorithms akash.dinkar12 409 views
0 votes
2 answers
8
0 votes
1 answer
9
Consider the problem of adding two $n$-bit binary integers, stored in two $n$-element arrays $A$ and $B$.The sum of the two integers should be stored in binary form in an $(n+1)$-element array $C$. State the problem formally and write pseudocode for adding the two integers.
asked Jun 25, 2019 in Algorithms akash.dinkar12 143 views
0 votes
0 answers
10
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 85 views
0 votes
1 answer
11
0 votes
1 answer
12
Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array $ A =( 31, 41, 59, 26, 41, 58)$
asked Jun 25, 2019 in Algorithms akash.dinkar12 101 views
0 votes
0 answers
13
What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine?
asked Jun 25, 2019 in Algorithms akash.dinkar12 138 views
0 votes
0 answers
14
Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n$, insertion sort runs in $8n^2$ steps, while merge sort runs in $64\ n \lg n$ steps. For which values of $n$ does insertion sort beat merge sort?
asked Jun 25, 2019 in Algorithms akash.dinkar12 202 views
0 votes
0 answers
15
Give an example of an application that requires algorithmic content at the application level, and discusses the function of the algorithms involved.
asked Jun 25, 2019 in Algorithms akash.dinkar12 32 views
0 votes
0 answers
16
Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is “approximately” the best is good enough.
asked Jun 25, 2019 in Algorithms akash.dinkar12 23 views
0 votes
0 answers
17
0 votes
0 answers
18
0 votes
0 answers
19
0 votes
0 answers
20
Give a real-world example that requires sorting or a real-world example that requires computing a convex hull.
asked Jun 25, 2019 in Algorithms akash.dinkar12 25 views
...