Transcript Algorithm Design and Analysis

chapter 2
Mathematical preliminaries
•
•
•
•
•
•
•
•
2.1 Set, Relation and Functions
2.2 Proof Methods
2.3 Logarithms
2.4 Floor and Ceiling Functions
2.5 Factorial and Binomial Coefficients
2.6 The Pigeonhole Principle
2.7 Summations
2.8 Recurrence Relations
Concept of Set
2.1
• Set: Any collection of objects, which are
called members or elements of the set.
• Set can be finite or infinite.
• Operation of Set:
–
–
–
–
A B
Union:
Intersection: A  B
A B
Difference:
Complement: A
2.1
Concepts of Relations
Relation: An ordered n-tuple (a1, a2, …, an) is an
ordered collection that has a1 as its first element,
a2 as its second element, …, and an as its nth
element.
Binary Relation: Let A and B be two nonempty
sets, R from A to B is a set of ordered pairs (a, b)
where a  A and b  B , that is R  A  B .

Equivalence Relations: A relations R on a set A
is called an equivalence relations if it is reflexive,
symmetric and transitive.
2.1
Concepts of Functions
• Function: a function f is a (binary) relation
such that for every element x  Dom ( f ) there
is exactly one element y  Ran ( f ) with ( x, y )  f
• Dom(f) : the domain of f, is the set:
Dom(f) = {a | for some b  B, (a, b)  f }
• Ran(f) : the range of R, is the set
Ran(f) = {b | for some a  A, (a, b)  f }
2.2 Proof Methods
•
•
•
•
•
Direct proof
Indirect proof
Proof by contradiction
Proof by counterexample
Mathematical induction
2.2
Direct Proof
• Method: To prove that “P->Q”, a direct
proof works by assuming that P is true and
then deducing the truth of Q from the truth
of P.
• E.g. : To prove the assertion: If n is an even
integer, then n2 is an even integer.
2.2
Indirect proof
• Method: the implication “P->Q” is logically
equivalent to the contrapositive implication
" Q  P"
• E.g. Consider the assertion: if n2 is an even
integer, then n is an even integer.
2.2
Proof by Contradiction
• Method: to prove the statement “P->Q” is
true, we start by assuming that P is true but
Q is false. If this assumption leads to a
contradiction, it means that our assumption
that “Q is false” must be wrong, and hence
Q must follow from P.
• E.g. to prove the assertion: there are
infinitely many primes.
2.2
Proof by counterexample
• Method: to provide quick evidence that a
postulated statement is false. When we are
faced with a problem that requires proving
or disproving a given assertion, we may
start by trying to disprove the assertion with
a counterexample.
• E.g. Let f(n)=n2+n+41 be a function defined
on the set of nonnegative integers. Consider
the assertion that f(n) is always a prime
number.
2.2
Mathematical induction
• Method: to prove that a property holds for a sequence
of natural numbers n0,n0+1,n0+2,…, where n0 can
be 0 or 1 or any natural number. Suppose we want to
prove a property P(n) for n=n0,n0+1,n0+2,…, whose
truth follows from the truth of property P(n-1) for all
n>n0. First, we prove that the property holds for n0.
This is called the basic step. Then, we prove that
whenever the property is true for n0,n0+1,…,n-1,
then it must follow that the property is true for n.This
is called the induction step. We then conclude that
the property holds for all values of n>=n0.
2.3
Logarithms
• Let b be a positive real number greater than
1, x a real number, and suppose that for
some positive real number y we have y=bx.
Then, x is called the logarithm of y to the
base b, and we write this as
x=logby
2.3
Logarithm_some formula
• logbxy=logbx+logby
• Logb(cy)=ylogbc
1
•
ln x  
dt
x
1
•
x logb y  y logb x
t
, x,y>0
2.4
Floor and Ceiling Functions
• Let x be a real number. The floor of x,
denoted by x ,is defined as the greatest
integer less than or equal to x. The ceiling
of x, denoted as x , is defined as the least
integer greater than or equal to x.
•
x / 2  x / 2  x
 x    x 
 x    x 
2.4
Floor and Ceiling Functions
• Theorem 2.1 Let f(x) be a monotonically
increasing function such that if f(x) is
integer, then x is integer. Then,
 f ( x )   f ( x )
 f ( x )   f ( x )
2.5
Factorial and Binomial Coefficients
_factorial
• Permutation: A permutation of n distinct
objects is defined to be an arrangement of
the objects in a row.
• Pkn  n(n  1)...( n  k  1) is called the number
of permutations of n objects taken k at a
time.
• Pnn  1  2  ...  n is called the number of
permutations of n objects.
2.5
Factorial and Binomial Coefficients
_ Binomial Coefficients
•
•
is called the combinations of n objects
taken k at a time, which is choose k objects
out of n objects, disregarding order.
Ckn
Pkn n(n  1)..., (n  k  1)
n!
C 


,n  k  0
k!
k!
k!(n  k )!
n
k
n
 
k 
• This quantity is denoted by , read “n
choose k”, which is called the binomial
coefficient.
2.5
Factorial and Binomial Coefficients
_ Binomial Coefficients
• Some equations:
•
• in particular
n  n 

k 

n  k 

  

n n
      1
n  0
•
 n   n  1  n  1
   
  

 k   k   k  1
2.5
Factorial and Binomial Coefficients
_ Binomial Coefficients
• Theorem2.2: Let n be a positive integer, Then
n j
(1  x )     x
j 0  j 
n
n
• If let x=1, then
n n
n
      ...     2n
 0  1
n
n
  

j even  j 
n
• If let x=-1, then
n
 

j odd  j 
n
2.6
The Pigeonhole Principle
• Theorem 2.3 If n balls are distributed into m boxes,
then
(1) one box must contain at least n / m balls, and
(2) one box must contain at most n / m balls.
• E.g. Let G=(V,E) be a connected undirected graph
with m vertices. Let p be a path in G that visits
n>m vertices. We show that p must contain a cycle.
Since n / m >=2, there is at least one vertex to be
visited by p more than once.
2.7
Summation
• A sequence a1,a2,…, is defined formally as a
function whose domain is the set of natural
numbers. Let S=a1,a2,…,an be any sequence
of numbers. The sum a1+a2+…+an can be
expressed compactly using the notation:
n
a
j 1
f ( j)
or
a
1 j n
f ( j)
Where f(j) is a function that defines a
permutation of the elements 1,2,…,n.
2.7
Summation-some formulae
•
•
n(n  1)
2
j



(
n
)

2
j 1
n
n
2
j
 
j 1
•
n(n  1)( 2n  1)
  (n 3 )
6
c n 1  1
c 
  (c n ) , c  1

c 1
j 0
n
j
• If c=2, then
n
2
j 0
j
 2n 1  1   (2n )
2.7
Summation-some formulae
• If c = ½, then
n
1
1

2

 2   (1)

j
n
2
j 0 2
• If |c|<1, and the sum is infinite, then

c j 
j 0
•
1
  (1)
1 c
n2
n 1
n 1
nc

nc

c
c
j
j
n
jc

jc



(
nc
), c  1


2
(c  1)
j 0
j 1
n
n
2.7
Approximation of summation by integration
• Let f(x) be a continuous function that is
monotonically decreasing or increasing, and
suppose we want to evaluate the summation
n
 f ( j)
j 1
• We can obtain upper and lower bounds by
approximating the summation by integration
as follows
n
n 1
n
f ( j)   f ( x)dx
if f(x) is decreasing, then m f ( x)dx  
m1
j m
n
n
if f(x) is increasing, then  f ( x)dx   f ( j)  n1 f ( x)dx
m1
j m
m
2.7
Approximation of summation by integration
• E.g.1: derive an upper and lower bounds for
the summation n k
j
, k  1.
j 1
• E.g. 2: derive upper and lower bounds for the
n
harmonic series
1
Hn  
j 1
j
• E.g. 3: derive upper and lower bounds for the
n
series
 log j
j 1
2.8 Recurrence Relation
•
•
•
•
•
Solution of linear homogeneous recurrence
Solution of inhomogeneous recurrence
Solution of divide-and -conquer recurrence
Definition:
A recurrence relation is called linear homogeneous
with constant coefficients if it is of the form
f (n)  a1 f (n  1)  a2 f (n  2)  ...  ak f (n  k ).
• In this case, f(n) is said to be of degree k. When an
additional term involving a constant or a function
of n appears in the recurrence, then it is called
inhomogeneous.
2.8
Linear homogeneous recurrences
• Form:
f (n)  a1 f (n  1)  a2 f (n  2)  ...  ak f (n  k ).
• Characteristic equation:
x k  a1 x k 1  a2 x x 2  ...  ak  0
•
•
•
•
•
First linear homogeneous recurrence f (n)  af (n  1)
f (n)  a f (0)
The solution is:
Second linear homogeneous recurrence
2
x
 a1 x  a2  0
The characteristic equation:
The solution is: f (n)  c1r1n  c2r2n , if r1  r2
n
f (n)  c1r n  c2nr n if
r1  r2  r
2.8
Inhomogeneous recurrences
• Form:
f (n)  f (n  1)  g (n) , n  1
• Solution:
f ( n )  f ( 0)   g ( i )
n
i 1
• Form:
f (n )  g (n ) f (n  1)  h(n )
• Solution:
n
h (i )
f (n)  g (n) g (n  1)... g (1)( f (0)  
) , n  1.
i 1 g (i ) g (i  1)... g (1)
2.8
Solution of divide-and-conquer recurrence
• Form:
if n  n0
 d
f (n)  
a1 f (n / c1 )  a2 f (n / c2 )  ...  a p f (n / c p )  g (n) if n  n0
• Some technique:
– Substitution
– Iteration
– Master theory
2.8.1
Substitution
• Method: To guess a solution and try to
prove it by appealing to mathematical
induction.
• Guess method 1: using the similar known
function.
• E.g. To solve the function:
T (n)  2T (n / 2)  n,
• Note: try to guess:
T (0)  1.
T (n )  ( n log n )
2.8.1
Substitution (cont.)
• Guess method 2: guess the loose upper and
lower bounds, then make the bounds accurate.
• E.g. To solve the function:
T (n)  2T (n / 2)  n,
• E.g. To solve the function:
T (1)  1
T (n)  T ( n / 2)  T ( n / 2)  1
2.8.1
Substitution (cont.)
• Change of variables: By changing the variable
to make the recurrence equation to be simple
one.
• E.g. To solve the function:
T ( n )  2T ( n )  log n,
T (1)  1
2.8.2
Iteration
• Method: Expanding the recurrence, change
the equation to be summation, then using
the solving technique of summation.
• E.g. To solve the function:
T (n)  n  3T ( n / 4)
2.8.3
Master Theorem
• Let a>=1 and b>1 to be constants, f(n) is a
function, T(n) is a function which defined in
nonnegative integer set, and with the form:
T (n )  aT (n / b)  f (n )
T(n) can be solved as follows,
log a 
f
(
n
)


(
n
) ,   0 is a constant, then T (n)   (nlog a )
(1) if
then T (n)  (nlog a log n)
(2) if f (n)   (nlog a )
(3) if f (n)  (nlog a ) ,   0 is a constant, and for all n,
af (n / b)  cf (n) , c  1 is a constant, then
b
b
b
b
T ( n )   ( f ( n )).
b
2.8.3
Master Theorem (cont.)
Intuitively, Master Theorem can be understood as
follows,
logb a
Just compare the functions f (n) and n
T(n) can be solved as follows,
logb a
logb a
(1) if n
bigger, then T (n)   (n )
(2) if f (n)
(3) If f (n)
then T (n)  ( f (n))
and nlog a with same order, then
bigger
T (n)   (n
b
logb a
log n)   ( f (n) log n)
2.8.3
Master Theorem (cont.)
e.g.1: To solve the function:
T (n )  9T (n / 3)  n
e.g. 2: To solve the function:
T ( n )  T ( 2n / 3)  1
e.g. 3: To solve the function:
T ( n )  3T ( n / 4)  n log n
e.g. 4: To solve the function:
T ( n )  2T ( n / 2)  n log n
Master Theorem (cont.)
• Theorem: Let b and d be nonnegative
constants, and let n be a power of 2, then,
the solution to the recurrence:
f(n)=2f(n/2)+bnlogn n>=2;
f(1)=d
is f(n)=θ(nlog2n)