PowerPoint Presentation
Iterative Algorithms
& Loop Invariants
Jeff Edmonds
York University
COSC 3101
Lecture 1
Actions vs Landmarks
Proof Using Loop Invariants
Code vs Math Assertions
Physics and Life
Home to School Problem
Recap of Proof of Meta Algorithm
Define Assertions and Measures
Code from LI
Pointers
Views of Algorithms
Insertion Sort
Selection Sort
Don’t Redo Work
Designing an Algorithm
Finding Errors
Fairy God Mother (Lake)
More of Input (Insertion and DFA)
More of Output (Selection & Blocks)
Narrowing the search space
The Partition Problem
Shrinking Instance (GCD) (Running Time)
Multiplying
Data Structure (System) Invariants
Bucket (Quick) Sort for Humans
Radix/Counting Sort
Lower Bound for Sort
‹#›
1
loop (until done)
take step
end loop
A good way to structure many programs:
Store the key information you currently know in some data structure.
In the main loop, take a step forward towards destination
by making a simple change to this data.
Iterative Algorithms
& Loop Invariants
‹#›
2
loop
exit when
codeB
codeC
next
I implored you to not worry
about the entire computation.
i-1
i
i
i
0
T+1
Trust who passes you
the baton
and go around once
Iterative Algorithms
‹#›
3
loop
exit when
codeB
codeC
9 km
5 km
A loop invariant is a statement/picture
about the state of your computation
to make sure it does not get lost.
Your algorithm must only maintain it
while making progress
I implored you to not worry
about the entire computation.
Iterative Algorithms
Loop Invariants
‹#›
4
Paradigm Shift
Is the black the form and the green the background?
Is the green the form and the black the background?
It is helpful to have different ways of looking at it.
Iterative Algorithms
Loop Invariants
‹#›
5
Iterative Algorithms
Loop Invariants
An Algorithm viewed
as a sequence of
Landmarks:
Actions:
I can get lost!!!
.. Right
.. Straight
.. Left …..
.. Straight
‹#›
6
Iterative Algorithms
Loop Invariants
An Algorithm viewed
as a sequence of
m = max(m,5)
Landmarks:
Actions:
m = 4
m = max(m,3)
m = max(m,7)
m = max(m,1)
I can get lost!!!
‹#›
7
Iterative Algorithms
Loop Invariants
Input:
4
5
3
7
1
Output: Max is 7.
Max of
4
is 4
An Algorithm viewed
as a sequence of
Max of
4
5
is 5
Max of
4
5
3
Max of
4
5
3
7
Max of
4
5
3
7
1
is 7
Landmarks:
Actions:
m = max(m,5)
m = 4
m = max(m,3)
m = max(m,1)
With landmarks,
I don’t got so lost.
Assumptions
(picture)
that must be true.
is 7
m =
max( , )
m
is 5
7
One step at a time:
Move from previous landmark
‹#›
8
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
Max of
4
5
3
is 5
Input:
4
5
3
7
1
Output: Max is 7.
Preconditions:
Any assumptions that must be true about the input instance.
‹#›
9
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
“postCond:
return max in{A[1]..A[n]}”
Max of
4
5
3
is 5
Input:
4
5
3
7
1
Output: Max is 7.
Postconditions:
The statement of what must be true when the algorithm/program returns.
‹#›
10
Max of
4
5
3
is 5
Input:
4
5
3
7
1
Output: Max is 7.
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
“loop-invariant:
m is max in {A[1]..A[i]}”
“postCond:
return max in {A[1]..A[n]}”
Loop Invariant:
any assumptions (picture) that
must be true at the top of the loop.
‹#›
11
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
“loop-invariant:
m is max in {A[1]..A[i]}”
“postCond:
return max in {A[1]..A[n]}”
Max of
4
5
3
is 5
Input:
4
5
3
7
1
Output: Max is 7.
Max of
4
is 4
Establish
the loop invariant.
‹#›
12
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 0
m = 0
“loop-invariant:
m is max in {A[1]..A[i]}”
“postCond:
return max in {A[1]..A[n]}”
Z
Max of
4
5
3
is 5
Input:
4
5
3
7
1
Output: Max is 7.
Max of
is ?
Establish
the loop invariant.
-
-4
m is the smallest number that is
bigger an every element in the empty set.
‹#›
13
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
m = max(m,A[i+1])
i = i + 1
endloop
“postCond:
return max in {A[1]..A[n]}”
Max of
4
5
3
is 5
Input:
4
5
3
7
1
Output: Max is 7.
Max of
4
5
3
7
is 7
Max of
4
is 4
Maintain
the loop invariant.
‹#›
14
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
Max of
4
5
3
is 5
Input:
4
5
3
7
1
Output: Max is 7.
Max of
4
5
3
7
is 7
Max of
4
is 4
Max of
4
5
3
7
1
is 7
Obtaining Postcondition
‹#›
15
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
A loop invariant is
any assumptions
(picture)
that must be true
at the top of the loop.
Tell me!
How can you possibly understand this algorithm without knowing what is true when
the computation is here?
‹#›
16
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
Not just to please the prof.
Not just to prove correctness.
Use them to think about your algorithm!
Before you start coding.
What do you want to be
true in the middle of your computation?
You need to know.
Let your reader know.
A loop invariant is
‹#›
17
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
Definition of Correctness
code
How is this proved?
array A[1..n]
code
m is max
in {A[1]..A[n]}
‹#›
18
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
Step 0
array A[1..n]
i = 1
m = A[1]
m is max
in {A[1]..A[i]}
‹#›
19
Step 1
¬
codeB
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
m = max(m,A[2])
m is max
in {A[1]}
m is max
in {A[1],A[2]}
‹#›
20
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
Step 2
m = max(m,A[3])
m is max
in {A[1],A[2]}
m is max
in {A[1]..A[3]}
¬
codeB
‹#›
21
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
Step i
m = max(m,A[i+1])
m is max
in {A[1]..A[i]}
m is max
in {A[1]..A[i+1]}
¬
codeB
‹#›
22
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
mt+1 = max(mt,A[it+1])
it+1 = it + 1
Induction
Step i
m is max
in {A[1]..A[it]}
¬
codeB
m is max
in {A[1]..A[it+1]}
‹#›
23
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
Last Step
codeC
i=n
return(m)
m is max
in {A[1]..A[i]}
return max
in {A[1]..A[n]}
‹#›
24
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
return max in {A[1]..A[n]}”
Definition of Correctness
code
array A[1..n]
code
return is max
in {A[1]..A[n]}
‹#›
25
I don’t like i=i+1
It is code/actions!
If you want to prove things,
you need math assertions.
it+1 = it+1
I will try to translate.
Lets demonstrate with a strange example.
Code vs
Math Assertions
‹#›
26
loop
“loop-invariant: ??
exit when ???
x = x + 1
y = y + x
x = x y
end loop
4:
5:
6:
7:
8:
Let xt and yt be the values of x and y
at the beginning of the iteration.
xt
yt
x
y
Your are at the top of the loop.
You do not know what
happened before.
Does this me that
this is the tth iteration?
No! In order be able to do it only once,
you can’t know what
happened before.
Don’t consider
t-1 or t+1
Code vs
Math Assertions
Could be denoted
x´ and y´
‹#›
27
loop
“loop-invariant: ??
exit when ???
x = x + 1
y = y + x
x = x y
end loop
4:
5:
6:
7:
8:
xt
+1
yt
+xt+1
( )(yt+xt+1)
x
y
Your are at the top of the loop.
You do not know what
happened before.
yt+1 = yt+xt+1
xt+1 = (xt+1)(yt+xt+1)
Excellent.
These are math assertions giving
the relationship between
the old and new values.
Let xt and yt be the values of x and y
at the beginning of the iteration.
Let xt+1 and yt+1 be their values after going around again.
Code vs
Math Assertions
‹#›
28
loop
“loop-invariant: ??
exit when ???
x = x + 1
y = y + x
x = x y
end loop
4:
5:
6:
7:
8:
xt
+1
yt
+xt+1
( )(yt+xt+1)
x
y
Your are at the top of the loop.
You do not know what
happened before.
yt+1 = yt+xt+1
xt+1 = (xt+1)(yt+xt+1)
Lets build a DFA from 2001
(Deterministic Finite Automata)
line=4, x=xt, y=yt
q
δ(
, iteration)
line=4, x=(xt+1)(yt+xt+1), y=yt+xt+1
= q
Let xt and yt be the values of x and y
at the beginning of the iteration.
Let xt+1 and yt+1 be their values after going around again.
Code vs
Math Assertions
‹#›
29
loop
“loop-invariant: ??
exit when ???
x = x + 1
y = y + x
x = x y
end loop
yt+1 = yt+xt+1
xt+1 = (xt+1)(yt+xt+1)
¬
codeB
true about xt and yt
¬
true about xt and yt
codeB
true about xt+1 and yt+1
Code vs
Math Assertions
Induction
Assume LI is true after t iterations
and prove true after t+1
‹#›
30
Your job is only to
Trust who passes you the baton
Go around once
Pass on the baton
i-1
i
i
i
0
T+1
A Relay Race
‹#›
31
loop
exit when
codeB
endloop
codeC
0
Person 0: Carries baton region to safe region
Establishing Loop Invariant
‹#›
32
Person i: Running around the track
i-1
i
loop
exit when
codeB
endloop
codeC
i
i
¬
codeB
Exit
Maintaining Loop Invariant
‹#›
33
T+1
loop
exit when
codeB
endloop
codeC
codeC
Exit
Clean up loose ends
Last Person: Carries baton from safe region to finish.
‹#›
34
Partial Correctness
Proves that IF the program terminates then it works
Þ
codeA
Establishing Loop Invariant
codeC
Clean up loose ends
Exit
¬
codeB
Maintaining Loop Invariant
Exit
‹#›
35
Designing an Algorithm
Define Problem Define Loop Invariants
Define Step Define Exit Condition Maintain Loop Inv
Initial Conditions Ending
Exit
Exit
Exit
‹#›
36
Iterative Algorithms
Loop Invariants
Physics( )
“preCond:
Input is a roller coaster
with car starting high.”
loop
exit when (car at end)
x t+t,v t+t
= Newton(x t,v t)
endloop
return(vfinal)
“postCond:
speed of car at end”
→
→
→
→
How does Newton solve this?
What is conserved?
Energy & Mass
Et+t = Et
(kinetic potential)
Actions?
Too much computation!
‹#›
37
Iterative Algorithms
Loop Invariants
Physics( )
“preCond:
Input is a roller coaster
with car starting high.”
loop
“loop-invariant:
Et = E0”
exit when (car at end)
x t+t,v t+t
= Newton(x t,v t)
endloop
return(vfinal)
“postCond:
speed of car at end”
→
→
→
→
Et+t = Et
A loop invariant is
any assumptions
(picture)
that must be true
at the top of the loop.
‹#›
38
Iterative Algorithms
Loop Invariants
Physics( )
“preCond:
Input is a roller coaster
with car starting high.”
loop
“loop-invariant:
Et = E0”
exit when (car at end)
x t+t,v t+t
= Newton(x t,v t)
endloop
return(vfinal)
“postCond:
speed of car at end”
→
→
→
→
A loop invariant is
like property
in physics that is
conserved/maintained.
‹#›
39
Iterative Algorithms
Loop Invariants
Physics( )
“preCond:
Input is a roller coaster
with car starting high.”
loop
“loop-invariant:
Et = E0”
exit when (car at end)
x t+t,v t+t
= Newton(x t,v t)
endloop
return(vfinal)
“postCond:
speed of car at end”
Et+t = Et = E0
→
→
→
→
¬
codeB
‹#›
40
Iterative Algorithms
Loop Invariants
Physics( )
“preCond:
Input is a roller coaster
with car starting high.”
E0 = ½mv02 + h0m
loop
“loop-invariant:
Et = E0”
exit when (car at end)
x t+t,v t+t
= Newton(x t,v t)
endloop
return(vfinal)
“postCond:
speed of car at end”
codeA
‹#›
41
Iterative Algorithms
Loop Invariants
Physics( )
“preCond:
Input is a roller coaster
with car starting high.”
E0 = ½mv02 + h0m
loop
“loop-invariant:
Et = E0”
exit when (car at end)
x t+t,v t+t
= Newton(x t,v t)
endloop
vfinal = (2E0/m-2hfinal)½
return(vfinal)
“postCond:
speed of car at end”
codeC
‹#›
42
Iterative Algorithms
Loop Invariants
Physics( )
“preCond:
Input is a roller coaster
with car starting high.”
E0 = ½mv02 + h0m
loop
“loop-invariant:
Et = E0”
exit when (car at end)
x t+t,v t+t
= Newton(x t,v t)
endloop
vfinal = (2E0/m-2hfinal)½
return(vfinal)
“postCond:
speed of car at end”
‹#›
43
Designing an Algorithm
Define Problem Define Loop Invariants
Define Step Define Exit Condition Maintain Loop Inv
Initial Conditions Ending
Exit
Exit
Exit
‹#›
44
Iterative Algorithms
Loop Invariants
Life( me)
“preCond:
I am born.”
Hopefully my parents help
loop
“loop-invariant:
I am well
and reasonably on track”
exit when (I die)
Maintain the loop invariant
Make a little progress
Make the world a little better.
endloop
“postCond:
It was a well spent and good life”
next
One day at a time.
‹#›
45
Designing an Algorithm
Define Problem Define Loop Invariants
Define Step Define Exit Condition Maintain Loop Inv
Initial Conditions Ending
Exit
Exit
Exit
‹#›
46
Designing an Algorithm
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
47
I like understanding things
using a story.
I will now tell one.
‹#›
48
The Getting to School Problem
‹#›
49
Problem Specification
Pre condition: location of home and school
Post condition: traveled from home to school
‹#›
50
Algorithm
What is an Algorithm?
‹#›
51
Algorithm
The algorithm defines the computation route.
‹#›
52
Algorithm
Is this reasonable?
‹#›
53
Complexity
There are an infinite number of input instances
Algorithm must work for each.
‹#›
54
Complexity
Difficult to predict where computation might be in the middle of the computation.
‹#›
55
The current “State” of computation is determined by values of all variables.
Location of Computation
‹#›
56
Suppose the computation ends up here?
Location of Computation
‹#›
57
Suppose the computation ends up here?
Location of Computation
‹#›
58
Don’t Panic
Where ever the computation might be, take best step towards school.
good enough
‹#›
59
General Principle
Do not worry about the entire computation.
Take one step at a time!
next
‹#›
60
Defining Algorithm
Wherever the computation might be, take step towards school.
‹#›
61
Take a step
What is required of this step?
‹#›
62
A Measure of Progress
79 km
75 km
‹#›
63
79 km
75 km
Defining Algorithm
Is this sufficient to define a working algorithm?
‹#›
64
Working Algorithm
Computation steadily approaches goal
79 km
75 km
‹#›
65
Defining Algorithm
Extra requirements
78.999 km
79 km
0 km
79 km
75 km
‹#›
66
Wherever the computation might be, take best step towards school.
Define a Step
‹#›
67
Some location too confusing for algorithm
Algorithm too lazy to define step for every location.
Computation Stuck
‹#›
68
Algorithm specifies from which locations it knows how to step.
Safe Locations
‹#›
69
“The computation is presently in a safe location.”
Maybe true and maybe not.
If not something has gone wrong.
Loop Invariant
‹#›
70
Defining Algorithm
From every safe location, define one step towards school.
‹#›
71
Take a step
What is required of this step?
‹#›
72
If the computation is in a safe location, it does not step into an unsafe one.
Maintain Loop Invariant
‹#›
73
Can we be assured that the computation will always be in a safe location?
If the computation is in a safe location, it does not step into an unsafe one.
Maintain Loop Invariant
‹#›
74
Can we be assured that the computation will always be in a safe location?
If the computation is in a safe location, it does not step into an unsafe one.
Maintain Loop Invariant
No. What if it is not initially true?
‹#›
75
From the Pre-Conditions on the input instance we must establish the loop invariant.
Establishing Loop Invariant
‹#›
76
Maintain Loop Invariant
Can we be assured that the computation will always be in a safe location?
By what principle?
‹#›
77
Maintain Loop Invariant
By Induction the computation will always be in a safe location.
‹#›
78
Ending The Algorithm
Exit
Define Exit Condition
Termination:
0 km
Exit
With sufficient progress,
the exit condition will be met.
Exit
from these we must establish the post conditions.
Exit
When we exit, we know
exit condition is true
loop invariant is true
‹#›
79
Let’s Recap
‹#›
80
Designing an Algorithm
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
Is this sufficient?
‹#›
81
Consider an Algorithm
Exit
0 km
Exit
Exit
79 km
75 km
Exit
‹#›
82
Loop Invariant Maintained
Exit
‹#›
83
Computation can always proceed
Exit
‹#›
84
Computation always makes progress
79 km
75 km
79 km
75 km
Exit
‹#›
85
Computation Terminates
79 km
75 km
0 km
0 km
0 km
Exit
Exit
‹#›
86
Computation Terminates
Exit
Exit
‹#›
87
Consider an Algorithm
This is sufficient!
Exit
0 km
Exit
Exit
79 km
75 km
Exit
‹#›
88
More about
Assertions
and
Measures of Progress
‹#›
89
An Algorithm viewed
as a sequence of
Landmarks:
Actions:
I can get lost!!!
.. Right
.. Straight
.. Left …..
.. Straight
‹#›
90
Purpose of Assertions
Useful for
thinking about algorithms
developing
describing
proving correctness
‹#›
91
Definition of Assertions
An assertion is a statement
about the current state of the data structure that is either true or false.
eg. the amount in your bank account
is not negative.
‹#›
92
Definition of Assertions
It is made at some particular point during the execution of an algorithm.
It should be true independent of
the path followed through the code
and independent of the input.
If it is false, then something has gone wrong in the logic of the algorithm.
‹#›
93
Definition of Assertions
An assertion is not a task for the algorithm to perform.
It is only a comment that is added for the benefit of the reader
and for the writer!
‹#›
94
Definition of Assertions
The current state of the computation
Everything that is true at a particular instant in time.
Imagine flying in from Mars,
what do you need to know about the present
to be able to continue.
It does not say anything about the past,
i.e. how the computation got here.
Eg
‹#›
95
Definition of Assertions
The current state of the computation
An assertion, A
is a function
that takes as input the current state
and that outputs
Eg A = “x is odd”
A( ) = True
A( ) = False
True or False
Computation is
on the path
Something has
gone wrong!
‹#›
96
Don't Be Frightened
An assertion need not consist of formal mathematical mumble jumble
Use an informal description
and a picture
‹#›
97
if( ) then
code<1,true>
else
code<1,false>
end if
if( ) then
code
else
code
end if
…
any
code
How is this proved?
Definition of Correctness
A Sequence of Assertions
Must check 2r different
settings of
paths through the code.
Is there a faster way?
‹#›
98
if( ) then
code<1,true>
else
code<1,false>
end if
if( ) then
code
else
code
end if
Step 1
code<1,true>
¬
code<1,false>
…
A Sequence of Assertions
‹#›
99
if( ) then
code<1,true>
else
code<1,false>
end if
if( ) then
code
else
code
end if
…
Step 2
code<2,true>
¬
code<2,false>
A Sequence of Assertions
Must check 2r not 2r different
settings of
paths through the code.
‹#›
100
Max( a,b,c )
“preCond:
Input has 3 numbers.”
m = a
“assert: m is max in {a}”
if( b>m )
m = b
endif
“assert: m is max in {a,b}”
if( c>m )
m = c
endif
“assert: m is max in {a,b,c}”
return(m)
“postCond:
return max in {a,b,c}”
A Sequence of Assertions
Example
code
‹#›
101
A Sequence of Assertions
Example
code<1,true>
¬
code<1,false>
Max( a,b,c )
“preCond:
Input has 3 numbers.”
m = a
“assert: m is max in {a}”
if( b>m )
m = b
endif
“assert: m is max in {a,b}”
if( c>m )
m = c
endif
“assert: m is max in {a,b,c}”
return(m)
“postCond:
return max in {a,b,c}”
‹#›
102
A Sequence of Assertions
Example
code<2,true>
¬
code<2,false>
Max( a,b,c )
“preCond:
Input has 3 numbers.”
m = a
“assert: m is max in {a}”
if( b>m )
m = b
endif
“assert: m is max in {a,b}”
if( c>m )
m = c
endif
“assert: m is max in {a,b,c}”
return(m)
“postCond:
return max in {a,b,c}”
‹#›
103
Max( a,b,c )
“preCond:
Input has 3 numbers.”
m = a
“assert: m is max in {a}”
if( b>m )
m = b
endif
“assert: m is max in {a,b}”
if( c>m )
m = c
endif
“assert: m is max in {a,b,c}”
return(m)
“postCond:
return max in {a,b,c}”
A Sequence of Assertions
Example
code
‹#›
104
Working Algorithm
Computation steadily approaches goal
79 km
75 km
You need to define some
Measure of progress
to prove that your algorithm
eventually terminates.
‹#›
105
Algorithm Termination
You need to define some
Measure of progress
to prove that your algorithm
eventually terminates.
An Measure of Progress, M
is a function
that takes as input the current state
and that outputs
Eg Measure = “value of y”
M( ) = 3
We must prove that this number goes down (up)
each iteration.
a real number
‹#›
106
Simple Example
A sum of objects
You MUST do it my way!
‹#›
107
Designing an Algorithm
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
108
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
What is the loop invariant?
Each iteration add in a new object.
Action not picture
If you fight me,
I will fail you
‹#›
109
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
What is the loop invariant?
What do you want to be true in the middle of the computation?
To have a partial sum:
s = 12 + 22 + 32 + … + i2
(and 1 ≤ i ≤ I)
‹#›
110
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
Loop Invariant: s = 12 + 22 + 32 + … + i2 (0 ≤ i ≤ I)
Measure of Progress
i = # of objects added.
79 km
75 km
Exit
Exit
79 km
Step to make progress
i = i+1
Exit Condition
i = I
‹#›
111
Code from LI
In order to make progress,
we may head in one direction.
79 km
75 km
Exit
Step to make progress
i = i+1
‹#›
112
Code from LI
In order to make progress,
we may head in one direction.
79 km
75 km
Exit
Step to make progress
i = i+1
‹#›
113
Code from LI
In order to maintain the loop invariant,
we must adjust to come back to the path.
Exit
‹#›
114
Code from LI
This may be how we determine
the step in then next iteration.
‹#›
115
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
Loop Invariant: s = 12 + 22 + 32 + … + i2
Partial Step: i = i+1
¬
codeB
Maintaining Loop Invariant
Exit
Let it and st be the values of i and s at the beginning of the iteration and let it+1 and st+1 be their value value after going around again.
‹#›
116
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
Loop Invariant: s = 12 + 22 + 32 + … + i2
Partial Step: i = i+1
Use the fact that you
already have the LI true
and take a small step.
¬
codeB:
Make the loop Invariant true!!!
Solve the entire algorithm!!!
Panic!!
next
‹#›
117
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
Loop Invariant: s = 12 + 22 + 32 + … + i2
Partial Step: i = i+1
st = 12 + 22 + 32 + … + it2
it < I
it+1 = it + 1
st+1
=12 + 22 + 32 + … + it+12
¬
codeB:
(codeB in loop)
(math)
Write down LHS/RHS
of what we must prove
‹#›
118
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
Loop Invariant: s = 12 + 22 + 32 + … + i2
Partial Step: i = i+1
st = 12 + 22 + 32 + … + it2
it < I
it+1 = it + 1
st+1
=[12 + 22 + 32 + … + it2 ]+ it+12
=12 + 22 + 32 + … + it+12
= st + it+12
¬
codeB:
st+1 = st + it+12
‹#›
119
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
Loop Invariant: s = 12 + 22 + 32 + … + i2
Partial Step: i = i+1
s = s + i2
i = i + 1
it+1 = it + 1
st+1 = st + it+12
i = i + 1
s = s + i2
We now translate
this math code
‹#›
120
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
Loop Invariant: s = 12 + 22 + 32 + … + i2
Step: i = i+1, s = s + i2
codeC
Clean up loose ends
Exit
‹#›
121
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
Loop Invariant: s = 12 + 22 + 32 + … + i2
Step: i = i+1, s = s + i2
s = 12 + 22 + 32 + … + i2
?? What math condition do I need here ??
S =12 + 22 + 32 + … + I2
codeC:
?? What math relationship do I need here ??
‹#›
122
Code from LI
Precondition: The input is an integer I.
Postcondition: The output is S = 12 + 22 + 32 + … + I2
Loop Invariant: s = 12 + 22 + 32 + … + i2
Step: i = i+1, s = s + i2
s = 12 + 22 + 32 + … + i2
I need:
s=S
i=I
S =12 + 22 + 32 + … + I2
codeC:
s=S (math statement)
i=I (math statement)
S is our output
i is our measure of progress
‹#›
123
Code from LI
s=S (math statement)
i=I (math statement)
We now translate
this math code
loop
“loop-invariant”
exit when i=I
code
endloop
“i=I”
“postCond”
codeC:
What is a math assertion that we what to be true
when we exit?
What is the code to make this true?
I like while statements.
while( i≠I )
i
codeC:
while( i≠I )
i
codeA
Establishing Loop Invariant
i s
0
1
2
3
1+4+9=14
1+4=5
1
0
i = 0
s = 0
‹#›
126
Designing an Algorithm
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
127
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Pointers
‹#›
Designing an Algorithm
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
144
Different Representations
of Algorithms
Code
Running example
DFA and Turing Machines
Higher level abstract view
‹#›
145
Code
Representation of an Algorithm
class InsertionSortAlgorithm extends SortAlgorithm {
void sort(int a[]) throws Exception {
for (int i = 1; i < a.length; i++) {
int j = i;
int B = a[i];
while ((j > 0) && (a[j-1] > B)) {
a[j] = a[j-1];
j--; }
a[j] = B;
}}
Pros and Cons?
‹#›
146
Code
Representation of an Algorithm
Runs on computers
Precise and succinct
Perception that being able to code is the only thing needed to get a job. (false)
I am not a computer
I need a higher level of intuition.
Prone to bugs
Language dependent
Pros:
Cons:
‹#›
147
Running Example
Representation of an Algorithm
Try out a problem or
solution on small examples.
‹#›
148
Running Example
Representation of an Algorithm
88
14
98
25
62
52
79
30
23
31
14
88
98
‹#›
149
Running Example
Representation of an Algorithm
14,23,25,30,31,52,62,79,88,98
Pros and Cons?
‹#›
150
Running Example
Representation of an Algorithm
Concrete
Dynamic
Visual
Relies on you to find the pattern.
Does not explain why it works.
Demonstrates for only one of many inputs.
Pros:
Cons:
‹#›
151
DFA and Turing Machines
Representation of an Algorithm
Pros and Cons?
‹#›
152
DFA and Turing Machines
Representation of an Algorithm
Good for theorems about algorithms
Not good for designing algorithms
Pros:
Cons:
‹#›
153
Higher Level Abstract View
Representation of an Algorithm
i-1
i
i
i
0
T+1
‹#›
154
Levels of Abstraction
It is hard to think of love in terms of the firing of neurons.
vs
Software developers view subsystems as entities with separate personalities, roles, and interactions,
not details of code.
vs
‹#›
155
Higher Level Abstract View
Representation of an Algorithm
Intuitive for humans
Useful for
thinking about
designing
describing algorithms
View from which correctness is self evident.
Mathematical mumbo jumbo
Too abstract
Students resist it
Pros:
Cons:
Method of choice
‹#›
156
Abstract away the inessential features of a problem
=
Value Simplicity
Goal: Understand and think about complex algorithm in simple ways.
Don’t tune out. There are deep ideas within the simplicity.
‹#›
157
Simple Example
Insertion Sort Algorithm
‹#›
158
Reconsidering Simple Examples
A good martial arts student will attentively repeat each fundamental technique many times.
In contrast, many college students tune out when a concept (e.g., depth first search) is taught more than once.
The better students listen carefully in order to refine and develop their understanding.
Repetition Is An Opportunity
Rudich www.discretemath.com
‹#›
159
Code
Representation of an Algorithm
class InsertionSortAlgorithm extends SortAlgorithm {
void sort(int a[]) throws Exception {
for (int i = 1; i < a.length; i++) {
int j = i;
int B = a[i];
while ((j > 0) && (a[j-1] > B)) {
a[j] = a[j-1];
j--; }
a[j] = B;
}}
‹#›
160
Higher Level Abstract View
Representation of an Algorithm
9 km
5 km
‹#›
161
Designing an Algorithm
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
162
Problem Specification
Precondition: The input is a list of n values with the same value possibly repeated.
Post condition: The output is a list consisting of the same n values in non-decreasing order.
88
14
98
25
62
52
79
30
23
31
14,23,25,30,31,52,62,79,88,98
‹#›
163
“State” of computation determined by values of all variables.
Location of Computation
‹#›
164
Location of Computation
88
14
98
25
62
52
79
30
23
31
14,23,25,30,31,52,62,79,88,98
“State” of computation determined by values of all variables.
88
14<52
25<62
79<98
30
23
31
‹#›
165
88
14
98
25
62
52
79
30
23
31
14,23,25,30,31,52,62,79,88,98
23
Location too confusing for algorithm
Algorithm too lazy to define step for every location.
Computation Stuck
88
14<52
25<62
79<98
30
31
‹#›
166
Algorithm specifies from which locations it knows how to step.
Safe Locations
88
14
98
25
62
52
79
30
23
31
14,23,25,30,31,52,62,79,88,98
‹#›
167
88
14
98
25
62
52
79
30
23
31
14,23,25,30,31,52,62,79,88,98
14
98
25
62
79
30
23,31,52,88
Define Loop Invariant
Loop Invariant:
Input numbers split to left and right.
Numbers on left are sorted.
‹#›
168
14
98
25
62
79
30
23,31,52,88
23
98
25
88
31
30
14,52,62,79
Location Not Determined
Which subset of the elements are sorted, is not specified.
‹#›
169
Defining Measure of Progress
14
98
25
62
79
30
23,31,52,88
6 elements
‹#›
170
Define Step
98
25
62
79
23,31,52,88
14
30
‹#›
171
Define Step
Select arbitrary element from side.
Insert it where it belongs.
98
25
62
79
23,31,52,88
14
98
25
79
30
23,31,52,62,88
14
30
‹#›
172
Making progress while Maintaining the loop invariant
98
25
62
79
23,31,52,88
14
98
25
79
30
23,31,52,62,88
14
30
79 km
75 km
5 elements
6 elements
Exit
Sorted sub-list
‹#›
173
88
14
98
25
62
52
79
30
23
31
88
14
98
25
62
52
79
30
23
31
n elements
14,23,25,30,31,52,62,79,88,98
14,23,25,30,31,52,62,79,88,98
0 elements
Beginning &
Ending
Exit
0 km
Exit
‹#›
174
Running Time
Inserting an element into a list of size i
takes (i) time.
Total = 1+2+3+…+n
98
25
62
79
23,31,52,88
14
98
25
79
30
23,31,52,62,88
14
30
= ?
‹#›
175
1 2 . . . . . . . . n
= number of white dots
1
+
2
+
3
+
. . .
+
n-1
+
n
=
S
Adding Made Easy
‹#›
176
1
+
2
+
3
+
. . .
+
n-1
+
n
=
S
n
+
n-1
+
n-2
+
. . .
+
2
+
1
=
S
1 2 . . . . . . . . n
= number of yellow dots
n . . . . . . . 2 1
= number of white dots
Adding Made Easy
‹#›
177
1
+
2
+
3
+
. . .
+
n-1
+
n
=
S
n
+
n-1
+
n-2
+
. . .
+
2
+
1
=
S
= number of white dots
= number of yellow dots
n+1 n+1 n+1 n+1 n+1
n
n
n
n
n
n
= n(n+1) dots in the grid
2S dots
S =
n (n+1)
2
Adding Made Easy
‹#›
178
Adding Made Easy
‹#›
179
Adding Made Easy
‹#›
180
Running Time
Inserting an element into a list of size i
takes (i) time.
Total = 1+2+3+…+n
98
25
62
79
23,31,52,88
14
98
25
79
30
23,31,52,62,88
14
30
= (n2)
‹#›
181
Algorithm Definition Completed
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
182
Insertion Sort
as a Relay Race
88
14
98
25
62
52
79
30
23
31
‹#›
183
Establish Loop Invariant
from preconditions
0
23
88
14
98
25
62
52
79
30
31
‹#›
184
Maintaining Loop Invariant
1
88
14
98
25
62
52
79
30
23
31
‹#›
185
Maintaining Loop Invariant
i-1
i
88
14
98
25
62
52
79
30
23
31
‹#›
186
Maintaining Loop Invariant
i
88
14
98
25
62
52
79
30
23
31
‹#›
187
Maintaining Loop Invariant
i-1
i
14
98
25
62
52
79
30
23
31,88
‹#›
188
Maintaining Loop Invariant
14
98
25
62
52
79
30
23
31,88
i
‹#›
189
Maintaining Loop Invariant
i-1
i
14
98
62
52
79
30
23
25,31,88
‹#›
190
Maintaining Loop Invariant
i
14
98
62
52
79
30
23
25,31,88
‹#›
191
Maintaining Loop Invariant
i-1
i
14
98
62
79
30
23
25,31,52,88
‹#›
192
Maintaining Loop Invariant
T
14,23,25,30,31,52,62,79,88,98
‹#›
193
Clean up loose ends
T+1
14,23,25,30,31,52,62,79,88,98
‹#›
194
Ok
I know you knew Insertion Sort
But hopefully you are beginning to appreciate
Loop Invariants
for describing algorithms
‹#›
195
Explaining Insertion Sort
We maintain a subset of elements sorted within a list. The remaining elements are off to the side somewhere. Initially, think of the first element in the array as a sorted list of length one. One at a time, we take one of the elements that is off to the side and we insert it into the sorted list where it belongs. This gives a sorted list that is one element longer than it was before. When the last element has been inserted, the array is completely sorted.
But don’t do this.
I want separate paragraphs
for the separate steps.
‹#›
196
14
98
25
62
79
30
23,31,52,88
Loop Invariant:
Input numbers split to left and right.
Numbers on left are sorted.
Select the smallest
Insertion Sort
Selection
What changes?
This was on an exam and most got it
Action not picture
WRONG
‹#›
197
88
98
52
62
79
31
14,23,25,30
Loop Invariant:
Input numbers split to left and right.
Numbers on left are sorted.
All left ≤ All right
Insertion Sort
Selection
What changes?
This was on an exam and most got it
≤
WRONG
‹#›
198
Define Step
88
98
52
62
79
31
14,23,25,30
≤
‹#›
199
Define Step
88
98
52
62
79
31
14,23,25,30
≤
88
98
52
62
79
14,23,25,30,31
≤
Select the smallest on right
and put it at the end of the left.
‹#›
200
Maintaining Loop Invariant
88
98
52
62
79
31
14,23,25,30
≤
88
98
52
62
79
14,23,25,30,31
≤
¬
codeB
Exit
Numbers now on
left are sorted.
Numbers on
left were sorted.
New number added to end
came from right.
All left ≤ All right
‹#›
201
Maintaining Loop Invariant
88
98
52
62
79
31
14,23,25,30
≤
88
98
52
62
79
14,23,25,30,31
≤
¬
codeB
Exit
Now
All left ≤ All right
Was All left ≤ All right
New number is smallest
from right
‹#›
202
Don't Redo Work
Prefix Averages:
Input: an array X[i] of n values
Output: The average of each prefix
A[i] = (X[1] + X[2] + … + X[i])/i
for i = 1 to n do
% compute A[i]
s = 0
for j = 1 to i do
s = s + X[j]
A[i] = s / i
return A
Which line works the hardest?
# times it is executed
=1+2+3+….+n
= O(n2)
The other lines effect this time
by a multiplicative constant
or less
Time(n) = O(n2)
n n n n n
n
n
n
n
n
n
‹#›
X 21 23 25 31 20 18 16 A 21 22 23 25 24 23 22
Don't Redo Work
Prefix Averages:
Input: an array X[i] of n values
Output: The average of each prefix
A[i] = (X[1] + X[2] + … + X[i])/i
Make “progress”
Maintain second LI
Maintain first
i=0; s = 0;
loop
% LI:
% LI:
exit when i = n
i = i+1
s = s + X[i]
A[i] = s / i
return A
A[1], … , A[i] computed
s = X[1] + X[2] + … + X[i]
Establish LI
Exit Cond + LI Post Cond
‹#›
Don't Redo Work
Prefix Averages:
Input: an array X[i] of n values
Output: The average of each prefix
A[i] = (X[1] + X[2] + … + X[i])/i
i=0; s = 0;
loop
% LI:
% LI:
exit when i = n
i = i+1
s = s + X[i]
A[i] = s / i
return A
A[1], … , A[i] computed
s = X[1] + X[2] + … + X[i]
Which line works the hardest?
# times it is executed
= n
The other lines effect this time
by a multiplicative constant
or less
Time(n) = O(n)
(Linear is better than quadratic.)
‹#›
Designing an Algorithm
‹#›
206
A Starry Night
How did Van Gogh come up with his famous painting, A Starry Night?
There's no easy answer.
Designing algorithms is an art form.
‹#›
207
A Sequence of Actions
Max( a,b,c )
“preCond: Input has 3 numbers.”
if( b>m )
m = b
endif
“assert: m is max in {a}”
m = a
if( c>m )
m = c
endif
“assert: m is max in {a,b}”
“assert: m is max in {a,b,c}”
return(m)
“postCond:
return max in {a,b,c}”
vs
A Sequence of Assertions
It is helpful to have
different ways of
looking at it.
‹#›
208
Designing Loop Invariants
Coming up with the loop invariant is the hardest part of designing an algorithm.
It requires practice, perseverance, and insight.
Yet from it
the rest of the algorithm
follows easily
‹#›
209
Use This Process
Don't come up with the loop invariant after the fact to make me happy.
Use it to design your algorithm.
‹#›
210
Don’t start coding
You must design a working algorithm first.
‹#›
211
Exemplification:
Try solving the problem
on small input examples.
Rudich www.discretemath.com
‹#›
212
Start with Small Steps
What basic steps might you follow to make some kind of progress towards the answer?
Describe or draw a picture of what the data structure might look like after a number of these steps.
‹#›
213
Picture from the Middle
Leap into the middle of the algorithm.
What would you like your data structure to look like when you are half done?
‹#›
214
The Work Completed
The loop invariant should state what work has been completed towards solving the problem and what works still needs to be done.
79 km
75 km
‹#›
215
Flow Smoothly
The loop invariant should flow smoothly from the beginning to the end of the algorithm.
At the beginning, it should follow easily from the preconditions.
It should progress in small natural steps.
Once the exit condition has been met, the postconditions should easily follow.
‹#›
216
Ask for 100%
A good philosophy in life is to ask for 100% of what you want,
but not to assume that you will get it.
What would you like to be true in the middle of your computation?
‹#›
217
Ask for 100%
Pretend that a genie has granted your wish.
You are now in the middle of your computation and your dream loop invariant is true.
‹#›
218
Ask for 100%
Maintain the Loop Invariant:
From here, are you able to take some computational steps that will make progress while maintaining the loop invariant?
‹#›
219
Ask for 100%
If you can maintain the loop invariant, great.
If not,
Too Weak: If your loop invariant is too weak, then the genie has not provided you with everything you need to move on.
Too Strong: If your loop invariant is too strong, then you will not be able to establish it initially or maintain it.
‹#›
220
No Assumptions:
Suppose a Martian jumped
into the top of the loop.
All you would know is that was true.
It alone must provide enough information
so that, after going around the loop, you can establish that the loop invariant is again true.
‹#›
221
Know What a LI Is Not
``the LI is ...''
code
A precondition
A postcondition
A statement that is always true
Eg: “1+1=2”
The steps taken by the algorithm
‹#›
222
Differentiating between Iterations
x=x+2
Meaningful as code
False as a mathematical statement
x’ = xi = value at the beginning of the iteration
x” = xi+1 = new value after going around the loop one more time.
x” = x’+2
Meaningful as a mathematical statement
‹#›
223
Iterative Algorithms
Loop Invariants
Max( A )
“preCond:
Input is array A[1..n]
of n values.”
i = 1
m = A[1]
loop
“loop-invariant:
m is max in {A[1]..A[i]}”
exit when (i=n)
m = max(m,A[i+1])
i = i + 1
endloop
return(m)
“postCond:
m is max in {A[1]..A[n]}”
Step i
m = max(m,A[i+1])
m is max
in {A[1]..A[i]}
m is max
in {A[1]..A[i+1]}
¬
codeB
‹#›
224
codeC
Clean up loose ends
Exit
Trivially true because
=
NEVER DO THIS!
codeA
loop
exit when
codeB
codeC
Miracle
Same Miracle
‹#›
The difficulty becomes
proving that it exits.
codeA
loop
exit when
codeB
codeC
Miracle
Same Miracle
‹#›
Which of the steps
to develop an iterative
algorithm did the student
fail to do correctly?
Find Errors
‹#›
227
Fine: Describes input
and output.
If I = -5, s = 1-5 j =
0
Find Errors
‹#›
228
Fine: Purpose outlined
in LI
Variables need to
be documented.
Find Errors
‹#›
229
Loop Invariants are pictures
of current state.
Not actions!
Not algorithms!
Find Errors
‹#›
230
Fine: Shows a relationship
between the variables.
Find Errors
‹#›
231
Let s’ and i’ be
values of s and i
when at the top of the loop.
Let s” and i” be
values after going
around again.
Find Errors
‹#›
232
LI s’ = j=1i’ j.
Code s” = s’+i’
i” = i’+1.
Together:
s” = (j=1i’ j) + i’.
i’ is added in twice.
i” should be added.
Find Errors
‹#›
233
i = 1 j=1i j = 1 = s.
Find Errors
‹#›
234
Exit
Better to say:
loop
loop-invariant: _____
exit when i > I
exit when i>I
Find Errors
‹#›
235
LI s = j=1i j.
Exit i > I
Together:
s = j=1I+1 j.
Post Cond.
exit when i>I
Exit
Find Errors
‹#›
236
Test:
on typical value
i = 3 s=1+2+3.
on special values
i = 1 s=1.
i = 0 s=1.
exit when i>I
Find Errors
‹#›
237
Typical Types of Loop Invariants
Fairy God Mother
More of the input
More of the output
Narowing the search space
Shrinking Input Instance
Data Structure (System) Invariant
‹#›
238
Typical Types of Loop Invariants
Fairy God Mother
I have arrived from Mars, some amount of progress has been made already and my Fairy God Mother has set the state of the computation to be just what I want so that I feel as comfortable as I could be given the amount of progress that has been made.
More of the input
More of the output
Narowing the search space
Shrinking Input Instance
Data Structure (System) Invariant
‹#›
239
Fairy God Mother
Loop Invariants
I run infinitely faster than the monster.
so my only goal is to get to
shore without him there.
The only problem is that
he runs 4 times faster than I swim.
Me: Radius 1, speed 1, time 1.
Him: Half circ., speed 4, time = 3.14/4 < 1
He wins.
‹#›
240
Fairy God Mother
Loop Invariants
He runs back and forth to catch me.
And I change my direction to avoid him.
Can I get away?
‹#›
241
Fairy God Mother
Loop Invariants
My progress is the distance
swum from the center.
What is your wish?
It is my job to
establish
maintain
and get the post condition
from this loop invariant
‹#›
242
Moving to the center.
My goal now is not to escape or to make progress.
My only goal is to establish the loop invariant by ..?
Fairy God Mother
Loop Invariants
Your motto should be:
0 is a fine number and is a fine set.
‹#›
243
Fairy God Mother
Loop Invariants
My goal now is not to excape or to make progress.
My only goal is to maintain the loop invariant
by ..?
by moving opposite him in my circle.
But he moves 4 times faster!!!
So the circumference of your circle must be ¼ of his.
‹#›
244
Fairy God Mother
Loop Invariants
d
rd
1
r
rd < d/4
r < 1/4
But he moves 4 times faster!!!
So the circumference of your circle must be ¼ of his.
‹#›
245
Fairy God Mother
Loop Invariants
Hence, I can maintain the loop invariant,
by moving opposite him
If I am less than ¼ from the middle,
then I can swim my circle faster
than he can run his.
(Even though he runs 4 times faster.)
And can use my extra speed
to make progress outward.
‹#›
246
Fairy God Mother
Loop Invariants
Swim for it.
When I am ¼ from the middle,
I can no longer maintain the loop invariant.
Hence, I … ?
Me: ¾ radius, speed 1, time = ¾ = 0.75
Him: Half circ., speed 4, time = 3.14/4 = 0.78
I win!
‹#›
247
Typical Types of Loop Invariants
Fairy God Mother
More of the input
More of the output
Narowing the search space
Shrinking Input Instance
Data Structure (System) Invariant
‹#›
248
Extra
More of the Input
Loop Invariant
The input consists of an array of objects
We have read in the first i objects.
We will pretend that this prefix
is the entire input.
We have a solution for this prefix
plus some additional information
Solution
‹#›
249
Loop Invariants and
Deterministic Finite Automaton
L = {a Î {0,1}* | a has length at most three and the number of 1's is odd }.
‹#›
250
Extra
More of the Input
Loop Invariant
The input consists of an array of objects
Solution
Extra
Solution
We read in the i+1st object.
We will pretend that this larger prefix
is the entire input.
We extend the solution we have
to one for this larger prefix.
(plus some additional information)
‹#›
251
Extra
More of the Input
Loop Invariant
The input consists of an array of objects
Solution
Extra
Solution
79 km
75 km
Exit
i to i+1
‹#›
252
More of the Input
Loop Invariant
The input consists of an array of objects
In the end, we have read in the entire input.
The LI gives us that we have a solution
for this entire input.
Solution
Exit
‹#›
253
Insertion Sort
The input consists of an array of integers
We have read in the first i objects.
We will pretend that this prefix
is the entire input.
We have a solution for this prefix
Solution
52,23,88,31,25,30,98,62,14,79
23,31,52,88
‹#›
254
Insertion Sort
The input consists of an array of integers
52,23,88,31,25,30,98,62,14,79
23,31,52,88
We read in the i+1st object.
We will pretend that this larger prefix
is the entire input.
We extend the solution we have
to one for this larger prefix.
23,25,31,52,88
‹#›
255
More of the Input
Loop Invariant
The input consists of an array of objects
A student midterm answer:
Each iteration considers the next input item.
Loop Invariants are pictures
of current state.
Not actions!
Not algorithms!
‹#›
256
More of the Input
Loop Invariant
The input consists of an array of objects
A student midterm answer:
We have considered the ith input element.
What about elements [1...i]?
‹#›
257
More of the Input
Loop Invariant
The input consists of an array of objects
A student midterm answer:
We have considered input elements [1..i].
So?
‹#›
258
More of the Input
Loop Invariant
The input consists of an array of objects
We have read in the first i objects.
We have a solution for each.
Solution
A student midterm answer:
Each object does not need a separate solution
The input as a whole needs a solution.
‹#›
259
More of the Input
Loop Invariant
The input consists of an array of objects
A student midterm answer:
We have a solution for the
prefix consisting of elements [1..i].
(plus some additional information)
Solution
Extra
‹#›
260
Longest Block of Ones
Alg reads the digits one at a time
and remembers enough about what read
so that it does not need to reread anything.
(i.e. a DFA)
00101111001100011111000011001
‹#›
261
Longest Block of Ones
00101111001100011
When it has read this much,
what does it remember?
Largest block so far.
1
1
1
Read the next character &
re-determine the largest block so far.
‹#›
262
Longest Block of Ones
00101111001100011
When it has read this much,
what does it remember?
Largest block so far.
1
1
1
Read the next character &
re-determine the largest block so far
& current largest.
Size of current block.
‹#›
263
Typical Types of Loop Invariants
Fairy God Mother
More of the input
More of the output
Narowing the search space
Shrinking Input Instance
Data Structure (System) Invariant
‹#›
264
More of the Output
Loop Invariant
The output consists of an array of objects
I have produced the first i objects.
Produce the i+1st output object.
Exit
79 km
75 km
Exit
i to i+1
Done when
output n objects.
‹#›
265
Selection Sort
The output consists of an array of integers
52,23,88,31,25,30,98,62,14,79
14,23,25,30,31,52,62,79,88,98
Input:
I have produced the first i objects.
Produce the i+1st output object.
Exit
Done when
output n objects.
‹#›
266
More of the Input/Output
Loop Invariant
The input consists of a set of objects
The output consists of a set of objects
Some i of the inputs have been handled.
We still have the precondition
on the input objects not yet handled.
We have produced some i of the output.
We have the post condition
on the output objects produced.
‹#›
267
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
More of the output?
With out falling
How far over can you shift it go over?
‹#›
268
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
More of the output:
I have produced the first i-1 objects.
But if I keep adding blocks
it will falling
Is this a proof that
it is not possible?
Try again
‹#›
269
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
More of the output:
I have produced the last i-1 objects.
Extra info:
Center of mass is within bottom block
Leaning distance so far
Where should we
put the next block?
it will falling
‹#›
270
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
More of the output:
I have produced the last i-1 objects.
Extra info:
Center of mass is within bottom block
Leaning distance so far
Where should we
put the next block?
it will falling
‹#›
271
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
More of the output:
I have produced the last i-1 objects.
Extra info:
Center of mass is within bottom block
Leaning distance so far
Where should we
put the next block?
No progress
‹#›
272
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
More of the output:
I have produced the last i-1 objects.
Extra info:
Center of mass is within bottom block
Leaning distance so far
Where should we
put the next block?
With the center of mass
of the above blocks
teetering on the edge
of supporting block.
‹#›
273
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
More of the output:
I have produced the last i-1 objects.
Extra info:
Center of mass is within bottom block
Leaning distance so far
Where is the new
center of mass?
‹#›
274
Leaning Tower
Where is the new
center of mass?
Mass = m2
Mass = m1
Center of mass = r1
Center of mass = r2
Center of mass
(Ignoring veridical)
‹#›
275
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
Where is the new
center of mass?
Center of mass = r1
Center of mass = r2
Center of mass
Mass = m1
= 1
= 1
To make the math easier,
lets call this zero.
mass2
mass1
Mass = m2
= i-1
= 0
Center of mass is 1/i from
right edge of ith block.
‹#›
276
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
I have produced the last i-1 objects.
More of the output:
Extra info:
Center of mass is 1/i from
right edge of ith block.
Leaning distance so far?
Add the next block.
1/i
1
‹#›
277
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
1/i
1
https://www.youtube.com/watch?v=pBYPXsGka74&feature=youtu.be
‹#›
278
Leaning Tower
Output: Stack them leaning as far over as possible.
Input: Lots of 2in wide blocks
https://www.youtube.com/watch?v=pBYPXsGka74&feature=youtu.be
‹#›
279
Typical Types of Loop Invariants
Fairy God Mother
More of the input
More of the output
Narowing the search space
Shrinking Input Instance
Data Structure (System) Invariant
Three
Binary Search like
examples
‹#›
280
Typical Types of Loop Invariants
Fairy God Mother
More of the input
More of the output
Narowing the search space
Shrinking Input Instance
Data Structure (System) Invariant
Three
Binary Search like
examples
‹#›
281
Define Problem: Binary Search
PreConditions
Key 25
Sorted List
PostConditions
Find key in list (if there).
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
‹#›
282
Define Loop Invariant
Maintain a sub-list
Such that
key 25
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
‹#›
283
Define Loop Invariant
Maintain a sub-list.
If the key is contained in the original list, then the key is contained in the sub-list.
key 25
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
‹#›
284
Define Step
Make Progress
Maintain Loop Invariant
key 25
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
‹#›
285
Define Step
Cut sub-list in half.
Determine which half the key would be in.
Keep that half.
key 25
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
‹#›
286
Define Step
Cut sub-list in half.
Determine which half the key would be in.
Keep that half.
key 25
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
If key ≤ mid,
then key is in
left half.
If key > mid,
then key is in
right half.
‹#›
287
Define Step
It is faster not to check if the middle element is the key.
Simply continue.
key 43
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
If key ≤ mid,
then key is in
left half.
If key > mid,
then key is in
right half.
‹#›
288
Make Progress
The size of the list becomes smaller.
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
79 km
75 km
79 km
75 km
Exit
‹#›
289
Initial Conditions
key 25
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
If the key is contained in the original list,
then the key is contained in the sub-list.
The sub-list is the entire original list.
n km
‹#›
290
Ending Algorithm
If the key is contained in the original list,
then the key is contained in the sub-list.
Sub-list contains one element.
Exit
Exit
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
0 km
If the key is contained in the original list,
then the key is at this location.
key 25
Check this location.
If it’s the key, then you have found it.
If it’s not, then
it was not in the original list.
‹#›
291
Running Time
The sub-list is of size n, n/2, n/4, n/8,…,1
Each step (1) time.
Total = (log n)
key 25
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
If key ≤ mid,
then key is in
left half.
If key > mid,
then key is in
right half.
‹#›
292
Code
‹#›
293
Algorithm Definition Completed
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
294
Study:
Many experienced programmers were asked to code up binary search.
80% got it wrong
Good thing is was not for a nuclear power plant.
‹#›
295
Make Precise Definitions
Maintain a sub-list with end points i & j.
key 25
i
j
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
‹#›
296
Make Precise Definitions
Maintain a sub-list with end points i & j.
key 25
i
j
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
Does not matter which,
but you need to be consistent.
‹#›
297
If the sub-list has even length,
which element is taken to be mid?
key 25
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
Make Precise Definitions
‹#›
298
If the sub-list has even length,
which element is taken to be mid?
key 25
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
Should not matter
Choose right.
Make Precise Definitions
mid
‹#›
299
Common Bugs
Cut sub-list in half.
Determine which half the key would be in.
Keep that half.
key 25
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
If key ≤ mid,
then key is in
left half.
If key > mid,
then key is in
right half.
‹#›
Common Bugs
If the middle element is the key,
it can be skipped over.
key 43
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
If key ≤ mid,
then key is in
left half.
If key > mid,
then key is in
right half.
Exit
‹#›
Common Bugs
Fix the bug.
key 43
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
If key ≤ mid,
then key is in
left half.
If key > mid,
then key is in
right half.
‹#›
Common Bugs
Second fix,
by making the left half slightly bigger.
key 43
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
If key ≤ mid,
then key is in
left half.
If key > mid,
then key is in
right half.
New bug?
‹#›
Common Bugs
Second fix,
by making the left half slightly bigger.
key 43
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
New bug?
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
No progress is made.
Loop for ever!
79 km
75 km
Exit
‹#›
Why is Binary Search so Easy to Get Wrong?
1
2
How many possible algorithms?
How many correct algorithms?
Probability of success by guessing?
3
i = mid
else
j = mid -1
i = mid + 1
else
j = mid
‹#›
Moral
Use the loop invariant method to think about algorithms.
Be careful with your definitions.
Be sure that the loop invariant is always maintained.
Be sure progress is always made.
‹#›
Loop Invariants
for
Iterative Algorithms
A second
Binary Search like
example
‹#›
38
25
17
4
21
31
28
35
51
42
40
49
63
55
71
Binary Search Tree
Key 17
A binary search tree.
Find key in BST (if there).
key 17?
‹#›
38
25
17
4
21
31
28
35
51
42
40
49
63
55
71
Binary Search Tree
≤
≤
Its left children ≤ Any node ≤ Its right children
Data Structure Invariant
key 17?
‹#›
38
25
17
4
21
31
28
35
51
42
40
49
63
55
71
Binary Search Tree
≤
≤
We have maintained a sub-tree.
If the key is contained in the original tree,
then the key is contained in this sub-tree.
Search Loop Invariant
key 17?
‹#›
Cut sub-tree in half.
Determine which half the key would be in.
Keep that half.
38
25
17
4
21
31
28
35
51
42
40
49
63
55
71
If key < root,
then key is
in left half.
If key > root,
then key is
in right half.
If key = root,
then key is
found
Binary Search Tree
≤
≤
key 17?
‹#›
38
25
17
4
21
31
28
35
51
42
40
49
63
55
71
Binary Search Tree
key 17?
We have maintained a sub-tree.
If the key is contained in the original tree,
then the key is contained in this sub-tree.
Search Loop Invariant
‹#›
Algorithm Definition Completed
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
Loop Invariants
for
Iterative Algorithms
A third
Binary Search like
example
‹#›
A volunteer, please.
Card Trick
‹#›
Pick a Card
Done
‹#›
Loop Invariant:
The selected card is one of these.
‹#›
Which column?
left
‹#›
Loop Invariant:
The selected card is one of these.
‹#›
Selected column is placed
in the middle.
‹#›
I will rearrange the cards.
‹#›
Relax Loop Invariant:
I will remember the same about each column.
‹#›
Which column?
right
‹#›
Loop Invariant:
The selected card is one of these.
‹#›
Selected column is placed
in the middle.
‹#›
I will rearrange the cards.
‹#›
Which column?
left
‹#›
Loop Invariant:
The selected card is one of these.
‹#›
Selected column is placed
in the middle.
‹#›
Here is your card.
Wow!
‹#›
The “Partitioning” Problem
(used in quicksort)
88
14
98
25
62
52
79
30
23
31
p=52
14
25
30
23
31
88
98
62
79
≤ 52 ≤
Input:
Output:
‹#›
Define Loop Invariant
or
31 23 25 98 30 14 62 79 88
p=52
≤ p
p ≤
31 23 71 25 98 30 62 79 88
p=52
≤ p
p ≤
‹#›
Defining Measure of Progress
4 elements
not
looked at
31 23 25 98 30 14 62 79 88
p=52
‹#›
Define Step
Make Progress
Maintain Loop Invariant
31 23 25 98 30 14 62 79 88
p=52
≤ p
p ≤
‹#›
Define Step
Make Progress
Maintain Loop Invariant
31 23 25 98 30 14 62 79 88
p=52
≤ p
p ≤
31 23 14 25 98 30 62 79 88
p=52
≤ p
p ≤
‹#›
Define Step
31 23 25 98 30 14 62 79 88
p=52
31 23 14 25 98 30 62 79 88
Four cases
31 23 14 25 98 30 62 79 88
p=52
31 23 14 25 98 30 62 79 88
31 23 25 98 30 71 62 79 88
p=52
31 23 25 98 30 71 62 79 88
31 23 71 25 98 30 62 79 88
p=52
31 23 25 98 30 71 62 79 88
‹#›
88
14
98
25
62
52
79
30
23
31
Beginning &
Ending
Exit
0 km
Exit
p=52
88 25 31 98 62 14 30 79 23
23 30 25 31 14 62 98 79 88
p=52
25
30
31
14
23
62
79
98
88
≤ 52 ≤
n-1 elements
not
looked at
0 elements
not
looked at
p=52
‹#›
Running Time
Each iteration takes (1) time.
Total = (n)
31 23 25 98 30 14 62 79 88
p=52
≤ p
p ≤
31 23 14 25 98 30 62 79 88
p=52
≤ p
p ≤
‹#›
Algorithm Definition Completed
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
23
79
30
14
62
98
52
25
88
31
p=52
23
79
30
14
62
98
31
25
88
79
30
14
62
98
31
25
88
23
88
79
30
14
62
98
31
25
23
88
79
30
14
62
98
31
25
23
88
79
14
62
98
31
25
30
23
88
79
14
62
98
31
25
30
23
88
79
14
62
98
31
25
30
23
88
79
98
14
62
31
25
30
23
88
79
98
62
14
31
25
30
23
88
79
98
62
14
31
25
30
23
Tracing an Example
‹#›
340
Typical Types of Loop Invariants
Fairy God Mother
More of the input
More of the output
Narowing the search space
Shrinking Input Instance
An instance has been produced that is smaller than the actual instance and these two instances require the same output. Hence, it is sufficient for me to forget about the actual instance and simply give the output for the new smaller one.
Data Structure (System) Invariant
‹#›
341
GCD(a,b)
= 4
Input:
Output: GCD(a,b)
= <64,44>
Maintain values such that
GCD(a,b) = GCD(x,y)
GCD(a,b) = GCD(a-b,b)
GCD(64,44) = GCD(20,44) = 4
Greatest Common Divisors
Let xt and yt be the values of x and y at the beginning of the iteration and let xt+1 and
yt+1 be their value after going around again.
‹#›
342
GCD(a,b)
= 4
Input:
Output: GCD(a,b)
= <64,44>
Maintain values such that
GCD(a,b) = GCD(x,y)
GCD(a,b) = GCD(a-b,b)
GCD(64,44) = GCD(20,44) = 4
Greatest Common Divisors
¬
codeB:
GCD(a,b) = GCD(xt,yt)
xt+1 = xt-yt , yt+1 = yt
GCD(a,b) = GCD(xt,yt) = GCD(xt-yt,yt) = GCD(xt+1,yt+1)
‹#›
343
GCD(a,b)
Input:
= 4
Output: GCD(a,b)
= <64,44>
Maintain values such that
GCD(a,b) = GCD(x,y)
GCD(a,b) = GCD(a-b,b)
GCD(64,44) = GCD(20,44) = 4
Greatest Common Divisors
xt+1 = xt-yt
codeB:
79 km
75 km
Exit
x is smaller
‹#›
344
GCD(a,b)
Input:
= <64,44>
= <64,44>
= <44,20>
= <24,20>
= < 4,20>
= <20, 4>
= <16, 4>
= <12, 4>
= < 8, 4>
= < 4, 4>
= < 0, 4>
GCD(a,b) = GCD(x,y) = 4
Running time?
= <20,44>
GCD(a,b) = GCD(x,y)
‹#›
345
GCD(a,b)
Input:
= <9999999999999,2>
= <9999999999999,2>
= <9999999999997,2>
= <9999999999995,2>
= <9999999999993,2>
= <9999999999991,2>
Time =
Poly Time?
O(a)
‹#›
346
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
n2
Grade School vs Kindergarten
a × b = a + a + a + ... + a
b
Running Time
T(n) = Time multiply
= θ(b) = linear time.
T(n) = Time multiply
= θ(n2) = quadratic time.
Which is faster?
92834765225674897 × 83883977590110394875
Which would you use?
Minutes?
Add a digit?
9
Exponential?
Centuries?
‹#›
347
Specifies how the running time
depends on the size of the input.
The Time Complexity of an Algorithm
“size” of input
“time” T(n) executed .
Work for me to
give you the instance.
Work for you to
solve it.
A function mapping
Work for you to
read the instance.
‹#›
348
83920
Size of Input Instance
‹#›
349
Size of Input Instance
Size of paper
# of bits
# of digits
Value
- n = 2 in2
- n = 17 bits
- n = 5 digits
- n = 83920
2’’
83920
5
1’’
Which are reasonable?
‹#›
350
Size of Input Instance
Size of paper
# of bits
# of digits
Value
- n = 2 in2
- n = 17 bits
- n = 5 digits
- n = 83920
Intuitive
2’’
83920
5
1’’
‹#›
351
Size of Input Instance
Size of paper
# of bits
# of digits
Value
- n = 2 in2
- n = 17 bits
- n = 5 digits
- n = 83920
Intuitive
Formal
2’’
83920
5
1’’
‹#›
352
Size of Input Instance
Size of paper
# of bits
# of digits
Value
- n = 2 in2
- n = 17 bits
- n = 5 digits
- n = 83920
Intuitive
Formal
Reasonable
# of bits =
3.32 * # of digits
2’’
83920
5
1’’
‹#›
353
Size of Input Instance
Size of paper
# of bits
# of digits
Value
- n = 2 in2
- n = 17 bits
- n = 5 digits
- n = 83920
Intuitive
Formal
Reasonable
Unreasonable
# of bits = log2(Value) Value = 2# of bits
2’’
83920
5
1’’
‹#›
354
Specifies how the running time
depends on the size of the input.
The Time Complexity of an Algorithm
“size” of input
“time” T(n) executed .
Work for you to
read the instance.
Work for you to
solve it.
A function mapping
Work for me to
give you the instance.
‹#›
355
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
n2
Grade School vs Kindergarten
a × b = a + a + a + ... + a
b
Running Time
T(n) = Time multiply
= θ(b) = linear time.
T(n) = Time multiply
= θ(n2) = quadratic time.
Which is faster?
92834765225674897 × 8388397759011039475
n = # digits = 20
Time ≈ 202 ≈ 400
b = value = 8388397759011039475
Time ≈ 8388397759011039475
‹#›
356
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
n2
Grade School vs Kindergarten
a × b = a + a + a + ... + a
b
Running Time
T(n) = Time multiply
= θ(b) = linear time.
T(n) = Time multiply
= θ(n2) = quadratic time.
Which is faster?
92834765225674897 × 8388397759011039475
n = # digits = 20
Time ≈ 202 ≈ 400
b = value
≈ 10n
Time ≈ 10n ≈ exponential!!!
‹#›
357
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
n2
Grade School vs Kindergarten
a × b = a + a + a + ... + a
b
Running Time
T(n) = Time multiply
= θ(b) = linear time.
T(n) = Time multiply
= θ(n2) = quadratic time.
Which is faster?
92834765225674897 × 8388397759011039475
n = # digits = 20
Time ≈ 202 ≈ 400
Adding a single digit
multiplies the time by 10!
9
‹#›
358
Grade School Addition: Linear time
Grade School Multiplication: Quadratic time
For big inputs, n << n2 << 2n
input size
t
ime
Oops this was worse!
Kindergarten Multiplication: Exponential time
Fast Fourier Transform: O(n logn) time
‹#›
359
Cryptography
n = # of bits vs N = value
Confused. Lets try again.
By considering
on line banking.
‹#›
360
I set up my banking password as follows.
wolframalpha:
next prime 90843823823904
gives p = 90843823823947
next prime 38475756939837
gives q = 38475756939857
I randomly choose two n digit primes
Cryptography
n = # of bits vs N = value
‹#›
361
I set up my banking password as follows.
p = 90843823823947 and q = 38475756939857
I randomly choose two n digit primes
Cryptography
n = # of bits vs N = value
I multiply N = pq = 3495284884937375456635355579
Time =
I make this product N public.
The pq factoring is my password.
n= 14
O(n2)
142 = 196.
‹#›
362
I know his public product
N = pq = 3495284884937375456635355579
Cryptography
n = # of bits vs N = value
I simply factor to find pq.
Then I can steal his money.
O(N)
= O(1028) = O(10n) = exponential time.
loop p = 2..N
check if N/p
Time =
No problem this is linear time.
n= 28
Linear in the value N
not the number of digits n
‹#›
363
Cryptography
n = # of bits vs N = value
Linear in the value N
not the number of digits n
Work for me to
give you the instance.
Work for you to
solve it.
Time complexity is a function
N = 3495284884937375456635355579
n= 28
n= 28
Time = 1028
>> Age of universe
‹#›
364
Is this Silly?
n = # of bits vs N = value
I know other professors
would give this answer.
Silly(N)
loop i = 1..N
Print( “HI”)
Time = O(N)
Size = n = O(log(N))
N = 2O(n)
= 2O(n)
But I insist on a different answer!
‹#›
365
Is this Silly?
n = # of bits vs N = value
If N is one 32-bit integer,
then N≤231
Silly(N)
loop i = 1..N
Print( “HI”)
Time = O(N)
Size = n = O(log(N))
N = 2O(n)
= 2O(n)
= O(1)
‹#›
366
Is this Silly?
n = # of bits vs N = value
If N is stored in n
32-bit integers
Time = O(N)
Size = n = O(log(N))
N = 2O(n)
Silly(x0,x1,x2,…, xn-1)
N = Σi=0..n-1 xi (232)i
loop i = 1..N
Print( “HI”)
Time = O(n)
Size = n
Silly(x0,x1,x2,…, xn-1)
loop i = 1..n
Print( “HI”)
Clearly Exponential!
Clearly
Linear!
Silly(N)
loop i = 1..N
Print( “HI”)
‹#›
367
Specifies how the running time
depends on the size of the input.
The Time Complexity of an Algorithm
“size” of input
“time” T(n) executed .
Work for you to
read the instance.
Work for you to
solve it.
A function mapping
Work for me to
give you the instance.
‹#›
368
The Time Complexity of an Algorithm
Size of Input N,M x1,x2,…, xN
Time
for xy
log2N +log2M
N log2x
log10N +log10M
N log10x
2
N
N
(log2x)2 bit ops
(log10x)2 char ops
formal
1 value op
formal
formal
same
same
# bits
# digits
# values
values
hastel
hastel
too small
too big
standard
standard
n
O(n2)
n
O(n2)
same
n
O(1)
‹#›
369
The Time Complexity of an Algorithm
Size of Input N,M x1,x2,…, xN
Time
for xy
log2N +log2M
N
(log2x)2 bit ops
formal
1 value op
formal
# bits
# values
n
O(n2)
standard
standard
n
O(1)
‹#›
370
GCD(a,b)
Input:
= <9999999999999,2>
= <9999999999999,2>
= <9999999999997,2>
= <9999999999995,2>
= <9999999999993,2>
= <9999999999991,2>
Work for me to
give you the instance.
Work for you to
solve it.
n= 13
a = 9999999999999
n= 13
‹#›
371
GCD(a,b)
Input:
= <9999999999999,2>
= <9999999999999,2>
= <9999999999997,2>
= <9999999999995,2>
= <9999999999993,2>
= <9999999999991,2>
Time =
Size =
O(a)
number of digits n
= 2O(n)
= O(log(a))
‹#›
372
GCD(a,b)
Speedup
=
smaller than y
‹#›
373
GCD(a,b)
Input:
= <44,64>
= <44,64>
= <64,44>
= <44,20>
= <20, 4>
= < 4, 0>
GCD(a,b) = GCD(x,y) = 4
GCD(a,b) = GCD(x,y)
‹#›
374
GCD(a,b)
Input:
= <10000000000001,9999999999999>
= <2,1>
= <1,0>
O(log(a)+log(b))
Time =
Size =
n = O(log(a)+log(b))
= O(n)
= <9999999999999,2>
GCD(a,b) = GCD(x,y) = 1
= <10000000000001,9999999999999>
Little progress
Lots of progress
Every two iterations:
the value x decreases by at least a factor of 2.
the size of x decreases by at least one bit
Lots of progress
‹#›
375
GCD(a,b)
‹#›
376
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Elementary School Algorithm: XY = Y+Y+Y+…+Y
s=0
for( i=1..X )
s = s+Y
return(s)
What is the loop invariant?
What relationship
do you want maintain
between the data items
X,Y,i,s?
s=iY
‹#›
377
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Elementary School Algorithm: XY = Y+Y+Y+…+Y
s=0
for( i=1..X )
s = s+Y
return(s)
Great, but lets try a Shrinking
Input Instance Loop invariant.
An instance has been produced that is smaller than the actual instance and these two instances require the same output.
‹#›
378
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Elementary School Algorithm: XY = Y+Y+Y+…+Y
s=0
x=X, y=Y
loop
exit when x=0
x = x-1
s = s+Y
return(s)
Great, but lets try a Shrinking
Input Instance Loop invariant.
An instance has been produced that is smaller than the actual instance and these two instances require the same output.
What is the maintained
relationship between X,Y,x,s?
XY = xy
+ s
x = X-i,
y = Y
s = iY
= (X-x)Y
= XY - xy
‹#›
379
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
Forget the algorithm.
Lets develop it using the steps.
‹#›
380
Multiplying
codeA
Establishing Loop Invariant
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
x=X, y=Y
s=0
With the minimal work possible
‹#›
381
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
Measure of Progress
x.
79 km
75 km
Exit
Exit
79 km
Step to make progress
x = x-1
Exit Condition
x = 0
‹#›
382
Multiplying
codeC
Clean up loose ends
Exit
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
‹#›
383
Multiplying
XY = xy + s
x = 0
Return( s )
Return( XY )
codeC:
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
= s
‹#›
384
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
¬
codeB
Maintaining Loop Invariant
Exit
79 km
75 km
Exit
Step to make progress
x = x-1
‹#›
385
Multiplying
In order to make progress,
we may head in one direction.
79 km
75 km
Exit
Step to make progress
x = x-1
‹#›
386
Multiplying
In order to make progress,
we may head in one direction.
79 km
75 km
Exit
Step to make progress
x = x-1
‹#›
387
Multiplying
In order to maintain the loop invariant,
we must adjust to come back to the path.
Exit
‹#›
388
Multiplying
This may be how we determine
the step in then next iteration.
‹#›
389
Multiplying
¬
codeB
Maintaining Loop Invariant
Exit
Let xt, yt, and st be the values of x, y, and s at the beginning of the iteration and let xt+1, yt+1, and st+1 be their value after going around again.
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
‹#›
390
Use the fact that you
already have the LI true
and take a small step.
Make the loop Invariant true!!!
Solve the entire algorithm!!!
Panic!!
next
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
¬
codeB:
Exit
‹#›
391
Multiplying
XY = xtyt + st
xt > 0
xt+1 =
XY
= xt+1yt+1 + st+1
¬
codeB:
st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
(st ?)
xt - 1
Write down LHS/RHS
of what we must prove
Exit
‹#›
392
Multiplying
XY = xtyt + st
xt > 0
xt+1 =
XY
= (xt -1)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st
¬
codeB:
st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
(st ?)
xt - 1
Use the LI
Plug in new values.
Exit
‹#›
393
Multiplying
XY = xtyt + st
xt > 0
xt+1 =
XY
= xtyt – yt + (st ?)
= (xt -1)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st
¬
codeB:
st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
xt - 1
Rearrange
(st ?)
Exit
‹#›
394
Multiplying
XY = xtyt + st
xt > 0
xt+1 =
XY
= xtyt – yt +
= (xt -1)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st
¬
codeB:
st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
st + yt
xt - 1
(st + yt)
Exit
‹#›
395
Multiplying
XY
= xtyt – yt +
= (xt -1)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
st
Y
X
yt
xt
=
1
st
yt
xt -1
=
yt
st+1
yt
xt+1
=
Exit
(st + yt)
‹#›
396
Designing an Algorithm
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
397
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Elementary School Algorithm: XY = Y+Y+Y+…+Y
s=0
x=X, y=Y
loop
exit when x=0
x = x-1
s = s+Y
return(s)
Time =
Linear Time?
O(X)
‹#›
398
Size of Input Instance
Size of paper
# of bits
# of digits
Value
- n = 2 in2
- n = 17 bits
- n = 5 digits
- n = 83920
Intuitive
Formal
Reasonable
Unreasonable
# of bits = log2(Value) Value = 2# of bits
2’’
83920
5
1’’
‹#›
399
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Elementary School Algorithm: XY = Y+Y+Y+…+Y
s=0
x=X, y=Y
loop
exit when x=0
x = x-1
s = s+Y
return(s)
Time =
O(X)
Size =
number of digits n
= 2O(n)
= O(log(X))
‹#›
400
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Elementary School Algorithm: XY = Y+Y+Y+…+Y
s=0
x=X, y=Y
loop
exit when x=0
x = x-1
s = s+Y
return(s)
We need to make X smaller faster!
x/2
‹#›
401
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
¬
codeB
Maintaining Loop Invariant
Exit
79 km
75 km
Exit
Step to make progress
x = x/2
‹#›
402
Multiplying
XY = xtyt + st
xt > 0
xt+1 =
¬
codeB:
st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
(yt ?)
(st ?)
xt /2
XY
= (xt /2)(yt ?)+ (st ?)
= xt+1yt+1 + st+1
= xtyt + st
Use the LI
Plug in new values.
Exit
‹#›
403
Multiplying
XY = xtyt + st
xt > 0
xt+1 =
¬
codeB:
st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt2
(st ?)
xt /2
XY
= (xt /2) + (st ?)
= xt+1yt+1 + st+1
= xtyt + st
(yt2)
Exit
‹#›
404
Multiplying
XY = xtyt + st
xt > 0
xt+1 =
¬
codeB:
st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt2
st
xt /2
XY
= (xt /2) +
= xt+1yt+1 + st+1
= xtyt + st
(yt2)
st
Exit
‹#›
405
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
XY
= (xt /2) +
= xt+1yt+1 + st+1
= xtyt + st
(yt2)
st
st
Y
X
yt
xt
=
½
st
yt
xt /2
=
st+1
yt+1
xt+1
=
Exit
‹#›
406
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Ethiopian Algorithm (Practice Test 1):
s=0
x=X, y=Y
loop
exit when x=0
if(x is even)
x = x/2, y=2y
else
x = x-1, s = s+Y
return(s)
Time =
O(log(X))
Size =
number of digits n
= O(n)
= O(log(X)+log(Y)
“Lots” of progress because
x becomes even!
“Lots” of progress because
x loses a bit!
‹#›
407
Multiplying
‹#›
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Allowed Operations of limited machine:
Adding: a+b
Doubling: a+a
Comparisons: if( a 0
xt+1 =
¬
codeB:
st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
(st ?)
xt - ut
XY
= (xt -ut)yt + (st ?)
= xt+1yt+1 + st+1
Use the LI
Plug in new values.
= xtyt + st
Exit
‹#›
411
Multiplying
XY = xtyt + st
xt > 0
xt+1 =
¬
codeB:
st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
(st ?)
xt - ut
XY
= xtyt – utyt + (st ?)
= (xt -ut)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st
Rearrange
Exit
‹#›
412
Multiplying
XY = xtyt + st
xt > 0
xt+1 =
¬
codeB:
st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
xt - ut
XY
= xtyt – utyt +
= (xt -ut)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st
st + vt, vt = utY
(st+utY)
Exit
‹#›
413
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
XY
= xtyt – utyt +
= (xt -ut)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st
st
Y
X
yt
xt
=
ut
st
yt
xt -ut
=
ut yt
st+1
yt
xt+1
=
Exit
‹#›
414
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Faster Algorithm:
s=0
x=X, y=Y
loop
exit when x=0
x = x-u[i]
s = s+v[i] with v[i] = u[i]Y
return(s)
Where u[i] is as large as possible.
How can we produce these u[i] and v[i] = u[i]Y?
‹#›
415
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Allowed Operations of limited machine:
Adding: a+b
Doubling: a+a
Comparisons: if( ax
1
Y
What is the loop invariant?
u[i] =
v[i] =
2iY
2i
v[i-1]+v[i-1]
u[i] will be subtracted from X.
‹#›
417
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Faster Algorithm:
u[i] = 2i, v[i] = 2iY, i = 0..?
s=0
x=X, y=Y
i =
loop
exit when x=0
while( x < u[i] ) i=i-1
x = x-u[i]
s = s+v[i]
return(s)
the last value in producing u[i]
But we don’t want x
to become negative.
‹#›
418
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Faster Algorithm:
u[i] = 2i, v[i] = 2iY, i = 0..?
s=0
x=X, y=Y
i =
loop
exit when x=0
while( x < u[i] ) i=i-1
x = x-u[i]
s = s+v[i]
return(s)
the last value in producing u[i]
Actually we will see that
u[i] gets used once if the ith bit of x is 1
and zero times if its is 0.
‹#›
419
Multiplying
Actually we will see that
u[i] gets used once if the ith bit of x is 1
and zero times if its is 0.
x = 10101102
u[0] = 12
u[1] = 102
u[2] = 1002
u[7] = 100000002
x3 = 1102
‹#›
420
Loop Invariants given in Practice Test:
LI0: u[i] = 2i, v[i] = 2iY, i = 0..?
LI1: X × Y = x × Y + s
LI2: x ≥ 0
LI3: x < 2i = u[i]
Progress: i = i-1
Multiplying
¬
codeB
Maintaining Loop Invariant
Exit
79 km
75 km
Exit
Step to make progress
i = i-1
‹#›
Multiplying
In order to make progress,
we may head in one direction.
79 km
75 km
Exit
Step to make progress
i = i-1
‹#›
422
Multiplying
In order to make progress,
we may head in one direction.
79 km
75 km
Exit
Step to make progress
i = i-1
‹#›
423
Multiplying
In order to maintain the loop invariant,
we must adjust to come back to the path.
Exit
‹#›
424
Multiplying
This may be how we determine
the step in then next iteration.
‹#›
425
Loop Invariants given in Practice Test:
LI0: u[i] = 2i, v[i] = 2iY, i = 0..?
LI1: X × Y = x × Y + s
LI2: x ≥ 0
LI3: x < 2i = u[i]
Multiplying
¬
codeB
Maintaining Loop Invariant
Exit
Let xt, st, and it be the values of x, s, and i at the beginning of the iteration and let xt+1, st+1, and it+1 be their value after going around again.
Exit
‹#›
Loop Invariants given in Practice Test:
LI0: u[i] = 2i, v[i] = 2iY, i = 0..?
LI1: X × Y = x × Y + s
LI2: x ≥ 0
LI3: x < 2i = u[i]
There are two case:
Multiplying
By case xt < u[it-1]
Exit
= u[it+1]
No change needed.
xt+1 = xt u[it-1]
= u[it+1]
We need to make xt smaller to reestablishes LI3.
xt+1 = xt - u[it-1]
0 <
< u[it-1]
= u[it+1]
This reestablishes LI3.
This reestablishes LI2.
‹#›
Loop Invariants given in Practice Test:
LI0: u[i] = 2i, v[i] = 2iY, i = 0..?
LI1: X × Y = x × Y + s
LI2: x ≥ 0
LI3: x < 2i = u[i]
There are two case:
Multiplying
xt+1 = xt - u[it-1]
This reestablishes LI1.
st+1 = st + v[it-1]
‹#›
Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Faster Algorithm:
u[i] = 2i, v[i] = 2iY, i = 0..?
s=0
x=X, y=Y
i =
loop
exit when x=0
i = i-1
if( x > u[i] )
x = x-u[i]
s = s+v[i]
return(s)
the last value in producing u[i]
‹#›
430
Typical Types of Loop Invariants
Fairy God Mother
More of the input
More of the output
Narowing the search space
Shrinking Input Instance
Data Structure (System) Invariant
‹#›
431
How about invariants for
a data structure or a system?
Data Structure Invariants
The importance of invariants is the same.
Differences:
An algorithm must terminate with an answer,
while systems and data structures may run forever.
An algorithm gets its full input at the beginning, while data structures gets a continuous stream of instructions from the user.
Both have invariants that must be maintained.
‹#›
432
Data Structure Invariants
An Abstract (Public) Data Structure:
The minimal needed by the User so he can
understand how best to visualize the data
and what each operation does.
Eg of Public Invariants:
Bank: The amount is not negative.
Stack: Contains an ordered list of objects which cannot be changed except at the top via the explicit push and pop operations.
Drug Allocation Data Base: A patient is not simultaneously prescribed a set of drugs that interact poorly with each other.
The implementer must make sure that each operation
maintains these invariants.
User
Implementer
Important in recursion and parsing.
‹#›
Data Structure Invariants
An Implemented (Private) Data Structure:
The details need to be worked out so that operations
are correct and efficient.
This is all hidden from the User.
Eg of Private Invariants:
Bank:
Stack:
Drug Allocation Data Base:
User
Implementer
Charge extra fees.
For each patient give name address
and list of drugs.
or
‹#›
Constructor
preCondConstructor
InvariantsData Struc
Establishing Loop Invariant
Data Structure Invariants
When a user wants to construct an instance
of data structure the implementer must
make sure that its constructor establishes
all of its loop-invariants.
Initially it contains no objects.
‹#›
435
InvariantsData Struc
Destructor
preCondDestructor
postCondData Struc
Clean up loose ends
Exit
Data Structure Invariants
A destructor for the data structure
must clean up loose ends.
‹#›
436
Data Structure Invariants
Assume we fly in from Mars and InvariantsData Struc t is true:
InvariantsData Struc t+1
postCondPush
Maintaining Loop Invariant
Exit
InvariantsData Struc t
Push Operation
preCondPush
Assume the user correctly calls the Push Operation:
preCondPush The input is info for a new element.
Implementer must ensure:
postCondPush The element is pushed on top of the stack.
InvariantsData Struc t+1
‹#›
437
Data Structure Invariants
InvariantsData Struc t
preCondPush
postCondPush
InvariantsData Struc t+1
next
‹#›
438
Data Structure Invariants
InvariantsData Struc t
preCondPush
postCondPush
InvariantsData Struc t+1
Don’t panic.
Just draw the pictures
and move the pointers.
‹#›
439
Data Structure Invariants
InvariantsData Struc t
preCondPush
postCondPush
InvariantsData Struc t+1
‹#›
440
Data Structure Invariants
InvariantsData Struc t
preCondPush
postCondPush
InvariantsData Struc t+1
Special Case: Empty
‹#›
441
Data Structure Invariants
preCondFind
Suppose you want to
find where the new
element 6 would go?
InvariantsData Struc t
postCondFind
We want the location sandwiched.
How do you get there?
Walk!
‹#›
442
Data Structure Invariants
preCondFind
InvariantsData Struc t
postCondFind
We want the location sandwiched.
What would you like to
be true in the middle
of your computation?
‹#›
443
Data Structure Invariants
How do you
initialize this walk?
Sandwich the location
before the first node.
‹#›
444
Data Structure Invariants
Just take one step.
How do you maintain this
while making progress?
Exit
‹#›
445
Data Structure Invariants
Exit
‹#›
446
Data Structure Invariants
preCondInsert
postCondFind
We want the location sandwiched.
The location for the new element has been found.
PostCondInsert
The new element has been inserted where it belongs.
‹#›
447
Data Structure Invariants
preCondInsert
The location for the new element has been found.
PostCondInsert
The new element has been inserted where it belongs.
postCondInsert
InvariantsData Struc t+1
‹#›
448
Bucket (Quick) Sort for Humans
Input: A pile of things to sort.
(Ex: Exams)
Output: Sort them
Requirements:
Easy to execute by humans
Only can have 7 piles on desk
Can move one exam (or pile)
at a time.
Fast – O(nlog(n)) time.
Likely the only algorithm
in this course which you will
execute by hand yourself.
‹#›
449
Bucket (Quick) Sort for Humans
[A-Z]
Denotes an unsorted pile of exams
with last names starting in the range [A-Z]
Input:
‹#›
Bucket (Quick) Sort for Humans
[A-Z]
Psychology study:
Humans can only think about
5 things at once.
Is the first letter
of the name
on the first exam
[A-E]
[F-K]
[L-O]
[P-T]
[U-Z]
in
‹#›
Bucket (Quick) Sort for Humans
[A-Z]
[A-E]
[F-K]
[L-O]
[P-T]
[U-Z]
Bucket Sort
Put exams one at a time
in the correct bucket.
‹#›
Bucket (Quick) Sort for Humans
[A-E]
[F-K]
[L-O]
[P-T]
[U-Z]
A stack of piles
each pile unsorted
all in one pile before all in next
A sorted pile
before all the rest
(upside down)
[]
sorted
‹#›
[A-E]
[F-K]
[L-O]
[P-T]
[U-Z]
[]
sorted
[A]
[B]
[C]
[D]
[E]
Bucket Sort
Put exams one at a time
in the correct bucket.
Bucket (Quick) Sort for Humans
‹#›
A stack of piles
each pile unsorted
all in one pile before all in next
A sorted pile
before all the rest
(upside down)
[]
sorted
[F-K]
[L-O]
[P-T]
[U-Z]
[A]
[B]
[C]
[D]
[E]
Bucket (Quick) Sort for Humans
‹#›
[]
sorted
[F-K]
[L-O]
[P-T]
[U-Z]
[A]
[B]
[C]
[D]
[E]
Bucket (Quick) Sort for Humans
[AA-AE]
[AF-AK]
[AL-AO]
[AP-AT]
[AU-AZ]
‹#›
[]
sorted
[F-K]
[U-Z]
[B]
[E]
Bucket (Quick) Sort for Humans
…
…
[AA-AE]
[AU-AZ]
…
A stack of piles
each pile unsorted
all in one pile before all in next
A sorted pile
before all the rest
(upside down)
‹#›
[]
sorted
[F-K]
[U-Z]
[B]
[E]
Bucket (Quick) Sort for Humans
…
…
[AA-AE]
[AU-AZ]
…
[AA-AE]
‹#›
[]
sorted
[F-K]
[U-Z]
[B]
[E]
Bucket (Quick) Sort for Humans
…
…
[AF-AK]
[AU-AZ]
…
[AA-AE]
sorted
When sufficiently small
sort by hand
‹#›
[AA-AE]
sorted
[F-K]
[U-Z]
[B]
[E]
Bucket (Quick) Sort for Humans
…
…
[AF-AK]
[AU-AZ]
…
A stack of piles
each pile unsorted
all in one pile before all in next
A sorted pile
before all the rest
(upside down)
‹#›
[AA-AE]
sorted
[F-K]
[U-Z]
[B]
[E]
Bucket (Quick) Sort for Humans
…
…
[AF-AK]
[AU-AZ]
…
[AF-AK]
sorted
‹#›
[AA-AK]
sorted
[F-K]
[U-Z]
[B]
[E]
Bucket (Quick) Sort for Humans
…
…
[AL-AO]
[AU-AZ]
…
A stack of piles
each pile unsorted
all in one pile before all in next
A sorted pile
before all the rest
(upside down)
‹#›
[AA-AK]
sorted
[F-K]
[U-Z]
[B]
[E]
Bucket (Quick) Sort for Humans
…
…
[AL-AO]
[AU-AZ]
…
[AL-AO]
[AP-AT]
[AU-AZ]
sorted
sorted
sorted
‹#›
[F-K]
[U-Z]
[B]
[E]
Bucket (Quick) Sort for Humans
…
…
[AA-AZ]
sorted
‹#›
[F-K]
[U-Z]
[B]
[E]
Bucket (Quick) Sort for Humans
…
…
[A]
A stack of piles
each pile unsorted
all in one pile before all in next
A sorted pile
before all the rest
(upside down)
sorted
‹#›
[A]
[F-K]
[U-Z]
[B]
[E]
Bucket (Quick) Sort for Humans
…
…
[BA-BE]
[BF-BK]
[BL-BO]
[BP-BT]
[BU-BZ]
sorted
‹#›
[A]
[F-K]
[U-Z]
[C]
[E]
Bucket (Quick) Sort for Humans
…
…
[BA-BE]
[BU-BZ]
…
A stack of piles
each pile unsorted
all in one pile before all in next
A sorted pile
before all the rest
(upside down)
sorted
‹#›
[A-ZT]
Bucket (Quick) Sort for Humans
[ZU-ZZ]
[ZU-ZZ]
sorted
sorted
‹#›
[A-Z]
Bucket (Quick) Sort for Humans
Exit
sorted
‹#›
Bucket (Quick) Sort for Humans
Fast – O(nlog(n)) time.
Each time you touch an exam,
the size of its pile goes
down by a factor of 5
Hence I touch it only log5n times.
(Assuming names distributed
randomly through alphabet)
[A-Z]
[A-E]
[F-K]
[L-O]
[P-T]
[U-Z]
[A-Z]
[A-E]
[F-K]
[L-O]
[P-T]
[U-Z]
‹#›
470
Input: A of stack of N punch cards.
Each card contains d digits.
Each digit between 0&(k-1)
Output: Sort the cards.
RadixSort
344
125
333
134
224
334
143
225
325
243
Bucket Sort Machine:
Select one digit
Separates cards into k piles.
wrt selected digit.
125
224
225
325
333
134
334
344
143
243
Stable sort: If two cards are the same for that digit,
their order does not change.
‹#›
RadixSort
344
125
333
134
224
334
143
225
325
243
Sort wrt which
digit first?
The most
significant.
125
134
143
224
225
243
344
333
334
325
Sort wrt which
digit Second?
The next most
significant.
125
224
225
325
134
333
334
143
243
344
All meaning in first sort lost.
‹#›
RadixSort
344
125
333
134
224
334
143
225
325
243
Sort wrt which
digit first?
Sort wrt which
digit Second?
The least
significant.
333
143
243
344
134
224
334
125
225
325
The next least
significant.
224
125
225
325
333
134
334
143
243
344
‹#›
RadixSort
344
125
333
134
224
334
143
225
325
243
Sort wrt which
digit first?
Sort wrt which
digit Second?
The least
significant.
333
143
243
344
134
224
334
125
225
325
The next least
significant.
2 24
1 25
2 25
3 25
3 33
1 34
3 34
1 43
2 43
3 44
Is sorted wrt first i digits.
‹#›
Sort wrt i+1st
digit.
2 24
1 25
2 25
3 25
3 33
1 34
3 34
1 43
2 43
3 44
Is sorted wrt
first i digits.
1 25
1 34
1 43
2 24
2 25
2 43
3 25
3 33
3 34
3 44
Is sorted wrt
first i+1 digits.
i+1
These are in the
correct order
because sorted
wrt high order digit.
RadixSort
‹#›
Sort wrt i+1st
digit.
2 24
1 25
2 25
3 25
3 33
1 34
3 34
1 43
2 43
3 44
Is sorted wrt
first i digits.
1 25
1 34
1 43
2 24
2 25
2 43
3 25
3 33
3 34
3 44
i+1
These are in the
correct order
because was sorted &
stable sort left sorted.
Is sorted wrt
first i+1 digits.
RadixSort
‹#›
CountingSort
Input: N records each labeled with a digit
between 0&(k-1).
Output: Stable sort the numbers.
Input:
Output:
0
0
0
0
0
1
1
1
1
1
1
1
1
1
2
2
3
3
3
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
Algorithm: Count to determine where records go.
Go through the records in order
putting them where they go.
‹#›
CountingSort
Stable sort: If two records are the same for that digit,
their order does not change.
Input:
Output:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
Therefore, the 4th record in input with digit 1 must be
the 4th record in output with digit 1.
It belongs in output index 8, because
8 records go before it
ie 5 records with a smaller digit &
3 records with the same digit
0
0
0
0
0
1
1
1
1
1
1
1
1
1
2
2
2
3
3
Count
These
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
# of records with digit v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
2
3
9
5
N records, k different values. Time to count?
(N)
(N× k)
We have counted # of each value
in the first i values.
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
# of records with digit v:
# of records with digit < v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
2
3
9
5
17
14
5
0
N records, k different values. Time to count?
(k2)
Too much
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
# of records with digit v:
# of records with digit < v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
2
3
9
5
17
14
5
0
Computed
N records, k different values. Time to count?
(k)
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
# of records with digit < v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
17
14
5
0
Location of first record
with digit v.
0
0
0
0
0
1
1
1
1
1
1
1
1
1
2
2
2
3
3
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
17
14
5
0
Location of first record
with digit v.
Algorithm: Go through the records in order
putting them where they go.
1
0
?
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
17
14
5
0
Location of next record
with digit v.
1
Algorithm: Go through the records in order
putting them where they go.
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
17
14
6
0
Location of next record
with digit v.
0
Algorithm: Go through the records in order
putting them where they go.
1
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
17
14
6
1
Location of next record
with digit v.
0
0
Algorithm: Go through the records in order
putting them where they go.
1
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
17
14
6
2
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
17
14
7
2
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
3
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
18
14
7
2
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
1
3
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
18
14
8
2
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
1
3
1
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
18
14
9
2
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
3
3
1
1
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
19
14
9
2
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
1
3
1
1
3
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
19
14
10
2
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
0
1
1
1
3
3
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
19
14
10
3
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
2
1
1
1
3
3
0
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
19
15
10
3
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
1
1
1
1
3
3
0
2
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
19
15
10
3
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
1
1
1
1
3
3
0
2
‹#›
CountingSort
Input:
Output:
Index:
11
10
9
8
7
6
5
4
3
2
1
0
12
13
14
15
16
17
18
Value v:
1
0
0
1
3
1
1
3
1
0
2
1
0
1
1
2
2
1
0
3
2
1
0
19
17
14
5
Location of next record
with digit v.
0
1
Algorithm: Go through the records in order
putting them where they go.
1
0
1
1
1
1
3
3
0
2
0
0
1
1
1
2
2
(N)
Time =
(Counting Ops)
×(log N + log k) (bit ops)
(N+k)
Total =
‹#›
Radix/Counting Sort
Input: N numbers, each L bits long.
Output: Sort the numbers.
111101110100101000101
L
N
101001010100010110111
110100011010011110101
111 101 110 100 101 000 101
101 001 010 100 010 110 111
110 100 011 010 011 110 101
d = L / log k
N
= log k (k will be set to N)
‹#›
Radix/Counting Sort
111 101 110 100 101 000 101
101 001 010 100 010 110 111
110 100 011 010 011 110 101
d = L / log k
N
= log k
digit between 0&(k-1).
using Counting Sort.
Input: N numbers, each L bits long.
Each card contains d digits.
Each digit between 0&(k-1)
Output: Sort the numbers.
Use Radix Sort: Sort wrt each digit
‹#›
Radix/Counting Sort
‹#›
Radix/Counting Sort
Time =
= (# of digits) × (Time of Counting Sort)
= L/log k × (N+k) × (log N + log k) bit ops
(Time of Radix Sort)
Set k to minimize time.
Wants k big.
Really wants k small, but does not
care as long as k N.
Set k=N
‹#›
Radix/Counting Sort
Time =
= (# of digits) × (Time of Counting Sort)
= L/log k × (N+k) × (log N + log k) bit ops
= L/log N × N × log N bit ops
= (L × N) bit ops
Size =
N numbers, each L bits long.
(Time of Radix Sort)
= (L × N) = n
= (n) bit ops
“Linear” Time
But sorting should take (N log N) time!!!
‹#›
Radix/Counting Sort
Time =
(L × N) bit ops
Size =
N numbers, each L bits long.
= (L × N)
Merge or Quick Sort
Time =
(N log N) comparisons
Size =
Size of N numbers, each arbitrarily long.
= (N log N) bits.
L =
> log N if you want N distinct numbers.
(N log N) bit ops
= (n)
‹#›
Merge, Quick, and Heap Sort can sort N numbers
using O(N log N) comparisons between the values.
Theorem: No algorithm can sort faster.
Time Complexity of Sorting
‹#›
504
I win if A on input I gives
the right output and
runs fast enough.
$ A, " I, [ A(I) = P(I) and Time(A,I) ≤ Tupper(|I|)]
I have an algorithm A that I claim works and is fast.
Oh yeah, I have an input I for which it does not .
A Upper Bound on Sorting
Sorting
10 n log(n)
MergeSort
I win!
‹#›
505
I win if A on input I gives
the wrong output or
runs slow.
" A, $ I, [ A(I) = P(I) or Time(A,I) ³ Tlower(|I|)]
I have an algorithm A that I claim works and is fast.
Oh yeah, I have an input I for which it does not .
A Lower Bound on Sorting
Sorting
0.1 n log(n)
???
I win!
‹#›
506
Narrowing the Search Space Loop Invariant
If the key is contained in the original list, then
it is contained in the narrowed subspace.
3 5 6 13 18 21 21 25 36 43 49 51 53 60 72 74 83 88 91 95
A Lower Bound on Sorting
key 25
If key ≤ mid,
then key is in
left half.
If key > mid,
then key is in
right half.
‹#›
507
Narrowing the Search Space Loop Invariant
If the key is contained in the original list, then
it is contained in the narrowed subspace.
A Lower Bound on Sorting
instance on which
the algorithm fails
I am looking for an instance I on which the algorithm A fails.
I give you an algorithm A
that I claim sorts faster.
‹#›
508
Narrowing the Search Space Loop Invariant
If the key is contained in the original list, then
it is contained in the narrowed subspace.
A Lower Bound on Sorting
instance on which
the algorithm fails
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
4 7 5 2 8 1 3 6
5 4 2 3 6 8 1 7
I maintain a set of instances
Oh dear!
The first t time steps of my algorithm A are the same given any of these instances!!!
‹#›
509
A Lower Bound on Sorting
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
4 7 5 2 8 1 3 6
5 4 2 3 6 8 1 7
I maintain a set of instances
79 km
75 km
My t+1st time step
a7 < a2
5th bit of a7 + a2
Any yes/no question
Now, its t+1st step is the same.
Oh dear!
The first t time steps of my algorithm A are the same given any of these instances!!!
I keep the larger half.
‹#›
510
A Lower Bound on Sorting
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
4 7 5 2 8 1 3 6
5 4 2 3 6 8 1 7
Initially, I have n! Permutations.
After t time steps I have N!/2t
N! = 1 × 2 × 3 × … × N/2 × … × N
N factors each at most N.
N/2 factors each at least N/2.
N! NN
‹#›
511
A Lower Bound on Sorting
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
4 7 5 2 8 1 3 6
5 4 2 3 6 8 1 7
Initially, I have n! Permutations.
After t time steps I have N!/2t
We exit when there are two instances.
Exit
T = log(N!) = N log(N)
‹#›
512
I give you algorithm A
I claim it sorts.
A Lower Bound on Sorting
Exit
I must output an instance
on which alg A either
Takes too much time
Or gives the wrong answer
4 7 5 2 8 1 3 6
‹#›
513
A Lower Bound on Sorting
Exit
Case 1: The algorithm does not stop at time T on these two instances.
Exit
T = log(N!)
= Q(N log(N)).
I must output an instance
on which alg A either
Takes too much time
Or gives the wrong answer
Oops!
4 7 5 2 8 1 3 6
‹#›
514
Oops!
I must give the wrong answer on one of these!
A Lower Bound on Sorting
Exit
Case 2: The algorithm stops at time T and gives an answer.
We exit when there are two instances
Exit
and these need different answers.
The first T time steps of alg A are the same on these two instances
and hence the same answer is given.
I must output an instance
on which alg A either
Takes too much time
Or gives the wrong answer
5 4 2 3 6 8 1 7
4 7 5 2 8 1 3 6
‹#›
515
Theorem: For every sorting algorithm A,
on the worst case input instance I,
Q(N log2 N) comparisons (or other bit operations)
need to be executed to sort N objects.
" A, $ I, A(I) = P(I) or Time(A,I) ³ N log2 N
Proof: Prover/Adversary Game
A Lower Bound on Sorting
‹#›
516
End Iterative Algorithms
Recursive Algorithms
Math Review
‹#›
Theorem: For every sorting algorithm A,
on the worst case input instance I,
Q(N log2 N) comparisons (or other bit operations)
need to be executed to sort N objects.
" A, $ I, A(I) = P(I) or Time(A,I) ³ N log2 N
Proof: Prover/Adversary Game
A Lower Bound on Sorting
‹#›
518
Sorting
Input:
Output:
Lower Bound:
Input: An Algorithm for Sorting A
Output: An instance I
on which alg A either
Takes too much time
Or gives the wrong answer
8
7
6
5
4
3
2
1
11
13
3
87
21
34
67
23
Values:
Indexes:
5
2
3
1
4
7
8
6
87
67
34
23
21
13
11
3
Values:
Indexes:
A Lower Bound on Sorting
8
7
6
5
4
3
2
1
11
13
3
87
21
34
67
23
Values:
Indexes:
5
2
3
1
4
7
6
8
87
67
34
23
21
13
3
11
Values:
Indexes:
‹#›
519
Algorithm Definition Completed
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
520
I give you algorithm A
I claim it sorts.
I must output an instance
on which alg A either
Takes too much time
Or gives the wrong answer
8
7
6
5
4
3
2
1
11
13
3
87
21
34
67
23
Values:
Indexes:
It might as well be a permutation of 1..N
(indexes not shown)
6
3
1
8
2
5
7
4
A Lower Bound on Sorting
‹#›
521
I give you algorithm A
I claim it sorts.
A Lower Bound on Sorting
Need to know
what the algorithm does
before we can know
what input to give it.
Need to give the
algorithm an input
before we can know
what the algorithm does with the input.
Break this cycle,
one iteration at a time.
‹#›
522
A Lower Bound on Sorting
Restrict the search space
‹#›
523
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
4 7 5 2 8 1 3 6
5 4 2 3 6 8 1 7
Oh dear!
The first t time steps of my algorithm A are the same given any of these instances!!!
I maintain a set of instances
(permutations of 1..n)
A Lower Bound on Sorting
‹#›
524
Initially, I consider all N! permutations of 1..N
Oh dear!
The first 0 time steps of my algorithm A are the same given any of these instances!!!
A Lower Bound on Sorting
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
4 7 5 2 8 1 3 6
5 4 2 3 6 8 1 7
‹#›
525
Initially, I consider all N! permutations of 1..N
The measure of progress
is the number of instances.
Initially, there are N! of them.
79 km
A Lower Bound on Sorting
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
4 7 5 2 8 1 3 6
5 4 2 3 6 8 1 7
‹#›
526
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
4 7 5 2 8 1 3 6
5 4 2 3 6 8 1 7
Because the first t time steps
are the same, what the alg knows is the same.
Hence, its t+1st step is the same.
My t+1st time step
a7 < a2
5th bit of a7 + a2
Any yes/no question
A Lower Bound on Sorting
‹#›
527
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
4 7 5 2 8 1 3 6
5 4 2 3 6 8 1 7
Because the first t time steps
are the same, what the alg knows is the same.
Hence, its t+1st step is the same.
I partition my instances based on what they do on this t+1st step.
My t+1st time step
a7 < a2
5th bit of a7 + a2
Any yes/no question
A Lower Bound on Sorting
‹#›
528
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
4 7 5 2 8 1 3 6
5 4 2 3 6 8 1 7
I keep the larger half.
A Lower Bound on Sorting
‹#›
529
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
I keep the larger half.
Oh dear!
The first t+1 time steps of my algorithm A are the same given any of these instances!!!
A Lower Bound on Sorting
‹#›
530
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
I keep the larger half.
A Lower Bound on Sorting
79 km
Initially, I have n! Permutations.
After t time steps I have N!/2t
‹#›
531
1 2 3 4 5 6 7 8
3 2 5 8 6 1 4 7
I keep the larger half.
A Lower Bound on Sorting
We exit when there are two instances.
Exit
Initially, I have n! Permutations.
After t time steps I have N!/2t
T = log(N!)
‹#›
532
A Lower Bound on Sorting
We exit when there are two instances.
Exit
T = log(N!)
N! = 1 × 2 × 3 × … × N/2 × … × N
N factors each at most N.
N/2 factors each at least N/2.
N! NN
= Q(N log(N)).
‹#›
533
I give you algorithm A
I claim it sorts.
A Lower Bound on Sorting
Exit
I must output an instance
on which alg A either
Takes too much time
Or gives the wrong answer
8
7
6
5
4
3
2
1
11
13
3
87
21
34
67
23
Values:
Indexes:
‹#›
534
A Lower Bound on Sorting
Exit
Case 1: The algorithm does not stop at time T on these two instances.
Exit
T = log(N!)
= Q(N log(N)).
I must output an instance
on which alg A either
Takes too much time
Or gives the wrong answer
8
7
6
5
4
3
2
1
11
13
3
87
21
34
67
23
Values:
Indexes:
Oops!
‹#›
535
Oops!
I must give the wrong answer on one of these!
I must output an instance
on which alg A either
Takes too much time
Or gives the wrong answer
8
7
6
5
4
3
2
1
11
13
3
87
21
34
67
23
Values:
Indexes:
A Lower Bound on Sorting
Exit
Case 2: The algorithm stops at time T and gives an answer.
We exit when there are two instances
Exit
and these need different answers.
The first T time steps of alg A are the same on these two instances
and hence the same answer is given.
‹#›
536
Theorem: For every sorting algorithm A,
on the worst case input instance I,
Q(N log2 N) comparisons (or other bit operations)
need to be executed to sort N objects.
" A, $ I, A(I) = P(I) or Time(A,I) ³ N log2 N
Proof: Prover/Adversary Game
A Lower Bound on Sorting
‹#›
537
PreCond: i=0
PostCond: i=131
Find Errors
LI is an action not a picture.
Loop Invariant:
i is increasing
Step: i = i+2
Exit Cond: i=131
‹#›
PreCond: i=0
PostCond: i=131
Find Errors
Loop Invariant:
??
Step: i = i+2
Exit Cond: i=131
Trivially true because
LI has no real content.
codeA
Establishing Loop Invariant
‹#›
PreCond: i=0
PostCond: i=131
Find Errors
Loop Invariant:
??
Step: i = i+2
Exit Cond: i=131
Trivially true because
LI has no real content.
¬
codeB
Maintaining Loop Invariant
Exit
‹#›
PreCond: i=0
PostCond: i=131
Find Errors
Loop Invariant:
??
Step: i = i+2
Exit Cond: i=131
codeC
Clean up loose ends
Exit
Trivially true because
=
NEVER DO THIS!
‹#›
PreCond: i=0
PostCond: i=131
Find Errors
Loop Invariant:
??
Step: i = i+2
Exit Cond: i=131
Trivially true
Let measure be the value of i
(or 131-i)
79 km
79 km
75 km
Exit
‹#›
PreCond: i=0
PostCond: i=131
Find Errors
Loop Invariant:
??
Step: i = i+2
Exit Cond: i=131
?
0 km
Exit
Sufficient progress is made
but alg fails to exit!
‹#›
PreCond: i=0
PostCond: i=131
Find Errors
Loop Invariant:
??
Step: i = i+2
Exit Cond: i=131
0 km
Exit
This change ensures we exit.
≥
?
‹#›
PreCond: i=0
PostCond: i=131
Find Errors
Loop Invariant:
??
Step: i = i+2
Exit Cond: i≥131
i is odd
‹#›
545
PreCond: i=0
PostCond: i=131
Find Errors
Loop Invariant:
i is odd
Step: i = i+2
Exit Cond: i≥131
codeA
Establishing Loop Invariant
i is odd
i=0
?
i = i+1
‹#›
546
PreCond: i=0
PostCond: i=131
Find Errors
Loop Invariant:
i is odd
Step: i = i+2
Exit Cond: i≥131
i=131
i≥131
codeC
Clean up loose ends
Exit
i is odd
& i ≤ 132
& i ≤ 132
‹#›
547
PreCond: i=0
PostCond: i=131
Find Errors
Loop Invariant:
i is odd
Step: i = i+2
Exit Cond: i≥131
& i ≤ 132
¬
codeB
Maintaining Loop Invariant
Exit
i’’ is odd and ≤132
i’ is odd and ≤132
i’ < 131
i’’ = i’+2
‹#›
548
Algorithm Definition Completed
Define Problem Define Loop Invariants Define Measure of Progress
Define Step Define Exit Condition Maintain Loop Inv
Make Progress Initial Conditions Ending
79 km
Exit
Exit
79 km
75 km
Exit
Exit
0 km
Exit
‹#›
549
km
¥
Þ
Þ
"
Þ
+
ü
ý
ï
ï
þ
ï
ï
Þ
"
Þ
S
iS
i
S
i
iS
i
(
)
(
)
(
)
(
)
0
1
Chart1
21 21
23 22
25 23
31 25
20 24
18 23
16 22
X
A
Sheet1
X 21 23 25 31 20 18 16
A 21 22 23 25 24 23 22
Chart1
21 21
23 22
25 23
31 25
20 24
18 23
16 22
X
A
Sheet1
X 21 23 25 31 20 18 16
A 21 22 23 25 24 23 22
2
1
2
2
1
1
R
m
m
r
m
r
m
+
+
=
2
1
2
2
1
1
R
m
m
r
m
r
m
+
+
=
i
i
i
1
)
1
(
1
0
)
1
(
1
1
=
-
+
×
-
+
×
=
å
=
=
=
n
i
n
i
d
..
1
)
ln(
1
d
e
n
=
d
n
2
=
mid or mid ?
22
ijij
++
êúéù
==
êúêú
ëûêú
mid
2
ij
+
éù
=
êú
êú
?
R
2
O
ij
+
êú
êú
ëû
OR
>
?
mid
2
ij
+
éù
=
êú
êú
if key L(mid)
³
OR