Register

Recent questions tagged cormen

0 votes
1 answer
121
Cormen Edition 3 Exercise 6.1 Question 1 (Page No. 153)
What are the minimum and maximum numbers of elements in a heap of height $h$?
What are the minimum and maximum numbers of elements in a heap of height $h$?
User Avatar
0 votes
1 answer
125
Cormen Edition 3 Exercise 4.5 Question 4 (Page No. 97)
Can the master method be applied to the recurrence $T(n)=4T(n/2)+n^2\ lg\ n$ ?Why or why not? Give an asymptotic upper bound for this recurrence.
Can the master method be applied to the recurrence $T(n)=4T(n/2)+n^2\ lg\ n$ ?Why or why not? Give an asymptotic upper bound for this recurrence.
User Avatar
0 votes
0 answers
126
Cormen Edition 3 Exercise 4.5 Question 3 (Page No. 97)
Use the master method to show that the solution to the binary-search recurrence $T(n)=T(n/2) + \Theta(1)$ is $T(n)=\Theta(lg\ n)$.
Use the master method to show that the solution to the binary-search recurrence $T(n)=T(n/2) + \Theta(1)$ is $T(n)=\Theta(lg\ n)$.
User Avatar
0 votes
0 answers
128
Cormen Edition 3 Exercise 4.5 Question 1 (Page No. 96)
Use the master method to give tight asymptotic bounds for the following recurrences. $T(n)=2T(n/4) + 1$ $T(n)=2T(n/4) +\sqrt{n}$ $T(n)=2T(n/4) +n$ $T(n)=2T(n/4) +n^2$
Use the master method to give tight asymptotic bounds for the following recurrences.$T(n)=2T(n/4) + 1$$T(n)=2T(n/4) +\sqrt{n}$$T(n)=2T(n/4) +n$$T(n)=2T(n/4) +n^2$
User Avatar
0 votes
0 answers
129
Cormen Edition 3 Exercise 4.4 Question 9 (Page No. 93)
Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n)=T(\alpha n) +T((1-\alpha)n) +cn$,where $\alpha$ is a constant in the range $0<\alpha<1$ and $c>0$ is also constant.
Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n)=T(\alpha n) +T((1-\alpha)n) +cn$,where $\alpha$ is a constant in the range $0<\alpha...
User Avatar
0 votes
0 answers
130
Cormen Edition 3 Exercise 4.4 Question 8 (Page No. 93)
Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n) =T(n-a)+T(a)+cn$, where $a\geq 1$ and $c >0$ are constants.
Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n) =T(n-a)+T(a)+cn$, where $a\geq 1$ and $c >0$ are constants.
User Avatar
0 votes
0 answers
131
Cormen Edition 3 Exercise 4.4 Question 7 (Page No. 93)
Draw the recursion tree for $T(n)=4T(\lfloor n/2\rfloor) +cn$, where $c$ is a constant,and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method.
Draw the recursion tree for $T(n)=4T(\lfloor n/2\rfloor) +cn$, where $c$ is a constant,and provide a tight asymptotic bound on its solution. Verify your bound by the subs...
User Avatar
0 votes
0 answers
132
Cormen Edition 3 Exercise 4.4 Question 6 (Page No. 93)
Argue that the solution to the recurrence $T(n)=T(n/3)+T(2n/3)+cn$,where $c$ is a constant, is $\Omega(n\lg n)$ by appealing to a recursion tree.
Argue that the solution to the recurrence $T(n)=T(n/3)+T(2n/3)+cn$,where $c$ is a constant, is $\Omega(n\lg n)$ by appealing to a recursion tree.
User Avatar
0 votes
0 answers
133
Cormen Edition 3 Exercise 4.4 Question 5 (Page No. 93)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n-1)+T(n/2) +n$.Use the substitution method to verify your answer.
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n-1)+T(n/2) +n$.Use the substitution method to verify your answer.
User Avatar
0 votes
0 answers
134
Cormen Edition 3 Exercise 4.4 Question 4 (Page No. 93)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) =2T(n-1) + 1$.Use the substitution method to verify your answer.
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) =2T(n-1) + 1$.Use the substitution method to verify your answer.
User Avatar
0 votes
0 answers
135
Cormen Edition 3 Exercise 4.4 Question 3 (Page No. 93)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=4T(n/2 +2)+n$.Use the substitution method to verify your answer.
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=4T(n/2 +2)+n$.Use the substitution method to verify your answer.
User Avatar
0 votes
1 answer
136
Cormen Edition 3 Exercise 4.4 Question 2 (Page No. 92)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n/2)+n^2$.Use the substitution method to verify your answer
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n/2)+n^2$.Use the substitution method to verify your answer
User Avatar
0 votes
0 answers
137
Cormen Edition 3 Exercise 4.4 Question 1 (Page No. 92)
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=3T(\lfloor n/2 \rfloor) + n$. Use the substitution method to verify your answer.
Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=3T(\lfloor n/2 \rfloor) + n$. Use the substitution method to verify your answer.
User Avatar
0 votes
1 answer
138
Cormen Edition 3 Exercise 4.3 Question 9 (Page No. 88)
Solve the recurrence $T(n)=3T(\sqrt n) +log\ n$ by making a change of variables.Your solution should be asymptotically tight. Do not worry about whether values are integral.
Solve the recurrence $T(n)=3T(\sqrt n) +log\ n$ by making a change of variables.Your solution should be asymptotically tight. Do not worry about whether values are integr...
User Avatar
0 votes
0 answers
142
Cormen Edition 3 Exercise 4.3 Question 3 (Page No. 87)
We saw that the solution of $T(n) = T(\lceil n/2 \rceil) + n$ is $O(lg\ n)$. Show that the solution of this recurrence is also $\Omega(n\ lg\ n)$. Conclude that the solution is $\Theta(n\log \ n)$.
We saw that the solution of $T(n) = T(\lceil n/2 \rceil) + n$ is $O(lg\ n)$. Show that the solution of this recurrence is also $\Omega(n\ lg\ n)$. Conclude that the solut...
User Avatar
0 votes
0 answers
148
Cormen Edition 3 Exercise 4.1 Question 2 (Page No. 74)
Write pseudo code for the brute-force method of solving the $maximum-subarray$ problem. Your procedure should run in $\Theta(n^2)$ time.
Write pseudo code for the brute-force method of solving the $maximum-subarray$ problem. Your procedure should run in $\Theta(n^2)$ time.
User Avatar
0 votes
0 answers
149
Cormen Edition 3 Exercise 3.2 Question 8 (Page No. 60)
Show that $K$ $ln$ $K = \Theta (n)$ implies $k=$\Theta$($n$/$ln$ $n$)$.
Show that $K$ $ln$ $K = \Theta (n)$ implies $k=$$\Theta$$($$n$$/$$ln$ $n$$)$.
User Avatar
0 votes
0 answers
150
Cormen Edition 3 Exercise 3.2 Question 7 (Page No. 60)
Prove by induction that the $i^{th}$ Fibonacci number satisfies the equality $F_i = \frac{\phi^i-\hat{\phi^i}}{\sqrt{5}}$ where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate.
Prove by induction that the $i^{th}$ Fibonacci number satisfies the equality$F_i = \frac{\phi^i-\hat{\phi^i}}{\sqrt{5}}$where $\phi$ is the golden ratio and $\hat{\phi}$ ...
User Avatar
Page: