Transcript 01.intro

1
Introduction
• History of algorithms.
• Examples of algorithms.
• Algorithms vs programs.
• Data structures.
• Abstract data types.
© 2001, D.A. Watt and D.F. Brown
1-1
What is an algorithm?
• An algorithm is a step-by-step procedure for solving a
stated problem.
• For example, there are many possible algorithms for
multiplying numbers:
 multiplication table (suitable only for small numbers)
 long multiplication
 multiplication using logarithms
 multiplication using a slide rule
 binary fixed-point or floating-point multiplication (in a computer).
1-2
History
• Euclid (~ 300 BCE), Eratosthenes (~ 200 BCE)
– arithmetic, geometric algorithms.
• al Khwarizmi (~ 800)
– arithmetic, algebraic, geometric algorithms.
• Napier (~ 1600)
– arithmetic using logarithms.
• Newton (~ 1700)
– differentiation, integration.
• Turing (~ 1940)
– code breaking, solvability.
1-3
Example 1: finding a midpoint (1)
• Midpoint algorithm:
To find the midpoint of a given straight-line segment AB:
1. Draw intersecting circles of equal radius, centered at A and B
respectively.
2. Let C and D be the points where the circles intersect.
3. Draw a straight line between C and D.
4. Let E be the point where CD intersects AB.
5. Terminate with answer E.
• Could be performed by a human equipped with drawing
instruments.
1-4
Example 1 (2)
• Animation:
1. Draw intersecting circles
of equal radius, centered
at A and B respectively.
2. Let C and D be the
points where the circles
intersect.
3. Draw a straight line
between C and D.
4. Let E be the point
where CD intersects AB.
5. Terminate with answer
E.
A
D
E
C
B
1-5
Example 2: GCDs (1)
• The greatest common divisor (GCD) of two positive
integers is the largest integer that exactly divides both.
E.g., the GCD of 77 and 21 is 7.
• Euclid’s GCD algorithm:
To compute the GCD of positive integers m and n:
1. Set p to m, and set q to n.
2. Until q exactly divides p, repeat:
2.1. Set p to q, and set q to (p modulo q).
3. Terminate with answer q.
• Could be performed by a human, perhaps equipped with an
abacus or calculator.
1-6
Example 2 (2)
• Animation:
To compute the GCD of positive integers m and n:
1. Set p to m, and set q to n.
2. Until q exactly divides p, repeat:
2.1. Set p to q, and set q to (p modulo q).
3. Terminate with answer q.
m 77
n 21
p 14
77
21
q 14
21
7
1-7
Example 2 (3)
• Implementation in Java:
static int gcd (int m, int n) {
// Return the greatest common divisor of positive integers m and n.
int p = m, q = n;
while (p % q != 0) {
int r = p % q;
p = q; q = r;
}
return q;
}
1-8
Example 3: square roots (1)
• A square root of a positive number a is a number r such
that r2 = a.
• Newton’s square-root algorithm:
To compute approximately the positive square root of a positive
number a:
1. Set r to the mean of 1 and a.
2. Until r2 is approximately equal to a, repeat:
2.1 Set r to the mean of r and a/r.
3. Terminate with answer r.
• Could be performed by a human, perhaps equipped with
log tables or a calculator.
1-9
Example 3 (2)
• Animation:
To compute approximately the positive square root
of a positive number a:
1. Set r to the mean of 1 and a.
2. Until r2 is approximately equal to a, repeat:
2.1 Set r to the mean of r and a/r.
3. Terminate with answer r.
a
2.0
r 1.414
1.417
1.5
1-10
Example 3 (3)
• Implementation in Java:
static float sqrt (float a) {
// Compute approximately the square root of positive real number a.
float r = (1.0 + a)/2;
while (Math.abs(r*r/a - 1.0) >= 0.00005)
r = (r + a/r)/2;
return r;
}
1-11
Algorithms vs. programs (1)
• Algorithms:
 can be performed by humans or machines
 can be expressed in any suitable language
 may be as abstract as we like.
• Programs:
 must be performed by machines
 must be expressed in a programming language
 must be detailed and specific.
1-12
Algorithms vs. programs (2)
• Here we express our algorithms in (precise) English.
• Steps may be numbered consecutively:
1. Do this.
2. Do that.
Do this and then do that.
• The extent of a conditional is indicated by indentation:
7. If …:
7.1. Do this.
7.2. Do that.
Do this and then do that, but
only if condition … is true.
• The extent of a loop is indicated by indentation:
8. While …, repeat:
8.1. Do this.
8.2. Do that.
Do this and then do that, as
long as condition … is true.
1-13
Algorithms vs. programs (3)
• If we wish to use the algorithm on a computer, we must
first code it in a programming language.
• There may be many ways of coding the algorithm, and
there is a wide choice of programming languages. But all
the resulting programs are implementations of the same
underlying algorithm.
• Here we express our implementations in Java.
(Alternatives would be C, Pascal, Ada, etc.)
1-14
Data structures
• A data structure is a systematic way of organizing a
collection of data.
• A static data structure is one whose capacity is fixed at
creation.
E.g.: array.
• A dynamic data structure is one whose capacity is
variable, so it can expand or contract at any time.
E.g.: linked list, binary tree.
• For each data structure we need algorithms for insertion,
deletion, searching, etc.
1-15
Example 4: representing strings
• Possible data structures to represent the string “Java”:
0
Array:
Linked list:
1
2
3
‘J’ ‘a’ ‘v’ ‘a’
‘J’
‘a’
‘v’
‘a’
1-16
Example 5: representing sets
• Possible data structures to represent the set of words
{bat, cat, mat, rat, sat}:
Array:
Linked
list:
Binary
search
tree:
0
1
2
3
4
bat
cat
mat
rat
sat
bat
cat
5
mat
6
rat
7
sat
cat
bat
rat
mat
sat
1-17
Abstract data types
• When we write application code, we don’t care how strings
are represented: we just declare variables of type String,
and manipulate them using String operations.
• Similarly, we don’t care how sets are represented: we just
declare variables of type Set, and manipulate them using
Set operations.
• An abstract data type is a data type whose representation
is hidden from, and of no concern to, the application code.
Examples: String, Set.
• Abstract data types are an excellent way to design large
programs.
1-18