Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged cormen
0
votes
2
answers
31
Cormen Edition 3 Exercise 8.2 Question 4 (Page No. 197)
Describe an algorithm that, given $n$ integers in the range $0$ to $k$ preprocesses its input and then answers any query about how many of the $n$ integers fall into the range $[a..b]$ in $O(1)$ time.Your algorithm should use $\Theta(n+k)$ preprocessing time.
Describe an algorithm that, given $n$ integers in the range $0$ to $k$ preprocesses its input and then answers any query about how many of the $n$ integers fall into the ...
akash.dinkar12
1.6k
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
countingsort
descriptive
+
–
0
votes
0
answers
32
Cormen Edition 3 Exercise 8.2 Question 3 (Page No. 196)
Suppose that we were to rewrite the for loop header in line $10$ of the COUNTINGSORT as 10 for j = 1 to A.length Show that the algorithm still works properly. Is the modified algorithm stable?
Suppose that we were to rewrite the for loop header in line $10$ of the COUNTINGSORT as 10 for j = 1 to A.lengthShow that the algorithm still works properly. Is the modif...
akash.dinkar12
349
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
countingsort
descriptive
+
–
0
votes
1
answer
33
Cormen Edition 3 Exercise 8.2 Question 2 (Page No. 196)
Prove that COUNTING-SORT is stable.
Prove that COUNTING-SORT is stable.
akash.dinkar12
371
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
countingsort
descriptive
+
–
0
votes
0
answers
34
Cormen Edition 3 Exercise 8.2 Question 1 (Page No. 196)
COUNTING-SORT(A, B, k) 1 let C[0, ,k] be a new array 2 for i = 0 to k 3 C[i] = 0 4 for j = 1 to A.length 5 C[A[j]] = C[A[j]] + 1 6 // C[i] now contains the number of elements equal to i . 7 for i =1 to k 8 C[i] = C[ ... j] 12 C[A[j]] = C[A[j]] - 1 illustrate the operation of COUNTING-SORT on the array $A=\langle 6,0,2,0,1,3,4,6,1,3,2 \rangle $
COUNTING-SORT(A, B, k) 1 let C[0,…,k] be a new array 2 for i = 0 to k 3 C[i] = 0 4 for j = 1 to A.length 5 C[A[j]] = C[A[j]] + 1 6 // C[i] now contains the number of el...
akash.dinkar12
349
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
countingsort
descriptive
+
–
0
votes
0
answers
35
Cormen Edition 3 Exercise 8.1 Question 4 (Page No. 194)
Suppose that you are given a sequence of $n$ elements to sort.The input sequence consists of $n/k$ subsequences, each containing $k$ elements.The elements in a given subsequence are all smaller than the elements in the ... of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
Suppose that you are given a sequence of $n$ elements to sort.The input sequence consists of $n/k$ subsequences, each containing $k$ elements.The elements in a given subs...
akash.dinkar12
451
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
descriptive
+
–
0
votes
0
answers
36
Cormen Edition 3 Exercise 8.1 Question 3 (Page No. 194)
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$.What about a fraction of $1/n$ inputs of length $n$? What about a fraction $1/2^n$?
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$.What about a fraction of $1/n$ inputs of length $n$?...
akash.dinkar12
265
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
descriptive
+
–
0
votes
1
answer
37
Cormen Edition 3 Exercise 8.1 Question 2 (Page No. 194)
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.
akash.dinkar12
450
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
+
–
0
votes
1
answer
38
Cormen Edition 3 Exercise 8.1 Question 1 (Page No. 193)
What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
akash.dinkar12
344
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
descriptive
+
–
1
votes
1
answer
39
Cormen Edition 3 Exercise 7.4 Question 6 (Page No. 185)
Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst a $\alpha$-to-$(1-\alpha)$ split, as a function of $\alpha$ in the range $0<\alpha<1$.
Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elemen...
akash.dinkar12
1.1k
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
difficult
+
–
0
votes
1
answer
40
Cormen Edition 3 Exercise 7.4 Question 5 (Page No. 185)
We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is nearly sorted. Upon calling quicksort on a subarray with fewer than $k$ elements, let it simply return without ... $k$, both in theory and in practice?
We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is “nearly” sorted. Upon callin...
akash.dinkar12
515
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
1
answer
41
Cormen Edition 3 Exercise 7.4 Question 4 (Page No. 184)
Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.
Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.
akash.dinkar12
513
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
time-complexity
descriptive
+
–
0
votes
1
answer
42
Cormen Edition 3 Exercise 7.4 Question 3 (Page No. 184)
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.
Show that the expression $q^2 +(n-q-1)^2$ achieves a maximum over $q=0,1,\dots ,n-1$ when $q=0$ or $q=n-1$.
akash.dinkar12
248
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
2
answers
43
Cormen Edition 3 Exercise 7.4 Question 2 (Page No. 184)
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.
Show that quicksort’s best-case running time is $\Omega(n\ lg\ n)$.
akash.dinkar12
630
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
time-complexity
descriptive
+
–
0
votes
0
answers
44
Cormen Edition 3 Exercise 7.4 Question 1 (Page No. 184)
Show that in the recurrence $T(n)=\max_{0<q\leq n-1} (T(q)+T(n-q-1))+\Theta(n)$ $T(n)=\Omega(n^2)$
Show that in the recurrence$T(n)=\max_{0<q\leq n-1} (T(q)+T(n-q-1))+\Theta(n)$$T(n)=\Omega(n^2)$
akash.dinkar12
323
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
recurrence-relation
descriptive
+
–
0
votes
1
answer
45
Cormen Edition 3 Exercise 7.3 Question 2 (Page No. 180)
RANDOMIZED-QUICKSORT(A, p, r) 1 if p < r 2 q = RANDOMIZED-PARTITION(A, p, r) 3 RANDOMIZED-QUICKSORT(A, p, q - 1) 4 RANDOMIZED-QUICKSORT(A, q + 1, r) RANDOMIZED-PARTITION(A, p, r) 1 i = RANDOM(p, r) 2 ... made to the random number generator RANDOM in the worst case? How about in the best case? Give your answer in terms of $\Theta$ notation.
RANDOMIZED-QUICKSORT(A, p, r) 1 if p < r 2 q = RANDOMIZED-PARTITION(A, p, r) 3 RANDOMIZED-QUICKSORT(A, p, q – 1) 4 RANDOMIZED-QUICKSORT(A, q + 1, r) RANDOMIZED-PARTITIO...
akash.dinkar12
478
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
1
answer
46
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?
akash.dinkar12
327
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
1
votes
1
answer
47
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 $...
akash.dinkar12
401
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
difficult
+
–
0
votes
0
answers
48
Cormen Edition 3 Exercise 7.2 Question 5 (Page No. 178)
Suppose that the splits at every level of quicksort are in the proportion $1-\alpha$ to $\alpha$, where $0<\alpha\leq1/2$ is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately $-lg\ n /lg\ \alpha$ and the maximum depth is approximately $-lg\ n / lg\ (1-\alpha)$.(Don’t worry about integer round-off.)
Suppose that the splits at every level of quicksort are in the proportion $1-\alpha$ to $\alpha$, where $0<\alpha\leq1/2$ is a constant. Show that the minimum depth of a ...
akash.dinkar12
319
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
0
answers
49
Cormen Edition 3 Exercise 7.2 Question 4 (Page No. 178)
Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order ... -sorted input. Argue that the procedure INSERTION-SORT would tend to beat the procedure QUICKSORT on this problem.
Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order...
akash.dinkar12
493
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
sorting
quick-sort
descriptive
+
–
0
votes
1
answer
50
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.
akash.dinkar12
1.1k
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
time-complexity
descriptive
+
–
1
votes
2
answers
51
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?
akash.dinkar12
511
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
time-complexity
descriptive
+
–
0
votes
1
answer
52
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)$.
akash.dinkar12
292
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
recurrence-relation
descriptive
+
–
0
votes
1
answer
53
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?
akash.dinkar12
908
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
1
answer
54
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)$.
akash.dinkar12
1.4k
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
quick-sort
descriptive
+
–
0
votes
1
answer
55
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...
akash.dinkar12
1.7k
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
sorting
quick-sort
descriptive
+
–
0
votes
1
answer
56
Cormen Edition 3 Exercise 7.1 Question 1 (Page No. 173)
PARTITION(A,p,r) 1 x = A[r] 2 i = p – 1 3 for j = p to r – 1 4 if A[j] <= x 5 i = i + 1 6 exchange A[i] with A[j] 7 exchange A[i+1] with A[r] 8 return i + 1 illustrate the operation of PARTITION on the array $A=\langle 13,19,9,5,12,8,7,4,21,2,6,11\rangle$
PARTITION(A,p,r) 1 x = A[r] 2 i = p – 1 3 for j = p to r – 1 4 if A[j] <= x 5 i = i + 1 6 exchange A[i] with A[j] 7 exchange A[i+1] with A[r] 8 return i + 1 illustrat...
akash.dinkar12
1.5k
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
sorting
quick-sort
descriptive
+
–
0
votes
0
answers
57
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...
akash.dinkar12
305
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
binary-heap
descriptive
+
–
0
votes
1
answer
58
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...
akash.dinkar12
512
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
binary-heap
descriptive
+
–
0
votes
0
answers
59
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.
akash.dinkar12
365
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
binary-heap
priority-queue
descriptive
+
–
0
votes
0
answers
60
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 ...
akash.dinkar12
250
views
akash.dinkar12
asked
Jun 27, 2019
Algorithms
cormen
algorithms
binary-heap
descriptive
+
–
Page:
« prev
1
2
3
4
5
6
7
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register