Register
Filter

Questions by akash.dinkar12

0 votes
1 answer
42
Cormen Edition 3 Exercise 7.3 Question 1 (Page No. 180)
Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?
Why do we analyze the expected running time of a randomized algorithm and not its worst-case running time?
1 votes
1 answer
43
Cormen Edition 3 Exercise 7.2 Question 6 (Page No. 179)
Argue that for any constant $0<\alpha\leq 1/2$, the probability is approximately $1-2\alpha$ that on a random input array, PARTITION produces a split more balanced than $1-\alpha$ to $\alpha$.
Argue that for any constant $0<\alpha\leq 1/2$, the probability is approximately $1-2\alpha$ that on a random input array, PARTITION produces a split more balanced than $...
0 votes
1 answer
46
Cormen Edition 3 Exercise 7.2 Question 3 (Page No. 178)
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
Show that the running time of QUICKSORT is $\Theta(n^2)$ when the array $A$ contains distinct elements and is sorted in decreasing order.
1 votes
2 answers
47
Cormen Edition 3 Exercise 7.2 Question 2 (Page No. 178)
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?
What is the running time of QUICKSORT when all elements of the array $A$ have the same value?
0 votes
1 answer
48
Cormen Edition 3 Exercise 7.2 Question 1 (Page No. 178)
Use the substitution method to prove that the recurrence $T(n)=T(n-1) + \Theta(n)$ has the solution $T(n) =\Theta(n^2)$.
Use the substitution method to prove that the recurrence $T(n)=T(n-1) + \Theta(n)$ has the solution $T(n) =\Theta(n^2)$.
0 votes
1 answer
49
Cormen Edition 3 Exercise 7.1 Question 4 (Page No. 174)
QUICKSORT(A,p,r) 1 if p < r 2 q = PARTITION(A,p,r) 3 QUICKSORT(A, p , q-1) 4 QUICKSORT(A, q + 1, r) How would you modify QUICKSORT to sort into nonincreasing order?
QUICKSORT(A,p,r) 1 if p < r 2 q = PARTITION(A,p,r) 3 QUICKSORT(A, p , q-1) 4 QUICKSORT(A, q + 1, r)How would you modify QUICKSORT to sort into nonincreasing order?
0 votes
1 answer
50
Cormen Edition 3 Exercise 7.1 Question 3 (Page No. 174)
Give a brief argument that the running time of PARTITION on a subarray of size $n$ is $\Theta(n)$.
Give a brief argument that the running time of PARTITION on a subarray of size $n$ is $\Theta(n)$.
0 votes
1 answer
51
Cormen Edition 3 Exercise 7.1 Question 2 (Page No. 174)
What value of $q$ does PARTITION return when all elements in the array $A[p..r]$ have the same value? Modify PARTITION so that $q=\lfloor(p+r)/2 \rfloor$ when all elements in the array $A[p..r]$ have the same value.
What value of $q$ does PARTITION return when all elements in the array $A[p..r]$ have the same value? Modify PARTITION so that $q=\lfloor(p+r)/2 \rfloor$ when all element...
0 votes
0 answers
53
Cormen Edition 3 Exercise 6.5 Question 9 (Page No. 166)
Give an $O(n\lg\ k)$- time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a minheap for $k$-way merging.)
Give an $O(n\lg\ k)$- time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a minhea...
0 votes
1 answer
54
Cormen Edition 3 Exercise 6.5 Question 8 (Page No. 166)
The operation HEAP-DELETE$(A, i)$ deletes the item in node $i$ from heap $A$. Give an implementation of HEAP-DELETE that runs in $O(lg\ n)$ time for an $n-$element max-heap.
The operation HEAP-DELETE$(A, i)$ deletes the item in node $i$ from heap $A$. Give an implementation of HEAP-DELETE that runs in $O(lg\ n)$ time for an $n-$element max-h...
0 votes
0 answers
55
Cormen Edition 3 Exercise 6.5 Question 7 (Page No. 166)
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
0 votes
0 answers
56
Cormen Edition 3 Exercise 6.5 Question 6 (Page No. 166)
Each exchange operation on line $5$ of HEAP-INCREASE-KEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the three assignments down to just one assignment.
Each exchange operation on line $5$ of HEAP-INCREASE-KEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the ...
0 votes
0 answers
58
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?
1 votes
0 answers
59
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.
Page: