Transcript Presentation1

Formal Definition of an Algorithm
Let’s see what the literature says. The following is taken
from Herman’s 1983 paper (available on the module
web-pages).
Hermes (1985) “An algorithm is a general procedure
such that for any appropriate question the answer can
be obtained by the use of a simple computation
according to a specified method…. [A] general
procedure [is] a process the execution of which is clearly
specified in the smallest details.
Minsky (1967) “…. And effective procedure is a set of
rules which tells us, from moment to moment, precisely
how to behave”
Towards a Formal Definition of an Algorithm
Hermes (1985) “An algorithm is a general procedure
such that for any appropriate question the answer can
be obtained by the use of a simple computation
according to a specified method…. [A] general
procedure [is] a process the execution of which is clearly
specified in the smallest details.
Towards a Formal Definition of an Algorithm
Minsky (1967) “…. And effective procedure is a set of
rules which tells us, from moment to moment, precisely
how to behave”
Towards a Formal Definition of an Algorithm
Rogers (1967) “… an algorithm is a clerical (ie deterministic,
bookkeeping) procedure which can be applied to any of a
certain class of symbolic inputs and which will eventually
yield, for each such input, a corresponding symbolic output.
Towards a Formal Definition of an Algorithm
Hopcroft and Ullman (1969). “A procedure is a finite
sequence of instructions that can be mechanically carried
out, such as a computer program… A procedure which
always terminates is called an algorithm.
Towards a Formal Definition of an Algorithm
Schneider and Gersting (2004). An algorithm is a wellordered collection of unambiguous and effectively
computable operations that, when executed, produces a
result, and halts in a finite amount of time.
Towards a Formal Definition of an Algorithm
Price (2009). An algorithm is a collection of atomic
operations which when executed without restriction produce
an emergent story which may have relevance or not.
Classification of Algorithms
Programming Problems
Uncomputable
Computable
Time
Polynomial
Space
Non-Polynomial
Classification of Algorithms
Programming Problems
Uncomputable
Computable
Time
Tractable
Space
Intractable
1267650600228229401496703205376
O (n)
2
O(n )
n
O(2 )
Harmut & Huber (1966):
Before Turing the algorithm was intuitive. A finite sequence of rules
operating on some input to generate output after a finite sequence of
steps.
Turing, Kleene and Markov discovered (equivalent) programming
languages which could implement this language.
Algorithms are realized in programming languages.
Donald Knuth (1966):
Algorithms are concepts which exist outside programming languages.
They are abstract method for computing something, whereas a program
is an embodiment of this method.
Binary Search
Daniel
Bob
Anne
Grant
Carol
Nathan
Sue
Sequential Search
Anne
Bob
Carol
Daniel
Grant
Nathan
Sue
Binary Search
Anne
Bob
Carol
Daniel
Grant
Nathan
Sue
Hamiltonian Cycles
A
C
B
D
Hamiltonian Cycles
A
C
B
D
10
30
20
5
18
25
Hamiltonian Cycles
Problem: Find a path between n cities to
(i) Visit each city once
(ii) End up at the starting city.
Input: [13 81 92 65 43 31 57 26 75 0]
Pivot: 65
Partition: [13 0 26 43 31 57] 65 [ 92 75 81]
Pivot: 31 81
Partition: [13 0 26] 31 [43 57] 65 [75] 81 [92]
Pivot: 13
Parititon: [0] 13 [26] 31 [43 57] 65 [75] 81 [92]
Combine: [0 13 26] 31 [43 57] 65 [75 81 92]
Combine: [0 13 26 31 43 57] 65 [75 81 92]
Combine: [0 13 26 31 43 57 65 75 81 92]
Quicksort
13
81
92
65
43
31
57
26
75
0
Quicksort
7
2
9
4
3
7
6
1
Execution Time of Algorithms
Sequential Search
Binary Search
( n)
(log n)
Quicksort
( n )
( n log n)
Permutation
( 2 n )
Selection Sort
2
Stable Marriage
The Gale-Shapley algorithm involves a number of
iterations.
Each unengaged man proposes to the preferred woman to
whom he has not yet proposed.
Each woman then considers all her suitors and tells the one
she most prefers "Maybe" and all the rest of them "No".
She is then provisionally "engaged".
In each subsequent round, each unengaged man proposes
to one woman to whom he has not yet proposed.
The women once again replies with one "maybe" and rejects
the rest.
Fun -2- Stable Marriage
We have N men and N women.
Each man “ranks” a woman and vice versa
We want to match people off so they are reasonably happy
Some Fun -1-
Take the first three digits of your phone number and multiply by 80
Add 1 to the result
Now Multiply by 250 and add the last 4 digits of your phone number
Add the last 4 digits of your phone number again
Subtract 250 and divide by 2. What do you see?
Sum a List of Numbers
Get the list of numbers
Set sum to zero
Move through the list until it is ended
get the next number in the list
add it to the sum
Output the sum
Algorithmic Thinking (Knuth)
The modern meaning for algorithm is quite similar to that of
recipe, process, method, technique, procedure, routine,
rigmarole except that the word ‘Algorithm’ connotes
something just a little different…
.. An algorithm has five important features:
Fitness
Definiteness
Input
Output
Effectiveness
Presently, the creation of algorithms is exclusive to humans,
whilst their execution may be ascribed either to human beings
or to computers.
Algorithmic A.N.Whitehead
“It is a profoundly erroneous truism, repeated by all copy books and
by eminent people when they are making speeches, that we should
cultivate the habit of thinking of what we are doing.
The precise opposite is the case. Civilization advances by extending
the number of important operations which we can perform without
thinking”.
An Introduction to Mathematics (1911).
Algorithmic Leibnitz
“It is unworthy of excellent men to lose hours like slaves in the
calculation which could safely be relegated to anyone else if
machines were used”
The Nature of Technology
• Memory Extension : Pencil and Paper. Word Processed
Documents, Photographs, Painting
• Language Extension : Text Messages
• Cognitive Extension : ??
• Heidegger
The Importance of Algorithmic Thinking
The existence of an algorithm to accomplish a particular task means
that that task can be automated, performed by a computer.
Such tasks may be boring, time-consuming or lethal.
The Danger of Algorithmic Thinking
An algorithm for a dentist is “drill and fill”
An algorithm for an educator is “fill and drill”
Bohm and Jacopini
Three constructs can construct all programmes:
Sequence
Selection
Repetition
Sequence…
Selection…
Loop…
Algorithms
and
Algorithmic Thinking
Comparison of Bubblesort and Quicksort
250000
200000
150000
Series1
Series2
100000
50000
0
0
50000
100000
150000
200000
250000
Binary Search Algorithm
1. Get the list of names 1,2,3,…N
2. Set “begin” to 1 and “end” to N
3. Set “found” to no
4. While “found” is no
1. Set “m” to middle value between “begin” and “end”
2. If “name” is “asked name”
1. Set “found” to yes
3. Else if “name” precedes “asked name” set “end” = m - 1
4. Else set “begin” to m + 1
Selection Sort Algorithm
1. Get the list of numbers
2. Put the wall at the beginning
3. While there are more elements in the unsorted part
1. Find the smallest element
2. Swap with the first element in the unsorted part
3. Move the wall one element to the right
Quick Sort Algorithm
1. Get the list
2. Choose a “pivot” from the list
3. Move all elements less than the pivot to the left of the pivot and the
greater elements to the right of the pivot.
4. Recursively apply 2,3 to the sub-lists generated
Consider this example taken from the instructions
on the back of a shampoo bottle: “Wet hair.
Lather. Rinse. Repeat”
You may often be told
“choose to do either (a) or (b)”
Algorithmic Leibnitz
“It is unworthy of excellent men to lose hours like slaves in the
calculation which could safely be relegated to anyone else if
machines were used”
The Nature of Technology
• Memory Extension : Pencil and Paper. Word Processed
Documents, Photographs, Painting
• Language Extension : Text Messages
• Cognitive Extension : ??
• Heidegger
Bohm and Jacopini
Three constructs can construct all programmes:
Sequence
Selection
Repetition
Sequence…
Selection…
Loop…
Binary Search Algorithm
1. Get the list of names 1,2,3,…N
2. Set “begin” to 1 and “end” to N
3. Set “found” to no
4. While “found” is no
1. Set “m” to middle value between “begin” and “end”
2. If “name” is “asked name”
1. Set “found” to yes
3. Else if “name” precedes “asked name” set “end” = m - 1
4. Else set “begin” to m + 1
Classification of Algorithms
Programming Problems
Uncomputable
Computable
Time
Polynomial
Space
Non-Polynomial