Register

Recent questions tagged cormen

0 votes
0 answers
62
Cormen Edition 3 Exercise 6.5 Question 4 (Page No. 165)
Why do we bother setting the key of the inserted node to $-\infty$ in line $2$ of MAX-HEAP-INSERT when the next thing we do is increase its key to the desired value?
Why do we bother setting the key of the inserted node to $-\infty$ in line $2$ of MAX-HEAP-INSERT when the next thing we do is increase its key to the desired value?
User Avatar
1 votes
0 answers
63
Cormen Edition 3 Exercise 6.5 Question 3 (Page No. 165)
Write pseudo code for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.
Write pseudo code for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.
User Avatar
0 votes
0 answers
66
Cormen Edition 3 Exercise 6.4 Question 5 (Page No. 161)
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
User Avatar
0 votes
0 answers
68
Cormen Edition 3 Exercise 6.4 Question 3 (Page No. 160)
What is the running time of HEAPSORT on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?
What is the running time of HEAPSORT on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?
User Avatar
0 votes
0 answers
71
Cormen Edition 3 Exercise 6.3 Question 3 (Page No. 159)
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n-$element heap.
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n-$element heap.
User Avatar
0 votes
0 answers
72
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
73
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
77
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
81
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
82
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
83
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
86
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
90
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
Page: