CS 473: Fundamental Algorithms, Spring 2011

Reductions, Recursion and Divide and Conquer

Lecture 5
February 1, 2011

Sariel (UIUC)

CS473

Spring 2011

1 / 42

Part I Reductions and Recursion

Sariel (UIUC)

CS473

Spring 2011

2 / 42

Reduction
Reducing problem A to problem B: Algorithm for A uses algorithm for B as a black box

Sariel (UIUC)

CS473

Spring 2011

3 / 42

Distinct Elements Problem

Problem Given an array A of n integers, are there any duplicates in A? Naive algorithm:
for i = 1 to n 1 do for j = i + 1 to n do if (A[i] = A[j]) return YES return NO

Running time: O(n2 )

Sariel (UIUC)

CS473

Spring 2011

4 / 42

Distinct Elements Problem

Problem Given an array A of n integers, are there any duplicates in A? Naive algorithm:
for i = 1 to n 1 do for j = i + 1 to n do if (A[i] = A[j]) return YES return NO

Running time: O(n2 )

Sariel (UIUC)

CS473

Spring 2011

4 / 42

Distinct Elements Problem

Problem Given an array A of n integers, are there any duplicates in A? Naive algorithm:
for i = 1 to n 1 do for j = i + 1 to n do if (A[i] = A[j]) return YES return NO

Running time: O(n2 )

Sariel (UIUC)

CS473

Spring 2011

4 / 42

Distinct Elements Problem

Problem Given an array A of n integers, are there any duplicates in A? Naive algorithm:
for i = 1 to n 1 do for j = i + 1 to n do if (A[i] = A[j]) return YES return NO

Running time: O(n2 )

Sariel (UIUC)

CS473

Spring 2011

4 / 42

Reduction to Sorting
Sort A for i = 1 to n 1 do if (A[i] = A[i + 1]) then return YES return NO

Running time: O(n) plus time to sort an array of n numbers Important point: algorithm uses sorting as a black box

Sariel (UIUC)

CS473

Spring 2011

5 / 42

Reduction to Sorting
Sort A for i = 1 to n 1 do if (A[i] = A[i + 1]) then return YES return NO

Running time: O(n) plus time to sort an array of n numbers Important point: algorithm uses sorting as a black box

Sariel (UIUC)

CS473

Spring 2011

5 / 42

Two sides of Reductions

Suppose problem A reduces to problem B Positive direction: Algorithm for B implies an algorithm for A Negative direction: Suppose there is no ecient algorithm for A then it implies no ecient algorithm for B (technical condition for reduction time necessary for this) Example: Distinct Elements reduces to Sorting in O(n) time An O(n log n) time algorithm for Sorting implies an O(n log n) time algorithm for Distinct Elements problem. If there is no o(n log n) time algorithm for Distinct Elements problem then there is no o(n log n) time algorithm for Sorting.

Sariel (UIUC)

CS473

Spring 2011

6 / 42

Two sides of Reductions

Suppose problem A reduces to problem B Positive direction: Algorithm for B implies an algorithm for A Negative direction: Suppose there is no ecient algorithm for A then it implies no ecient algorithm for B (technical condition for reduction time necessary for this) Example: Distinct Elements reduces to Sorting in O(n) time An O(n log n) time algorithm for Sorting implies an O(n log n) time algorithm for Distinct Elements problem. If there is no o(n log n) time algorithm for Distinct Elements problem then there is no o(n log n) time algorithm for Sorting.

Sariel (UIUC)

CS473

Spring 2011

6 / 42

Recursion
Reduction: reduce one problem to another Recursion: a special case of reduction reduce problem to a smaller instance of itself self-reduction Problem instance of size n is reduced to one or more instances of size n 1 or less. For termination, problem instances of small size are solved by some other method as base cases

Sariel (UIUC)

CS473

Spring 2011

7 / 42

Recursion
Reduction: reduce one problem to another Recursion: a special case of reduction reduce problem to a smaller instance of itself self-reduction Problem instance of size n is reduced to one or more instances of size n 1 or less. For termination, problem instances of small size are solved by some other method as base cases

Sariel (UIUC)

CS473

Spring 2011

7 / 42

Recursion
Recursion is a very powerful and fundamental technique Basis for several other methods
Divide and conquer Dynamic programming Enumeration and branch and bound etc Some classes of greedy algorithms

Makes proof of correctness easy (via induction) Recurrences arise in analysis

Sariel (UIUC)

CS473

Spring 2011

8 / 42

Selection Sort
Sort a given array A[1..n] of integers. Recursive version of Selection sort.
SelectSort(A[1..n]): if n = 1 return Find smallest number in A. Swap A[1] and A[i] SelectSort(A[2..n])

Let A[i] be smallest number

T(n): time for SelectSort on an n element array. T(n) = T(n 1) + n for n > 1 and T(1) = 1 for n = 1 T(n) = (n2 ).
Sariel (UIUC) CS473 9 Spring 2011 9 / 42

Selection Sort
Sort a given array A[1..n] of integers. Recursive version of Selection sort.
SelectSort(A[1..n]): if n = 1 return Find smallest number in A. Swap A[1] and A[i] SelectSort(A[2..n])

Let A[i] be smallest number

T(n): time for SelectSort on an n element array. T(n) = T(n 1) + n for n > 1 and T(1) = 1 for n = 1 T(n) = (n2 ).
Sariel (UIUC) CS473 9 Spring 2011 9 / 42

Selection Sort
Sort a given array A[1..n] of integers. Recursive version of Selection sort.
SelectSort(A[1..n]): if n = 1 return Find smallest number in A. Swap A[1] and A[i] SelectSort(A[2..n])

Let A[i] be smallest number

T(n): time for SelectSort on an n element array. T(n) = T(n 1) + n for n > 1 and T(1) = 1 for n = 1 T(n) = (n2 ).
Sariel (UIUC) CS473 9 Spring 2011 9 / 42

thunderclap the world will vanish.

Of course, being good computer scientists, we read this story and immediately substitute n for the hardwired constant sixty-four.4 How can we move a tower of n disks from one needle to another, using a third needles as an occasional placeholder, never placing any disk on top of a smaller disk?

Tower of Hanoi

The Tower of Hanoi puzzle

The trick to solving this puzzle is to think recursively. Instead of trying to solve the entire puzzle all at once, lets concentrate on moving just the largest disk. We cant move it at the beginning, Move the other n disks from peg have peg 2, one 1 disks a time. because allstack of disks are covering it; we 0 toto move those n disk at to the third needle before we cannot putnth larger disk on a we move the nth disk, we have to move those Rule: can move the a disk. And then after smaller disk. n 1 disks back on top of it. So now all we have to gure out is how to. . .

Question: what is a strategy and how many moves does it take?

3 4

This English translation is from W. W. Rouse Ball and H. S. M. Coxeters book Mathematical Recreations and Essays. Recognizing that the underlying mathematical abstraction would10 unchanged, we may also freely use cookies and be Sariel (UIUC) CS473 Spring 2011 10 / 42

Algorithms

Lecture 1: Recursion

Tower of Hanoi via Recursion

STOP!! Thats it! Were done! Weve successfully reduced the n-disk Tower of Hanoi problem to two instances of the (n 1)-disk Tower of Hanoi problem, which we can gleefully hand off to the Recursion Fairy (or, to carry the original story further, to the junior monks at the temple).

recursion

recursion

The Tower of Hanoi algorithm; ignore everything but the bottom disk

Our algorithm does make one subtle but important assumption: there is a largest disk. In other words, our recursive algorithm works for any n 1, but it breaks down when n = 0. We must handle that base case directly. Fortunately, the monks at Benares, being good Buddhists, are quite adept at moving zero disks from one needle to another.

The base case for the Tower of Hanoi algorithm; there is no bottom disk

While its tempting to think about how all those smaller disks get movedin other words, what happens when the recursion is unfoldedits not necessary. In fact, for more complicated problems, (UIUC) up the recursion is a CS473 distraction. Our11 only task is to reduce the problem to one 11 / 42 Sariel opening Spring 2011

Recursive Algorithm
Hanoi(n, src, dest, tmp): If (n > 0) then Hanoi(n 1, src, tmp, dest) Move disk n from src to dest Hanoi(n 1, tmp, dest, src)

T(n): time to move n disks via recursive strategy T(n) = 2T(n 1) + 1 n>1 and T(1) = 1

Sariel (UIUC)

CS473

12

Spring 2011

12 / 42

Recursive Algorithm
Hanoi(n, src, dest, tmp): If (n > 0) then Hanoi(n 1, src, tmp, dest) Move disk n from src to dest Hanoi(n 1, tmp, dest, src)

T(n): time to move n disks via recursive strategy T(n) = 2T(n 1) + 1 n>1 and T(1) = 1

Sariel (UIUC)

CS473

12

Spring 2011

12 / 42

Recursive Algorithm
Hanoi(n, src, dest, tmp): If (n > 0) then Hanoi(n 1, src, tmp, dest) Move disk n from src to dest Hanoi(n 1, tmp, dest, src)

T(n): time to move n disks via recursive strategy T(n) = 2T(n 1) + 1 n>1 and T(1) = 1

Sariel (UIUC)

CS473

12

Spring 2011

12 / 42

Analysis

T(n) = = = = = = = =

2T(n 1) + 1 22 T(n 2) + 2 + 1 ... 2i T(n i) + 2i1 + 2i2 + . . . + 1 ... 2n1 T(1) + 2n2 + . . . + 1 2n1 + 2n2 + . . . + 1 (2n 1)/(2 1) = 2n 1

Sariel (UIUC)

CS473

13

Spring 2011

13 / 42

Non-Recursive Algorithms for Tower of Hanoi

Pegs numbered 0, 1, 2 Non-recursive Algorithm 1: Always move smallest disk forward if n is even, backward if n is odd. Never move the same disk twice in a row. Done when no legal move. Non-recursive Algorithm 2: Let (n) be the smallest integer k such that n/2k is not an integer. Example: (40) = 4, (18) = 2. In step i move disk (i) forward if n i is even and backward if n i is odd. Moves are exactly same as those of recursive algorithm. Prove by induction.
Sariel (UIUC) CS473 14 Spring 2011 14 / 42

Non-Recursive Algorithms for Tower of Hanoi

Pegs numbered 0, 1, 2 Non-recursive Algorithm 1: Always move smallest disk forward if n is even, backward if n is odd. Never move the same disk twice in a row. Done when no legal move. Non-recursive Algorithm 2: Let (n) be the smallest integer k such that n/2k is not an integer. Example: (40) = 4, (18) = 2. In step i move disk (i) forward if n i is even and backward if n i is odd. Moves are exactly same as those of recursive algorithm. Prove by induction.
Sariel (UIUC) CS473 14 Spring 2011 14 / 42

Non-Recursive Algorithms for Tower of Hanoi

Pegs numbered 0, 1, 2 Non-recursive Algorithm 1: Always move smallest disk forward if n is even, backward if n is odd. Never move the same disk twice in a row. Done when no legal move. Non-recursive Algorithm 2: Let (n) be the smallest integer k such that n/2k is not an integer. Example: (40) = 4, (18) = 2. In step i move disk (i) forward if n i is even and backward if n i is odd. Moves are exactly same as those of recursive algorithm. Prove by induction.
Sariel (UIUC) CS473 14 Spring 2011 14 / 42

Part II Divide and Conquer

Sariel (UIUC)

CS473

15

Spring 2011

15 / 42

Divide and Conquer Paradigm

Divide and Conquer is a common and useful type of recursion

Approach
Break problem instance into smaller instances - divide step Recursively solve problem on smaller instances Combine solutions to smaller instances to obtain a solution to the original instance - conquer step Question: Why is this not plain recursion? In divide and conquer, each smaller instance is typically at least a constant factor smaller than the original instance which leads to ecient running times. There are many examples of this particular type of recursion that it deserves its own treatment.
Sariel (UIUC) CS473 16 Spring 2011 16 / 42

Divide and Conquer Paradigm

Divide and Conquer is a common and useful type of recursion

Approach
Break problem instance into smaller instances - divide step Recursively solve problem on smaller instances Combine solutions to smaller instances to obtain a solution to the original instance - conquer step Question: Why is this not plain recursion? In divide and conquer, each smaller instance is typically at least a constant factor smaller than the original instance which leads to ecient running times. There are many examples of this particular type of recursion that it deserves its own treatment.
Sariel (UIUC) CS473 16 Spring 2011 16 / 42

Divide and Conquer Paradigm

Divide and Conquer is a common and useful type of recursion

Approach
Break problem instance into smaller instances - divide step Recursively solve problem on smaller instances Combine solutions to smaller instances to obtain a solution to the original instance - conquer step Question: Why is this not plain recursion? In divide and conquer, each smaller instance is typically at least a constant factor smaller than the original instance which leads to ecient running times. There are many examples of this particular type of recursion that it deserves its own treatment.
Sariel (UIUC) CS473 16 Spring 2011 16 / 42

Sorting
Input Given an array of n elements Goal Rearrange them in ascending order

Sariel (UIUC)

CS473

17

Spring 2011

17 / 42

Merge Sort [von Neumann]

MergeSort
1

Input: Array A[1 . . . n] ALGORITHMS

Divide into subarrays A[1 . . . m] and A[m + 1 . . . n], where m = n/2 ALGOR ITHMS Recursively MergeSort A[1 . . . m] and A[m + 1 . . . n] AGLOR HIMST

Merge the sorted arrays AGHILMORST

Sariel (UIUC) CS473 18 Spring 2011 18 / 42

Merge Sort [von Neumann]

MergeSort
1

Input: Array A[1 . . . n] ALGORITHMS

Divide into subarrays A[1 . . . m] and A[m + 1 . . . n], where m = n/2 ALGOR ITHMS Recursively MergeSort A[1 . . . m] and A[m + 1 . . . n] AGLOR HIMST

Merge the sorted arrays AGHILMORST

Sariel (UIUC) CS473 18 Spring 2011 18 / 42

Merge Sort [von Neumann]

MergeSort
1

Input: Array A[1 . . . n] ALGORITHMS

Divide into subarrays A[1 . . . m] and A[m + 1 . . . n], where m = n/2 ALGOR ITHMS Recursively MergeSort A[1 . . . m] and A[m + 1 . . . n] AGLOR HIMST

Merge the sorted arrays AGHILMORST

Sariel (UIUC) CS473 18 Spring 2011 18 / 42

Merge Sort [von Neumann]

MergeSort
1

Input: Array A[1 . . . n] ALGORITHMS

Divide into subarrays A[1 . . . m] and A[m + 1 . . . n], where m = n/2 ALGOR ITHMS Recursively MergeSort A[1 . . . m] and A[m + 1 . . . n] AGLOR HIMST

Merge the sorted arrays AGHILMORST

Sariel (UIUC) CS473 18 Spring 2011 18 / 42

Merge Sort [von Neumann]

MergeSort
1

Input: Array A[1 . . . n] ALGORITHMS

Divide into subarrays A[1 . . . m] and A[m + 1 . . . n], where m = n/2 ALGOR ITHMS Recursively MergeSort A[1 . . . m] and A[m + 1 . . . n] AGLOR HIMST

Merge the sorted arrays AGHILMORST

Sariel (UIUC) CS473 18 Spring 2011 18 / 42

Merging Sorted Arrays

Use a new array C to store the merged array Scan A and B from left-to-right, storing elements in C in order AGLOR HIMST AGHILMORST Merge two arrays using only constantly more extra space (in-place merge sort): doable but complicated and typically impractical

Sariel (UIUC)

CS473

19

Spring 2011

19 / 42

Merging Sorted Arrays

Use a new array C to store the merged array Scan A and B from left-to-right, storing elements in C in order AGLOR HIMST AGHILMORST Merge two arrays using only constantly more extra space (in-place merge sort): doable but complicated and typically impractical

Sariel (UIUC)

CS473

19

Spring 2011

19 / 42

Merging Sorted Arrays

Use a new array C to store the merged array Scan A and B from left-to-right, storing elements in C in order AGLOR HIMST AGHILMORST Merge two arrays using only constantly more extra space (in-place merge sort): doable but complicated and typically impractical

Sariel (UIUC)

CS473

19

Spring 2011

19 / 42

Merging Sorted Arrays

Use a new array C to store the merged array Scan A and B from left-to-right, storing elements in C in order AGLOR HIMST AGHILMORST Merge two arrays using only constantly more extra space (in-place merge sort): doable but complicated and typically impractical

Sariel (UIUC)

CS473

19

Spring 2011

19 / 42

Merging Sorted Arrays

Use a new array C to store the merged array Scan A and B from left-to-right, storing elements in C in order AGLOR HIMST AGHILMORST Merge two arrays using only constantly more extra space (in-place merge sort): doable but complicated and typically impractical

Sariel (UIUC)

CS473

19

Spring 2011

19 / 42

Merging Sorted Arrays

Use a new array C to store the merged array Scan A and B from left-to-right, storing elements in C in order AGLOR HIMST AGHILMORST Merge two arrays using only constantly more extra space (in-place merge sort): doable but complicated and typically impractical

Sariel (UIUC)

CS473

19

Spring 2011

19 / 42

Running Time
T(n): time for merge sort to sort an n element array T(n) = T( n/2 ) + T( n/2 ) + cn What do we want as a solution to the recurrence? Almost always only an asymptotically tight bound. That is we want to know f(n) such that T(n) = (f(n)). T(n) = O(f(n)) - upper bound T(n) = (f(n)) - lower bound

Sariel (UIUC)

CS473

20

Spring 2011

20 / 42

Running Time
T(n): time for merge sort to sort an n element array T(n) = T( n/2 ) + T( n/2 ) + cn What do we want as a solution to the recurrence? Almost always only an asymptotically tight bound. That is we want to know f(n) such that T(n) = (f(n)). T(n) = O(f(n)) - upper bound T(n) = (f(n)) - lower bound

Sariel (UIUC)

CS473

20

Spring 2011

20 / 42

Running Time
T(n): time for merge sort to sort an n element array T(n) = T( n/2 ) + T( n/2 ) + cn What do we want as a solution to the recurrence? Almost always only an asymptotically tight bound. That is we want to know f(n) such that T(n) = (f(n)). T(n) = O(f(n)) - upper bound T(n) = (f(n)) - lower bound

Sariel (UIUC)

CS473

20

Spring 2011

20 / 42

Solving Recurrences: Some Techniques

Know some basic math: geometric series, logarithms, exponentials, elementary calculus Expand the recurrence and spot a pattern and use simple math Recursion tree method imagine the computation as a tree Guess and verify useful for proving upper and lower bounds even if not tight bounds Albert Einstein: Everything should be made as simple as possible, but not simpler. Know where to be loose in analysis and where to be tight. Comes with practice, practice, practice!

Sariel (UIUC)

CS473

21

Spring 2011

21 / 42

Solving Recurrences: Some Techniques

Know some basic math: geometric series, logarithms, exponentials, elementary calculus Expand the recurrence and spot a pattern and use simple math Recursion tree method imagine the computation as a tree Guess and verify useful for proving upper and lower bounds even if not tight bounds Albert Einstein: Everything should be made as simple as possible, but not simpler. Know where to be loose in analysis and where to be tight. Comes with practice, practice, practice!

Sariel (UIUC)

CS473

21

Spring 2011

21 / 42

Recursion Trees
MergeSort: n is a power of 2
1

Unroll the recurrence. T(n) = 2T(n/2) + cn

n cn

n/2 cn/2

n/2 cn/2

n/4 cn/4

n/4 cn/4

n/4 cn/4

n/4 cn/4

2 3

Identify a pattern. At the ith level total work is cn Sum over all levels. The number of levels is log n. So total is cn log n = O(n log n)

Sariel (UIUC)

CS473

22

Spring 2011

22 / 42

Recursion Trees
MergeSort: n is a power of 2
1

Unroll the recurrence. T(n) = 2T(n/2) + cn

n cn

n/2 cn/2

n/2 cn/2

n/4 cn/4

n/4 cn/4

n/4 cn/4

n/4 cn/4

2 3

Identify a pattern. At the ith level total work is cn Sum over all levels. The number of levels is log n. So total is cn log n = O(n log n)

Sariel (UIUC)

CS473

22

Spring 2011

22 / 42

Recursion Trees
MergeSort: n is a power of 2
1

Unroll the recurrence. T(n) = 2T(n/2) + cn

n cn

n/2 cn/2

n/2 cn/2

n/4 cn/4

n/4 cn/4

n/4 cn/4

n/4 cn/4

2 3

Identify a pattern. At the ith level total work is cn Sum over all levels. The number of levels is log n. So total is cn log n = O(n log n)

Sariel (UIUC)

CS473

22

Spring 2011

22 / 42

Recursion Trees
MergeSort: n is a power of 2
1

Unroll the recurrence. T(n) = 2T(n/2) + cn

n cn

n/2 cn/2

n/2 cn/2

n/4 cn/4

n/4 cn/4

n/4 cn/4

n/4 cn/4

2 3

Identify a pattern. At the ith level total work is cn Sum over all levels. The number of levels is log n. So total is cn log n = O(n log n)

Sariel (UIUC)

CS473

22

Spring 2011

22 / 42

Recursion Trees
MergeSort: n is a power of 2
1

Unroll the recurrence. T(n) = 2T(n/2) + cn

n cn

n/2 cn/2

n/2 cn/2

n/4 cn/4

n/4 cn/4

n/4 cn/4

n/4 cn/4

2 3

Identify a pattern. At the ith level total work is cn Sum over all levels. The number of levels is log n. So total is cn log n = O(n log n)

Sariel (UIUC)

CS473

22

Spring 2011

22 / 42

MergeSort Analysis
When n is not a power of 2

When n is not a power of 2, the running time of mergesort is expressed as T(n) = T( n/2 ) + T( n/2 ) + cn

n1 = 2k1 < n 2k = n2 (n1 , n2 powers of 2) T(n1 ) < T(n) T(n2 ) (Why?) T(n) = (n log n) since n/2 n1 < n n2 2n.

Sariel (UIUC)

CS473

23

Spring 2011

23 / 42

MergeSort Analysis
When n is not a power of 2

When n is not a power of 2, the running time of mergesort is expressed as T(n) = T( n/2 ) + T( n/2 ) + cn

n1 = 2k1 < n 2k = n2 (n1 , n2 powers of 2) T(n1 ) < T(n) T(n2 ) (Why?) T(n) = (n log n) since n/2 n1 < n n2 2n.

Sariel (UIUC)

CS473

23

Spring 2011

23 / 42

MergeSort Analysis
When n is not a power of 2

When n is not a power of 2, the running time of mergesort is expressed as T(n) = T( n/2 ) + T( n/2 ) + cn

n1 = 2k1 < n 2k = n2 (n1 , n2 powers of 2) T(n1 ) < T(n) T(n2 ) (Why?) T(n) = (n log n) since n/2 n1 < n n2 2n.

Sariel (UIUC)

CS473

23

Spring 2011

23 / 42

MergeSort Analysis
When n is not a power of 2

When n is not a power of 2, the running time of mergesort is expressed as T(n) = T( n/2 ) + T( n/2 ) + cn

n1 = 2k1 < n 2k = n2 (n1 , n2 powers of 2) T(n1 ) < T(n) T(n2 ) (Why?) T(n) = (n log n) since n/2 n1 < n n2 2n.

Sariel (UIUC)

CS473

23

Spring 2011

23 / 42

Recursion Trees
MergeSort: n is not a power of 2

T(n) = T( n/2 ) + T( n/2 ) + cn Observation: For any number x, x/2 + x/2 = x.

Sariel (UIUC)

CS473

24

Spring 2011

24 / 42

When n is not a power of 2: Guess and Verify

If n is power of 2 we saw that T(n) = (n log n). Can guess that T(n) = (n log n) for all n. Verify? proof by induction! Induction Hypothesis: T(n) 2cn log n for all n 1 Base Case: n = 1. T(1) = 0 since no need to do any work and 2cn log n = 0 for n = 1. Induction Step Assume T(k) 2ck log k for all k < n and prove it for k = n.

Sariel (UIUC)

CS473

25

Spring 2011

25 / 42

When n is not a power of 2: Guess and Verify

If n is power of 2 we saw that T(n) = (n log n). Can guess that T(n) = (n log n) for all n. Verify? proof by induction! Induction Hypothesis: T(n) 2cn log n for all n 1 Base Case: n = 1. T(1) = 0 since no need to do any work and 2cn log n = 0 for n = 1. Induction Step Assume T(k) 2ck log k for all k < n and prove it for k = n.

Sariel (UIUC)

CS473

25

Spring 2011

25 / 42

Induction Step
We have T(n) =

T( n/2 ) + T( n/2 ) + cn 2c n/2 log n/2 + 2c n/2 log n/2 + cn (by induct 2c n/2 log n/2 + 2c n/2 log n/2 + cn 2c( n/2 + n/2 ) log n/2 + cn 2cn log n/2 + cn 2cn log(2n/3) + cn (since n/2 2n/3 for all n 2) 2cn log n + cn(1 2 log 3/2) 2cn log n + cn(log 2 log 9/4) 2cn log n

Sariel (UIUC)

CS473

26

Spring 2011

26 / 42

Guess and Verify

The math worked out like magic! Why was 2cn log n chosen instead of say 4cn log n? Typically we dont know upfront what constant to choose. Instead we assume that T(n) cn log n for some constant that will be xed later. All we need to prove that there is some suciently large constant that will make the algebra go through. We need to choose such that log 3/2 > 1. Typically you do the algebra with and then show at the end that can be chosen to be suciently large constant.

Sariel (UIUC)

CS473

27

Spring 2011

27 / 42

Guess and Verify

The math worked out like magic! Why was 2cn log n chosen instead of say 4cn log n? Typically we dont know upfront what constant to choose. Instead we assume that T(n) cn log n for some constant that will be xed later. All we need to prove that there is some suciently large constant that will make the algebra go through. We need to choose such that log 3/2 > 1. Typically you do the algebra with and then show at the end that can be chosen to be suciently large constant.

Sariel (UIUC)

CS473

27

Spring 2011

27 / 42

Guess and Verify: When is a guess incorrect?

Suppose we guessed that the soln to the mergesort recurrent is T(n) = O(n). We try to prove by induction that T(n) cn for some constant . Induction Step: attempt T(n) = T( n/2 ) + T( n/2 ) + cn c n/2 + c n/2 + cn cn + cn ( + 1)cn

But we want to show that T(n) cn! So guess does not work for any constant . Suggests that our guess is incorrect.

Sariel (UIUC)

CS473

28

Spring 2011

28 / 42

Selection Sort vs Merge Sort

Selection Sort spends O(n) work to reduce problem from n to n 1 leading to O(n2 ) running time. Merge Sort spends O(n) time after reducing problem to two instances of size n/2 each. Running time is O(n log n) Question: Merge Sort splits into 2 (roughly) equal sized arrays. Can we do better by splitting into more than 2 arrays? Say k arrays of size n/k each?

Sariel (UIUC)

CS473

29

Spring 2011

29 / 42

Selection Sort vs Merge Sort

Selection Sort spends O(n) work to reduce problem from n to n 1 leading to O(n2 ) running time. Merge Sort spends O(n) time after reducing problem to two instances of size n/2 each. Running time is O(n log n) Question: Merge Sort splits into 2 (roughly) equal sized arrays. Can we do better by splitting into more than 2 arrays? Say k arrays of size n/k each?

Sariel (UIUC)

CS473

29

Spring 2011

29 / 42

Quick Sort
Quick Sort[Hoare]
1 2

Pick a pivot element from array Split array into 3 subarrays: those smaller than pivot, those larger than pivot, and the pivot itself. Linear scan of array does it. Time is O(n) Recursively sort the subarrays, and concatenate them.

Example: array: 16, 12, 14, 20, 5, 3, 18, 19, 1 pivot: 16 split into 12, 14, 5, 3, 1 and 20, 19, 18 and recursively sort put them together with pivot in middle
Sariel (UIUC) CS473 30 Spring 2011 30 / 42

Quick Sort
Quick Sort[Hoare]
1 2

Pick a pivot element from array Split array into 3 subarrays: those smaller than pivot, those larger than pivot, and the pivot itself. Linear scan of array does it. Time is O(n) Recursively sort the subarrays, and concatenate them.

Example: array: 16, 12, 14, 20, 5, 3, 18, 19, 1 pivot: 16 split into 12, 14, 5, 3, 1 and 20, 19, 18 and recursively sort put them together with pivot in middle
Sariel (UIUC) CS473 30 Spring 2011 30 / 42

Quick Sort
Quick Sort[Hoare]
1 2

Pick a pivot element from array Split array into 3 subarrays: those smaller than pivot, those larger than pivot, and the pivot itself. Linear scan of array does it. Time is O(n) Recursively sort the subarrays, and concatenate them.

Example: array: 16, 12, 14, 20, 5, 3, 18, 19, 1 pivot: 16 split into 12, 14, 5, 3, 1 and 20, 19, 18 and recursively sort put them together with pivot in middle
Sariel (UIUC) CS473 30 Spring 2011 30 / 42

Quick Sort
Quick Sort[Hoare]
1 2

Pick a pivot element from array Split array into 3 subarrays: those smaller than pivot, those larger than pivot, and the pivot itself. Linear scan of array does it. Time is O(n) Recursively sort the subarrays, and concatenate them.

Example: array: 16, 12, 14, 20, 5, 3, 18, 19, 1 pivot: 16 split into 12, 14, 5, 3, 1 and 20, 19, 18 and recursively sort put them together with pivot in middle
Sariel (UIUC) CS473 30 Spring 2011 30 / 42

Time Analysis
Let k be the rank of the chosen pivot. Then, T(n) = T(k 1) + T(n k) + O(n) If k = n/2 then T(n) = T( n/2 1)+T( n/2 )+O(n) 2T(n/2)+O(n). Then, T(n) = O(n log n).
Theoretically, median can be found in linear time.

Typically, pivot is the rst or last element of array. Then, T(n) = max (T(k 1) + T(n k) + O(n))
1kn

In the worst case T(n) = T(n 1) + O(n), which means T(n) = O(n2 ). Happens if array is already sorted and pivot is always rst element.

Sariel (UIUC)

CS473

31

Spring 2011

31 / 42

Time Analysis
Let k be the rank of the chosen pivot. Then, T(n) = T(k 1) + T(n k) + O(n) If k = n/2 then T(n) = T( n/2 1)+T( n/2 )+O(n) 2T(n/2)+O(n). Then, T(n) = O(n log n).
Theoretically, median can be found in linear time.

Typically, pivot is the rst or last element of array. Then, T(n) = max (T(k 1) + T(n k) + O(n))
1kn

In the worst case T(n) = T(n 1) + O(n), which means T(n) = O(n2 ). Happens if array is already sorted and pivot is always rst element.

Sariel (UIUC)

CS473

31

Spring 2011

31 / 42

Time Analysis
Let k be the rank of the chosen pivot. Then, T(n) = T(k 1) + T(n k) + O(n) If k = n/2 then T(n) = T( n/2 1)+T( n/2 )+O(n) 2T(n/2)+O(n). Then, T(n) = O(n log n).
Theoretically, median can be found in linear time.

Typically, pivot is the rst or last element of array. Then, T(n) = max (T(k 1) + T(n k) + O(n))
1kn

In the worst case T(n) = T(n 1) + O(n), which means T(n) = O(n2 ). Happens if array is already sorted and pivot is always rst element.

Sariel (UIUC)

CS473

31

Spring 2011

31 / 42

Time Analysis
Let k be the rank of the chosen pivot. Then, T(n) = T(k 1) + T(n k) + O(n) If k = n/2 then T(n) = T( n/2 1)+T( n/2 )+O(n) 2T(n/2)+O(n). Then, T(n) = O(n log n).
Theoretically, median can be found in linear time.

Typically, pivot is the rst or last element of array. Then, T(n) = max (T(k 1) + T(n k) + O(n))
1kn

In the worst case T(n) = T(n 1) + O(n), which means T(n) = O(n2 ). Happens if array is already sorted and pivot is always rst element.

Sariel (UIUC)

CS473

31

Spring 2011

31 / 42

Part III Fast Multiplication

Sariel (UIUC)

CS473

32

Spring 2011

32 / 42

Multiplying Numbers
Problem Given two n-digit numbers x and y, compute their product.

Grade School Multiplication

Compute partial product by multiplying each digit of y with x and adding the partial products. 3141 2718 25128 3141 21987 6282 8537238
Sariel (UIUC) CS473 33 Spring 2011 33 / 42

Time Analysis of Grade School Multiplication

Each partial product: (n) Number of partial products: (n) Addition of partial products: (n2 ) Total time: (n2 )

Sariel (UIUC)

CS473

34

Spring 2011

34 / 42

A Trick of Gauss
Carl Fridrich Gauss: 17771855 Prince of Mathematicians

Observation: Multiply two complex numbers: (a + bi) and (c + di) (a + bi)(c + di) = ac bd + (ad + bc)i

How many multiplications do we need? Only 3! If we do extra additions and subtractions. Compute ac, bd, (a + b)(c + d). Then (ad + bc) = (a + b)(c + d) ac bd
Sariel (UIUC) CS473 35 Spring 2011 35 / 42

A Trick of Gauss
Carl Fridrich Gauss: 17771855 Prince of Mathematicians

Observation: Multiply two complex numbers: (a + bi) and (c + di) (a + bi)(c + di) = ac bd + (ad + bc)i

How many multiplications do we need? Only 3! If we do extra additions and subtractions. Compute ac, bd, (a + b)(c + d). Then (ad + bc) = (a + b)(c + d) ac bd
Sariel (UIUC) CS473 35 Spring 2011 35 / 42

A Trick of Gauss
Carl Fridrich Gauss: 17771855 Prince of Mathematicians

Observation: Multiply two complex numbers: (a + bi) and (c + di) (a + bi)(c + di) = ac bd + (ad + bc)i

How many multiplications do we need? Only 3! If we do extra additions and subtractions. Compute ac, bd, (a + b)(c + d). Then (ad + bc) = (a + b)(c + d) ac bd
Sariel (UIUC) CS473 35 Spring 2011 35 / 42

Divide and Conquer

Assume n is a power of 2 for simplicity and numbers are in decimal. x = xn1 xn2 . . . x0 and y = yn1 yn2 . . . y0 x = 10n/2 xL + xR where xL = xn1 . . . xn/2 and xR = xn/21 . . . x0 y = 10n/2 yL + yR where yL = yn1 . . . yn/2 and yR = yn/21 . . . y0 Therefore

xy = (10n/2 xL +xR )(10n/2 yL +yR ) = 10n xL yL +10n/2 (xL yR +xR yL )+xR

Sariel (UIUC)

CS473

36

Spring 2011

36 / 42

Example

1234 5678 = (100 12 + 34) (100 56 + 78) = 10000 12 56 +100 (12 78 + 34 56) +34 78

Sariel (UIUC)

CS473

37

Spring 2011

37 / 42

Time Analysis

xy = (10n/2 xL +xR )(10n/2 yL +yR ) = 10n xL yL +10n/2 (xL yR +xR yL )+xR 4 recursive multiplications of number of size n/2 each plus 4 additions and left shifts (adding enough 0s to the right) T(n) = 4T(n/2) + O(n) T(1) = O(1)

T(n) = (n2 ). No better than grade school multiplication! Can we invoke Gausss trick here?

Sariel (UIUC)

CS473

38

Spring 2011

38 / 42

Time Analysis

xy = (10n/2 xL +xR )(10n/2 yL +yR ) = 10n xL yL +10n/2 (xL yR +xR yL )+xR 4 recursive multiplications of number of size n/2 each plus 4 additions and left shifts (adding enough 0s to the right) T(n) = 4T(n/2) + O(n) T(1) = O(1)

T(n) = (n2 ). No better than grade school multiplication! Can we invoke Gausss trick here?

Sariel (UIUC)

CS473

38

Spring 2011

38 / 42

Time Analysis

xy = (10n/2 xL +xR )(10n/2 yL +yR ) = 10n xL yL +10n/2 (xL yR +xR yL )+xR 4 recursive multiplications of number of size n/2 each plus 4 additions and left shifts (adding enough 0s to the right) T(n) = 4T(n/2) + O(n) T(1) = O(1)

T(n) = (n2 ). No better than grade school multiplication! Can we invoke Gausss trick here?

Sariel (UIUC)

CS473

38

Spring 2011

38 / 42

Time Analysis

xy = (10n/2 xL +xR )(10n/2 yL +yR ) = 10n xL yL +10n/2 (xL yR +xR yL )+xR 4 recursive multiplications of number of size n/2 each plus 4 additions and left shifts (adding enough 0s to the right) T(n) = 4T(n/2) + O(n) T(1) = O(1)

T(n) = (n2 ). No better than grade school multiplication! Can we invoke Gausss trick here?

Sariel (UIUC)

CS473

38

Spring 2011

38 / 42

Improving the Running Time

xy = (10n/2 xL +xR )(10n/2 yL +yR ) = 10n xL yL +10n/2 (xL yR +xR yL )+xR Gauss trick: xL yR + xR yL = (xL + xR )(yL + yR ) xL yL xR yR Recursively compute only xL yL , xR yR , (xL + xR )(yL + yR ).

Time Analysis
Running time is given by T(n) = 3T(n/2) + O(n) which means T(n) = O(nlog2 3 ) = O(n1.585 )
Sariel (UIUC) CS473 39 Spring 2011 39 / 42

T(1) = O(1)

Improving the Running Time

xy = (10n/2 xL +xR )(10n/2 yL +yR ) = 10n xL yL +10n/2 (xL yR +xR yL )+xR Gauss trick: xL yR + xR yL = (xL + xR )(yL + yR ) xL yL xR yR Recursively compute only xL yL , xR yR , (xL + xR )(yL + yR ).

Time Analysis
Running time is given by T(n) = 3T(n/2) + O(n) which means T(n) = O(nlog2 3 ) = O(n1.585 )
Sariel (UIUC) CS473 39 Spring 2011 39 / 42

T(1) = O(1)

Improving the Running Time

xy = (10n/2 xL +xR )(10n/2 yL +yR ) = 10n xL yL +10n/2 (xL yR +xR yL )+xR Gauss trick: xL yR + xR yL = (xL + xR )(yL + yR ) xL yL xR yR Recursively compute only xL yL , xR yR , (xL + xR )(yL + yR ).

Time Analysis
Running time is given by T(n) = 3T(n/2) + O(n) which means T(n) = O(nlog2 3 ) = O(n1.585 )
Sariel (UIUC) CS473 39 Spring 2011 39 / 42

T(1) = O(1)

Improving the Running Time

xy = (10n/2 xL +xR )(10n/2 yL +yR ) = 10n xL yL +10n/2 (xL yR +xR yL )+xR Gauss trick: xL yR + xR yL = (xL + xR )(yL + yR ) xL yL xR yR Recursively compute only xL yL , xR yR , (xL + xR )(yL + yR ).

Time Analysis
Running time is given by T(n) = 3T(n/2) + O(n) which means T(n) = O(nlog2 3 ) = O(n1.585 )
Sariel (UIUC) CS473 39 Spring 2011 39 / 42

T(1) = O(1)

State of the Art

Schnhage-Strassen 1971: O(n log n log log n) time using o Fast-Fourier-Transform (FFT) Martin Frer 2007: O(n log n2O(log u

n)

) time

Conjecture: there is an O(n log n) time algorithm

Sariel (UIUC)

CS473

40

Spring 2011

40 / 42

Analyzing the Recurrences

Basic divide and conquer: T(n) = 4T(n/2) + O(n), T(1) = 1. Claim: T(n) = (n2 ). Saving a multiplication: T(n) = 3T(n/2) + O(n), T(1) = 1. Claim: T(n) = (n1+log 1.5 ) Use recursion tree method: In both cases, depth of recursion L = log n. Work at depth i is 4i n/2i and 3i n/2i respectively: number of children at depth i times the work at each child Total work is therefore n L 2i and n L (3/2)i respectively. i=0 i=0

Sariel (UIUC)

CS473

41

Spring 2011

41 / 42

Analyzing the Recurrences

Basic divide and conquer: T(n) = 4T(n/2) + O(n), T(1) = 1. Claim: T(n) = (n2 ). Saving a multiplication: T(n) = 3T(n/2) + O(n), T(1) = 1. Claim: T(n) = (n1+log 1.5 ) Use recursion tree method: In both cases, depth of recursion L = log n. Work at depth i is 4i n/2i and 3i n/2i respectively: number of children at depth i times the work at each child Total work is therefore n L 2i and n L (3/2)i respectively. i=0 i=0

Sariel (UIUC)

CS473

41

Spring 2011

41 / 42

Recursion tree analysis

Sariel (UIUC)

CS473

42

Spring 2011

42 / 42

Notes

Sariel (UIUC)

CS473

43

Spring 2011

43 / 42

Notes

Sariel (UIUC)

CS473

44

Spring 2011

44 / 42

Notes

Sariel (UIUC)

CS473

45

Spring 2011

45 / 42

Notes

Sariel (UIUC)

CS473

46

Spring 2011

46 / 42