程序代写代做代考 compiler algorithm Java AI data structure Stack of Stack Frames

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-3x1)  y

Strange(x,y):

x1 = x/4; y1 = 3y; f1 = Strange( x1, y1 );
x2 = x – 3x1; 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 = 31
bd = 32
(a+b)(c+d) =63
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 xy

‹#›
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 = 31
bd = 32
(a+b)(c+d) =63
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 = 21100 + 34 = a10n/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 = 21 102 + (22+31) 101 + 32 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-1j=0,d-1.aibj 2(i+j)/d
XY =

‹#›

Cutting into d pieces.
Instances for friends
Number of friends is
d2.
i=0..d-1j=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-1j=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 = 31 bd = 32 (a+b)(c+d) =63 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 xy 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() = n
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+m0, 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 & must
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 : The input is a list of n values with the same value possibly repeated. : 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

‹#›
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 : The input is a list of n values and an integer k. : The kth smallest in the list.

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 Key 25
A binary search tree.

Find key in BST (if there).

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+47
(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.


h


g

h

g

‹#›
Derivatives
Input: a function f.
Output: Its derivative df/dx.

g

h

g


h


g

h

h

‹#›
340

Derivatives
Input: a function f.
Output: Its derivative df/dx.

g

g

h

g


h


g

h

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