Questions by akash.dinkar12 / GATE Overflow for GATE CSE

0 votes

1 answer

81

Cormen Edition 3 Exercise 2.3 Question 3 (Page No. 39)
Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence $T(n) = \begin{cases} 2 \text{, if n=2, } \\2T(n/2)+n \text{, if n=$2^k$,for k >1} \end{cases}$ is $T(n) = n\ lg\ n$.

Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence$T(n) = \begin{cases} 2 \text{, if n=2, } ...

613 views

asked Jun 26, 2019

0 votes

1 answer

82

Cormen Edition 3 Exercise 2.3 Question 7 (Page No. 39)
Describe a $\Theta(n\ lg\ n)$ time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whose sum is exactly $x$.

Describe a $\Theta(n\ lg\ n)$ time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whos...

373 views

asked Jun 26, 2019

0 votes

1 answer

83

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

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

823 views

asked Jun 26, 2019

0 votes

0 answers

84

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 elimin...

351 views

asked Jun 26, 2019

0 votes

1 answer

85

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

509 views

asked Jun 26, 2019

0 votes

0 answers

86

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 copyi...

606 views

asked Jun 26, 2019

1 votes

1 answer

87

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 $

1.8k views

asked Jun 26, 2019

0 votes

1 answer

88

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?

435 views

asked Jun 25, 2019

0 votes

1 answer

89

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

3.5k views

asked Jun 25, 2019

0 votes

1 answer

90

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 $. Then find the second smallest...

3.7k views

asked Jun 25, 2019

0 votes

2 answers

91

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.

2.1k views

asked Jun 25, 2019

0 votes

1 answer

92

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

1.7k views

asked Jun 25, 2019

0 votes

0 answers

93

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 s...

435 views

asked Jun 25, 2019

0 votes

1 answer

94

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.

772 views

asked Jun 25, 2019

0 votes

1 answer

95

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)$

643 views

asked Jun 25, 2019

0 votes

0 answers

96

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?

393 views

asked Jun 25, 2019

0 votes

0 answers

97

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 so...

634 views

asked Jun 25, 2019

0 votes

0 answers

98

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.

148 views

asked Jun 25, 2019

0 votes

0 answers

99

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.

157 views

asked Jun 25, 2019

0 votes

1 answer

100

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?

313 views

asked Jun 25, 2019

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