Transcript CSC201Lecture02_Math_Recursion

CSC201
Analysis and Design of Algorithms
Lecture 2:
Definition of algorithm and
Mathematical Background for
algorithm analysis
Asst.Proof.Dr.Surasak Mungsing
E-mail: [email protected]
Apr-16
1
Topics




4/9/2016
Definition of algorithm
Mathematical background
Performance of algorithm
Recursion
2
Definition
 Algorithm (in mathematic and computer Science) is
 an effective method expressed as a finite of well-defined for
calculating a function. They are used for calculation, data
processing, and automated reasoning. [from Wikipedia]
 a step-by-step problem-solving procedure, especially an
established, recursive computational procedure for solving a
problem in a finite number of steps. [from the free online
dictionary]
 a step-by-step problem-solving procedure, especially an
established, recursive computational procedure for solving a
problem in a finite number of steps. [from answer.com ]
 Algorithms that require very long time to solve problem, in practice,
may be useless
 Algorithms that require extraordinary large memory for processing may
not be practical for running on most of current computers
4/9/2016
3
Selection Problem
Problem:
Select the kth largest integer from the given set of N
integers
Solutions:
at least two algorithms that can solve this problem
Algorithm 1 Read N integers and put them in an array, then sort
them with a simple sorting algorithm, such as Bubble Sort, and
return the value at the index kth of the array
Algorithm 2 Read only the first k integer into an array, then sort
them in ascending. Next read in the rest of integer one-by -one
and compare the value with the kth one in the array, if it is less
than the kth value then do nothing, else replace the value in the
arayy at the right position. Repeat the process until no integer left.
4/9/2016
4
Mathematical Background




4/9/2016
Exponential
Logarithms
Series
Proof
5
Exponential
XAXB = XA+B
XA/XB = XA-B
(XA)B = XAB
XN + XN = ?
2N + 2N = ?
4/9/2016
6
Logarithms
Definition
XA = B iff logxB = A
Theorem 1
logBA = logCB/logCA ; A, B, C > 0, A  1
Theorem 2
log(AB) = log A + log B; A, B > 0
Remark
logarithm written as log (without base number mean log base 2
or log2
ค่าทีค
่ วรจาไว ้อ ้างอิง
log1 = 0
log2 = 1
log1,024 = 10
log 1,048,576 = 20
4/9/2016
because
because
because
because
7
20 = 1
21 = 2
210 = 1,024
220 = 1,048,576
Series
N

i=0
Ai
AN+1 -1
=
A -1
N
If A=2 ; 
2i = 2N+1 -1
i=0
N
If 0<A<1 ; 
i=0
Ai ≤
1
1- A
N
If N=∞ ; 
i=0
4/9/2016
1
Ai approaches
1- A
8
Series (cont.)
N

i
=
i=1
N(N+1)
2

N2
2
N
N3

N(N+1)(2N+1)
i2 =

6
i=1
3
N

i=1
Apr-16
ik

Nk+1
|k + 1 |
k ≠ -1
9
Proof
 Proof by Induction
 Proof by Contradiction
 Proof by Counterexample
4/9/2016
10
Proof by Induction
 Mathematical induction is a method of
mathematical proof typically used to establish
that a given statement is true of all natural
numbers (non-negative integers). It is done by
proving that the first statement in the infinite
sequence of statements is true, and then
proving that if any one statement in the infinite
sequence of statements is true, then so is the
next one. [http://en.wikipedia.org/wiki/Mathematical_induction ]
Apr-16
11
Proof by Induction
The simplest and most common form of mathematical induction proves
that a statement involving a natural number n holds for all values of n.
The proof consists of two steps:
1. The basis (base case): showing that the statement holds when n is
equal to the lowest value that n is given in the question. Usually, n = 0
or n =
2. The inductive step: showing that if the statement holds for some
n, then the statement also holds when n + 1 is substituted for n.
The assumption in the inductive step that the statement holds for some
n is called the induction hypothesis (or inductive hypothesis)
4/9/2016
12
Example : Proof by Induction
Prove that Fi < (5/3)i for i  1
1. Prove base case; F1 = 1 < 5/3,
F2 = 1 <25/9, F3=2 <125/27
2. Show inductive hypothesis i = 1, 2, …, k
2. Show that the statement is true for k+1
Fk+1 < (5/3)k+1
Fk+1= Fk+Fk-1
Fk+1 < (5/3)k+ (5/3)k-1 < (3/5) (5/3)k+1 + (3/5)2 (5/3)k+1
< (3/5) (5/3)k+1 + (9/25) (5/3)k+1
Fk+1 < (3/5 + 9/25) (5/3)k+1 < (24/25) (5/3)k+1
< (5/3)k+1
from definition;
4/9/2016
13
Example: Proof by Induction
Prove that 1+2+3+…+n = n(n+1)/2
1. Basis: Show that the statement holds for n = 1
if n=1 then 1*(1+1)/2 = 1 (prove base case)
2. Inductive step: show that if P(n) holds, then also
P(n+1) holds.
Assume P(n) holds (for some unspecified value of n). It must
then be shown that P(n + 1) holds, that is:
1+2+3+…+n+(n+1) = n(n+1)/2 +(n+1)
= (n2+n+2n+2)/2
= (n2+3n+2)/2
= (n+1)(n+2)/2
hereby showing that indeed P(n + 1) holds.
4/9/2016
14
Proof by contradiction
 In logic, proof by contradiction is a form of proof
that establishes the truth or validity of a proposition by
showing that the proposition being false would imply a
contradiction. Since by the law of bivalence a
proposition must be either true or false, and its falsity
has been shown impossible, the proposition must be
true.
 The idea:


Apr-16
Assume that a given proposition is untrue.
Based on that assumption reach two conclusions
that contradict each other.
15
Prove that there is no largest prime number
(this is the idea of Euclid's original proof)
 Prime numbers are integers with no exact integer divisors except 1 and
themselves.
1. To prove: "There is no largest prime number" by contradiction.
2. Assume: There is a largest prime number, call it p.
3. Consider the number N that is one larger than the product of all of the
primes smaller than or equal to p. N=1*2*3*5*7*11...*p + 1. Is
it prime?
4. N is at least as big as p+1 and so is larger than p and so, by Step 2,
cannot be prime.
 On the other hand, N has no prime factors between 1 and p because
they would all leave a remainder of 1. It has no prime factors larger
than p because Step 2 says that there are no primes larger than p. So
N has no prime factors and therefore must itself be prime
 We have reached a contradiction (N is not prime by Step 4, and N is
prime by Step 5) and therefore our original assumption that there is a
largest prime must be false
Apr-16
16
Proof by Counterexample
 In logic, and especially in its applications to
mathematics and philosophy, a
counterexample is an exception to a proposed
general rule.
 In mathematics, counterexamples are often
used to prove the boundaries of possible
theorems.
 In philosophy, counterexamples are usually used
to argue that a certain philosophical position is
wrong by showing that it does not apply in
certain cases.
Apr-16
17
Example: Proof by Counterexample
Prove that the statement Fk  k2 is not true
To prove , select k =11 and show that
F11 = 144 > 112
that is the statement does not hold
( Fibonacci numbers, Fi:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … )
4/9/2016
18
9-Apr-16
19
Recurrence Relation
Some Examples
09 เม.ย. 59
The Pizza Slicing Problem
 How many pieces of pizza can you get with N
straight cuts ?
The Pizza Slicing Problem (cont.)
 ... N cuts
 2N slices
But ... who said you should cut
through the center every time?
A Better Slicing Method ...
 When cutting, intersect all previous cuts and
avoid previous intersection points!
So ... How Many Pieces?
 The N-th cut creates N new pieces.
 Hence, the total number of pieces given by N cuts, denoted P(N), is
given by the following two rules:
 P(1) = 2
 P(N) = P(N-1) + N
 Recursive definition of P(N)!
Recurrence Relations
 The pizza-cutting problem is an example of
recurrence relation, where a function f (N) is
recursively defined.
(Base Case)
(Recursive Case)
f (1) = 2
f (N) = f (N - 1) + N for N > 2
 The standard method for solving recurrence
relations, called“unfolding”, makes repeated
substitutions applying the recursive rule until the
base case is reached.
Recurrence Relations (cont.)
f (N)
f (N)
f (N)
...
f (N)
= f (N - 1) + N
= f (N - 2) + (N - 1) + N
= f (N - 3) + (N - 2) + (N - 1) + N
= f (N - i) + (N - i -1) + … + (N - 1) + N
 The base case is reached when i =N - 1
f (N) = 2 + 2 + 3 + … + (N - 2) + (N -1) + N
f (N)  N(
N1
)  1  (N2 )
2
Towers of Hanoi
 Goal: transfer all N disks from peg A to peg C
 Rules:
 move one disk at a time
 never place larger disk above smaller one
Recursive Solution
 Recursive solution:
 transfer N -1 disks from A to B
 move largest disk from A to C
 transfer N -1 disks from B to C
 Total number of moves:
T(N) =2 T(N -1) +1
Solution of the Recurrence for
Towers of Hanoi
 Recurrence relation:
T(N) =2 T(N-1) +1
T(1) =1
 Solution by unfolding:
T(N) = 2 ( 2 T(N-2) +1 ) + 1 =
= 4T(N -2) + 2 + 1 =
= 4 (2T(N -3)+1 ) + 2 +1 =
= 8T(N -3) + 4 + 2 +1 =
…
=2i T(N - i) + 2i-1 + 2i-2 + ... + 21 + 20
9-Apr-16
30
Exercise
จงแสดงวิธท
ี า
1.


xi = 1/(1-x) ;
i=0
2.

i/2i
i=1

2
where 0<x<1
Exercise
3.
4.
5.
6.
7.
X N + X N= ?
2 N + 2 N= ?
log 1048576 = ?
log 1024 = ?
20 + 21 + … + 200 =?
8. จงพิสจ
ู น์วา่
N
 (2i-1) = N 2
i=1
Apr-16
32