Transcript Copy of Lecture_2010_11

Algorithms
and
Algorithmic Thinking
(Abstraction part 1)
Recap
Statement of The Problem
Theory of the Problem
Modelling of the Problem
Algorithmic description
Future
delights
today
Programming the Algorithm done
Executing the Program done
Abstraction
The ability to separate the high level view of an
entity or an operation from the low-level details of
its implementation.
Abstract
Process / (Data)
Non-Abstract
Process / (Data)
A Fun Algorithm
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?
A Serious Algorithm – Sum of a List
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
A fun Algorithm - 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.
Stable Marriage - Example
A
W
A
W
B
X
B
X
C
Y
C
Y
D
Z
D
Z
A
W
A
W
B
X
B
X
C
Y
C
Y
D
Z
D
Z
A
W
A
W
B
X
B
X
C
Y
C
Y
D
Z
D
Z
A
W
A
W
A
W
B
X
B
X
B
X
C
Y
C
Y
C
Y
D
Z
D
Z
D
Z
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.
Fun -3- Magic Card Trick
Is this an Algorithm?
Consider this example taken from the instructions
on the back of a shampoo bottle:
• Wet hair
• Lather
• Rinse
• Repeat
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
Process
Non-Algorithmic
Process
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.
Examples of Recent Serious Algorithms
(1) Matching of kidney donor – recipients
(2) Traffic-flow engineering
(3) Cancer Research.
Examples of “Standard” Computing Algorithms
(1a) Sequential Search
(1b) Binary Search
(2a) Selection Sort
(2c) Quicksort
Sequential Search Algorithm - Description
Anne
Bob
Carol
Daniel
Grant
Nathan
Sue
Sequential Search Algorithm - Example
Anne
Bob
Carol
Daniel
Grant
Nathan
Sue
Binary Search Algorithm - Description
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
Binary Search Algorithm - Example
Anne
Bob
Carol
Daniel
Grant
Nathan
Sue
How to Make a Binary Tree
Binary Search (Tree Representation)
Daniel
Bob
Anne
Nathan
Carol
Grant
Sue
Depth of a Binary Tree (complete)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4
2
1
6
3
5
7
Depth of a Binary Tree (incomplete)
1
2
3
4
5
6
7
8
4
2
1
6
3
5
7
8
Comparison
of Sequential and Binary Search
60
50
40
Series1
30
Series2
20
10
0
0
10
20
30
40
50
60
Selection Sort Algorithm - Description
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
Selection Sort Algorithm - Example
10
30
20
5
18
25
Quick Sort Algorithm - Description
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
Quicksort Algorithm Example
13
81
92
65
43
31
57
26
75
0
Comparison of Selection sort and Quicksort
250000
200000
150000
Series1
Series2
100000
50000
0
0
50000
100000
150000
200000
250000
Hamiltonian Cycles
Problem: Find a path between n cities to
(i) Visit each city once
(ii) End up at the starting city.
Hamiltonian Cycles
A
C
B
D
Travelling Salesman Problem
Find the Hamiltonian circuit
between a number of cities
where each link has an
associated cost
Application of the TSP is to logistics. Good routes or
schedules for:
• trucks (Dantzig & Ramser, 1959)
• order-pickers in a warehouse (Ratli & Rosenthal, 1981)
• service engineers (Pante, Lowe & Chandrasekaran, 1987)
• aircraft (Boland, Jones & Nemhauser, 1994)
• tourists (Gentili, 2003)
TSP – Simulated Annealing
1
pick an initial solution
2
set an initial temperature
3
choose the next neighbour of the current solution:
4
if the neighbour is “better” make that neighbour the
current solution
5
if the neighbour is “worse”, make this neighbour the
current solution, based on the temperature and how
“worse” the neighbour is. (Probabilitistic calculation).
6
decrease the temperature slightly
7
go to 3.
TSP – Ant Colony Model
Pattern Matching
C C G A T A C G T T A G C T T A C
Pattern Matching (Worst Case -1-)
C C C C C C C C C
Pattern Matching (Worst Case -2-)
A A A A A A A A A
Pattern Matching (Best Case)
A B C D E F G H I
Worst-Case Execution Time of Algorithms
Sequential Search
( n )
Binary Search
(log n)
Selection Sort
( n 2 )
Quicksort
(n log n)
Pattern Matching
(mn)
Permutation
(2n )
Worst-Case Execution Time on a 2GHz Pentium
n
( n )
(log n)
( n 2 )
(n log n)
(mn)
(2n )
10
20
100
1000
Classification of Algorithms
Programming Problems
Uncomputable
Computable
Time
Tractable
Space
Intractable
A.N.Whitehead and Leibnitz
“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).
“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”