Chapter 4 Flashcards
Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray A[1..j], extend the answer to find a maximum subarray ending at indexj+1 by using the following observation: a maximum subarrayA[i..j+1], for some 1 ≤ i ≤ j+1. Determine a maximum subarray of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index j.
Pan has discovered a way of multiplying 68×68 matrices using 132464multiplications, a way of multiplying 70×70 matrices using 143640multiplications, and a way of multiplying 72×72 matrices using 155424 multiplications. Which method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm? How does it compare to Strassen’s algorithm?
Show that the solution of T(n) = T(n - 1) + n is O(n2).
How quickly can you multiply a kn×n matrix by an n×kn matrix, using Strassen’s algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.
kn×n)(n×kn) produces a kn×kn matrix. This produces k^2multiplications of n×n matrices.
(n×kn)(kn×n) produces an n×n matrix. This produces k multiplications and k−1 additions.
1Prove the following with substitution method: a. T(n) = 4T(n/2) + n^2 = Ω(n^2 lgn)
Solve by substitution
Recursion tree
Chapter 4 (5%). Find an asymptotic solution of the following recurrence. Express your answer using Θ-notation, and give a brief justification. 𝑇(𝑛) = 𝑙𝑜𝑔 𝑛 + 𝑇(√𝑛)
Use a recurrence tree to give an asymptotically tight solution to the recurrence T(n) = T(n-a) + T(a) + cn, where a ≥ 1 and c > 0 are constants.
- Suppose you know the solution of 𝑇(𝑛) = 5𝑇(𝑛/3) + 𝑛 is 𝑇(𝑛) = 𝛩(𝑛 𝑙𝑜𝑔3 5 ).
- a. Show that a substitution proof with the assumption 𝑇(𝑛) ≤ 𝑐𝑛^𝑙𝑜𝑔3^5 fails.
- b. Show how to subtract off a lower-order term to make a substitution proof work.
*
Show upper and lower bound
Show upper and lower bound
Show upper and lower bound
