Dynamic Programming

Madhavan Mukund
https://www.cmi.ac.in/~madhavan

Programming, Data Structures and Algorithms using Python

Week 9
Inductive definitions

Factorial
fact(0) = 1
fact(n) = n × fact(n − 1)

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 2/9

Inductive definitions

Factorial
fact(0) = 1
fact(n) = n × fact(n − 1)

Insertion sort
isort([ ]) = [ ]
isort([x0 , x1 , . . . , xn ]) =
insert(isort([x0 , x2 , . . . , xn−1 ]), xn )

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 2/9

Inductive definitions . . . recursive programs

Factorial def fact(n):

if n <= 0:
fact(0) = 1
return(1)
fact(n) = n × fact(n − 1) else:
return(n * fact(n-1))

Insertion sort def isort(l):

isort([ ]) = [ ] if l == []:
isort([x0 , x1 , . . . , xn ]) =
return(l)
insert(isort([x0 , x2 , . . . , xn−1 ]), xn ) else:
return(insert(isort(l[:-1]),l[-1]))

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 3/9

Optimal substructure property

Solution to original problem can be Factorial

derived by combining solutions to fact(0) = 1
subproblems
fact(n) = n × fact(n − 1)

Insertion sort
isort([ ]) = [ ]
isort([x0 , x1 , . . . , xn ]) =
insert(isort([x0 , x2 , . . . , xn−1 ]), xn )

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 4/9

Optimal substructure property

Solution to original problem can be Factorial

derived by combining solutions to fact(0) = 1
subproblems
fact(n) = n × fact(n − 1)
fact(n−1) is a subproblem of fact(n)
Insertion sort
So are fact(n−2), fact(n−3), . . . ,
isort([ ]) = [ ]
fact(0)
isort([x0 , x1 , . . . , xn ]) =
insert(isort([x0 , x2 , . . . , xn−1 ]), xn )

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 4/9

Optimal substructure property

Solution to original problem can be Factorial

derived by combining solutions to fact(0) = 1
subproblems
fact(n) = n × fact(n − 1)
fact(n−1) is a subproblem of fact(n)
Insertion sort
So are fact(n−2), fact(n−3), . . . ,
isort([ ]) = [ ]
fact(0)
isort([x0 , x1 , . . . , xn ]) =
isort([x0 , x1 , . . . , xn−1 ]) is a subproblem insert(isort([x0 , x2 , . . . , xn−1 ]), xn )
of isort([x0 , x1 , . . . , xn ])
So is isort([xi , . . . , xj ]) for any
0≤i <j ≤n

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 4/9

Interval scheduling

IIT Madras has a special video

classroom for delivering online lectures
Different teachers want to book the
classroom
Slot for instructor i starts at s(i) and
finishes at f (i)
Slots may overlap, so not all bookings
can be honoured
Choose a subset of bookings to
maximize the number of teachers who
get to use the room

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 5/9

Interval scheduling

IIT Madras has a special video Subproblems

classroom for delivering online lectures
Each subset of bookings is a subproblem
Different teachers want to book the
classroom
Slot for instructor i starts at s(i) and
finishes at f (i)
Slots may overlap, so not all bookings
can be honoured
Choose a subset of bookings to
maximize the number of teachers who
get to use the room

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 5/9

Interval scheduling

IIT Madras has a special video Subproblems

classroom for delivering online lectures
Each subset of bookings is a subproblem
Different teachers want to book the
Generic greedy strategy
classroom
Slot for instructor i starts at s(i) and Pick one request from those in
finishes at f (i) contention
Eliminate bookings in conflict with this
Slots may overlap, so not all bookings
choice
can be honoured
Solve the resulting subproblem
Choose a subset of bookings to
maximize the number of teachers who
get to use the room

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 5/9

Subproblems . . .

Each subset of bookings is a subproblem Generic greedy strategy

Pick one request from those in

contention
Eliminate bookings in conflict with this
choice
Solve the resulting subproblem

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 6/9

Subproblems . . .

Each subset of bookings is a subproblem Generic greedy strategy

Given N bookings, 2N subproblems Pick one request from those in

contention
Eliminate bookings in conflict with this
choice
Solve the resulting subproblem

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 6/9

Subproblems . . .

Each subset of bookings is a subproblem Generic greedy strategy

Given N bookings, 2N subproblems Pick one request from those in

contention
Greedy strategy looks at only a small
fraction of subproblems Eliminate bookings in conflict with this
choice
Solve the resulting subproblem

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 6/9

Subproblems . . .

Each subset of bookings is a subproblem Generic greedy strategy

Given N bookings, 2N subproblems Pick one request from those in

contention
Greedy strategy looks at only a small
fraction of subproblems Eliminate bookings in conflict with this
choice
Each choice rules out a large number
of subproblems Solve the resulting subproblem

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 6/9

Subproblems . . .

Each subset of bookings is a subproblem Generic greedy strategy

Given N bookings, 2N subproblems Pick one request from those in

contention
Greedy strategy looks at only a small
fraction of subproblems Eliminate bookings in conflict with this
choice
Each choice rules out a large number
of subproblems Solve the resulting subproblem
Greedy strategy needs a proof of
optimality

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 6/9

Weighted Interval scheduling

Same scenario as before but each

request comes with a weight
For instance, the room rent for using
the resource

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 7/9

Weighted Interval scheduling

Same scenario as before but each

request comes with a weight
For instance, the room rent for using
the resource

Revised goal: maximize the total weight

of the bookings that are selected
Not the same as maximizing the
number of bookings selected

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 7/9

Weighted Interval scheduling

Same scenario as before but each

request comes with a weight
For instance, the room rent for using
the resource

Revised goal: maximize the total weight

of the bookings that are selected
Not the same as maximizing the
number of bookings selected

Greedy strategy for unweighted case

Select request with earliest finish time

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 7/9

Weighted Interval scheduling

Same scenario as before but each Not a valid strategy any more
request comes with a weight
weight 1
For instance, the room rent for using
the resource
weight 3
Revised goal: maximize the total weight
of the bookings that are selected weight 1
Not the same as maximizing the
number of bookings selected

Greedy strategy for unweighted case

Select request with earliest finish time

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 7/9

Weighted Interval scheduling

Same scenario as before but each Not a valid strategy any more
request comes with a weight
weight 1
For instance, the room rent for using
the resource
weight 3
Revised goal: maximize the total weight
of the bookings that are selected weight 1
Not the same as maximizing the
number of bookings selected
Search for another greedy strategy that
Greedy strategy for unweighted case works . . .
Select request with earliest finish time

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 7/9

Weighted Interval scheduling

Same scenario as before but each Not a valid strategy any more
request comes with a weight
weight 1
For instance, the room rent for using
the resource
weight 3
Revised goal: maximize the total weight
of the bookings that are selected weight 1
Not the same as maximizing the
number of bookings selected
Search for another greedy strategy that
Greedy strategy for unweighted case works . . .
Select request with earliest finish time
. . . or look for an inductive solution that
is “obviously” correct

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 7/9

Weighted Interval scheduling

Order the bookings by starting time,

b1 , b2 , . . . , bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time,

b1 , b2 , . . . , bn
Begin with b1

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time,

b1 , b2 , . . . , bn
Begin with b1
Either b1 is part of the optimal
solution, or it is not

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time,

b1 , b2 , . . . , bn
Begin with b1
Either b1 is part of the optimal
solution, or it is not
Include b1 ⇒ eliminate conflicting
requests in b2 , . . . , bn and solve
resulting subproblem

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time,

b1 , b2 , . . . , bn
Begin with b1
Either b1 is part of the optimal
solution, or it is not
Include b1 ⇒ eliminate conflicting
requests in b2 , . . . , bn and solve
resulting subproblem
Exclude b1 ⇒ solve subproblem
b2 , . . . , bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time,

b1 , b2 , . . . , bn
Begin with b1
Either b1 is part of the optimal
solution, or it is not
Include b1 ⇒ eliminate conflicting
requests in b2 , . . . , bn and solve
resulting subproblem
Exclude b1 ⇒ solve subproblem
b2 , . . . , bn
Evaluate both options, choose the
maximum

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time, Inductive solution considers all options
b1 , b2 , . . . , bn
Begin with b1
Either b1 is part of the optimal
solution, or it is not
Include b1 ⇒ eliminate conflicting
requests in b2 , . . . , bn and solve
resulting subproblem
Exclude b1 ⇒ solve subproblem
b2 , . . . , bn
Evaluate both options, choose the
maximum

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time, Inductive solution considers all options
b1 , b2 , . . . , bn For each bj , optimal solution either
has bj or does not
Begin with b1
Either b1 is part of the optimal
solution, or it is not
Include b1 ⇒ eliminate conflicting
requests in b2 , . . . , bn and solve
resulting subproblem
Exclude b1 ⇒ solve subproblem
b2 , . . . , bn
Evaluate both options, choose the
maximum

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time, Inductive solution considers all options
b1 , b2 , . . . , bn For each bj , optimal solution either
has bj or does not
Begin with b1
For b1 , we have explicitly checked
Either b1 is part of the optimal both cases
solution, or it is not
Include b1 ⇒ eliminate conflicting
requests in b2 , . . . , bn and solve
resulting subproblem
Exclude b1 ⇒ solve subproblem
b2 , . . . , bn
Evaluate both options, choose the
maximum

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time, Inductive solution considers all options
b1 , b2 , . . . , bn For each bj , optimal solution either
has bj or does not
Begin with b1
For b1 , we have explicitly checked
Either b1 is part of the optimal both cases
solution, or it is not
If b2 is not in conflict with b1 , it will
Include b1 ⇒ eliminate conflicting be considered in both subproblems,
requests in b2 , . . . , bn and solve with and without b1
resulting subproblem
Exclude b1 ⇒ solve subproblem
b2 , . . . , bn
Evaluate both options, choose the
maximum

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time, Inductive solution considers all options
b1 , b2 , . . . , bn For each bj , optimal solution either
has bj or does not
Begin with b1
For b1 , we have explicitly checked
Either b1 is part of the optimal both cases
solution, or it is not
If b2 is not in conflict with b1 , it will
Include b1 ⇒ eliminate conflicting be considered in both subproblems,
requests in b2 , . . . , bn and solve with and without b1
resulting subproblem
If b2 is in conflict with b1 , it will be
Exclude b1 ⇒ solve subproblem considered in the subproblem where b1
b2 , . . . , bn is excluded
Evaluate both options, choose the
maximum

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

Weighted Interval scheduling

Order the bookings by starting time, Inductive solution considers all options
b1 , b2 , . . . , bn For each bj , optimal solution either
has bj or does not
Begin with b1
For b1 , we have explicitly checked
Either b1 is part of the optimal both cases
solution, or it is not
If b2 is not in conflict with b1 , it will
Include b1 ⇒ eliminate conflicting be considered in both subproblems,
requests in b2 , . . . , bn and solve with and without b1
resulting subproblem
If b2 is in conflict with b1 , it will be
Exclude b1 ⇒ solve subproblem considered in the subproblem where b1
b2 , . . . , bn is excluded
Evaluate both options, choose the ...
maximum

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 8/9

The challenge

b1 is in conflict with b2 , but both are

compatible with b3 , b4 , . . . , bn

b1
b2
b3
b4
· · · bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 9/9

The challenge

b1 is in conflict with b2 , but both are

compatible with b3 , b4 , . . . , bn
Choose b1 ⇒ subproblem b3 , . . . , bn

b1
b2
b3
b4
· · · bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 9/9

The challenge

b1 is in conflict with b2 , but both are

compatible with b3 , b4 , . . . , bn
Choose b1 ⇒ subproblem b3 , . . . , bn
Exclude b1 ⇒ subproblem b2 , . . . , bn

b1
b2
b3
b4
· · · bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 9/9

The challenge

b1 is in conflict with b2 , but both are

compatible with b3 , b4 , . . . , bn
Choose b1 ⇒ subproblem b3 , . . . , bn
Exclude b1 ⇒ subproblem b2 , . . . , bn
Next stage:
Choose/exclude b2

b1
b2
b3
b4
· · · bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 9/9

The challenge

b1 is in conflict with b2 , but both are

compatible with b3 , b4 , . . . , bn
Choose b1 ⇒ subproblem b3 , . . . , bn
Exclude b1 ⇒ subproblem b2 , . . . , bn
Next stage:
Choose/exclude b2
Both choices result in b3 , . . . , bn ,
same subproblem

b1
b2
b3
b4
· · · bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 9/9

The challenge

b1 is in conflict with b2 , but both are Inductive solution generates same

compatible with b3 , b4 , . . . , bn subproblem at different stages
Choose b1 ⇒ subproblem b3 , . . . , bn
Exclude b1 ⇒ subproblem b2 , . . . , bn
Next stage:
Choose/exclude b2
Both choices result in b3 , . . . , bn ,
same subproblem

b1
b2
b3
b4
· · · bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 9/9

The challenge

b1 is in conflict with b2 , but both are Inductive solution generates same

compatible with b3 , b4 , . . . , bn subproblem at different stages
Choose b1 ⇒ subproblem b3 , . . . , bn Naive recursive implementation
Exclude b1 ⇒ subproblem b2 , . . . , bn evaluates each instance of subproblem
Next stage: from scratch
Choose/exclude b2
Both choices result in b3 , . . . , bn ,
same subproblem

b1
b2
b3
b4
· · · bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 9/9

The challenge

b1 is in conflict with b2 , but both are Inductive solution generates same

compatible with b3 , b4 , . . . , bn subproblem at different stages
Choose b1 ⇒ subproblem b3 , . . . , bn Naive recursive implementation
Exclude b1 ⇒ subproblem b2 , . . . , bn evaluates each instance of subproblem
Next stage: from scratch
Choose/exclude b2 Can we avoid this wasteful
Both choices result in b3 , . . . , bn , recomputation?
same subproblem

b1
b2
b3
b4
· · · bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 9/9

The challenge

b1 is in conflict with b2 , but both are Inductive solution generates same

compatible with b3 , b4 , . . . , bn subproblem at different stages
Choose b1 ⇒ subproblem b3 , . . . , bn Naive recursive implementation
Exclude b1 ⇒ subproblem b2 , . . . , bn evaluates each instance of subproblem
Next stage: from scratch
Choose/exclude b2 Can we avoid this wasteful
Both choices result in b3 , . . . , bn , recomputation?
same subproblem
Memoization and dynamic programming
b1
b2
b3
b4
· · · bn

Madhavan Mukund Dynamic Programming PDSA using Python Week 9 9/9