Stack of Stack Frames
Recursion
Jeff Edmonds
York University
COSC 3101
Lecture 3
Thinking about Algorithms Abstractly
Multiplying
Recurrence Relations
Code
Stack of Stack Frames
Tree of Stack Frames
Friends and Strong Induction
Towers of Hanoi
Check List
Merge & Quick Sort
Simple Recursion on Trees
Generalizing the Problem
Things not to do
Heap Sort & Priority Queues
Trees Representing Equations
Pretty Print
Parsing
Recursive Images
Ackermann’s Function
‹#›
1
Merge Sort
88
14
98
25
62
52
79
30
23
31
Consider your input instance.
You are assured that it meets the precondition.
Your job is to produce an output
that meets the post condition.
14,23,25,30,31,52,62,79,88,98
Technique:
Divide and Conquer
‹#›
2
Merge Sort
88
14
98
25
62
52
79
30
23
31
You can have as many
friends as you want.
You give each a sub instance.
Meets the precondition
Smaller
Trust them to give you
the output for their instances.
Split Set into Two
1,2,3
Trust your friends
Don’t micro manage them
3
2
1
79 cm
By magic!
‹#›
3
Merge Sort
Split Set into Two
25,31,52,88,98
Get one friend to
sort the first half.
Trust your friend
Don’t micro manage him.
14
62
79
30
23
88
98
25
52
31
79 cm
You can have as many
friends as you want.
You give each a sub instance.
Meets the precondition
Smaller
Trust them to give you
the output for their instances.
‹#›
4
Merge Sort
Split Set into Two
25,31,52,88,98
Get another friend to
sort the second half.
Trust your friend
Don’t micro manage him.
14
62
79
30
23
14,23,30,62,79
79 cm
You can have as many
friends as you want.
You give each a sub instance.
Meets the precondition
Smaller
Trust them to give you
the output for their instances.
‹#›
5
Merge Sort
Split Set into Two
Use this help to solve your own instance.
Merge two sorted lists into one
14,23,30,62,79
25,31,52,88,98
‹#›
6
Merge Sort
Split Set into Two
Use this help to solve your own instance.
Merge two sorted lists into one
98
88,
79
62,
52,
31,
30,
25,
23,
14,
‹#›
7
Merge Sort
Split Set into Two
Use this help to solve your own instance.
14,23,25,30,31,52,62,79,88,98
Merge two sorted lists into one
‹#›
8
Precondition
Postcondition
On Step At a Time
next
I implored you to not worry
about the entire computation.
next
It can be difficult to understand
where computation go.
i-1
i
i
i
0
T+1
x/4 3y
(x-3x1) y
Strange(x,y):
x1 = x/4; y1 = 3y; f1 = Strange( x1, y1 );
x2 = x – 3x1; y2 = y; f2 = Strange( x2, y2 );
return( f1+f2 );
‹#›
9
Friends & Strong Induction
Recursive Algorithm:
Assume you have an algorithm that works.
Use it to write an algorithm that works.
If I could get in,
I could get the key.
Then I could unlock the door
so that I can get in.
Circular Argument!
‹#›
10
Friends & Strong Induction
Recursive Algorithm:
Assume you have an algorithm that works.
Use it to write an algorithm that works.
To get into my house
I must get the key from a smaller house
‹#›
11
Friends & Strong Induction
Recursive Algorithm:
Assume you have an algorithm that works.
Use it to write an algorithm that works.
Use brute force
to get into
the smallest house.
‹#›
12
Friends & Strong Induction
Recursive Algorithm:
Assume you have an algorithm that works.
Use it to write an algorithm that works.
Use brute force
to get into
the smallest house.
Advice:
Do not trace it out.
Trust your friend.
Do your job.
‹#›
13
Representations of Recursive Algorithms
Pros
Views
Code
Tracing out
stack of stack frames
Tree of stack frames
Friends (strong induction)
I need a higher level
of understanding
I am not a computer
Crazy making
Too much
Must trust.
Cons
How implement for
a computer
How runs on computer
View entire computation
Worry about
one step at a time
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e – f) 10n/2 + f )
‹#›
14
X = 33
Y = 12
Recursion
Friends & Strong Induction
Consider your input instance
If it is small enough solve it on your own.
Allocate work
Construct one or more sub-instances
It must be smaller
and meet the precondition
Assume by magic your friends
give you the answer for these.
Use this help to solve your own instance.
Do not worry about anything else.
Micro-manage friends by tracing out what they and their friend’s friends do.
Who your boss is.
X = 3
Y = 1
XY = 3
X = 3
Y = 2
XY = 6
X = 6
Y = 3
XY = 18
ac = 31
bd = 32
(a+b)(c+d) =63
XY = 396
= 3
= 6
=18
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e – f) 10n/2 + f )
Know Precond:
Postcond:
ints x,y
product xy
‹#›
15
X = 33
Y = 12
Recursion
Friends & Strong Induction
X = 3
Y = 1
XY = 3
X = 3
Y = 2
XY = 6
X = 6
Y = 3
XY = 18
ac = 31
bd = 32
(a+b)(c+d) =63
XY = 396
= 3
= 6
=18
This technique is often
referred to as
Divide and Conquer
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e – f) 10n/2 + f )
‹#›
16
Complex Numbers
Remember how to multiply 2 complex numbers?
(a+bi)(c+di) = [ac –bd] + [ad + bc] i
Input: a,b,c,d Output: ac-bd, ad+bc
If a real multiplication costs 1 and an addition costs a penny. What is the cheapest way to obtain the output from the input?
Can you do better than 4.02?
‹#›
17
Gauss’ $3.05 Method:
Input: a,b,c,d Output: ac-bd, ad+bc
m1 = ac
m2 = bd
A1 = m1 – m2 = ac-bd
m3 = (a+b)(c+d) = ac + ad + bc + bd
A2 = m3 – m1 – m2 = ad+bc
‹#›
18
Question:
The Gauss “hack” saves one multiplication out of four. It requires 25% less work.
Could there be a context where performing 3 multiplications for every 4 provides a more dramatic savings?
‹#›
19
How to add 2 n-digit numbers.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
+
Tom Lehrer
New Math
Decimal Digits
or Binary Bits
I don’t care.
Running Time
‹#›
20
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
+
How to add 2 n-digit numbers.
Running Time
‹#›
21
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
+
How to add 2 n-digit numbers.
Running Time
‹#›
22
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
+
How to add 2 n-digit numbers.
Running Time
‹#›
23
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
+
How to add 2 n-digit numbers.
Running Time
‹#›
24
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
+
*
*
How to add 2 n-digit numbers.
Running Time
‹#›
25
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
+
*
*
*
*
*
*
T(n) = The amount of time grade school addition uses to add two n-digit numbers
≤ θ(n) = linear time.
On any reasonable computer adding 3 digits can be done in constant time.
Means some constant
(eg 10) times n.
How to add 2 n-digit numbers.
Running Time
‹#›
26
QUESTION: Is there an algorithm to add two n-digit numbers whose time grows sub-linearly in n?
No! You must read the input
to know the answer.
And this takes time n!
How to add 2 n-digit numbers.
Running Time
‹#›
27
So any algorithm for addition must use time at least linear in the size of the numbers.
Grade school addition is essentially as good as it can be.
How to add 2 n-digit numbers.
Running Time
‹#›
28
How to multiply 2 n-bit numbers.
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
n2
Running Time
‹#›
29
Neat! We have demonstrated that as things scale multiplication is a harder problem than addition.
Grade School Addition: Linear time
Grade School Multiplication: Quadratic time
For big inputs, even 100000 n << 0.000001 n2
# of bits in numbers
t
ime
Running Time
‹#›
30
Grade School Addition: Linear time
Grade School Multiplication: Quadratic time
Don’t jump to conclusions!
We compared two algorithms.
We did not prove that
no possible multiplication algorithm
runs in linear time.
Neat! We have demonstrated that as things scale multiplication is a harder problem than addition.
Is there a clever algorithm to multiply two numbers in less than quadratic time?
Running Time
‹#›
31
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
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?
‹#›
32
On Line Banking?
loop b = 2..N
check if N/b
Running Time
T(n) = Time factor
= θ(N) = linear time.
Given a value N find
N = a × b
9283476522567489783883977590110394875
Minutes?
Add a digit?
9
Exponential?
Centuries?
‹#›
33
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’’
‹#›
34
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
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
‹#›
35
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
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!!!
‹#›
36
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
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
‹#›
37
Grade School Addition: Linear time
Grade School Multiplication: Quadratic time
For big inputs, n << n2 << 2n
# of bits in numbers
t
ime
Oops this was worse!
Kindergarten Multiplication: Exponential time
‹#›
38
Divide And Conquer
(an approach to faster algorithms)
DIVIDE my instance to the problem into smaller instances to the same problem.
Have a friend (recursively) solve them.
Do not worry about it yourself.
GLUE the answers together so as to obtain the answer to your larger instance.
‹#›
39
The input X can be thought of in two ways:
as an integer X = 2134
as a string X = “2134” of n=4 digits.
A recursive program gives each “friend” an smaller instance.
Simply cut this string into two halves a and b.
These can be thought of in two ways:
as strings a = “21” and b= “34” with n/2 = 2 digits each.
as integers a = 21 and b= 34.
Note: X = 2134
= 21100 + 34
= a10n/2 + b
Multiplication of 2 n-bit numbers
X =
a
b
= a 2n/2 + b
Y =
c
d
= c 2n/2 + d
‹#›
40
X = a 2n/2 + b and Y = c 2n/2 + d
X Y = (a 2n/2 + b) (c 2n/2 + d)
= ac 2n + (ad+bc) 2n/2 + bd
Multiplication of 2 n-bit numbers
X Y = 23
12
46
230
276
ac 10n + ( ad + bc ) 10n/2 + cd
= 21 102 + (22+31) 101 + 32
Example:
X = 23 and Y = 12
23
12
6
40
30
200
276
‹#›
41
Multiplication of 2 n-bit numbers
X =
Y =
XY = ac 2n + (ad+bc) 2n/2 + bd
a
b
c
d
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
return( MULT(a,c) 2n + (MULT(a,d) + MULT(b,c)) 2n/2 + MULT(b,d) )
‹#›
42
Multiplication of 2 n-bit numbers
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
return( MULT(a,c) 2n + (MULT(a,d) + MULT(b,c)) 2n/2 + MULT(b,d) )
T(n) = time taken by MULT on two n-bit numbers
What is T(n)?
What is its growth rate?
Is it θ(n2)?
‹#›
43
Recurrence Relation
T(1) = k for some constant k
T(n) = 4 T(n/2) + k’ n + k’’
(for some constants k’ and k’’)
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
return( MULT(a,c) 2n + (MULT(a,d) + MULT(b,c)) 2n/2 + MULT(b,d) )
‹#›
44
Recurrence Relation
Lets be concrete
T(1) = 1
T(n) = 4 T(n/2) + n
How do we unravel T(n)?
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
return( MULT(a,c) 2n + (MULT(a,d) + MULT(b,c)) 2n/2 + MULT(b,d) )
‹#›
45
Technique 1
Guess and Verify
Recurrence Relation:
T(1) = 1 & T(n) = 4T(n/2) + n
Guess: G(n) = 2n2 – n
Verify:
Left Hand Side Right Hand Side
T(1) = 2(1)2 – 1
T(n)
= 2n2 – n
1
4T(n/2) + n
= 4 [2(n/2)2 – (n/2)] + n
= 2n2 – n
‹#›
46
Technique 2: Decorate The Tree
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
T(n) = n + 4 T(n/2)
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
T(1)
T(1) = 1
1
=
‹#›
47
n
T(n/2)
T(n/2)
T(n/2)
T(n/2)
T(n)
=
‹#›
48
n
T(n/2)
T(n/2)
T(n/2)
T(n)
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
‹#›
49
n
T(n)
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
‹#›
50
n
T(n)
=
n/2
n/2
n/2
n/2
11111111111111111111111111111111 . . . . ……………………... . 111111111111111111111111111111111
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
‹#›
51
n
n/2 + n/2 + n/2 + n/2
Level i is the sum of 4i copies of n/2i
. . . . . . . . . . . . . . . . . . . . . . . . . .
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
n/4 +
0
1
2
i
n/4 +
n/4 +
n/4 +
n/4 +
n/4 +
n/4 +
n/4 +
n/4 +
n/4 +
n/4 +
n/4 +
n/4 +
n/4 +
n/4 +
n/4
log2n
‹#›
52
=1×n
= 4×(n/2)
= 16×(n/4)
= 4i ×(n/2i)
= 4logn×(n/2logn)
Total: ?
= nlog4 × 1 = n2
alogn
= (2loga)logn
= 2(loga · logn)
= (2logn)loga
= nloga
Level i is the sum of 4i copies of n/2i
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
log2n
Increases by a factor of 2.
‹#›
53
Geometric Sum
‹#›
54
∑i=0..n ri = r0 + r1 + r2 +. . . + rn
= Q(biggest term)
Geometric Increasing
True whenever terms increase quickly
‹#›
55
Adding Made Easy
‹#›
56
Adding Made Easy
‹#›
57
=1×n
= 4×n/2
= 16×n/4
= 4i ×n/2i
Total:
= 4logn×n/2logn
Total = biggest
= nlog4 × 1 = n2
Increases by a factor of 2.
θ(n2)
‹#›
58
Divide and Conquer MULT: θ(n2) time
Grade School Multiplication: θ(n2) time
All that work for nothing!
Let’s understand the math better.
‹#›
59
Evaluating: T(n) = aT(n/b)+f(n)
>
)
This version is more than we really need.
‹#›
60
Recurrence Relations
» Time of Recursive Program
With all this recursing and looping, how do we determine the running time of this recursive program?
procedure Eg(In)
n = |In|
if(n£1) then
put “Hi”
else
loop i=1..f(n)
put “Hi”
loop i=1..a
In/b = In cut in b pieces
Eg(In/b)
T(1) = 1
T(n) = a T(n/b) + f(n)
Recurrence relations.
‹#›
61
Recurrence Relations
» Time of Recursive Program
Let n be the “size” of our input.
procedure Eg(In)
n = |In|
if(n£1) then
put “Hi”
else
loop i=1..f(n)
put “Hi”
loop i=1..a
In/b = In cut in b pieces
Eg(In/b)
T(1) = 1
T(n) = a T(n/b) + f(n)
‹#›
62
Recurrence Relations
» Time of Recursive Program
Let T(n) be the # of “Hi”s
printed by me
procedure Eg(In)
n = |In|
if(n£1) then
put “Hi”
else
loop i=1..f(n)
put “Hi”
loop i=1..a
In/b = In cut in b pieces
Eg(In/b)
T(1) = 1
T(n) = a T(n/b) + f(n)
‹#›
63
Recurrence Relations
» Time of Recursive Program
Let T(n) be the # of “Hi”s
printed by me
And by all of my friends.
procedure Eg(In)
n = |In|
if(n£1) then
put “Hi”
else
loop i=1..f(n)
put “Hi”
loop i=1..a
In/b = In cut in b pieces
Eg(In/b)
T(1) = 1
T(n) = a T(n/b) + f(n)
‹#›
64
If my input is sufficiently small
(according to my measure of size)
then I print (1) “Hi”s.
Recurrence Relations
» Time of Recursive Program
procedure Eg(In)
n = |In|
if(n£1) then
put “Hi”
else
loop i=1..f(n)
put “Hi”
loop i=1..a
In/b = In cut in b pieces
Eg(In/b)
T(1) = 1
T(n) = a T(n/b) + f(n)
‹#›
65
I personally output
f(n) “Hi”s,
i.e. top level stack frame.
Recurrence Relations
» Time of Recursive Program
procedure Eg(In)
n = |In|
if(n£1) then
put “Hi”
else
loop i=1..f(n)
put “Hi”
loop i=1..a
In/b = In cut in b pieces
Eg(In/b)
T(1) = 1
T(n) = a T(n/b) + f(n)
‹#›
66
I have a friends
i.e. recurse a times.
Recurrence Relations
» Time of Recursive Program
procedure Eg(In)
n = |In|
if(n£1) then
put “Hi”
else
loop i=1..f(n)
put “Hi”
loop i=1..a
In/b = In cut in b pieces
Eg(In/b)
T(1) = 1
T(n) = a T(n/b) + f(n)
‹#›
67
Let b be the factor by which I shrink the input before giving it to a friend.
i.e. if my input has size n then my friends are of size n/b.
Recurrence Relations
» Time of Recursive Program
procedure Eg(In)
n = |In|
if(n£1) then
put “Hi”
else
loop i=1..f(n)
put “Hi”
loop i=1..a
In/b = In cut in b pieces
Eg(In/b)
T(1) = 1
T(n) = a T(n/b) + f(n)
‹#›
68
By definition of T,
the number of “Hi”s printed by one of my friends
and all of his friends is T(n/b).
Recurrence Relations
» Time of Recursive Program
procedure Eg(In)
n = |In|
if(n£1) then
put “Hi”
else
loop i=1..f(n)
put “Hi”
loop i=1..a
In/b = In cut in b pieces
Eg(In/b)
T(1) = 1
T(n) = a T(n/b) + f(n)
‹#›
69
Hence, the total number printed
by me
and my a friends is
T(n) = a T(n/b) + f(n)
Recurrence Relations
» Time of Recursive Program
procedure Eg(In)
n = |In|
if(n£1) then
put “Hi”
else
loop i=1..f(n)
put “Hi”
loop i=1..a
In/b = In cut in b pieces
Eg(In/b)
T(1) = 1
T(n) = a T(n/b) + f(n)
‹#›
70
Evaluating: T(n) = aT(n/b)+f(n)
Level
0
1
2
i
h
‹#›
71
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size
0
1
2
i
h
‹#›
72
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size
0 n
1
2
i
h
‹#›
73
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size
0 n
1 n/b
2
i
h
‹#›
74
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size
0 n
1 n/b
2 n/b2
i
h
‹#›
75
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size
0 n
1 n/b
2 n/b2
i n/bi
h n/bh
‹#›
76
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size
0 n
1 n/b
2 n/b2
i n/bi
h n/bh
‹#›
77
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size
0 n
1 n/b
2 n/b2
i n/bi
h n/bh = 1
base case
‹#›
78
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size
0 n
1 n/b
2 n/b2
i n/bi
h n/bh = 1
‹#›
79
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size
0 n
1 n/b
2 n/b2
i n/bi
h = log n/log b n/bh = 1
bh = n
h log b = log n
h = log n/log b
‹#›
80
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame
0 n
1 n/b
2 n/b2
i n/bi
h = log n/log b 1
‹#›
81
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame
0 n f(n)
1 n/b f(n/b)
2 n/b2 f(n/b2)
i n/bi f(n/bi)
h = log n/log b 1 T(1)
‹#›
82
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames
0 n f(n)
1 n/b f(n/b)
2 n/b2 f(n/b2)
i n/bi f(n/bi)
h = log n/log b n/bh T(1)
‹#›
83
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames
0 n f(n) 1
1 n/b f(n/b) a
2 n/b2 f(n/b2) a2
i n/bi f(n/bi) ai
h = log n/log b n/bh T(1) ah
‹#›
84
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames
0 n f(n) 1
1 n/b f(n/b) a
2 n/b2 f(n/b2) a2
i n/bi f(n/bi) ai
h = log n/log b n/bh T(1) ah
‹#›
85
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames
0 n f(n) 1
1 n/b f(n/b) a
2 n/b2 f(n/b2) a2
i n/bi f(n/bi) ai
h = log n/log b n/bh T(1) ah
ah = a
= n
log n/log b
log a/log b
‹#›
86
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames Work in Level
0 n f(n) 1
1 n/b f(n/b) a
2 n/b2 f(n/b2) a2
i n/bi f(n/bi) ai
h = log n/log b n/bh T(1)
n
log a/log b
‹#›
87
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames Work in Level
0 n f(n) 1 1 · f(n)
1 n/b f(n/b) a a · f(n/b)
2 n/b2 f(n/b2) a2 a2 · f(n/b2)
i n/bi f(n/bi) ai ai · f(n/bi)
h = log n/log b n/bh T(1)
n
log a/log b
n · T(1)
log a/log b
Total Work T(n) = ∑i=0..h ai×f(n/bi)
‹#›
88
Evaluating: T(n) = aT(n/b)+f(n)
= ∑i=0..h ai×f(n/bi)
If a Geometric Sum
∑i=0..n xi = θ(max(first term, last term))
‹#›
89
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames Work in Level
0 n f(n) 1 1 · f(n)
1 n/b f(n/b) a a · f(n/b)
2 n/b2 f(n/b2) a2 a2 · f(n/b2)
i n/bi f(n/bi) ai ai · f(n/bi)
h = log n/log b n/bh T(1)
n
log a/log b
n · T(1)
log a/log b
Dominated by Top Level or Base Cases
‹#›
90
Evaluating: T(n) = aT(n/b)+f(n)
>
)
I personally do f(n) work.
The size of the friend’s input is 1/b of the size n of my input.
I have a friends.
T(n) is the total time for me and all my friends to solve
my instance of size n.
‹#›
91
Evaluating: T(n) = aT(n/b)+f(n)
>
)
Is it fine if the size of the friend’s input is
If the friends input
is bigger,
then the time
will be bigger.
n/b
n/b + 1
n/b + 100
n/b + 100 n/log(n)
n-1
Yes
Yes
Yes
Yes
No
i.e. no significant
change to running
time when n is big.
Time becomes
exponential.
‹#›
92
Evaluating: T(n) = aT(n/b)+f(n)
>
)
This version is more than we really need.
This version is more than we really need.
‹#›
93
Evaluating: T(n) = aT(n/b)+f(n)
‹#›
94
Time for top level:
Time for base cases:
Dominated?: c = 1 < 2 = log a/log b
θ(n ) =
log a/log b
θ(n ) = θ(n2)
log 4/log 2
Hence, T(n) = ?
= θ(base cases) = θ(n ) = θ(n2).
log a/log b
Evaluating: T(n) = aT(n/b) + nc
= 4T(n/2) + n
n c =
= n1
1
If we reduce the number of friends from 4 to 3
is the savings just 25%?
‹#›
95
n
T(n)
=
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
n/2
T(n/4)
T(n/4)
T(n/4)
T(n/4)
‹#›
96
Time for top level: n1.58, c=1.58
Time for base cases:
Dominated?: c = 1.58 = log a/log b
Hence, all θ(logn) layers require a total of θ(n1.58) work.
The sum of these layers is no longer geometric.
Hence T(n) = θ(n1.58 logn)
θ(n ) =
log a/log b
θ(n ) = θ(n1.58)
log 3/log 2
Evaluating: T(n) = aT(n/b) + nc
= 3T(n/2) + n
1.58
‹#›
97
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames Work in Level
0 n f(n) 1 1 · f(n)
1 n/b f(n/b) a a · f(n/b)
2 n/b2 f(n/b2) a2 a2 · f(n/b2)
i n/bi f(n/bi) ai ai · f(n/bi)
h = log n/log b n/bh T(1)
n
log a/log b
n · T(1)
log a/log b
All levels the same: Top Level to Base Cases
‹#›
98
Evaluating: T(n) = aT(n/b)+f(n)
>
)
‹#›
99
Logs
log 27
log 9
=
‹#›
100
Logs
log? 27
log? 9
=
Which base?
‹#›
101
Logs
log2 27
log2 9
=
It does not matter.
log2 c
log2 c
· logc 27
· logc 9
=
logc 27
logc 9
Which is easiest?
‹#›
102
Logs
log3 27
log3 9
=
log3 33
log3 32
=
3
2
Please no calculators in exams.
And I wont ask
log 25
log 9
‹#›
103
Divide and Conquer MULT: θ(n2) time
Grade School Multiplication: θ(n2) time
All that work for nothing!
Let’s try to multiply faster.
‹#›
104
T(1) = 1
T(n) = 4 T(n/2) + n
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
return( MULT(a,c) 2n + (MULT(a,d) + MULT(b,c)) 2n/2 + MULT(b,d) )
MULT revisited
We likely can’t reduce our work n.
Later we will consider reducing the size n/2 of our friend’s instance.
Can you see a way to reduce
the number 4 of friends?
‹#›
105
Gauss’ Hack:
Input: a,b,c,d Output: ac, ad+bc, bd
A1 = ac
A3 = bd
m3 = (a+b)(c+d)
A2 = m3 – A1- A3 = ad + bc
2 additions and one multiplication
= ac + ad + bc + bd
‹#›
106
Gaussified MULT – Karatsuba 1962)
T(n) = 3 T(n/2) + n
MULT(X,Y)
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e2n + (MULT(a+b, c+d) – e – f) 2n/2 + f )
Hence T(n) = θ(n1.58)
‹#›
107
Cutting into d pieces.
X = i=0..d-1ai 2i/d
Y = j=0..d-1bj 2j/d
ad-1
a2
a1
a0
bd-1
b2
b1
b0
X =
Y =
…
…
Instances for friends?
i=0..d-1j=0,d-1.aibj 2(i+j)/d
XY =
‹#›
Cutting into d pieces.
Instances for friends
Number of friends is
d2.
i=0..d-1j=0,d-1.aibj 2(i+j)/d
XY =
ad-1
a2
a1
a0
bd-1
b2
b1
b0
Y\X
aibj
…
…
…
…
bj
ai
‹#›
Time for top level:
Time for base cases:
Dominated?: c = 1 < 2 = log a/log b
θ(n ) =
log a/log b
θ(n )
log d^2/log d
Hence, T(n) = ?
= θ(base cases) = θ(n ) = θ(n2).
log a/log b
Evaluating: T(n) = aT(n/b) + nc
= T(n/ ) +
n c =
= n1
1
d2
d
n1
= θ(n2)
Cutting into d pieces.
‹#›
All that work for nothing!
Cutting into d pieces.
‹#›
Cutting into d pieces.
i=0..d-1j=0,d-1.aibj 2(i+j)/d
XY =
ad-1
a2
a1
a0
bd-1
b2
b1
b0
Y\X
…
…
…
…
bj
ai
Values needed
Number of friends is
Instance for friend
Fancy Gaussian trick
= k=0..2d-2 (j aj bk-j) 2k/d
2d-1
aibj
‹#›
log a/log b =
Evaluating: T(n) = aT(n/b) + nc
= T(n/ ) +
2d-1
d
n1
Cutting into d pieces.
log 2d-1/log d
≈ log 2d/log d
= log(d) +1/log d
→ 1
Say d=logn
‹#›
Time for top level:
Time for base cases:
Dominated?: c = 1 ≈ log a/log b
θ(n )
log a/log b
Hence, T(n) = ?
= θ(n log n).
Evaluating: T(n) = aT(n/b) + nc
= T(n/ ) +
n c =
= n1
1
2d-1
d
n1
≈ θ(n1)
Cutting into d pieces.
Actually θ(n log n log log n).
‹#›
Multiplication Algorithms
Kindergarten ?
n2n
Grade School n2
Karatsuba n1.58…
Fastest Known n logn
3*4=3+3+3+3
‹#›
115
The Goal is to UNDERSTAND
Recursive Algorithms
Fundamentally to their core
‹#›
116
Representation:
Understand the relationship between different representations of the same information or idea
1
2
3
Rudich www.discretemath.com
‹#›
117
Representations of Recursive Algorithms
Pros
Views
Code
Tracing out
stack of stack frames
Tree of stack frames
Friends (strong induction)
I need a higher level
of understanding
I am not a computer
Crazy making
Too much
Must trust.
Cons
How implement for
a computer
How runs on computer
View entire computation
Worry about
one step at a time
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
‹#›
118
Code Representation
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:
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
‹#›
119
X = 2133
Y = 2312
ac =
bd =
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Stack Frame:
A particular execution
of one routine
on one particular input instance.
My responsibility is to ensure that my algorithm works
under the assumption
that my friends do
their job correctly.
Lets trace out the execution
on a computer.
‹#›
120
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Stack Frame:
A particular execution
of one routine
on one particular input instance.
My responsibility is to ensure that my algorithm works
under the assumption
that my friends do
their job correctly.
Lets trace out the execution
on a computer.
‹#›
121
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac =
bd =
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Our friend is
a separate execution
with separate stack frame
with its own local variables.
My responsibility is to ensure that my algorithm works
under the assumption
that my friends do
their job correctly.
Lets trace out the execution
on a computer.
‹#›
122
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = ?
bd =
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
123
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 2
Y = 2
XY=
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
124
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 2
Y = 2
XY = 4
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
125
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = 4
bd =
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
126
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = 4
bd = ?
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
127
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = 4
bd = ?
(a+b)(c+d) =
XY =
X = 1
Y = 3
XY = 3
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
128
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = 4
bd = 3
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
129
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = 4
bd = 3
(a+b)(c+d) = ?
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
130
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = 4
bd = 3
(a+b)(c+d) = ?
XY =
X = 3
Y = 5
XY = 15
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
131
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = 4
bd = 3
(a+b)(c+d) = 15
XY = ?
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
132
X = 2133
Y = 2312
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 21
Y = 23
ac = 4
bd = 3
(a+b)(c+d) = 15
XY = 483
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
133
X = 2133
Y = 2312
ac = 483
bd =
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
134
X = 2133
Y = 2312
ac = 483
bd = ?
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
135
X = 2133
Y = 2312
ac = 483
bd = ?
(a+b)(c+d) =
XY =
X = 33
Y = 12
ac = ?
bd =
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
136
X = 2133
Y = 2312
ac = 483
bd = ?
(a+b)(c+d) =
XY =
X = 33
Y = 12
ac = ?
bd =
(a+b)(c+d) =
XY =
X = 3
Y = 1
XY = 3
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
137
X = 2133
Y = 2312
ac = 483
bd = ?
(a+b)(c+d) =
XY =
X = 33
Y = 12
ac = 3
bd = ?
(a+b)(c+d) =
XY =
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
138
X = 2133
Y = 2312
ac = 483
bd = ?
(a+b)(c+d) =
XY =
X = 33
Y = 12
ac = 3
bd = ?
(a+b)(c+d) =
XY =
X = 3
Y = 2
XY = 6
Stack of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
139
X = 2133
Y = 2312
ac = 483
bd = ?
(a+b)(c+d) =
XY =
X = 33
Y = 12
ac = 3
bd = 6
(a+b)(c+d) = ?
XY =
Stack of Stack Frames
An so on ….
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Lets trace out the execution
on a computer.
‹#›
140
Trace what actually occurs in the computer
Concrete.
It is what students attempt to describe when told not to give code.
Described in words it is impossible to follow who is doing what.
Does not explain why it works.
Demonstrates for only one of many inputs.
Pros:
Cons:
Stack of Stack Frames
‹#›
141
X = 2133
Y = 2312
ac = 483
bd = 396
(a+b)(c+d) = 1890
XY = 4931496
X = 21
Y = 23
ac = 4
bd = 3
(a+b)(c+d) = 15
XY = 483
X = 33
Y = 12
ac = 3
bd = 6
(a+b)(c+d) = 18
XY = 396
X = 54
Y = 35
ac = 15
bd = 20
(a+b)(c+d) = 72
XY = 1890
X = 2
Y = 2
XY=4
X = 1
Y = 3
XY=3
X = 3
Y = 5
XY=15
X = 3
Y = 1
XY=3
X = 3
Y = 2
XY=6
X = 6
Y = 3
XY=18
X = 5
Y = 3
XY=15
X = 4
Y = 5
XY=20
X = 9
Y = 8
XY=72
Tree of Stack Frames
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
‹#›
142
View the entire computation.
Good for computing the running time.
Must describe entire tree.
For each stack frame
input instance
computation
solution returned.
who calls who
Structure of tree may be complex.
Pros:
Cons:
Tree of Stack Frames
‹#›
143
Representations of Recursive Algorithms
Pros
Views
Code
Tracing out
stack of stack frames
Tree of stack frames
Friends (strong induction)
Must trust.
Cons
Worry about
one step at a time
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
‹#›
144
X = 2133
Y = 2312
ac = 483
bd = 396
(a+b)(c+d) = 1890
XY = 4931496
X = 21
Y = 23
ac = 4
bd = 3
(a+b)(c+d) = 15
XY = 483
X = 33
Y = 12
ac = 3
bd = 6
(a+b)(c+d) = 18
XY = 396
X = 54
Y = 35
ac = 15
bd = 20
(a+b)(c+d) = 72
XY = 1890
X = 2
Y = 2
XY=4
X = 1
Y = 3
XY=3
X = 3
Y = 5
XY=15
X = 3
Y = 1
XY=3
X = 3
Y = 2
XY=6
X = 6
Y = 3
XY=18
X = 5
Y = 3
XY=15
X = 4
Y = 5
XY=20
X = 9
Y = 8
XY=72
One Friend for each stack frame.
Each worries only about his job.
Imagine that you are one.
Friends & Strong Induction
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
‹#›
145
X = 33
Y = 12
Consider your input instance
If it is small enough solve it on your own.
Allocate work
Construct one or more sub-instances
It must be smaller
and meet the precondition
Assume by magic your friends
give you the answer for these.
Use this help to solve your own instance.
Do not worry about anything else.
Micro-manage friends by tracing out what they and their friend’s friends do.
Who your boss is.
X = 3
Y = 1
XY = 3
X = 3
Y = 2
XY = 6
X = 6
Y = 3
XY = 18
ac = 31
bd = 32
(a+b)(c+d) =63
XY = 396
= 3
= 6
=18
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return( e 10n + (MULT(a+b, c+d)
– e - f) 10n/2 + f )
Know Precond:
Postcond:
ints x,y
product xy
Friends & Strong Induction
‹#›
146
Consider generic instances.
ac
bd
(a+b)(c+d)
MULT(X,Y):
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return
e 10n + (MULT(a+b, c+d) – e - f) 10n/2 + f
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Remember!
Do not worry about
Who your boss is.
How your friends solve their instance.
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return
e 10n + (MULT(a+b, c+d) – e - f) 10n/2 + f
Friends & Strong Induction
‹#›
147
X = 2133
Y = 2312
ac = 483
bd = 396
(a+b)(c+d) = 1890
XY = 4931496
X = 21
Y = 23
ac = 4
bd = 3
(a+b)(c+d) = 15
XY = 483
X = 33
Y = 12
ac = 3
bd = 6
(a+b)(c+d) = 18
XY = 396
X = 54
Y = 35
ac = 15
bd = 20
(a+b)(c+d) = 72
XY = 1890
X = 2
Y = 2
XY=4
X = 1
Y = 3
XY=3
X = 3
Y = 5
XY=15
X = 3
Y = 2
XY=6
X = 6
Y = 3
XY=18
X = 5
Y = 3
XY=15
X = 4
Y = 5
XY=20
X = 9
Y = 8
XY=72
X = 3
Y = 1
XY=3
This solves the problem for every possible instance.
MULT(X,Y):
If |X| = |Y| = 1 then return( XY )
Break X into a,b and Y into c,d
e = MULT(a,c) and f =MULT(b,d)
return
e 10n + (MULT(a+b, c+d) – e - f) 10n/2 + f
Friends & Strong Induction
‹#›
148
Worry about one step at a time.
An abstraction within which to develop, think about, and describe algorithms in such way that their correctness is transparent.
Students resist it.
Students expect too much from their friends.
Each sub-instance must be
a smaller instance
to the same problem.
Students expect too much from their boss.
You only know your instance. You do not know your boss’s instance.
Pros:
Cons:
Friends & Strong Induction
‹#›
149
So that we know
what is expected of us.
what we can expect
from our friend.
To be sure that we solve the problem for every legal instance.
So that we know
what we can give to a friend.
Carefully write the specifications for the problem.
Required output
Set of legal instances (inputs)
If you want more from your friends,
change the pre and/or postconditions
Be sure to document it.
Be sure you and all of your friends
are using the same pre/postconditions.
Be sure to handle these changes yourself.
Friends & Strong Induction
‹#›
150
Induction
Strong Induction
Friends & Strong Induction
‹#›
151
Induction Hypothesis:
“The recursive algorithm works
for every instance of size n.”
“The algorithm works for every instance of any size.”
Base case
size i
Friends & Strong Induction
‹#›
152
Give and solve the recurrence relation
for the Running Time of this algorithm.
T(n) = aT(n/b)+f(n)
Friends & Strong Induction
‹#›
153
Input Size
A Measure of Size, Size
is a function
that takes as input the computation’s input I
and that outputs
Eg Input is
Size(
or 3n+7m
Algorithm Designer gets to decide!
According to this measure
Your friend’s instance must be smaller than yours.
You must solve sufficiently small instances on your own.
a real number
‹#›
154
Input Size
Does the program always halt?
m keeps getting bigger!
Algorithm Designer gets to
define the measure of size.
Size(
n
Sufficiently small to halt.
I = <3,5>
<2,10>
<1,20>
<0,40>
Size = 3
2
1
0
‹#›
155
Input Size
Does the program always halt?
Each subinstance is smaller.
But according to what
measure of size?
Size(
?
There is an infinite path!
I = <4,2>
<3,2>
<4,1>
<3,1>
<4,0>
<3,1>
<4,-1>
….
‹#›
156
Input Size
Does the program always halt?
Each subinstance is smaller.
But according to what
measure of size?
Size(
n+m
I = <4,2>
<3,2>
<4,1>
<3,1>
<4,0>
<3,1>
<4,-1>
If n+m0, then
Every friend’s instance
is smaller.
When it gets
sufficiently small
the computation must stop.
Maximum dept =
n+m
‹#›
157
Input Size
Does the program always halt?
According to what single measure
of size are both instances smaller?
Size(
an+bm
I =
Every friend’s instance must be smaller.
size = a(n-1)+b(m+2)
= an+bm –an +2b
= an+bm – 1
size = a(n+1)+b(m-3)
= an+bm +a -3b
= an+bm – 1
Solve: a=5 b=2
‹#›
158
Input Size
Does the program always halt?
According to what single measure
of size are both instances smaller?
Size(
5n+2m
I =
Every friend’s instance is smaller.
Maximum dept =
5n+2m
size = 5(n-1)+2(m+2)
= 5n+2m -1
size = 5(n+1)+2(m-3)
= 5n+2m -1
‹#›
159
Input Size
Does the program always halt?
According to what single measure
of size are both instances smaller?
Size(
I =
There is an infinite path!
….
‹#›
160
Output
Try explaining what this
algorithm does by tracing it out.
I dare you!!!
It is much easier to
TAKE ONE STEP AT A TIME
‹#›
161
n=1
X
n=2
Y
Output
‹#›
162
n=1
X
n=2
n=3
Y
A ? B ? C
Output
‹#›
163
n=1
X
n=2
n=3
Y
A Y B X C
Output
‹#›
164
n=1
X
n=2
n=3
Y
AYBXC
Output
‹#›
165
n=1
X
n=2
n=3
n=4
Y
AYBXC
A ? B ? C
Output
‹#›
166
n=1
X
n=2
n=3
n=4
Y
AYBXC
A AYBXC B Y C
Output
‹#›
167
n=1
X
n=2
n=3
n=4
Y
AYBXC
AAYBXCBYC
Output
‹#›
168
n=1
X
n=2
n=3
n=4
n=5
Y
AYBXC
AAYBXCBYC
A ? B ? C
Output
‹#›
169
n=1
X
n=2
n=3
n=4
n=5
Y
AYBXC
AAYBXCBYC
AAAYBXCBYCBAYBXCC
Output
‹#›
170
n=1
X
n=2
n=3
n=4
n=5
Y
AYBXC
AAYBXCBYC
AAAYBXCBYCBAYBXCC
Output
‹#›
171
Time: T(1) =
T(n-1) + T(n-2) + 3
T(n) =
1
Print A B C
‹#›
172
Time: T(1) =
2T(n-1)
T(n-1) + T(n-2) + 3
T(n) =
1
1
T(2) =
= 2Q(n)
defined?
T(n-1) + T(n-2)
= Fibonacci Numbers
= 4T(n-2)
= 2iT(n-i)
‹#›
173
Towers of Hanoi
This job of mine is a bit daunting.
Where do I start?
And I am lazy.
‹#›
174
Towers of Hanoi
At some point,
the biggest disk moves.
I will do that job.
‹#›
175
Towers of Hanoi
To do this,
the other disks must be in the middle.
‹#›
176
Towers of Hanoi
How will these move?
I will get a friend to do it.
And another to move these.
I only move the big disk.
‹#›
177
Towers of Hanoi
‹#›
178
Towers of Hanoi
Get a job at the Towers of Hanoi company
at level n=1,2,3,4,…..
Or get transferred in as the president
& you decide what your vice president does.
‹#›
179
Towers of Hanoi
Time:
T(1) = 1,
T(n) =
≈ 2(2T(n-2))
≈ 4(2T(n-3))
≈ 2T(n-1)
≈ 4T(n-2)
≈ 8T(n-3)
≈ 2i T(n-i)
≈ 2n
1 + 2T(n-1)
‹#›
180
It takes 2n-1-1 moves to complete my task.
I move one
Total = 2n-1
It takes 2n-1-1 moves to complete my task.
= (2n-1-1) + 1 + (2n-1-1)
Towers of Hanoi
‹#›
181
Evaluating: T(n) = aT(n-b)+f(n)
h = ?
n-hb
n-ib
n-2b
n-b
T(0)
f(n-ib)
f(n-2b)
f(n-b)
f(n)
n
Work in Level
# stack frames
Work
in stack
frame
Instance
size
a
ai
a2
a
1
n/b
a · T(0)
ai · f(n-ib)
a2 · f(n-2b)
a · f(n-b)
1 · f(n)
n/b
|base case| = 0 = n-hb
h = n/b
h = n/b
i
2
1
0
Level
Likely dominated by base cases
Exponential
‹#›
182
Evaluating: T(n) = 1T(n-b)+f(n)
h = ?
Work in Level
# stack frames
Work
in stack
frame
Instance
size
1
1
1
1
1
f(0)
f(n-ib)
f(n-2b)
f(n-b)
f(n)
n-b
n
n-hb
n-ib
n-2b
T(0)
f(n-ib)
f(n-2b)
f(n-b)
f(n)
h = n/b
i
2
1
0
Level
Total Work T(n) = ∑i=0..h f(b·i)
= θ(f(n)) or θ(n·f(n))
‹#›
183
Evaluating: T(n) = aT(n/b)+f(n)
‹#›
184
Check Lists for Recursive Programs
This is the format of “all” recursive programs.
Don’t deviate from this.
Or else!
‹#›
185
Check Lists for Recursive Programs
This is input instance is your mission.
You must return this output.
(An x, y, & z in every computation path.)
Focus on your mission.
‹#›
186
Check Lists for Recursive Programs
The
document these variables
and what you must do.
‹#›
187
Check Lists for Recursive Programs
To get help,
you construct an instance for each friend
It must be valid and smaller.
And pass them to them.
‹#›
188
Check Lists for Recursive Programs
Each friend returns a solution his sub-instance.
Trust him to do this.
But don’t expect him to do or know anything else.
‹#›
189
Check Lists for Recursive Programs
Combine their solutions
to construct a solution to your instance.
Return your solution.
‹#›
190
Check Lists for Recursive Programs
If your solution is too small
to get solved by the general technique
solve it yourself.
Be sure you handle every legal instance.
‹#›
191
Check Lists for Recursive Programs
You rarely need to change the values of these variable
beyond their initial setting
(this is not an iterative algorithm.)
Your rarely need additional
input, output, or local variable.
But it you do document them.
‹#›
192
Check Lists for Recursive Programs
Have NO global variables.
If you change the value of a local variable n,
neither your friends nor your boss get that value.
‹#›
193
Sorting Problem Specification
88
14
98
25
62
52
79
30
23
31
14,23,25,30,31,52,62,79,88,98
‹#›
194
Recursive Sorts
Given list of objects to be sorted
Split the list into two sub-lists.
Recursively have a friend sort the two sub-lists.
Combine the two sorted sub-lists into one entirely sorted list.
‹#›
195
Minimal effort splitting
Lots of effort recombining
Lots of effort splitting
Minimal effort recombining
Four Recursive Sorts
Merge Sort Insertion Sort
Quick Sort Selection Sort
Size of Sub-lists
n/2,n/2
n-1,1
‹#›
196
Merge Sort
88
14
98
25
62
52
79
30
23
31
Divide and Conquer
(no real work)
‹#›
197
Merge Sort
88
14
98
25
62
52
79
30
23
31
Split Set into Two
(no real work)
25,31,52,88,98
Get one friend to
sort the first half.
14,23,30,62,79
Get one friend to
sort the second half.
‹#›
198
Merge Sort
Merge two sorted lists into one
25,31,52,88,98
14,23,30,62,79
14,23,25,30,31,52,62,79,88,98
‹#›
199
‹#›
200
Merge Sort Sort
Time: T(n) =
Q(n log(n))
Total work
at any level
= Q(n)
# levels
= Q(log(n))
‹#›
201
Merge Sort Sort
Time: T(n) =
c = 1 = log a/log b = log 2/log 2
Hence, all levels the same and T(n) = Q(n log(n))
2T(n/2) + Q(n)
‹#›
202
Evaluating: T(n) = aT(n/b)+f(n)
Level Instance
size Work
in stack
frame # stack frames Work in Level
0 n f(n) 1 1 · f(n)
1 n/b f(n/b) a a · f(n/b)
2 n/b2 f(n/b2) a2 a2 · f(n/b2)
i n/bi f(n/bi) ai ai · f(n/bi)
h = log n/log b n/bh T(1)
n
log a/log b
n · T(1)
log a/log b
Total Work T(n) = ∑i=0..h ai×f(n/bi)
2T(n/2) + Q(n)
2i·Q(n/2i) = Q(n)
= Q(n) · log(n)
All levels basically the same.
‹#›
203
Quick Sort
88
14
98
25
62
52
79
30
23
31
Divide and Conquer
Partition set into two using
randomly chosen pivot
‹#›
204
Quick Sort
Divide and Conquer
Partition set into two using
randomly chosen pivot
14
25
30
23
31
88
98
62
79
≤ 52 ≤
‹#›
205
Quick Sort
14
25
30
23
31
88
98
62
79
≤ 52 ≤
14,23,25,30,31
Get one friend to
sort the first half.
62,79,98,88
Get one friend to
sort the second half.
‹#›
206
Quick Sort
14,23,25,30,31
62,79,98,88
52
Glue pieces together.
(No real work)
14,23,25,30,31,52,62,79,88,98
‹#›
207
‹#›
208
Quick Sort
88
14
98
25
62
52
79
30
23
31
14
25
30
23
88
98
62
79
≤ 31 ≤
Let pivot be the first
element in the list?
52
‹#›
209
Quick Sort
14,23,25,30,31,52,62,79,88,98
≤ 14 ≤
23,25,30,31,52,62,79,88,98
If the list is already sorted,
then the slit is worst case unbalanced.
‹#›
210
Probabilistic Algorithms
Probabilistic Algorithms
Suppose there are n doors.
Half are promised to have prizes.
The algorithm A specifies which doors are opened.
The input I specifies which doors have prizes.
The adversary, knowing your algorithm,
gives you the worst case input.
I have an algorithm A that I claim works.
Actually my algorithm always gives the right answer
and is fast.
Oh yeah, I have a worst case input I for which it does not.
Probabilistic Algorithms
A(I)=P(I)
“I,
$A,
Problem P is computable if
& Time(A,I) ≤ T
‹#›
213
My algorithm A specifies which doors are opened.
Oh dear.
I know which doors you choose.
My input I puts no prizes
behind the first n/2 doors you look in.
A(I)=P(I)
“I,
$A,
Probabilistic Algorithms
Problem P is computable if
& Time(A,I) ≤ T
No. Actually, I am quite mean.
I really do give a worst case input.
=n/2 +1
‹#›
214
My algorithm A specifies to pivot with the middle item.
Oh dear.
I know this.
My input I puts the smallest element in the middle.
A(I)=P(I)
“I,
$A,
Probabilistic Algorithms
Problem P is computable if
& Time(A,I) ≤ T
No. Actually, I am quite mean.
I really do give a worst case input.
=n2
Remember Quick Sort
‹#›
215
I have a random algorithm A that I claim works.
I know the algorithm A, but not its random coin flips R.
I do my best to give you a worst case input I.
“I,
$A,
Problem P is computable by a random algorithm if
Probabilistic Algorithms
The random coin flips R are independent of the input.
And for EVERY input I,
I want the correct answer.
AR(I)=P(I)
R,
”
My algorithm A will open all doors if necessary.
‹#›
216
I have a random algorithm A that I claim works.
I know the algorithm A, but not its random coin flips R.
I do my best to give you a worst case input I.
“I,
$A,
Problem P is computable by a random algorithm if
Probabilistic Algorithms
The random coin flips R are independent of the input.
And for EVERY input I,
the expected running time (over choice of R) is great.
There are worst case coin flips but not worst case inputs.
AR(I)=P(I)
“R,
ExpectedR Time(AR,I) ≤ T
‹#›
217
I have a random algorithm A that I claim works.
I know the algorithm A, but not its random coin flips R.
I do my best to give you a worst case input I.
“I,
$A,
Problem P is computable by a random algorithm if
Probabilistic Algorithms
AR(I)=P(I)
“R,
ExpectedR Time(AR,I) ≤ T
Each random door has a 50% chance of finding a prize.
So the expected number of doors is 2.
=2
‹#›
218
I know the algorithm A, but not its random coin flips R.
I do my best to give you a worst case input I.
Problem P is computable by a random algorithm if
Probabilistic Algorithms
I have a random algorithm A that I claim works.
PrR
“I,
AR(I)=P(I)
Some random algorithm might give the wrong answer on exponentially few random coin flips
$A,
≥ 1-2-T
Time(AR,I) ≤ T
Each random door has a 50% chance of finding a prize.
The probability of finding no prize behind T doors is
2-T
‹#›
219
Quick Sort
Best Time:
Worst Time:
Expected Time:
T(n) = 2T(n/2) + Q(n)
= Q(n log(n))
= Q(n2)
T(n) = T(0) + T(n-1) + Q(n)
T(n) = T(1/3n) + T(2/3n) + Q(n)
= Q(n log(n))
‹#›
220
Quick Sort
Expected Time:
T(n) = T(1/3n) + T(2/3n) + Q(n)
= Q(n log(n))
Top work Q(n)
2nd level
3rd level
# levels =
Q(n)
Q(n)
1/3
1/3
1/3
2/3
2/3
2/3
2/3
= Q(log(n))
3/2
log (n)
‹#›
221
Kth Element Problem Specification
88
14
98
25
62
52
79
30
23
31
14,23,25,30,31,52,62,79,88,98
k=3
Output: 25
‹#›
222
88
14
98
25
62
52
79
30
23
31
Partition set into two using
randomly chosen pivot
14
25
30
23
31
88
98
62
79
≤ 52 ≤
Kth Element Problem Specification
‹#›
223
14
25
30
23
31
88
98
62
79
≤ 52 ≤
Kth Element Problem Specification
k=3
r=5 elements on left
14,23,25,30,31
Get one friend to
find k=3rd element in first half.
Output: 25
‹#›
224
14
25
30
23
31
88
98
62
79
≤ 52 ≤
Kth Element Problem Specification
k=8
r=5 elements on left
Get one friend to
find k=8-5=3rd element in second half.
Output: 79
52,62,79,98,88
‹#›
225
‹#›
226
T(n) =
Kth Element Problem Specification
= Q(n)
1 T(n/2) + Q(n)
Best Time:
Expected Time:
Worst Time:
n
log a/log b
# of base cases =
= n0 = 1
n
log 1/log 2
=
n
+n/2
+n/4
+n/8
…
+1
‹#›
227
T(n) =
= Q(n)
1 T(n/2) + Q(n)
Expected Time:
Kth Element Problem Specification
T(n) = 1 T(n-1) + Q(n)
Worst Time:
≈ n+T(n-1)
≈ n+(n-1)+T(n-2)
≈ n+(n-1)+(n-2)+T(n-3)
≈ n+(n-1)+(n-2)+(n-3)+…+1
≈ Q(n2)
Best Time:
‹#›
228
T(n) =
= Q(n)
1 T(n/2) + Q(n)
T(n) = 1 T(2/3n) + Q(n)
Expected Time:
= Q(n)
Kth Element Problem Specification
T(n) = 1 T(n-1) + Q(n)
Worst Time:
= Q(n2)
Best Time:
‹#›
229
N=7
N=2
N=1
N=1
N=2
N=1
N=1
N=2
N=1
N=1
N=1
N=4
N=3
b4
b3
b7 = b3 × b4
T(N) = 2T(N/2) + 1
= (N)
Size = log(b) + log(N)
= 2(n)
Power
bN
N
log a/log b
# of base cases =
= N
N
log 2/log 2
=
‹#›
230
N=7
N=1
N=3
b3
b7 = (b3)2 × b
T(N) = 1T(N/2) + 1
= (log(N))
Size = log(b) + log(N)
= (n)
Power
N
log a/log b
# of base cases =
= N0 = 1
N
log 1/log 2
=
All levels
the same
‹#›
231
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
(define)
‹#›
232
Recursion on Trees
A binary tree is:
– the empty tree
– a node with a right and a left sub-tree.
3
8
1
3
2
2
7
6
5
9
4
1
tree because
(define)
‹#›
233
Recursion on Trees
A binary tree is:
– the empty tree
– a node with a right and a left sub-tree.
3
8
1
3
2
2
7
6
5
9
4
1
tree
tree
node
(define)
‹#›
234
Recursion on Trees
A binary tree is:
– the empty tree
– a node with a right and a left sub-tree.
3
8
1
3
2
2
7
6
5
9
4
1
tree because
(define)
‹#›
235
Recursion on Trees
A binary tree is:
– the empty tree
– a node with a right and a left sub-tree.
3
8
1
3
2
2
7
6
5
9
4
1
tree
tree
node
(define)
‹#›
236
Recursion on Trees
A binary tree is:
– the empty tree
– a node with a right and a left sub-tree.
3
8
1
3
2
2
7
6
5
9
4
1
tree because
(define)
‹#›
237
Recursion on Trees
A binary tree is:
– the empty tree
– a node with a right and a left sub-tree.
3
8
1
3
2
2
7
6
5
9
4
1
tree
node
tree
(define)
‹#›
238
Recursion on Trees
A binary tree is:
– the empty tree
– a node with a right and a left sub-tree.
3
8
1
3
2
2
7
6
5
9
4
1
tree because
empty
(define)
‹#›
239
Recursion on Trees
number of nodes = ?
3
8
1
3
2
2
7
6
5
9
4
1
6
5
Get help from friends
(friends)
‹#›
240
Recursion on Trees
number of nodes
3
8
1
3
2
2
7
6
5
9
4
1
= number on left + number on right + 1
= 6 + 5 + 1 = 12
6
5
(friends)
‹#›
241
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
(communication)
Being lazy, I will only consider
my root node and my communication with my friends.
I will never look at my children subtrees
but will trust them to my friends.
6
‹#›
242
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
(communication)
We will only communicate through these walls
Q(1) info
via the pre & post-conditions.
6
‹#›
243
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
(communication)
I know only what you tell me
via the pre-condition.
I tell you only what the post-condition
instructs me to.
‹#›
244
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
(communication)
I certainly will tell you the answer
for my subtree
to the computational problem at hand
‹#›
245
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
(communication)
I can also tell you anything else
about this subtree.
Simply ask by changing
the post-condition.
‹#›
246
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
(communication)
But remember,
I know nothing about the outside world
(root, other subtree, whether I am left or right.)
except what you tell me.
‹#›
247
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
(communication)
I tell you extra information
by changing the pre-condition.
(Info about left subtree, the root,
things my boss told me, …)
6
‹#›
248
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
(communication)
Of course if the pre or post-conditions change
then I must fill this contract with my boss too.
6
‹#›
249
Recursion on Trees
Base Case ?
3
8
1
3
2
2
7
6
5
9
4
1
number of nodes
1
Are we done?
(base case)
‹#›
250
Recursion on Trees
Base Case ?
3
8
1
3
2
2
7
6
5
9
4
1
number of nodes
?
(base case)
‹#›
251
Recursion on Trees
Base Case ?
3
8
1
3
2
2
7
6
5
9
4
1
number of nodes
0
Better base case!
(base case)
‹#›
252
Recursion on Trees
Base Case ?
3
8
1
3
2
2
7
6
5
9
4
1
number of nodes
1
Does this still need to be a base case?
(base case)
‹#›
253
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
0
0
number of nodes
= number on left + number on right + 1
= 0 + 0 + 1 = 1
No!
(base case)
‹#›
254
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
0
0
Most programmers don’t use
the empty tree as a base case.
This causes a lot more work.
(base case)
‹#›
255
Recursion on Trees
(code)
‹#›
256
Recursion on Trees
3
Designing Program/Test Cases
generic
generic
3
generic
3
0
0
0+0+1=1
n1
n2
n1 + n2 + 1
0
n1
n1+0+1
Same code works!
Same code works!
Try same code
Try same code
0
Base Case
(cases)
‹#›
Time: T(n) =
Recursion on Trees
This only works for balanced tree.
We don’t know how many nodes on left vs right.
How do we solve this?
aT(n/b) + Q(nc)
= 2T(n/2) + Q(1)
= Q(n)
= T(left) + T(right) + Q(1)
= ??
(time)
‹#›
258
Time: T(n) =
Recursion on Trees
∑stack frame Work done by stack frame
X = 2133
Y = 2312
ac = 483
bd = 396
(a+b)(c+d) = 1890
XY = 4931496
X = 21
Y = 23
ac = 4
bd = 3
(a+b)(c+d) = 15
XY = 483
X = 33
Y = 12
ac = 3
bd = 6
(a+b)(c+d) = 18
XY = 396
X = 54
Y = 35
ac = 15
bd = 20
(a+b)(c+d) = 72
XY = 1890
X = 2
Y = 2
XY=4
X = 1
Y = 3
XY=3
X = 3
Y = 5
XY=15
X = 3
Y = 1
XY=3
X = 3
Y = 2
XY=6
X = 6
Y = 3
XY=18
X = 5
Y = 3
XY=15
X = 4
Y = 5
XY=20
X = 9
Y = 8
XY=72
(time)
‹#›
259
Recursion on Trees
One stack frame
for each node in the tree
and for empty trees hang off
And constant work per stack frame.
= Q(n) ×
Time: T(n) =
∑stack frame Work done by stack frame
Q(1) = Q(n)
(time)
‹#›
260
Recursion on Trees
number of nodes =
One friend for each sub-tree.
3
8
1
3
2
2
7
6
5
9
4
1
4
4
2
2
4
Many Children
4 + 2 + 4 + 2 + 1 = 13
(friends)
(mult-children)
‹#›
261
Recursion on Trees
(code)
(mult-children)
‹#›
262
Recursion on Trees
3
Designing Program/Test Cases
generic
generic
3
generic
3
0
+1=1
n1
n1 + 1
Same code works!
Same code works!
Try same code
Try same code
generic
n1
n3
n1 + n2 + n3 + 1
n2
But is this needed
(if not the input)
(cases)
(mult-children)
‹#›
Recursion on Trees
(code)
(mult-children)
‹#›
264
Recursion on Trees
One stack frame for
each node in the tree
And constant work per stack frame.
= Q(n) ×
Time: T(n) =
∑stack frame Work done by stack frame
Q(1) = Q(n)
Q(n) = Q(n2)
(time)
(mult-children)
‹#›
265
Recursion on Trees
Time: T(n) =
∑stack frame Work done by stack frame
= Q(edgeTree)
(time)
(mult-children)
= ∑stack frame Q(# subroutine calls)
Q(nodeTree) = Q(n)
= ∑node Q(# edge in node)
‹#›
266
We pass the recursive program a “binary tree”.
But what type is it really?
This confused Jeff at first.
class LinkedBinaryTree {
class Node
{
E element;
Node parent;
Node left;
Node right;
}
Node root = null;
Tree
Recursion on Trees
‹#›
One would think tree is of type LinkedBinaryTree.
Then getting its left subtree,
would be confusing.
class LinkedBinaryTree {
class Node
{
E element;
Node parent;
Node left;
Node right;
}
Node root = null;
Tree
Recursion on Trees
left_Tree
(LinkedBinaryTree tree)
‹#›
One would think tree is of type LinkedBinaryTree.
Then getting its left subtree,
would be confusing.
class LinkedBinaryTree {
class Node
{
E element;
Node parent;
Node left;
Node right;
}
Node root = null;
Tree
Recursion on Trees
left_Tree
(LinkedBinaryTree tree)
‹#›
It is easier to have tree be of type Node.
But it is thought of as the subtree rooted at the node pointed at.
The left child is then
class LinkedBinaryTree {
class Node
{
E element;
Node parent;
Node left;
Node right;
}
Node root = null;
Tree
Recursion on Trees
(Node tree)
tree
tree.left
or
tree.Getleft()
or
Tree.leftSub(tree)
or
leftSub(tree)
‹#›
But the outside user does not know about pointers to nodes.
class LinkedBinaryTree {
class Node
{
E element;
Node parent;
Node left;
Node right;
}
Node root = null;
public int NumberNodes() {
return NumberNodesRec( root );
}
Tree
Recursion on Trees
tree
private int NumberNodesRec
(Node tree)
NumberNodesRec
NumberNodesRec
‹#›
Recursion on Trees
sum of nodes = ?
3
8
1
3
2
2
7
6
5
9
4
1
23
25
Get help from friends
(sum)
‹#›
Recursion on Trees
sum of nodes
3
8
1
3
2
2
7
6
5
9
4
1
= sum on left + sum on right + value at root
= 23 + 25 + 3 = 51
23
25
(sum)
‹#›
273
Recursion on Trees
Base Case ?
3
8
1
3
2
2
7
6
5
9
4
1
sum of nodes = ?
0
(sum)
‹#›
Recursion on Trees
(sum)
‹#›
275
Recursion on Trees
3
generic
generic
3
generic
3
0
s1
s2
s1 + s2 + 3
0
s1
s1 + 3
0
0
0+0+ 3 =3
Designing Program/Test Cases
(sum)
‹#›
Recursion on Trees
max of nodes = ?
3
8
1
3
2
2
7
6
5
9
4
1
8
9
Get help from friends
(max)
‹#›
277
Recursion on Trees
max of nodes
3
8
1
3
2
2
7
6
5
9
4
1
= max( max on left, max on right, value at root)
= max( 8, 9, 3) = 9
8
9
(max)
‹#›
Recursion on Trees
Base Case ?
3
8
1
3
2
2
7
6
5
9
4
1
max of nodes = ?
?
(max)
‹#›
279
3+4+2+8+…
Sum so far is 17
Sum so far is
0
Recursion on Trees
NewSum = OldSum + nextElement
= 0 + 3
= 3
(max)
‹#›
3*4*2*3*…
Product so far is 72
Product so far is
1
Recursion on Trees
NewProd = OldProd × nextElement
= 1 × 3
= 3
(max)
‹#›
281
True and True and False and …
Conclusion so far is True
Conclusion so far is
True
Recursion on Trees
NewProd = OldProd and nextElement
= True and True
= True
(max)
‹#›
Max(3,4,2,3,…
Max so far is 4
Max so far is
-¥
Recursion on Trees
NewMax = max(OldMax, next Element)
= max( -¥ , 3 )
= 3
(max)
‹#›
283
Recursion on Trees
(max)
‹#›
Recursion on Trees
height of tree = ?
3
8
1
3
2
2
7
6
5
9
4
1
3
4
Get help from friends
(height)
‹#›
285
Recursion on Trees
height of tree
3
8
1
3
2
2
7
6
5
9
4
1
= max(height of left,height on right) + 1
= max(3,4) + 1 = 5
3
4
(height)
‹#›
Recursion on Trees
Base Case ?
3
8
1
3
2
2
7
6
5
9
4
1
height of tree
?
(height)
‹#›
287
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
height of tree?
2 nodes or 1 edge
0 nodes
? edges
Base Case ?
(height)
‹#›
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
Work it out backwards
? edges
height =
= max(height of left,height on right) + 1
= max(?,?) + 1
?
?
0 edge
(height)
‹#›
289
Recursion on Trees
3
8
1
3
2
2
7
6
5
9
4
1
Work it out backwards
-1 edges
height =
= max(height of left,height on right) + 1
= max(-1,-1) + 1
-1
-1
0 edge
(height)
‹#›
Recursion on Trees
(height)
‹#›
291
Recursion on Trees
number of leaves = ?
3
8
1
3
2
2
7
6
5
9
4
1
3
2
Get help from friends
(#leaves)
‹#›
Recursion on Trees
number of leaves
3
8
1
3
2
2
7
6
5
9
4
1
= number on left + number on right
= 3 + 2 = 5
3
2
(#leaves)
‹#›
293
Recursion on Trees
Base Case ?
3
8
1
3
2
2
7
6
5
9
4
1
number of leaves
0
(#leaves)
‹#›
Recursion on Trees
3
generic
generic
3
generic
3
0
L1
L2
L1 + L2
0
L1
L1
0
0
0+0 = 0
Needs to be
another base case.
1
No!
Designing Program/Test Cases
(#leaves)
‹#›
295
Recursion on Trees
(#leaves)
‹#›
296
Recursion on Trees
(travers)
‹#›
297
Recursion on Trees
Copy Tree
3
8
1
3
2
2
7
6
5
9
4
1
(height)
8
1
3
2
2
7
6
5
9
4
1
3
‹#›
298
Recursion on Trees
(copy)
‹#›
299
Recursion on Trees
?
Drops the tree.
(deallocate)
‹#›
300
38
25
17
4
21
31
28
35
51
42
40
49
63
55
71
Define Problem: Binary Search Tree
A binary search tree.
Recursion on Trees
(BST)
‹#›
301
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
≤
≤
(BST)
‹#›
302
Define Loop Invariant
Maintain a sub-tree.
If the key is contained in the original tree, then the key is contained in the sub-tree.
key 17
38
25
17
4
21
31
28
35
51
42
40
49
63
55
71
(BST)
‹#›
303
Define Step
Cut sub-tree in half.
Determine which half the key would be in.
Keep that half.
key 17
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
(BST)
‹#›
304
Recursion on Trees
(BST)
‹#›
305
Recursion on Trees
(IsBST)
‹#›
306
Time: T(n) =
= Q(n log(n))
2T(n/2) + Q(
Recursion on Trees
Computing max is too much work.
n)
If tree very
unbalanced?
T(n) =
1T(n-1) + (n)
= (n2)
(IsBST)
‹#›
307
Recursion on Trees
Extra info from below
(IsBST)
‹#›
308
Time: T(n) =
= Q(n log(n))
2T(n/2) + Q(
Recursion on Trees
Computing max is too much work.
n)
1
n
(IsBST)
‹#›
309
Recursion on Trees
Extra info from above
-¥, ¥
38
min
max
min
root
root
max
min
max
(IsBST)
‹#›
310
Things to Remember
Things to Do
and
Things NOT TO DO
‹#›
311
Trust your friends to solve sub-instances.
The sub-instance given must be
smaller and
must be an instance to the same problem.
Combine solution given by friend
to construct your own solution for your instance.
Focus on one step.
Do not talk of their friends friends friends.
Solve small instances on your own.
I am obsessed with the
Friends – Strong Induction View of Recursion.
Do it!
‹#›
312
“You did NOT ask for code in the question
so I am explaining it as it is easier.”
Yes, but I asked you to give
a recursive algorithm
and said very strongly in my Unit steps
what that should look like.
Typical Test Answer
“We start at the leaf nodes
and work up the tree.”
But this is not recursion!
‹#›
313
Define pre & post conditions
Don’t have inputs or outputs
that are not explained!
Typical Test Answer
‹#›
314
Typical Test Answer
Call recursively
on the correct
types of input
k,num,v
‹#›
315
Typical Test Answer
Call recursively
Save the results
(or don’t bother calling)
returning the correct
types of output
‹#›
316
Typical Test Answer
Combine solutions
given by friends
to construct
your own solution.
‹#›
317
Typical Test Answer
Return things
of the correct types.
Not an
element
In every path
through code
the root?
‹#›
318
Typical Test Answer
Sub-instances
need to be smaller.
“Size” is size of the tree
Wrong base case
‹#›
319
Typical Test Answer
Still zero.
The friend has
his own variable n.
What is the value of n here?
No Global Variables.
‹#›
320
Typical Test Answer
No Global Variables.
Maybe they mean to pass the
new n in and out.
Please don’t use these
to pass out values
when I am marking.
‹#›
321
Typical Test Answer
Looks like
an iterative algorithm
Which is it?
Looks like
an recursive algorithm
‹#›
322
Heaps, Heap Sort, &
Priority Queues
‹#›
323
Heap Definition
Completely Balanced Binary Tree
The value of each node
³ each of the node’s children.
Left or right child could be larger.
Where can 1 go?
Maximum is at root.
Where can 8 go?
Where can 9 go?
‹#›
324
Heap Data Structure
Completely Balanced Binary Tree
Implemented by an Array
‹#›
Heapify
?
Maximum needs
to be at root.
Where is the maximum?
‹#›
Find the maximum.
Put it in place
?
Repeat or recurse
Heapify
Time = O(logn)
‹#›
327
Make Heap
Get help from friends
‹#›
328
Make Heap
Get help from friends
Heapify
‹#›
329
Make Heap
Get help from friends
T(n) = 2T(n/2) + log(n)
Running time:
= Q(n)
Heapify
Heap
‹#›
330
Priority Queues
Sorted
List Unsorted
List Heap
Items arrive with a priority.
O(n) O(1) O(logn)
Item removed is that with highest priority. O(1) O(n) O(logn)
‹#›
Heap Sort
Put number in a priority queue – O(n) time
Remove them one at a time in order – n O(logn)
‹#›
332
Recursion on Trees
Evaluate Equation Tree = ?
+
12
7
Get help from friends
3+47
(3+4)7
‹#›
Recursion on Trees
Evaluate Equation Tree
7
7
= rootop( value on left, value on right )
= rootop(7,7) = 7 7 = 49
+
(3+4)7
‹#›
334
Recursion on Trees
Evaluate Equation Tree
7
Base Case ?
+
(3+4)7
‹#›
‹#›
336
Derivatives
Input: a function f.
Output: Its derivative df/dx.
‹#›
Derivatives
‹#›
338
Derivatives
Input: a function f.
Output: Its derivative df/dx.
g´
h
g´
g´
h´
g
h
g´
g
‹#›
Derivatives
Input: a function f.
Output: Its derivative df/dx.
g
h
g´
g
g´
h
g´
g´
g
g´
h
h
g´
h´
‹#›
340
Derivatives
Input: a function f.
Output: Its derivative df/dx.
g
g
h
g´
g
g´
h
g´
g´
g
g´
h
h
g´
h´
h
h
‹#›
Simplify
Input: a function f.
Output: f simplified.
‹#›
342
Simplify
‹#›
Recursion on Trees
Printing a Tree
When I taught this
one year, a student
needed just this
algorithm for his job.
‹#›
344
Recursion on Trees
Typing line by line?
Get help from friends
‹#›
Recursion on Trees
One stack frame prints:
His input gives:
his tree
whether left or right
sting for each line
‹#›
346
Recursion on Trees
He gives his friends:
their trees
whether left or right
string for each line
‹#›
‹#›
348
‹#›
‹#›
350
‹#›
Input:
Output:
s=6*8+((2+42)*(5+12)+987*7*123+15*54)
Parsing
‹#›
352
Context Free Grammars
+
exp
term
fact
fact
(
exp
)
7
term
+
term
fact
3
fact
4
(3+4)7
‹#›
353
Input:
Java Code
Parsing/Compiling
Output:
Machine Code
simulating the Java code.
‹#›
Input:
Java Code
Parsing/Compiling
Output:
Machine Code
simulating the Java code.
Challenge: Keep track of three algorithms simultaneously
The compiler
The Java code being compiled
The MARIE code being produced.
‹#›
Parsing
‹#›
Parsing
‹#›
357
Parsing
Algorithm: GetExp( s, i )
Input: s is a string of tokens
i is a start index
Output: p is a parsing of the longest valid expression
j is the end index
s=6*8+((2+42)*(5+12)+987*7*123+15*54)
‹#›
Parsing
Algorithm: GetTerm( s, i )
Input: s is a string of tokens
i is a start index
Output: p is a parsing of the longest valid term
j is the end index
s=6*8+((2+42)*(5+12)+987*7*123+15*54)
‹#›
359
Parsing
Algorithm: GetFact( s, i )
Input: s is a string of tokens
i is a start index
Output: p is a parsing of the longest valid factor
j is the end index
s=6*8+((2+42)*(5+12)+987*7*123+15*54)
‹#›
Algorithm: GetExp( s, i )
s=6*8+((2+42)*(5+12)+987*7*123+15*54)
p
p
p
‹#›
361
Algorithm: GetExp( s, i )
Exp
…
p
p
p
+
+
+
‹#›
Algorithm: GetTerm( s, i )
s=6*8+((2+42)*(5+12)+987*7*123+15*54)
p
p
‹#›
363
Algorithm: GetTerm( s, i )
Term
…
p
p
p
*
*
*
‹#›
Parsing
Algorithm: GetFact( s, i )
s=6*8+((2+42)*(5+12)+987*7*123+15*54)
‹#›
365
Parsing
Algorithm: GetFact( s, i )
Fact
42
‹#›
Algorithm: GetFact( s, i )
s=6*8+((2+42)*(5+12)+987*7*123+15*54)
p
‹#›
367
Algorithm: GetFact( s, i )
Fact
p
(
)
‹#›
Look Ahead One: A grammar is said to be look ahead one if,
given any two rules for the same non-terminal,
the first place that the rules differ in actual characters.
This feature allows our parsing algorithm to look only
at the next token in order to decide what to do next.
Thus the algorithm runs in linear time.
Parsing/Compiling
A ⇒ B ’u’ C ’w’ E
A ⇒ B ’u’ C ’x’ F
A ⇒ B ’u’ C
A ⇒ B ’v’ G H
A ⇒ F G
(Ok if first character(s) within a B
is different than in a F.)
(and next character is not ‘w’ or ‘x’)
?
This parsing algorithm only works for Look Ahead One Grammars.
‹#›
Parsing/Compiling
A ⇒ ( A )
A ⇒
Generates (((())))
This parsing algorithm only works for Look Ahead One Grammars.
A ⇒ a A a
A ⇒
Generates aaaaaaaa
GetA(s,i)
if( s[i] = ‘(‘ )
pA,jA, = GetA(s,i+1)
if( s[jA] = ‘)‘ )
return( ‘(‘ pA ’)’, jA+1)
else
return( error )
else
return(,i)
Not Look Ahead One
? (next character is ‘a’)
Parser can’t find middle.
A ⇒ A B
A ⇒ A C
Recurses forever.
‹#›
Parsing/Compiling
A ⇒ BC
A ⇒ DE
B ⇒ b ….
D ⇒ d ….
This parsing algorithm only works for Look Ahead One Grammars.
GetA(s,i)
if( s[i] = ‘b‘ )
pB,jB, = GetB(s,i)
pC,jC, = GetC(s,jB)
return( pB pC , jC )
elseif( s[i] = ‘d‘ )
pD,jD, = GetD(s,i)
pE,jE, = GetE(s,jD)
return( pD pE , jE )
Not Look Ahead One
Don’t know whether to call
GetB or GetD
A ⇒ BC
A ⇒ DE
B ⇒ bbb ….
D ⇒ bbb ….
‹#›
Parsing
Stackframes nodes in parse tree
‹#›
372
Recursive Images
if n=0, draw
else draw
And recursively
Draw here with n-1
if n=1
n=0
‹#›
Recursive Images
if n=0, draw
else draw
And recursively
Draw here with n-1
if n=2
n=1
‹#›
374
Recursive Images
if n=0, draw
else draw
And recursively
Draw here with n-1
if n=3
n=2
‹#›
Recursive Images
if n=0, draw
else draw
And recursively
Draw here with n-1
if n=30
‹#›
376
Recursive Images
if n=1
if n=2
if n=3
if n=4
if n=5
if n=0
‹#›
Recursive Images
if n=1
if n=0
if n=2
if n=3
if n=4
if n=5
‹#›
378
Recursive Images
L(n) = 4/3 L(n-1)
Þ ¥
= (4/3)n
‹#›
‹#›
380
‹#›
‹#›
382
‹#›
383
‹#›
Ackermann’s Function
n applications
How big is A(5,5)?
‹#›
385
385
Ackermann’s Function
n applications
n applications
‹#›
386
386
Ackermann’s Function
n applications
n applications
‹#›
387
387
Ackermann’s Function
n applications
‹#›
388
388
Ackermann’s Function
n applications
‹#›
389
389
Ackermann’s Function
n applications
‹#›
390
390
Please feel free
to ask questions!
Please give me feedback
so that I can better serve you.
Thanks for the feedback that you have given me already.
‹#›
391
End
‹#›
392
Ackermann’s Function
‹#›
Ackermann’s Function
‹#›
Ackermann’s Function
‹#›
Ackermann’s Function
‹#›
Ackermann’s Function
‹#›
397
397
Cut Out
‹#›
398
Hard to write an iterative program
to traverse on a recursive structure tree
3
8
1
3
2
2
7
6
5
9
4
1
Need pointers from each node
to its parent.
‹#›
399
Hard to write a recursive program that implements an iterative algorithm.
‹#›
400
Call recursively
on the correct
types of input
Writing a Recursive Program
‹#›
401
Writing a Recursive Program
Call recursively
on sub-instances
which will give
useful information.
node in sub-tree
?
3
8
1
3
2
2
7
6
5
9
4
1
‹#›
402
Writing a Recursive Program
Call recursively
on sub-instances
which will give
useful information.
3
8
1
3
2
2
7
6
5
9
4
1
node in sub-tree
3rd
node
in whole tree
?
‹#›
403
Writing a Recursive Program
Call recursively
on sub-instances
which will give
useful information.
3
8
1
3
2
2
7
6
5
9
4
1
node in sub-tree
node
in whole tree
+1
3rd
nl
nl
+3rd
‹#›
404
Writing a Recursive Program
Call recursively
on sub-instances
which will give
useful information.
node in sub-tree
node
in whole tree
+1
3rd
nl
+3rd
3
8
1
3
2
2
7
6
5
9
4
1
‹#›
405
Writing a Recursive Program
nl
3
8
1
3
2
2
7
6
5
9
4
1
nl
But who will
count nodes in
left sub-tree?
My friend
‹#›
406
Writing a Recursive Program
nl
3
8
1
3
2
2
7
6
5
9
4
1
nl
But who will
count nodes in
left sub-tree?
My friend
‹#›
407
Writing a Recursive Program
Call recursively
Save the results
(or don’t bother calling)
returning the correct
types of output
‹#›
408
Writing a Recursive Program
Combine solutions
given by friends
to construct
your own solution.
‹#›
409
Writing a Recursive Program
Sub-instances
need to be smaller.
“Size” is # nodes
in the tree
‹#›
410
Writing a Recursive Program
Sub-instances
need to be smaller.
When the instance
sufficiently small
solve on your own.
‹#›
411
Writing a Recursive Program
Return things
of the correct types.
‹#›
412
Writing a Recursive Program
Running Time
T(n) =
2T(n/2) + (1)
= (n)
Faster?
Not possible
because must
count # nodes
in left tree.
‹#›
413
Writing a Recursive Program
Running Time
T(n) =
2T(n/2) + (n)
= (n logn)
If tree very
unbalanced?
T(n) =
1T(n-1) + (n)
= (n2)
‹#›
414
End Recursive Algorithms
Graphs Searching Algorithms
Math Review
‹#›
415
Heaps, Heap Sort, &
Priority Queues
‹#›
416
Heap Definition
Completely Balanced Binary Tree
The value of each node
³ each of the node’s children.
Left or right child could be larger.
Where can 1 go?
Maximum is at root.
Where can 8 go?
Where can 9 go?
‹#›
417
Heap Data Structure
Completely Balanced Binary Tree
Implemented by an Array
‹#›
Make Heap
Get help from friends
‹#›
419
Heapify
?
Maximum needs
to be at root.
Where is the maximum?
‹#›
Find the maximum.
Put it in place
?
Repeat
Heapify
‹#›
421
Heap
Running Time:
Heapify
‹#›
‹#›
423
‹#›
Make Heap
Get help from friends
T(n) = 2T(n/2) + log(n)
Running time:
= Q(n)
Heapify
Heap
‹#›
425
Heaps
Heap
?
Another algorithm
‹#›
?
Heap
‹#›
427
?
Heap
‹#›
?
‹#›
429
Heap
‹#›
Running Time:
i
log(n) -i
2log(n) -i
‹#›
431
Priority Queues
‹#›
Selection Sort
Largest i values are sorted on side.
Remaining values are off to side.
6,7,8,9
< 3 4 1 5 2 Exit 79 km 75 km Exit Max is easier to find if a heap. Selection ‹#› 433 Heap Sort Largest i values are sorted on side. Remaining values are in a heap. Exit 79 km 75 km Exit ‹#› Heap Data Structure Heap Array 5 3 4 2 1 9 8 7 6 Heap Array ‹#› 435 Heap Sort Largest i values are sorted on side. Remaining values are in a heap. Exit Put next value where it belongs. 79 km 75 km Exit Heap ? ‹#› Heap Sort ‹#› 437 Heap Sort ? ? ? ? ? ? ? Sorted ‹#› Heap Sort Running Time: ‹#› 439 nn/2 + n/2 + n/2 + n/2 . . . . . . . . . . . . . . . . . . . . . . . . . . 012i n/4 +n/4 +n/4 +n/4 +n/4 +n/4 +n/4 +n/4 +n/4 +n/4 +n/4 +n/4 +n/4 +n/4 +n/4 +n/4 PowerPoint Presentation 0 1 2 i n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 n n/2 + n/2 + n/2 + n/2 . . . . . . . . . . . . . . . . . . . . . . . . . . Level i is the sum of 4 i copies of n /2 i 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+ 1+1+1+1+1+1+1+1+1+1+1+1 . . . . . . . . . . . . . . . . . . . . . . . . . . n /2 + n /2 + n /2 + n /2 n 0 1 2 i log 2 n n /4 + n /4 + n /4 + n /4 + n /4 + n /4 + n /4 + n /4 + n /4 + n /4 + n /4 + n /4 + n /4 + n /4 + n /4 + n /4 PowerPoint Presentation 0 1 2 i log2n n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 + n/4 n n/2 + n/2 + n/2 + n/2 Level i is the sum of 4i copies of n/2i . . . . . . . . . . . . . . . . . . . . . . . . . . 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 S i S S S S i S i nS n ( ) , [ ( ), ( ), ( ), . . . , ( ) ( )] ( ) 0 0 1 2 1 " - Þ ü ý ï ï þ ï ï Þ " S iS i S i nS n ( ) ( ) ( ) ( ) 0 1 " Þ + ü ý ï ï þ ï ï Þ " Þ Þ " - Þ ü ý ï ï þ ï ï Þ " Þ S i S S S S i S i nS n ( ) , [ ( ), ( ), ( ), . . . , ( ) ( )] ( ) 0 0 1 2 1 S n ( ) = êú ëû ) ) (n T ( T (n) T ) ( T ) ( T k k- k k k 1 : Step Inductive 0 0 : Case Base 1 - = = ) ))))) ( T ( T ( T ( T ( T ( T (n) T k k k- k- k- k- k- k 0 that , on induction by Proof 1 1 1 1 1 L = . each for function different a i.e. Define k T A(k,n) (n) T k k = n (n) T + = 2 0 n (n) T + = 2 0 (n) T = 1 = + + + + + ) ( T 0 2 2 2 2 1 L n ´ 2 n (n) T ´ = 2 1 (n) T = 2 = ´ ´ ´ ´ ´ ) ( T 0 2 2 2 2 2 L n 2 n (n) T 2 2 = (n) T = 3