Introduction to Algorithms
1
Topics
• Systematic problem solving
• Algorithms
2
The Problem-solving Process
"Doctor, my head hurts"
Analysis Patient has elevated
pressure in anterior
Problem parietal lobe
specification
1. Sterilize cranial saw
Design
2. Anaesthetize patient
3. Remove top of skull
Algorithm 4. Get the big spoon...
5. etc., etc.
Implementation sterilize(saw,alcohol);
raise_hammer();
lower hammer(fast);
Program
start(saw);
/* etc. etc. */
Compilation 0100111010110010101010101
0010101010101001100101010
Executable 1010100101101001110101010
(solution) 1010010010111010011110101
010111110101010001101… 4
The Problem-solving Process
“Engg, my TV not working"
Analysis There was a spark in wire
Problem
specification 1. Take new wire
Design 2. Remove the old one
3. Connect new wire
4. Check if it works
Algorithm 5. etc., etc.
Implementation New=NewWire(length,amp);
Replace(old,new);
check(TV);
Program /* etc. etc. */
Compilation
01001110101100101010101010010
10101010100110010101010101001
011010011101010101010010010111
Executable 010011110101010111110101010001
(solution) 10100001101...
5
The Problem-solving Process
Analysis
Problem
specification
Design
Algorithm
Implementation
Program
Compilation
Executable
(solution) 6
Algorithm – Working Definition
• A sequence of instructions describing how
to do a task
[As opposed to actually executing the
instructions]
7
Algorithm -- Examples
• A cooking recipe
• The rules of how to play a game
• Projector instructions
• Description of a martial arts technique
• Directions for driving from A to B
• A car repair manual
8
Algorithm – Examples (cont)
• Recipe for Almond and honey slice
• Rose milk shake
9
Almond and Honey Slice Preheat oven for 200° C
Line a 30 cm 20 cm baking
tray with baking foil paper,
1/2 quantity Shortcrust
and then with pastry
Pastry
Bake blind for 20 minutes, then
185 g unsalted butter
remove foil paper
100 g sugar
Turn oven up to 220° C.
5 tablespoons honey
Bring remaining ingredients to a
50 ml cream boil, stirring.
50 ml brandy or spirit Spread evenly over pastry.
300 g flaked almonds Bake until topping is bubbling,
about 15 minutes.
From: Stephanie Alexander, The Cool before cutting into fingers
Cook’s Companion, Viking/Penguin, or squares.
Ringwood, Victoria, 1996, p. 349.
10
Rose milk shake Pore milk to mixer jar
200 ml rose syrup Add rose syrup to jar
1 ltr milk
100 g sugar Add sugar
150 g Ice cubes
Switch on the mixer and mix
them for 30 seconds
Add ice cubes to the jar and
again switch the mixer on for
30 seconds.
Pore the mix in glass and serve
11
Rose milk shake Pore milk to mixer jar
200 ml rose syrup Add rose syrup to jar
1 ltr milk
100 g sugar Add sugar
Instructions are given
150 g Ice cubes
in the order in which Switch on the mixer and mix
they are performed them for 30 seconds
(“executed”)
Add ice cubes to the jar and
again switch the mixer on for
30 seconds
Pore the mix in glass and serve
12
From Algorithms to Programs
Problem
Algorithm: A sequence
of instructions describing
how to do a task (or
process)
C Program 13
Components of an Algorithm
• Variables and values
• Instructions
– Sequences
– Procedures
– Selections
– Repetitions
Also required: Documentation
14
Values
• Represent quantities, amounts or
measurements
• May be numerical or alphabetical
(or other things)
• Often have a unit related to their purpose
• Example:
– Recipe ingredients
15
Rose milk shake
Pore milk to mixer jar
200 ml rose syrup
Add rose syrup to jar
1 ltr milk
100 g sugar Add sugar
150 g Ice cubes Switch on the mixer switch and
mix them for 30 seconds
Add ice cubes to the jar and
again switch the mixer on for
30 seconds
Pore the mix in glass and serve
16
Rose milk shake
Pore milk to mixer jar
200 ml rose syrup
Add rose syrup to jar
1 ltr milk
100 g sugar Add sugar
150 g Ice cubes Switch on the mixer switch and
mix them for 30 seconds
Add ice cubes to the jar and
again switch the mixer on for
30 seconds
Pore the mix in glass and serve
17
Variables
• Are containers for values – places to store
values
• Example:
Variable Values
200 ml rose syrup
This jar
1 ltr of milk
can contain
100 g of sugar
etc.
18
Restrictions on Variables
• Variables may be restricted to contain a
specific type of value
19
Components of an Algorithm
Values and Variables
• Instruction (a.k.a. primitive)
– Sequence (of instructions)
– Procedure (involving instructions)
– Selection (between instructions)
– Repetition (of instructions)
• Documentation (beside instructions)
20
