Chapitre 2: Dynamic Programming

Fibonacci numbers
18:21

Definition (Fibonacci numbers)

1123581321 \dots

Exercise

Write a Python code that calculates Fibonacci numbers

Question

What happens if you calculate the $50$ th Fibonacci numbers? What is the running time of the above code?

Memoization
18:21

Definition (Memoization)

Optimization technique used to speed up programs by caching the results of expensive function calls and returning them when the same inputs are encountered again.

Exercise

Write a memoized version of fibonacci(n)

Question

What's the time complexity?

Memoization in real-life Python
18:21

In practice, there is a decorator that does all the work for you.

Bottom-up
18:21

Question

With the memoized function, the space complexity in $O (n)$ . Can you write an algorithm with $O (1)$ space complexity?

Dynamic programming
18:21

Question

What is dynamic programming?

Problem is broken down into overlapping subproblems
Results of the subproblems are saved
Solve the original problem

Two ways:

Top down (recurse + memoize)
Bottom up

Rod cutting
18:21

Question (Rod cutting problem)

What is the highest revenue we can get by cutting an $n$ feet rod and selling the pieces?

Length	1	2	3	4	5	6	7	8	9
Price	1	5	8	9	10	17	17	20	24

Question

What would the runtime be if we brute-force this problem and try all rod-cutting combinations?

Bottom-up version of rod cutting
18:21

Exercise

Write a bottom-up version of cut_rod

Question

What are the time and space complexities?

Rod cutting: exercises
18:21

Exercises

What if we want to know the actual cuts and not just the value?
What if the process of cutting itself had a cost?

Exercises
18:21

Dynamic programming
18:21

	Fibonacci	Rod cutting
Subproblems
Relate
Original
Order
Base cases
Running time

Remark

Time complexity = # subproblems \times non-recursive work

Longest Common subsequence
18:21

Problem (Longest Common Subsequence)

Given two sequences A and B, find the longest sequence L that's a subsequence of both A and B.

Example

A LCS of "hieroglyphology" and "michaelangelo" is "hello".

Exercise

Determine an LCS of

10010101010110110

Exercise

What is the time complexity of the naive brute-force algorithm?

Problem analysis
18:21

Subproblems: C[i,j] denotes the length of LCS of X[:i] and X[:j]
Base cases: C[0,j] = C[i, 0] = 0
Recurrence: $C [i, j] = ⎩ ⎨ ⎧ 0 C [i - 1, j - 1] + 1 max {C [i, j - 1], C [i - 1, j]} if ij = 0 if ij > 0 and X [i - 1] = Y [j - 1] otherwise$

Top-down implementation
18:21

Exercise

Write a top-down implementation of LCS

Towards the bottom-up implementation
18:21

		T	H	E	I	R
	0
H
A
B
I
T

		B	D	C	A	B	A
	0
A
B
C
B
D
A
B

LCS: Python implementation
18:21

Exercise

Below is a bottom-up implementation of LCS. What's its time complexity?

Parent pointers
18:21

We'll use parent pointers to relate a subproblem to its parent.

		T	H	E	I	R
	0
H
A
B
I
T

Exercise

Find the LCS using parent pointers.

		B	D	C	A	B	A
	0
A
B
C
B
D
A
B

LCS: Python implementation with parent pointers
18:21

Exercise

Change the implementation so it actually computes the LCS and not only its length.

Longest increasing subsequence
18:21

Problem (Longest increasing Subsequence)

Given a sequence A, find the longest subsequence L of A consisting of increasing numbers.

Example

An LIS of "carbohydrate" would be "abort"

Analysis of the problem
18:21

	Longest increasing subsequence
Subproblems
Relate
Original
Order
Base cases
Running time

Exercise

Implement the LIS algorithm in Python.

Knapsack
18:21

Problem

$n$ objects and a knapsack
Item $i$ weighs $w_{i}$ and has value $v_{i}$
Knapsack has capacity of $W$
Goal is to fill knapsack and maximize total value

Example

#	value	weight
1	1	1
2	6	2
3	18	5
4	22	6
5	28	7

If $W = 11$ , the optimal choice is to take items 3 and 4.

Analysis of the knapsack problem
18:21

	Knapsack
Guess
Subproblems
Relate
Original
Order
Base cases
Running time

Knapsack: top-down implementation
18:21

Exercise

Write a top-down implementation of the Knapsack problem

Knapsack: towards the bottom-up implementation
18:21

Use the idea of parent pointers to reconstruct the solution.

	0	1	2	3	4	5	6	7	8	9	10	11
{}
{1}
{1, 2}
{1, 2, 3}
{1, 2, 3, 4}
{1, 2, 3, 4, 5}

#	value	weight
1	1	1
2	6	2
3	18	5
4	22	6
5	28	7

Bottom-Up implementation of Knapsack
18:21

Exercise

Write a bottom-up implementation of Knapsack. Use parent pointers to construct the original solution.

Running-time: pseudo-polynomial
18:21

Proposition

T (n) = O (nW)

Remark

Storing $W$ in memory requires $O (lo g_{2} W)$ bit. Knapsack is therefore exponential in the input size, but polynomial in the input. We say it's a pseudo-polynomial algorithm.

Exercises: Question 4
18:21

Fibonacci numbers18:21

Definition (Fibonacci numbers)

Exercise

Question

Memoization18:21

Definition (Memoization)

Exercise

Question

Memoization in real-life Python18:21

Bottom-up18:21

Question

Dynamic programming18:21

Question

Rod cutting18:21

Question (Rod cutting problem)

Question

Top down solution18:21

Question

Bottom-up version of rod cutting18:21

Exercise

Question

Rod cutting: exercises18:21

Exercises

Exercises18:21

Dynamic programming18:21

Remark

Longest Common subsequence18:21

Problem (Longest Common Subsequence)

Example

Exercise

Exercise

Problem analysis18:21

Top-down implementation18:21

Exercise

Towards the bottom-up implementation18:21

LCS: Python implementation18:21

Exercise

Parent pointers18:21

Exercise

LCS: Python implementation with parent pointers18:21

Exercise

Longest increasing subsequence18:21

Problem (Longest increasing Subsequence)

Example

Analysis of the problem18:21

Exercise

Knapsack18:21

Problem

Example

Analysis of the knapsack problem18:21

Knapsack: top-down implementation18:21

Exercise

Knapsack: towards the bottom-up implementation18:21

Bottom-Up implementation of Knapsack18:21

Exercise

Running-time: pseudo-polynomial18:21

Proposition

Remark

Exercises: Question 418:21

Fibonacci numbers
18:21

Memoization
18:21

Memoization in real-life Python
18:21

Bottom-up
18:21

Dynamic programming
18:21

Rod cutting
18:21

Top down solution
18:21

Bottom-up version of rod cutting
18:21

Rod cutting: exercises
18:21

Exercises
18:21

Dynamic programming
18:21

Longest Common subsequence
18:21

Problem analysis
18:21

Top-down implementation
18:21

Towards the bottom-up implementation
18:21

LCS: Python implementation
18:21

Parent pointers
18:21

LCS: Python implementation with parent pointers
18:21

Longest increasing subsequence
18:21

Analysis of the problem
18:21

Knapsack
18:21

Analysis of the knapsack problem
18:21

Knapsack: top-down implementation
18:21

Knapsack: towards the bottom-up implementation
18:21

Bottom-Up implementation of Knapsack
18:21

Running-time: pseudo-polynomial
18:21

Exercises: Question 4
18:21