menu
search
Log In
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

Subjects

Recent questions in Algorithms

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

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
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)$.
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
Cormen Edition 3 Exercise 2.3 Question 4 (Page No. 38)
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.
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
Cormen Edition 3 Exercise 2.3 Question 2 (Page No. 37)
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$.
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
Cormen Edition 3 Exercise 2.3 Question 1 (Page No. 37)
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 $
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
Cormen Edition 3 Exercise 2.2 Question 4 (Page No. 29)
How can we modify almost any algorithm to have a good best-case running time?
How can we modify almost any algorithm to have a good best-case running time?
asked Jun 25, 2019 in Algorithms akash.dinkar12 84 views
0 votes
1 answer
6
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.
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
Cormen Edition 3 Exercise 2.2 Question 2 (Page No. 29)
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$ ... , rather than for all n elements? Give the best-case and worst-case running times of selection sort in $\Theta$-notation
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
Cormen Edition 3 Exercise 2.2 Question 1 (Page No. 29)
Express the function $n^3/1000 -100n^2-100n+3$ in terms of $\Theta$ notation.
Express the function $n^3/1000 -100n^2-100n+3$ in terms of $\Theta$ notation.
asked Jun 25, 2019 in Algorithms akash.dinkar12 240 views
0 votes
1 answer
9
Cormen Edition 3 Exercise 2.1 Question 4 (Page No. 22-23)
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.
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
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.
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
Cormen Edition 3 Exercise 2.1 Question 2 (Page No. 22)
Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order.
Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order.
asked Jun 25, 2019 in Algorithms akash.dinkar12 235 views
0 votes
1 answer
12
Cormen Edition 3 Exercise 2.1 Question 1 (Page No. 22)
Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array $ A =( 31, 41, 59, 26, 41, 58)$
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
Cormen Edition 3 Exercise 1.2 Question 3 (Page No. 14)
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?
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
Cormen Edition 3 Exercise 1.2 Question 2 (Page No. 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?
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
Cormen Edition 3 Exercise 1.2 Question 1 (Page No. 14)
Give an example of an application that requires algorithmic content at the application level, and discusses the function of the algorithms involved.
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
Cormen Edition 3 Exercise 1.1 Question 5 (Page No. 11)
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.
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
Cormen Edition 3 Exercise 1.1 Question 4 (Page No. 11)
How are the shortest-path and traveling-salesman problems given above similar? How are they different?
How are the shortest-path and traveling-salesman problems given above similar? How are they different?
asked Jun 25, 2019 in Algorithms akash.dinkar12 27 views
0 votes
0 answers
18
Cormen Edition 3 Exercise 1.1 Question 3 (Page No. 11)
Select a data structure that you have seen previously, and discuss its strengths and limitations.
Select a data structure that you have seen previously, and discuss its strengths and limitations.
asked Jun 25, 2019 in Algorithms akash.dinkar12 21 views
0 votes
0 answers
19
Cormen Edition 3 Exercise 1.1 Question 2 (Page No. 11)
Other than speed, what other measures of efficiency might one use in a real-world setting?
Other than speed, what other measures of efficiency might one use in a real-world setting?
asked Jun 25, 2019 in Algorithms akash.dinkar12 29 views
0 votes
0 answers
20
Cormen Edition 3 Exercise 1.1 Question 1 (Page No. 11)
Give a real-world example that requires sorting or a real-world example that requires computing a convex hull.
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
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...