程序代写代做代考 Excel algorithm data structure PowerPoint Presentation

程序代写 CS代考 / Algorithm算法代写代考, data structure

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

codeA
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

codeA
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 codeA

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

codeA
loop

exit when
codeB
endloop
codeC

0

Person 0: Carries baton region to safe region

codeA

Establishing Loop Invariant

‹#›
32

Person i: Running around the track

i-1
i codeA
loop

exit when
codeB
endloop
codeC

i

i


¬
codeB

Exit

Maintaining Loop Invariant

‹#›
33

T+1

codeA
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 = pq = 3495284884937375456635355579 Time = I make this product N public. The pq factoring is my password. n= 14 O(n2)  142 = 196. ‹#› 362 I know his public product N = pq = 3495284884937375456635355579 Cryptography n = # of bits vs N = value I simply factor to find pq. 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 xy

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 xy

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: XY

Elementary School Algorithm: XY = 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=iY

‹#›
377

Multiplying
Precondition: Integers X and Y.
Postcondition: XY

Elementary School Algorithm: XY = 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: XY

Elementary School Algorithm: XY = 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?
XY = xy

+ s
x = X-i,
y = Y
s = iY
= (X-x)Y
= XY - xy

‹#›
379

Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
Forget the algorithm.
Lets develop it using the steps.

‹#›
380

Multiplying

codeA

Establishing Loop Invariant

Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s

x=X, y=Y
s=0
With the minimal work possible

‹#›
381

Multiplying
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + 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: XY
Loop Invariant: XY = xy + s

‹#›
383

Multiplying

XY = xy + s

x = 0

Return( s )
Return( XY )


codeC:

Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s

= s

‹#›
384

Multiplying

Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + 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: XY
Loop Invariant: XY = xy + 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: XY
Loop Invariant: XY = xy + s

¬
codeB:

Exit

‹#›
391

Multiplying

XY = xtyt + st

xt > 0

xt+1 =
XY

= xt+1yt+1 + st+1

¬
codeB:

st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
(st ?)
xt - 1
Write down LHS/RHS
of what we must prove

Exit

‹#›
392

Multiplying

XY = xtyt + st

xt > 0

xt+1 =
XY

= (xt -1)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st

¬
codeB:

st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
(st ?)
xt - 1
Use the LI
Plug in new values.

Exit

‹#›
393

Multiplying

XY = xtyt + st

xt > 0

xt+1 =
XY
= xtyt – yt + (st ?)
= (xt -1)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st

¬
codeB:

st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
xt - 1
Rearrange
(st ?)

Exit

‹#›
394

Multiplying

XY = xtyt + st

xt > 0

xt+1 =
XY
= xtyt – yt +
= (xt -1)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st

¬
codeB:

st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
st + yt
xt - 1
(st + yt)

Exit

‹#›
395

Multiplying

XY
= xtyt – yt +
= (xt -1)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st

Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + 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: XY

Elementary School Algorithm: XY = 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: XY

Elementary School Algorithm: XY = 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: XY

Elementary School Algorithm: XY = 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: XY
Loop Invariant: XY = xy + s

¬
codeB

Maintaining Loop Invariant

Exit

79 km

75 km

Exit

Step to make progress
x = x/2

‹#›
402

Multiplying

XY = xtyt + st

xt > 0

xt+1 =

¬
codeB:

st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
(yt ?)
(st ?)
xt /2
XY

= (xt /2)(yt ?)+ (st ?)
= xt+1yt+1 + st+1
= xtyt + st
Use the LI
Plug in new values.

Exit

‹#›
403

Multiplying

XY = xtyt + st

xt > 0

xt+1 =

¬
codeB:

st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt2
(st ?)
xt /2
XY

= (xt /2) + (st ?)
= xt+1yt+1 + st+1
= xtyt + st

(yt2)

Exit

‹#›
404

Multiplying

XY = xtyt + st

xt > 0

xt+1 =

¬
codeB:

st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt2
st
xt /2
XY

= (xt /2) +
= xt+1yt+1 + st+1
= xtyt + st

(yt2)
st

Exit

‹#›
405

Multiplying


Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
XY

= (xt /2) +
= xt+1yt+1 + st+1
= xtyt + st
(yt2)
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: XY

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: XY

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: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
(st ?)
xt - ut
XY

= (xt -ut)yt + (st ?)
= xt+1yt+1 + st+1
Use the LI
Plug in new values.
= xtyt + st

Exit

‹#›
411

Multiplying

XY = xtyt + st

xt > 0

xt+1 =

¬
codeB:

st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
(st ?)
xt - ut
XY
= xtyt – utyt + (st ?)
= (xt -ut)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st
Rearrange

Exit

‹#›
412

Multiplying

XY = xtyt + st

xt > 0

xt+1 =

¬
codeB:

st+1 =
Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
yt+1 =
yt
xt - ut
XY
= xtyt – utyt +
= (xt -ut)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + st

st + vt, vt = utY
(st+utY)

Exit

‹#›
413

Multiplying


Precondition: Integers X and Y.
Postcondition: XY
Loop Invariant: XY = xy + s
XY
= xtyt – utyt +
= (xt -ut)yt + (st ?)
= xt+1yt+1 + st+1
= xtyt + 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: XY

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: XY

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] =

2iY
2i
v[i-1]+v[i-1]
u[i] will be subtracted from X.

‹#›
417

Multiplying
Precondition: Integers X and Y.
Postcondition: XY

Faster Algorithm:
u[i] = 2i, v[i] = 2iY, 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: XY Faster Algorithm: u[i] = 2i, v[i] = 2iY, 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] = 2iY, 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] = 2iY, 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] = 2iY, 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] = 2iY, 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: XY Faster Algorithm: u[i] = 2i, v[i] = 2iY, 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

Related Posts