Week 6

Question 1

What is dynamic programming?

Answer 1

• A technique for solving optimisation problems
• similar solution to divide and conquer except the recursive calls are replaced by reference to a table of values computed by subproblems of the original problem

Question 2

How is a problem solved by dynamic programming?

Answer 2

1. characterise the structure, key elements and parameters of the problem and how they related to each other
2. define the value of the optimal solution recursively, express the optimal solution in terms of it’s subproblems
3. define base cases (subproblems that can be solved directly/need no further decomposition)
4. define a recurrence relation which tells us the relationship between subproblems
5. Solve the subproblems and combine them to obtain the solution of the original problem

Question 3

What type of problem are dynamic programming solutions used to typically solve?

Answer 3

Optimisation problems
- that have a maximising or minimising function
- applied where brute force is infeasible

Question 4

What are the 3 features a problem must have to be effectively solved by dynamic programming?

Answer 4

1. must be able to break the problem into subproblems with a similar structure
2. the optimal solutions must be composed of the optimal solutions of subproblems
3. optimal solutions to some subproblems can contain subproblems in common (overlap)

Question 5

What is memoisation?

Answer 5

• Where computed values are stored in cache and later retrieved when they’re needed instead of recomputing them, in order to make applications more efficient/faster

Question 6

What can make the run time of a dynamic programming solution poor?

Answer 6

Subproblems overlap and recompute the same value over and over which is inefficient

Question 7

What is the naive dynamic programming runtime of calculating the fibonacci sequence?

Answer 7

O(2^n)

Question 8

What is the dynamic programming memoisation run time of calculating the fibonacci sequence?

Answer 8

• Removing recalculating values and taking them from a table give us O(n^2)

Question 9

What problems can we solve with dynamic programming?

Answer 9

• Calculating Fibonacci sequence
• {0,1} Knapsack Problem
• Weighted Interval Scheduling

Question 10

What is the dynamic programming runtime of the solution for the {0,1} Knapsack problem?

Answer 10

O(n*W)
- where n is the number of elements to be packed
- and W is the max weight the knapsack can hold
- inefficient as run time is exponential as Wmax is exponential?

Question 11

What is weighted interval scheduling?

Answer 11

• have a collection of tasks to schedule with a start and finish time but also a value Vi
• aim is to schedule a subset of non-conflicting tasks have the maximum total value

Question 12

What is the time complexity for finding the weighted interval scheduling problem solution using dynamic programming?

Answer 12

O(n*logn) since we use memoisation

Question 13

What can we use to prove that the dynamic programming solution for the weighted interval scheduling problem is correct?

Answer 13

We can use proof by induction
- since every succeeding task’s optimal solution can be calculated by the optimal solutions of preceeding tasks (computed and stored in the dynamic programming table),
- we can show that the induction base holds and then show the induction step also holds