Emil Sekerinski, McMaster University, Winter Term 16/17

COMP SCI 1MD3 Introduction to Programming

 f(m)
What are the differences
a m b in the descriptions?

Suppose f is monotonically
increasing on [a, b] and:
f(a) ≤ 0, f(b) ≥ 0
To determine the x-intersect with
precision ε > 0:
An x-intersect of function f is
1. as long as b – a > ε, do 2. – 4.
an x such that f(x) = 0.
2. calculate m = (a + b)/2
3. if f(m) ≤ 0, set a to m, or
4. if f(m) ≥ 0, set b to m
The result is (a, b) such that
f(a) ≤ 0, f(b) ≥ 0, b – a ≤ ε
¡ Declarative descriptions state the properties of the result.
They describe what the result is. They are short, but cannot
be followed.
§ In the case of x-intersect, there could be several possible
results or their could be none

¡ Imperative descriptions tell how the result is obtained by

given a sequence of instructions. Each step is simple enough
that it can be followed.
§ In the case of x-intersect, restrictions on the input are
imposed (f monotonic), additional input is needed (a, b, ε),
and the result is only approximate (with ε). There is
repetition (line 1) and selection (lines 3, 4).
Suppose f is monotonically Suppose f is monotonically
increasing on [a, b] and: increasing on [a, b] and:
f(a) ≤ 0, f(b) ≥ 0 f(a) ≤ 0, f(b) ≥ 0
To determine the precise To determine the x-intersect with
x-intersect : precision ε > 0:
1. as long as b – a > 0, do 2. – 4. 1. as long as b – a > ε, do 2. – 4.
2. calculate m = (a + b)/2 2. calculate m = (a + b)/2
3. if f(m) ≤ 0, set a to m, or 3. if f(m) ≤ 0, set a to m, or
4. If f(m) ≥ 0, set b to m 4. if f(m) ≥ 0, set b to m
The result is (a, b) such that The result is (a, b) such that
a = b, f(a) = 0 f(a) ≤ 0, f(b) ≥ 0, b – a ≤ ε

No, for some f the “precise algorithm” will not stop: if a, b are
rational and the x-intersect is irrational, it be never be reached.
An algorithm specifies a sequence of instructions to be
executed by a machine that, when provided with input, will
eventually stop and produce some output.

A washing machine follows an algorithm for

the sequence of washing and drying cycles.
The instructions of that machine are taking
water in, letting water out, applying
detergent, rotating the drum, and heating
the water. The input is the selected program,
water, detergent, and the dirty laundry. The
output is the clean laundry and waste water.
 A traffic light follows an algorithm for
switching the light. The instructions of a
traffic light are turning individual lights
on and off.

Driving directions are an algorithm to be

executed by a human. The instructions are
driving to the next stop, continuing straight
ahead, turning left, turning right.

A cookbook recipe is an algorithm to be executed

by a human. Instructions are, putting ingredients
in a pot, stirring the soup for a minute, waiting
five minutes, and turning heat on and off.
¡ The computation prescribed by an algorithm goes through a
sequence of states, starting from an initial state, and each
instruction leading to a new state.

¡ The trace is the resulting sequence of states.

Algorithm comes from the Latin

translation, Algoritmi de numero Indorum,
of the 9th-century Muslim mathematician
al-Khowârizmî’s arithmetic treatise
al-Khowârizmî Concerning the Hindu Art of
Reckoning.
 Euclid’s algorithm for computing the greatest common divisor of two integer
numbers goes back to the Greek mathematician Euclid (circa 300 bc):

Assume that positive integers x and y are given. Trace for input x = 28 and y = 42:
1. Let u be x and v be y.
Instruction u v
2. As long as u is not equal to v, do one of
the following: 1. 42
28
2.1. If u > v, then subtract v from u.
2.2. If v > u, then subtract u from v. 2.2. 28 14
Finally, u is equal to v and their value is the
greatest common divisor of x and y. 2.1. 14 14

The state is given by the values of the variables u, v. The

input to the algorithm are x, y and the output is the gcd(x, y). WIKIPEDIA
Algorithms are supposed to be executed “mechanically”:

¡ Algorithms must be precise: each instruction and the next

possible instruction to be taken must be unambiguous.

¡ Algorithm must be effective: each instruction must be

executable by the underlying machine.

Two fundamental questions:

¡ Correctness: What is the produced output and for which

inputs is it produced?

¡ Efficiency: How many instructions do need to be executed in

the worst case or on average? How many resources (like
memory) are needed in the process?
A. The algorithm is in error Suppose f is monotonically
because it is ambiguous increasing on [a, b] and:
f(a) ≤ 0, f(b) ≥ 0
B. The algorithm is not in To determine the x-intersect with
error, but the inputs precision ε > 0:
which lead to f(m) = 0 are 1. as long as b – a > ε, do 2. – 4.
not allowed 2. calculate m = (a + b)/2
3. if f(m) ≤ 0, set a to m, or
C. Either instruction 3 or 4 is 4. if f(m) ≥ 0, set b to m
executed, it doesn't The result is (a, b) such that
matter f(a) ≤ 0, f(b) ≥ 0, b – a ≤ ε

Follow-up question: is the output of this algorithm always

unique? A: yes, B: no
Algorithms are formulated textually or as flowcharts:
Flowcharts connect instructions and conditions:

Instruction (statement, command, action), e.g.

S • turn green light on
• continue straight ahead
• subtract v from u

Condition (Boolean expression, test), e.g.

+ – • drum is full
B • water boils
• u is not equal to v
 We restrict to hierarchically structured flowcharts composed of:
Basic: Selection:
+ – if B then S else T Start
B (optional):

A S T End
(optional):

Sequence: Repetition:

– if B then S while B do S
B –
S + B
+
S then T
S
T S
The basic instructions of flowcharts are those of underlying
machine has for changing the state. If the machine is a
computer, the basic instruction is the assignment to a variable

x := e x becomes e

The multiple assignment updates variables simultaneously:

x, y := e, f x becomes e and y becomes f

For example, if initially x = 3 and y = 4, then x, y := x + y, x – y

sets x to 7 and y to –1
 ¡ Flowcharts are
u, v := x, y hierarchically
composed
–
u≠v ¡ This ensures that
+ every flowchart
+ – has a single entry
u>v
and single exit
u := u - v v := v - u

¡ This avoids
spaghetti-like
flowcharts!
https://en.wikipedia.org/wiki/Flowchart
 Patient
http://www.smartdraw.com/flowchart/flowchart-software.htm
leaves
https://www.gliffy.com/examples/flow-charts/
The median of x, y, z, is the “middle” number. The median of 3, 7, 2
is 3. The median of 3, 7, 3 is also 3. Assign the median of x, y, z to m!
+ –
x<y

+ – + –
z<x x<z

+ – + –
m := x z<y m := x z<y

m := z m := y m := y m := z
 • Annotations express
what holds at particular
points
+ –
x<y
x<y • They are declarative
z<x + – x<y descriptions
z<x
x<y x≤z
+ – • They help understanding
m := x z<y x<y
algorithms and arguing
y≤z
their correctness
m := z m := y
z<m x<m
m<y m≤z • It is good practice to
explicitly write the main
annotations

• There is a danger of over-

annotating!
¡ Let ti for 0 ≤ i < n be a i, min, max := 1, t0, t0
series of n temperature
readings where each –
i<n
reading is an integer +
and n > 0 + –
ti < min
¡ Set min and max to the –
min := ti ti > max
minimal and maximal +
temperature!
max := ti

i := i + 1
¡ How many comparisons
with ti will be made in i, min, max := 1, t0, t0
the best and worst case? –
¡ n – 1 comparisons i<n
if t is strictly decreasing +
¡ 2 x (n – 1) comparisons if + –
ti < min
t is increasing
–
¡ How many assignments min := ti ti > max
to min and max will be +
made in the best and max := ti
worst case!
¡ 1 to min, 1 to max if all ti
are the same i := i + 1
¡ 1 + n in total if t strictly
increasing
1. At check-in counter: • Reformulate as an algorithm!
§ Present id
§ Put luggage on scale. If too • Verbs indicate instructions.
heavy pay fee or remove
items and put luggage back
on scale • Conditions suggest selection
§ Obtain boarding pass
and repetition
2. At security check:
§ Place necklace, belt, etc., in • Although this is presented in
tray “structured English”, look for
§ Pass through scanner synonyms and implicit
§ If scanner beeps check for information.
further accessories and try
again
3. At the gate:
§ Present boarding pass
Go to
1. At check-in counter: • Reformulate as an algorithm!
§ Present id
§ Put luggage on scale. If too • Verbs indicate instructions.
heavy pay fee or remove
items and put luggage back
on scale • Conditions suggest selection
and repetition
Go to§ Obtain boarding pass
2. At security check:
§ Place necklace, belt, etc., in • Although this is presented in
tray “structured English”, look for
§ Pass through scanner synonyms and implicit
§ If scanner beeps check for information.
further accessories and try
again
Go to
3. At the gate:
§ Present boarding pass
 Go to check-in counter

Present passport

1. At check-in counter: Put luggage on scale

§ Present id
too heavy and –
§ Put luggage on scale. If too
heavy pay fee or remove not willing to pay
+
items and put luggage back
on scale Remove luggage from scale
§ Obtain boarding pass
Remove items
2. At security check:
§ Place necklace, belt, etc., in Put luggage on scale
tray
§ Pass through scanner –
§ If scanner beeps check for
too heavy
further accessories and try
again +
3. At the gate: Pay fee
§ Present boarding pass
 Obtain boarding pass have no
luggage
Go to security check

¡ How would you argue for the Place accessories in tray

correctness of this algorithm?
Pass through scanner
¡ You cannot go through the
–
security check with luggage scanner beeps
+
¡ At the gate you have to have Place accessories in tray
the boarding pass
Pass through scanner
¡ Correctness is ensured by
checking if an annotation have
Go to gate
holds on all paths leading to boarding
it! Present boarding pass pass
¡ Algorithms can either be transformational, computing
output given some input, or can be interactive (or online
algorithms), producing output and needing input during
computation

¡ Scheduling a meeting, running a car

repair shop, (board and computer)
games are interactive algorithms

¡ In this course, we mainly consider

transformational algorithms
¡ Algorithmic notions are not only applicable to programs

¡ They give us a vocabulary to talk about a wide range of

problems. They are a tool for our mind

¡ Increasingly, they are used to describe the environment in

which computers operate, e.g. approval processes in banks,
information flows in hospitals
¡ Programs are algorithms that can be
executed automatically by a computer

¡ Fixed-program computers serve only

one purpose (some early computers,
digital clock, washing machine)

¡ One of the first modern stored-program WIKIPEDIA

computers was the Manchester Mark-1 from 1949

¡ It achieved universality by storing instructions the same way

as data, allowing programs to be changed – the universality
of “machines” was anticipated by Alan Turing in 1936
 ¡ Eight bits (binary digits)
memory Processor form a byte and a
(CPU) number of bytes (say 4)
bus form a word that holds
4328 …11010 register
either data (like an
integer) or an instruction
variable, ¡ In a von Neumann
e.g. “u”
Architecture programs
and data are placed in the
1036 …11001 arithmetic
same memory (typical for
unit CPUs)
¡ In a Harvard Architecture
instruction two distinct memories
0 e.g. “minus” are used for instructions
and data (typical for
e.g. 32 bits GPUs)
¡ Instructions of a computer are
the computer’s machine language

¡ Fortran, an early high-level language

from 1958 was a “formula translator” Fortran “arithmetic if”:
for mathematical expressions into IF (X) 10, 20, 30
machine language Jump to card 10, 20 , 30
if X < 0, X = 0, X > 0

¡ Starting with Algol, Pascal in the 60’s and 70’s, programming

languages are closer to algorithmic notation.

¡ While graphical programming languages have dedicated use,

textual languages are dominant for large programs.
Pascal: C, Java: Python:

function gcd(x, y: integer): integer; int gcd(int x, int y) { def gcd(x, y):
var u, v: integer; int u, v; u, v = x, y
begin u := x; v := y; u = x; v = y; while u != v:
while u <> v do while (u != v) if u > v: u = u – v
if u > v then u := u – v if (u > v) u = u – v; else: v = v – u
else v := v – u; else v = v – u; return u
gcd := u return u;
end }
u, v := x, y

u≠v –
+
+ u>v –

u := u - v v := v - u
¡ Machine instructions are very primitive:
§ Move data between memory and processor registers
§ Perform an arithmetic operation on registers
§ Compare registers
§ Jump to another memory location

¡ Compilers translate high-level programs to machine

language

u := u – v R1 := u move u to register 1
R2 := v move v to register 2
R1 := R1 – R2 subtract register 2 from 1
u := R1 move register 1 to u
¡ Notation:
§ <> or != for ≠
§ begin … end or {…} or indentation for bracketing
¡ Safety:
§ type checking (Java: static, Python: dynamic, C: little)
¡ Support for large programs:
§ classes (Java, Python: yes, C: no)
§ exceptions (Java, Python: yes, C: no)
¡ Instructions and standard libraries:
§ data types like lists, sets, dictionaries (Python: yes)
§ interaction, graphics (mixed)
¡ Application:
§ dedicated (JavaScript, Flash: web pages)
§ general-purpose (Java, Python, Pascal, C: yes)
¡ The Python notation is compact and intuitive,
making it a good beginner’s language

¡ Python compiles to an intermediate language The language and

and interprets that, why Python is sometimes the IDLE
referred to as an interpreted language; this environment are
named after the
makes interactions with the Python British comedians
environment quick, allowing easy exploration Monty Python

¡ Python supports many mathematical data types, allowing

programs to be abstract and easy to understand

¡ Python is widely used in industry