Transcript Slides for Rosen, 5th edition

Chap. 7
Chapter 7:
Advanced Counting Techniques
(c)2001-2003, Michael P. Frank
1
Chap. 7
§7.1: Recurrence Relations
• A recurrence relation (R.R., or just recurrence) for
a sequence {an} is an equation that expresses an in
terms of one or more previous elements
a0, …, an−1 of the sequence, for all n≥n0.
– A recursive definition, without the base cases.
• A particular sequence (described non-recursively)
is said to solve the given recurrence relation if it is
consistent with the definition of the recurrence.
– A given recurrence relation may have many solutions.
(c)2001-2003, Michael P. Frank
§ 7.1 – Recurrence Relations
2
Chap. 7
Recurrence Relation Example
• Consider the recurrence relation
an = 2an−1 − an−2 (n≥2).
• Which of the following are solutions?
an = 3n
an = 2n
an = 5
(c)2001-2003, Michael P. Frank
§ 7.1 – Recurrence Relations
3
Chap. 7
Example Applications
• Recurrence relation for growth of a bank
account with P% interest per given period:
Mn = Mn−1 + (P/100)Mn−1
• Growth of a population in which each
organism yields 1 new one every period
starting 2 periods after its birth.
Pn = Pn−1 + Pn−2 (Fibonacci relation)
(c)2001-2003, Michael P. Frank
§ 7.1 – Recurrence Relations
4
Chap. 7
Solving Compound Interest RR
• Mn = Mn−1 + (P/100)Mn−1
= (1 + P/100) Mn−1
= r Mn−1
(let r = 1 + P/100)
(c)2001-2003, Michael P. Frank
§ 7.1 – Recurrence Relations
5
Chap. 7
Tower of Hanoi Example
• Problem: Get all disks from peg 1 to peg 2.
– Only move 1 disk at a time.
– Never set a larger disk on a smaller one.
Peg #1
(c)2001-2003, Michael P. Frank
Peg #2
§ 7.1 – Recurrence Relations
Peg #3
6
Chap. 7
Hanoi Recurrence Relation
• Let Hn = # moves for a stack of n disks.
• Optimal strategy:
– Move top n−1 disks to spare peg. (Hn−1 moves)
– Move bottom disk. (1 move)
– Move top n−1 to bottom disk. (Hn−1 moves)
• Note:
(c)2001-2003, Michael P. Frank
Hn = 2Hn−1 + 1
§ 7.1 – Recurrence Relations
7
Chap. 7
Solving Tower of Hanoi RR
Hn = 2 Hn−1 + 1
(c)2001-2003, Michael P. Frank
§ 7.1 – Recurrence Relations
8
Chap. 7
Finding Recurrence Relation
Ex: Find a recurrence relation and give initial
conditions for the number of bit strings of length n
that do not have two consecutive 0s. How many
such bit strings are there of length 5?
(c)2001-2003, Michael P. Frank
§ 7.1 – Recurrence Relations
9
Chap. 7
Codeword Enumeration
Ex:Consider a string of decimal digits a valid
codeword if it contains an even number of 0 digits.
For example, 1230407869 is valid, whereas
120987045608 is not valid. Let an be the number
of valid n-digit codewords. Find a recurrence
relation for an .
(c)2001-2003, Michael P. Frank
§ 7.1 – Recurrence Relations
10
Chap. 7
Catalan Numbers
Ex: Find a recurrence relation for Cn , the number of
ways to parenthesize the product of n+1 numbers,
x0, x1,…, xn, to specify the order of multiplication.
For example, C3 = 5.
(c)2001-2003, Michael P. Frank
§ 7.1 – Recurrence Relations
11
Chap. 7
§7.2: Solving Recurrences
General Solution Schemas
• A linear homogeneous recurrence of degree
k with constant coefficients (“kLiHoReCoCo”) is a recurrence of the form
an = c1an−1 + … + ckan−k,
where the ci are all real, and ck ≠ 0.
• The solution is uniquely determined if k
initial conditions a0…ak−1 are provided.
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
12
Chap. 7
Solving LiHoReCoCos
• Basic idea: Look for solutions of the form
an = rn, where r is a constant.
• This requires the characteristic equation:
rn = c1rn−1 + … + ckrn−k, i.e.,
rk − c1rk−1 − … − ck = 0
• The solutions (characteristic roots) can
yield an explicit formula for the sequence.
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
13
Chap. 7
Solving 2-LiHoReCoCos
• Consider an arbitrary 2-LiHoReCoCo:
an = c1an−1 + c2an−2
• It has the characteristic equation (C.E.):
r2 − c1r − c2 = 0
• Thm. 1: If this CE has 2 roots r1≠r2, then
an = α1r1n + α2r2n for n≥0
for some constants α1, α2.
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
14
Chap. 7
Example
• Solve the recurrence an = an−1 + 2an−2 given the
initial conditions a0 = 2, a1 = 7.
• Solution:
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
15
Chap. 7
Example Continued…
• To find α1 and α2, solve the equations for the initial
conditions a0 and a1:
Simplifying, we have the pair of equations:
which we can solve easily by substitution:
• Final answer:
Check: {an≥0} = 2, 7, 11, 25, 47, 97 …
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
16
Chap. 7
Example
• Find an explicit formula for the Fibonacci
numbers.
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
17
Chap. 7
The Case of Degenerate Roots
• Now, what if the C.E. r2 − c1r − c2 = 0 has
only 1 root r0?
• Theorem 2: Then,
an = α1r0n + α2nr0n, for all n≥0,
for some constants α1, α2.
• Ex: an  6an1  9an2 , a0  1, a1  6
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
18
Chap. 7
k-LiHoReCoCos
• Consider a k-LiHoReCoCo:
• It’s C.E. is:
k
r k   ci r k i  0
k
an   ci an i
i 1
i 1
• Thm.3: If this has k distinct roots ri, then the
solutions to the recurrence are of the form:
k
an    i ri
n
i 1
for all n≥0, where the αi are constants.
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
19
Chap. 7
Example
• Ex: an  6an1  11an2  6an3 ,
a0  2, a1  5, a2  15
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
20
Chap. 7
Degenerate k-LiHoReCoCos
• Suppose there are t roots r1,…,rt with
multiplicities m1,…,mt. Then:
 mi 1
 n
j
an     i , j n ri
i 1  j 0

t
for all n≥0, where all the α are constants.
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
21
Chap. 7
Example
• Ex: an  3an1  3an2  an3 ,
a0  1, a1  2, a2  1
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
22
Chap. 7
LiNoReCoCos
• Linear nonhomogeneous RRs with constant
coefficients may (unlike LiHoReCoCos)
contain some terms F(n) that depend only
on n (and not on any ai’s). General form:
an = c1an−1 + … + ckan−k + F(n)
The associated homogeneous recurrence relation
(associated LiHoReCoCo).
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
23
Chap. 7
Solutions of LiNoReCoCos
• A useful theorem about LiNoReCoCos:
– If an = p(n) is any particular solution to the
LiNoReCoCo
 k

an    ci ani   F (n)
 i 1

– Then all its solutions are of the form:
an = p(n) + h(n),
where an = h(n) is any solution to the associated
k


homogeneous RR
an    ci ani 
 i 1
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences

24
Chap. 7
Example
• Find all solutions to an = 3an−1+2n. Which
solution has a1 = 3?
– Notice this is a 1-LiNoReCoCo. Its associated
1-LiHoReCoCo is an = 3an−1, whose solutions
are all of the form an = α3n. Thus the solutions
to the original problem are all of the form an =
p(n) + α3n. So, all we need to do is find one
p(n) that works.
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
25
Chap. 7
Trial Solutions
• If the extra terms F(n) are a degree-t polynomial
in n, you should try a degree-t polynomial as the
particular solution p(n).
• This case: F(n) is linear so try an = cn + d.
(for all n)
(collect terms)
So
So
is a solution.
• Check: an≥1 = {−5/2, −7/2, −9/2, … }
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
26
Chap. 7
Finding a Desired Solution
• From the previous, we know that all general
solutions to our example are of the form:
Solve this for α for the given case, a1 = 3:
• The answer is
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
27
Chap. 7
Example
Ex: an  5an1  6an2  7n
(c)2001-2003, Michael P. Frank
§ 7.2 – Solving Recurrences
28
Chap. 7
§7.3: Divide & Conquer R.R.s
Main points so far:
• Many types of problems are solvable by
reducing a problem of size n into some
number a of independent subproblems, each
of size n/b, where a1 and b>1.
• The time complexity to solve such problems
is given by a recurrence relation:
– T(n) = a·T(n/b) + g(n)
(c)2001-2003, Michael P. Frank
§ 7.3 – D-C Recurrence Relations
29
Chap. 7
Divide+Conquer Examples
• Binary search: Break list into 1 subproblem (smaller list) (so a=1) of size
n/2 (so b=2).
– So T(n) = T(n/2)+c
(g(n)=c constant)
• Merge sort: Break list of length n into 2
sublists (a=2), each of size n/2 (so b=2),
then merge them, in g(n) = Θ(n) time.
– So T(n) = 2T(n/2) + cn (roughly, for some c)
(c)2001-2003, Michael P. Frank
§ 7.3 – D-C Recurrence Relations
30
Chap. 7
Divide+Conquer Examples
• Finding the Maximum and Minimum:
Break list into 2 sub-problem (smaller list)
(so a=2) of size n/2 (so b=2).
– So T(n) = 2T(n/2)+2
(c)2001-2003, Michael P. Frank
(g(n)=2 constant)
§ 7.3 – D-C Recurrence Relations
31
Chap. 7
Fast Multiplication Example
• The ordinary grade-school algorithm takes Θ(n2) steps to
multiply two n-digit numbers.
– This seems like too much work!
• So, let’s find an asymptotically faster multiplication
algorithm!
• To find the product cd of two 2n-digit base-b numbers,
c=(c2n-1c2n-2…c0)b and d=(d2n-1d2n-2…d0)b,
First, we break c and d in half:
c=bnC1+C0,
(c)2001-2003, Michael P. Frank
d=bnD1+D0,
and then... (see next slide)
§ 7.3 – D-C Recurrence Relations
32
Chap. 7
Derivation of Fast Multiplication
cd  (b nC1  C0 )(b n D1  D0 )
(Multiply out
 b C1 D1  b (C1 D0  C0 D1 )  C0 D0 polynomials)
Zero
 b 2 nC1 D1  C0 D0 
2n
n
b n (C1 D0  C0 D1  (C1 D1  C1 D1 )  (C0 D0  C0 D0 ))
 (b 2 n  b n )C1 D1  (b n  1)C0 D0 
b n (C1 D0  C1 D1  C0 D0  C0 D1 )
 (b 2 n  b n )C1 D1  (b n  1)C0 D0 
b n (C1  C0 )(D0  D1 )
(c)2001-2003, Michael P. Frank
(Factor last polynomial)
§ 7.3 – D-C Recurrence Relations
33
Chap. 7
Recurrence Rel. for Fast Mult.
Notice that the time complexity T(n) of the
fast multiplication algorithm obeys the
recurrence:
Time to do the needed adds &
• T(2n)=3T(n)+(n) subtracts of n-digit and 2n-digit
numbers
i.e.,
• T(n)=3T(n/2)+(n)
So a=3, b=2.
(c)2001-2003, Michael P. Frank
§ 7.3 – D-C Recurrence Relations
34
Chap. 7
The Master Theorem
Consider a function f(n) that, for all n=bk for
all kZ+,,satisfies the recurrence relation:
f(n) = a f (n/b) + cnd
with a≥1, integer b>1, real c>0, d≥0. Then:
(n d )
if a  b d

f (n)  (n d logb n) if a  b d
d
(n logb a )
if
a

b

(c)2001-2003, Michael P. Frank
§ 7.3 – D-C Recurrence Relations
35
Chap. 7
Examples
Consider a function f(n) that, for all n=2k for
all kZ+,,satisfies the recurrence relation:
f(n) = 5f(n/2) + 3. Then: f (n) 
Complexity of Merge Sort:
M (n)  2M (n / 2)  n
 M ( n) 
(c)2001-2003, Michael P. Frank
§ 7.3 – D-C Recurrence Relations
36
Chap. 7
Example
• Recall that complexity of fast multiply was:
T(n)=3T(n/2)+(n)
• Thus, a=3, b=2, d=1. So a > bd, so case 3
of the master theorem applies, so:
T (n) 
which is (n1.58…), so the new algorithm is
strictly faster than ordinary Θ(n2) multiply!
(c)2001-2003, Michael P. Frank
§ 7.3 – D-C Recurrence Relations
37
Chap. 7
Example
• The Closest-Pair Problem:a set of n
points, ( x1 , y1 ),, ( xn , yn )
d ( i , j )  ( xi  x j ) 2  ( yi  y j ) 2
• How can this closest pair of points be found
in an efficient way?
T(n)=2T(n/2)+7n
T (n) 
(c)2001-2003, Michael P. Frank
§ 7.3 – D-C Recurrence Relations
38
Chap. 7
§7.4: Generating Functions
• Definition:generating function for the
sequence a0 , a1 ,, ak , of real numbers is the
infinite series

G( x )  a0  a1 x  a2 x 2    ak x k     ak x k
k 0
(c)2001-2003, Michael P. Frank
§ 7.4 – Generating Functions
39
Chap. 7
Examples
• What is the generating function of the
sequence 1,1,1,1,1,1?
G (x) 
• What is the generating function of the
sequence {a k }, ak  C (m, k ) ?
G (x) 
(c)2001-2003, Michael P. Frank
§ 7.4 – Generating Functions
40
Chap. 7
Examples
• The function f(x)=1/(1x) is the generating
function of the sequence 1,1,1,…for |x|<1.
• The function f(x)=1/(1ax) is the generating
function of the sequence 1,a,a2,…for |ax|<1.
(c)2001-2003, Michael P. Frank
§ 7.4 – Generating Functions
41
Chap. 7
Theorem


k 0
k 0
Le t f ( x )   a k x k , g ( x )   bk x k , th e n

f ( x )  g ( x )   (a k  bk ) x k , an d
k 0
 k
 k
f ( x ) g ( x )     a j bk  j  x
k 0  j 0


Convolution of ak and bk
(c)2001-2003, Michael P. Frank
§ 7.4 – Generating Functions
42
Chap. 7
Example
What sequence has the generating function
f(x)=1/(1x)2 ?

1
  xk
1  x k 0
1

2
(1  x)
(c)2001-2003, Michael P. Frank
§ 7.4 – Generating Functions
43
Chap. 7
Extended Binomial Coefficient
 u   u(u  1)(u  k  1) / k! , if k  0
   
if k  0
 k  1,
 u
Note: u positive integer,    0 if k  u
Examples:
k 
  2
  
 3 
1 / 2 

 
 3 
(c)2001-2003, Michael P. Frank
§ 7.4 – Generating Functions
44
Chap. 7
Extended Binomial Theorem
 u k
(1  x )     x ,
k 0  k 

u
whe re x  1
Can be proved using Maclaurin series.
Examples: 

(1  x )
n
  n k
   x   ( 1)k C ( n  k  1, k ) x k
k 0  k 
k 0

(1  x ) n   C ( n  k  1, k ) x k
k 0
(c)2001-2003, Michael P. Frank
§ 7.4 – Generating Functions
45
Chap. 7
Example
Find the number of solutions of
e1  e2  e3  17, where e1 , e2 , and e3 are nonnegative
integerswith 2  e1  5, 3  e2  6, 4  e3  7.
Sol: Find the coefficient of x17 ,
The answer is
(c)2001-2003, Michael P. Frank
§ 7.4 – Generating Functions
46
Chap. 7
Example
Solve the recurrence relation:
ak  3ak 1 for k  1, 2, 3, and a0  2.
Sol: Let G(x) be the generating function of
{ak} , G( x )   a x

k
k 0
(c)2001-2003, Michael P. Frank
k
§ 7.4 – Generating Functions
47
Chap. 7
Example(Cont’d)
G ( x) 
 ak 
(c)2001-2003, Michael P. Frank
§ 7.4 – Generating Functions
48