Transcript Document
Application:
Algorithms
Lecture 19
Section 3.8
Tue, Feb 20, 2007
Algorithms
An algorithm is a step-by-step procedure
that is guaranteed to stop after a finite
number of steps for all legitimate inputs.
Example: Max Algorithm
Describe an algorithm for finding the
maximum value in a list of numbers.
Special cases:
What if the list is empty?
Others?
An Algorithmic Language
An algorithmic language is much like a
computer language.
Its primary purpose is to express
unambiguously the steps of an algorithm,
including all decisions and special cases
that may arise.
Assignment Statements
An assignment statement is of the form
x := expr
where x is a variable and expr is an
expression.
Examples
found := true
count := count + 1
Conditional Statements
One-way conditional statements:
if condition then
sequence of statements
Two-way conditional statements:
if condition then
sequence of statements
else
sequence of statements
Iterative Statements
While loops:
while condition
sequence of statements
end while
For loops:
for var := init expr to final expr
sequence of statements
next var
For Loops
A for loop can always be rewritten as a
while loop.
var := init expr
while var final expr
sequence of statements
var := var + 1
end while
A Notation for Algorithms
An algorithm will be organized into three
parts:
Input – List all input variables and any
special assumptions about them.
Algorithm body – Describe the step-by-step
procedure.
Output – List the output variables.
Example: Finding the Max
Input: a, n
a is a list of numbers.
n is the size of the list, n 1.
Algorithm body:
max := a[1]
for i := 2 to n
if a[i] > max then
max = a[i]
Output: max
Tracing an Algorithm
Write a trace table for the Max algorithm
and the input a = {7, 3, 8, 6, 4}, n = 5.
Iteration
a
n
max
i
0
{7, 3, 8, 6, 4}
5
7
2
1
2
3
4
Tracing an Algorithm
Write a trace table for the Max algorithm
and the input a = {7, 3, 8, 6, 4}, n = 5.
Iteration
a
n
max
i
0
{7, 3, 8, 6, 4}
5
7
2
7
3
1
2
3
4
Tracing an Algorithm
Write a trace table for the Max algorithm
and the input a = {7, 3, 8, 6, 4}, n = 5.
Iteration
a
n
max
i
0
{7, 3, 8, 6, 4}
5
7
2
1
7
3
2
8
4
3
4
Tracing an Algorithm
Write a trace table for the Max algorithm
and the input a = {7, 3, 8, 6, 4}, n = 5.
Iteration
a
n
max
i
0
{7, 3, 8, 6, 4}
5
7
2
1
7
3
2
8
4
3
8
5
4
Tracing an Algorithm
Write a trace table for the Max algorithm
and the input a = {7, 3, 8, 6, 4}, n = 5.
Iteration
a
n
max
i
0
{7, 3, 8, 6, 4}
5
7
2
1
7
3
2
8
4
3
8
5
4
8
6
Greatest Common Divisors
Let a and b be integers that are not both 0.
The greatest common divisor of a and b,
denoted gcd(a, b), is the unique positive
integer d with the following properties:
d | a and d | b.
For every integer c, if c | a and c | b, then
c | d.
Least Common Multiples
Let a and b be nonzero integers.
The least common multiple of a and b,
denoted lcm(a, b), is the unique positive
integer m with the following properties:
a | m and b | m.
For every integer c, if a | c and b | c, then
m | c.
The High-school gcd
Algorithm
The high-school method is very inefficient.
Factor each number into standard form.
For each prime that appears in both
factorizations, use it as a factor of the gcd
along with the smaller of the two
exponents.
Example
Find the gcd of 81900 and 54810.
We factor them as
81900 = 22 32 52 71 131 290
54810 = 21 33 51 71 130 291
Therefore, the gcd is
2 32 5 7 = 630
The Euclidean Algorithm
Factoring is inefficient; therefore, this
algorithm is inefficient.
The run time of this algorithm is O(10d),
where d is the number of digits in the
number.
Euclid had a much better idea.
The run time of the Euclidean Algorithm is
O(d), where d is the number of digits in the
number.
The Euclidean Algorithm
Input: A, B (positive integers, not both 0)
The Euclidean Algorithm
Algorithm body:
Output: b
a := A
b := B
if b = 0 then
swap a and b
r := a mod b
while r > 0
a := b
b := r
r := a mod b
end while
Example
Apply the Euclidean Algorithm to A = 81900
and B = 54810.
Iteration
A
B
a
b
r
0
81900
54810
81900
54810
27090
1
2
Example
Apply the Euclidean Algorithm to A = 81900
and B = 54810.
Iteration
A
B
a
b
r
0
81900
54810
81900
54810
27090
54810
27090
630
1
2
Example
Apply the Euclidean Algorithm to A = 81900
and B = 54810.
Iteration
A
B
a
b
r
0
81900
54810
81900
54810
27090
1
54810
27090
630
2
27090
630
0
Least Common Multiples
What is the efficient way to find lcm’s?
What is the lcm of 81900 and 54810?
Proof of the Euclidean
Algorithm
Theorem: The Euclidean Algorithm
terminates for all legitimate inputs A and B.
Proof:
We may assume that B > 0.
After the first iteration of the while loop,
0b<B
since b is the remainder of A divided by B.
Proof of the Euclidean
Algorithm
Each iteration produces a nonnegative
remainder that is smaller than the previous
remainder.
This cannot happen more than B times
before the remainder is 0.
Proof of the Euclidean
Algorithm
Lemma 1: If b > 0, then gcd(b, 0) = b.
Proof:
b | b and b | 0.
For all integers c, if c | 0 and c | b, then
c | b.
Therefore, b = gcd(b, 0).
Proof of the Euclidean
Algorithm
Lemma 2: If a and b are integers, with b
0, and q and r are integers such that
a = qb + r
then gcd(a, b) = gcd(b, r).
Proof:
Let d = gcd(b, r).
Then d | b and d | r and any integer that
divides b and r must also divide d.
Proof of the Euclidean
Algorithm
We must show that d | a and d | b and any
integer that divides a and b must also
divide d.
We already know that d | b.
Since a = qb + r, it follows that d | a.
Let c be an integer such that c | a and c | b.
Since r = a – qb, it follows that c | r and so
c | d.
Therefore, d = gcd(a, b).
Proof of the Euclidean
Algorithm
Theorem: The Euclidean Algorithm
produces the gcd of A and B.
Proof:
After the final iteration of the while loop,
r = 0.
By Lemma 1, the output b is the gcd of b
and r.
By Lemma 2, that is equal to the gcd of “a”
and “b” in the final iteration.
Proof of the Euclidean
Algorithm
But “a” and “b” on the last iteration were “b”
and “r” on the previous iteration.
Therefore, gcd(a, b) on the last iteration
equals gcd(b, r) on the previous iteration,
which equals gcd(a, b) on the previous
iteration, and so on.
Following this argument all the back to the
first iteration, we see that the output is
gcd(A, B).
Proof of the Euclidean
Algorithm
In the next chapter, we will study
mathematical induction.
At that point, we will be able to make this
argument more rigorous.