Introduction to Algorithms

6.046J/18.401J

Lecture 4
Prof. Piotr Indyk
 Today

• Randomized algorithms: algorithms that flip

coins
– Matrix product checker: is AB=C ?
– Quicksort:
• Example of divide and conquer
• Fast and practical sorting algorithm
• Other applications on Wednesday

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.2
 Randomized Algorithms

• Algorithms that make random decisions

• That is:
– Can generate a random number x from
some range {1…R}
– Make decisions based on the value of x
• Why would it make sense ?

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.3
 Two cups, one coin

• If you always choose a fixed cup, the adversary

will put the coin in the other one, so the expected
payoff = $0
• If you choose a random cup, the expected payoff
= $0.5
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.4
 Randomized Algorithms

• Two basic types:

– Typically fast (but sometimes slow):
Las Vegas
– Typically correct (but sometimes output
garbage): Monte Carlo
• The probabilities are defined by the random
numbers of the algorithm! (not by random
choices of the problem instance)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.5
 Matrix Product

• Compute C=A×B
– Simple algorithm: O(n3) time
– Multiply two 2×2 matrices using 7 mult.
→O(n2.81…) time [Strassen’69]
– Multiply two 70 × 70 matrices using 143640
multiplications → O(n2.795…) time [Pan’78]
–…
– O(n2.376…) [Coppersmith-Winograd]

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.6
 Matrix Product Checker

• Given: n×n matrices A,B,C

• Goal: is A×B=C ?
• We will see an O(n2) algorithm that:
– If answer=YES, then Pr[output=YES]=1
– If answer=NO, then Pr[output=YES] ≤ ½

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.7
 The algorithm

• Algorithm:
– Choose a random binary vector x[1…n] ,
such that Pr[xi=1]=½ , i=1…n
– Check if ABx=Cx
• Does it run in O(n2) time ?
– YES, because ABx = A(Bx)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.8
 Correctness

• Let D=AB, need to check if D=C

• What if D=C ?
– Then Dx=Cx ,so the output is YES
• What if D≠C ?
– Presumably there exists x such that
Dx≠Cx
– We need to show there are many such x

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.9
 D≠C

?
≠

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.10
 Vector product

• Consider vectors d≠c (say, di≠ci)

• Choose a random binary x
• We have dx=cx iff (d-c)x=0
• Pr[(d-c)x=0]= ?

(d-c): d1-c1 d2-c2 … di-ci … dn-cn

= Σj≠i(dj-cj)xj + (di-ci)xi
x: x1 x2 … xi … xn

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.11
 Analysis, ctd.

• If xi=0, then (c-d)x=S1

• If xi=1, then (c-d)x=S2≠S1
• So, ≥1 of the choices gives (c-d)x≠0
→ Pr[cx=dx] ≤ ½

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.12
 Matrix Product Checker
• Is A×B=C ?
• We have an algorithm that:
– If answer=YES, then Pr[output=YES]=1
– If answer=NO, then Pr[output=YES] ≤ ½
• What if we want to reduce ½ to ¼ ?
– Run the algorithm twice, using independent random numbers
– Output YES only if both runs say YES
• Analysis:
– If answer=YES, then Pr[output1=YES, output2=YES ]=1
– If answer=NO, then
Pr[output=YES] = Pr[output1=YES, output2=YES]
= Pr[output1=YES]*Pr[output2=YES]
≤¼

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.13
 Quicksort
• Proposed by C.A.R. Hoare in 1962.
• Divide-and-conquer algorithm.
• Sorts “in place” (like insertion sort, but not
like merge sort).
• Very practical (with tuning).
• Can be viewed as a randomized Las Vegas
algorithm

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.14
 Divide and conquer
Quicksort an n-element array:
1. Divide: Partition the array into two subarrays
around a pivot x such that elements in lower
subarray ≤ x ≤ elements in upper subarray.
xx ≤≤ xx≤≤ xx xx ≥≥ xx
2. Conquer: Recursively sort the two subarrays.
3. Combine: Trivial.
Key: Linear-time partitioning subroutine.
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.15
 Pseudocode for quicksort
QUICKSORT(A, p, r)
if p < r
then q ← PARTITION(A, p, r)
QUICKSORT(A, p, q–1)
QUICKSORT(A, q+1, r)

Initial call: QUICKSORT(A, 1, n)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.16
 Partitioning subroutine
PARTITION(A, p, r) ⊳ A[ p . . r]
x ← A[ p] ⊳ pivot = A[ p]
i←p
for j ← p + 1 to r
do if A[ j] ≤ x
then i ← i + 1
exchange A[i] ↔ A[ j]
exchange A[ p] ↔ A[i]
return i
Invariant: xx ≤≤ xx ≥≥ xx ??
p i j r
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.17
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.18
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.19
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.20
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
66 55 13
13 10
10 88 33 22 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.21
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
66 55 13
13 10
10 88 33 22 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.22
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
66 55 13
13 10
10 88 33 22 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.23
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
66 55 13
13 10
10 88 33 22 11
11
66 55 33 10
10 88 13
13 22 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.24
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
66 55 13
13 10
10 88 33 22 11
11
66 55 33 10
10 88 13
13 22 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.25
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
66 55 13
13 10
10 88 33 22 11
11
66 55 33 10
10 88 13
13 22 11
11
66 55 33 22 88 13
13 10
10 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.26
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
66 55 13
13 10
10 88 33 22 11
11
66 55 33 10
10 88 13
13 22 11
11
66 55 33 22 88 13
13 10
10 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.27
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
66 55 13
13 10
10 88 33 22 11
11
66 55 33 10
10 88 13
13 22 11
11
66 55 33 22 88 13
13 10
10 11
11
i j

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.28
 Example of partitioning

66 10
10 13
13 55 88 33 22 11
11
66 55 13
13 10
10 88 33 22 11
11
66 55 33 10
10 88 13
13 22 11
11
66 55 33 22 88 13
13 10
10 11
11
22 55 33 66 88 13
13 10
10 11
11
i
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.29
 Analysis of quicksort

• Assume all input elements are distinct.

• In practice, there are better partitioning
algorithms for when duplicate input
elements may exist.
• What is the worst case running time of
Quicksort ?
xx ≤≤ xx ≥≥ xx

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.30
 Worst-case of quicksort
• Input sorted or reverse sorted.
• Partition around min or max element.
• One side of partition always has no elements.
T (n) = T (0) + T (n − 1) + Θ(n)
= Θ(1) + T (n − 1) + Θ(n)
= T (n − 1) + Θ(n)
= Θ( n 2 ) (arithmetic series)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.31
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.32
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
T(n)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.33
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
cn
T(0) T(n–1)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.34
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
cn
T(0) c(n–1)
T(0) T(n–2)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.35
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
cn
T(0) c(n–1)
T(0) c(n–2)
T(0) O

Θ(1)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.36
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
cn  n 
T(0) c(n–1) Θ ∑ k  = Θ(n 2 )
 k =1 
T(0) c(n–2)
T(0) O

Θ(1)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.37
 Worst-case recursion tree
T(n) = T(0) + T(n–1) + cn
cn  n 
Θ(1) c(n–1) Θ ∑ k  = Θ(n 2 )
 k =1 
Θ(1) c(n–2)
h=n
Θ(1) O

Θ(1)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.38
 Nice-case analysis

If we’re lucky, PARTITION splits the array evenly:

T(n) = 2T(n/2) + Θ(n)
= Θ(n lg n) (same as merge sort)

1 9
What if the split is always 10 : 10 ?
T (n) = T (101 n ) + T (109 n ) + Θ(n)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.39
 Analysis of nice case
T (n)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.40
 Analysis of nice case
cn
T (101 n ) T (109 n )

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.41
 Analysis of nice case
cn
1
10
cn 9
10
cn

T (100
1
n ) T (100
9
n ) T (100
9
n )T (100
81
n)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.42
 Analysis of nice case
cn cn
1
10
cn 9
10
cn cn
log10/9n
1
100
cn 9
100
cn 9
100
cn 81
100
cn cn
…

…
Θ(1)
Θ(1)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.43
 Analysis of nice case
cn cn
1
10
cn 9
cn cn
log10n 10
log10/9n
1
100
cn 9
100
cn 9
100
cn 81
100
cn cn
…

…
Θ(1)
Θ(1)
cn log10n ≤ T(n) ≤ cn log10/9n + Ο(n)
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.44
 Randomized quicksort
• Partition around a random element. I.e.,
around A[t] , where t chosen uniformly
at random from {p…r}
• We will show that the expected time is
O(n log n)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.45
 “Paranoid” quicksort

• Will modify the algorithm to make it easier to

analyze:
• Repeat:
• Choose the pivot to be a random element
of the array
• Perform PARTITION
• Until the resulting split is “lucky”, i.e., not
worse than 1/10: 9/10
• Recurse on both sub-arrays
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.46
 Analysis
• Let T(n) be an upper bound on the expected
running time on any array of n elements
• Consider any input of size n
• The time needed to sort the input is bounded
from the above by a sum of
• The time needed to sort the left subarray
• The time needed to sort the right subarray
• The number of iterations until we get a
lucky split, times cn
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.47
 Expectations

• By linearity of expectation:

T (n) ≤ max T (i ) + T (n − i ) + E[# partitions ] • cn

where maximum is taken over i ∈ [n/10,9n/10]

• We will show that E[#partitions] is ≤ 10/8
• Therefore:
T (n) ≤ max T (i ) + T (n − i ) + 2cn, i ∈ [n / 10,9n / 10]
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.48
 Final bound
• Can use the recursion tree argument:
• Tree depth is Θ(log n)
• Total expected work at each level is at most
10/8 cn
• The total expected time is Ο(n log n)

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.49
 Lucky partitions

• The probability that a random pivot induces

lucky partition is at least 8/10
(we are not lucky if the pivot happens to be
among the smallest/largest n/10 elements)
• If we flip a coin, with heads prob. p=8/10 ,
the expected waiting time for the first head
is 1/p = 10/8

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.50
 Quicksort in practice

• Quicksort is a great general-purpose

sorting algorithm.
• Quicksort is typically over twice as fast
as merge sort.
• Quicksort can benefit substantially from
code tuning.
• Quicksort behaves well even with
caching and virtual memory.
• Quicksort is great!
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.51
 More intuition
Suppose we alternate lucky, unlucky,
lucky, unlucky, lucky, ….
L(n) = 2U(n/2) + Θ(n) lucky
U(n) = L(n – 1) + Θ(n) unlucky
Solving:
L(n) = 2(L(n/2 – 1) + Θ(n/2)) + Θ(n)
= 2L(n/2 – 1) + Θ(n)
= Θ(n lg n) Lucky!
How can we make sure we are usually lucky?
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.52
 Randomized quicksort
analysis
Let T(n) = the random variable for the running
time of randomized quicksort on an input of size
n, assuming random numbers are independent.
For k = 0, 1, …, n–1, define the indicator
random variable
1 if PARTITION generates a k : n–k–1 split,
Xk =
0 otherwise.
E[Xk] = Pr{Xk = 1} = 1/n, since all splits are
equally likely, assuming elements are distinct.
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.53
 Analysis (continued)
T(0) + T(n–1) + Θ(n) if 0 : n–1 split,
T(1) + T(n–2) + Θ(n) if 1 : n–2 split,
T(n) =
M
T(n–1) + T(0) + Θ(n) if n–1 : 0 split,
n −1
= ∑ X k (T (k ) + T (n − k − 1) + Θ(n)) .
k =0

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.54
 Calculating expectation
 n −1 
E[T (n)] = E  ∑ X k (T (k ) + T (n − k − 1) + Θ(n) )
k =0 

Take expectations of both sides.

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.55
 Calculating expectation
 n −1 
E[T (n)] = E  ∑ X k (T (k ) + T (n − k − 1) + Θ(n) )
k =0 
n −1
= ∑ E[ X k (T (k ) + T (n − k − 1) + Θ(n) )]
k =0

Linearity of expectation.

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.56
 Calculating expectation
 n −1 
E[T (n)] = E  ∑ X k (T (k ) + T (n − k − 1) + Θ(n) )
k =0 
n −1
= ∑ E[ X k (T (k ) + T (n − k − 1) + Θ(n) )]
k =0
n −1
= ∑ E[ X k ] ⋅ E[T (k ) + T (n − k − 1) + Θ(n)]
k =0

Independence of Xk from other random

choices.

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.57
 Calculating expectation
 n −1 
E[T (n)] = E  ∑ X k (T (k ) + T (n − k − 1) + Θ(n) )
k =0 
n −1
= ∑ E[ X k (T (k ) + T (n − k − 1) + Θ(n) )]
k =0
n −1
= ∑ E[ X k ] ⋅ E[T (k ) + T (n − k − 1) + Θ(n)]
k =0
n −1 n −1 n −1
= 1 ∑ E [T (k )] + 1 ∑ E [T (n − k − 1)] + 1 ∑ Θ(n)
n k =0 n k =0 n k =0

Linearity of expectation; E[Xk] = 1/n .

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.58
 Calculating expectation
 n −1 
E[T (n)] = E  ∑ X k (T (k ) + T ( n − k − 1) + Θ(n) )
k =0 
n −1
= ∑ E[ X k (T (k ) + T (n − k − 1) + Θ(n) )]
k =0
n −1
= ∑ E[ X k ] ⋅ E[T (k ) + T (n − k − 1) + Θ(n)]
k =0
n −1 n −1 n −1
= 1 ∑ E [T (k )] + 1 ∑ E [T (n − k − 1)] + 1 ∑ Θ(n)
n k =0 n k =0 n k =0
n −1
= 2 ∑ E [T (k )] + Θ(n) Summations have
n k =1
identical terms.
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.59
 Hairy recurrence
n −1
E[T (n)] = 2 ∑ E [T (k )] + Θ(n)
n k =2
(The k = 0, 1 terms can be absorbed in the Θ(n).)
Prove: E[T(n)] ≤ an lg n for constant a > 0 .
• Choose a large enough so that an lg n
dominates E[T(n)] for sufficiently small n ≥ 2.
n −1
Use fact: ∑ k lg k ≤ 1 n 2 lg n − 1n 2
2 8 (exercise).
k =2
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.60
 Substitution method
n −1
E [T (n)] ≤ 2 ∑ ak lg k + Θ(n)
n k =2
Substitute inductive hypothesis.

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.61
 Substitution method
n −1
E [T (n)] ≤ 2 ∑ ak lg k + Θ(n)
n k =2

≤ 2a  1 n 2 lg n − 1 n 2  + Θ(n)
n 2 8 
Use fact.

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.62
 Substitution method
n −1
E [T (n)] ≤ 2 ∑ ak lg k + Θ(n)
n k =2

≤ 2a  1 n 2 lg n − 1 n 2  + Θ(n)
n 2 8 
= an lg n −  an − Θ(n) 
 4 
Express as desired – residual.

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.63
 Substitution method
n −1
E [T (n)] ≤ 2 ∑ ak lg k + Θ(n)
n k =2

= 2a  1 n 2 lg n − 1 n 2  + Θ(n)
n 2 8 
= an lg n −  an − Θ(n) 
 4 
≤ an lg n ,
if a is chosen large enough so that
an/4 dominates the Θ(n).
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.64
 • Assume Running
Running time
time
== O(n)
O(n) for
for nn
elements.
elements.

September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.65
 Randomized Algorithms
• Algorithms that make decisions based on
random coin flips.
• Can “fool” the adversary.
• The running time (or even correctness) is a
random variable; we measure the expected
running time.
• We assume all random choices are
independent .
• This is not the average case !
September 20, 2004 (c) Piotr Indyk & Charles Leiserson L4.66