Chapter 4 Flashcards Preview

Algorithm > Chapter 4 > Flashcards

Flashcards in Chapter 4 Deck (28)
Loading flashcards...
1

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.

2

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?

3

Show that the solution of T(n) = T(n - 1) + n is O(n2).

4

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.

5

6

1Prove the following with substitution method: a. T(n) = 4T(n/2) + n^2 = Ω(n^2 lgn)

7

Solve by substitution

 

8

Recursion tree

9

10

11

12

Chapter 4 (5%). Find an asymptotic solution of the following recurrence. Express your answer using Θ-notation, and give a brief justification. 𝑇(𝑛) = 𝑙𝑜𝑔 𝑛 + 𝑇(√𝑛)

 

13

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.

14

2. 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.
  •  

15

16

17

18

19

Show upper and lower bound

20

Show upper and lower bound

21

Show upper and lower bound

 

22

23

24

25

26

27

28