Register

Recent questions tagged descriptive

0 votes
0 answers
1201
Cormen Edition 3 Exercise 6.3 Question 2 (Page No. 159)
Why do we want the loop index $i$ in line $2$ of BUILD-MAX-HEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor A.length/2 \rfloor$?
Why do we want the loop index $i$ in line $2$ of BUILD-MAX-HEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor A.length/2 \rfl...
User Avatar
0 votes
0 answers
1202
Cormen Edition 3 Exercise 6.3 Question 1 (Page No. 159)
BUILD-MAX-HEAP(A) 1 A.heapsize=A.length 2 for i=A.length/2 downto 1 3 MAX-HEAPIFY(A,i) Using Figure $6.3$ as a model, illustrate the operation of BUILD-MAX-HEAP on the array $A=\langle 5,3,17,10,84,19,6,22,9 \rangle $
BUILD-MAX-HEAP(A) 1 A.heapsize=A.length 2 for i=A.length/2 downto 1 3 MAX-HEAPIFY(A,i)Using Figure $6.3$ as a model, illustrate the operation of BUILD-MAX-HEAP on the arr...
User Avatar
0 votes
0 answers
1205
Cormen Edition 3 Exercise 6.2 Question 4 (Page No. 156)
What is the effect of calling MAX-HEAPIFY$(A,i)$ for $i > A.heapsize/2$.
What is the effect of calling MAX-HEAPIFY$(A,i)$ for $i A.heapsize/2$.
User Avatar
0 votes
0 answers
1206
Cormen Edition 3 Exercise 6.2 Question 3 (Page No. 156)
What is the effect of calling MAX-HEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?
What is the effect of calling MAX-HEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?
User Avatar
0 votes
0 answers
1210
Cormen Edition 3 Exercise 2.4 Question 4 (Page No. 42)
Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $\Theta (n\ lg\ n)$ worst-case time. (Hint: Modify merge sort.)
Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $\Theta (n\ lg\ n)$ worst-case time. (Hint: Modify merge sort.)
User Avatar
0 votes
0 answers
1211
Cormen Edition 3 Exercise 2.4 Question 3 (Page No. 42)
What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
User Avatar
0 votes
1 answer
1212
Cormen Edition 3 Exercise 2.4 Question 2 (Page No. 42)
What array with elements from the set $\{1,2,\dots n\}$ has the most inversions? How many does it have?
What array with elements from the set $\{1,2,\dots n\}$ has the most inversions? How many does it have?
User Avatar
0 votes
1 answer
1213
Cormen Edition 3 Exercise 2.4 Question 1 (Page No. 41)
List the five inversions of the array $\langle 2,3,8,6,1\rangle$
List the five inversions of the array $\langle 2,3,8,6,1\rangle$
User Avatar
0 votes
1 answer
1215
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...
User Avatar
0 votes
0 answers
1219
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...
User Avatar
1 votes
1 answer
1220
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 $
User Avatar
0 votes
1 answer
1221
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?
User Avatar
0 votes
2 answers
1224
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.
User Avatar
0 votes
1 answer
1227
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.
User Avatar
0 votes
1 answer
1228
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)$
User Avatar
0 votes
0 answers
1229
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?
User Avatar
Page: