Dynamic programming

Question 1

What is the basic idea behind dynammic programming?

Answer 1

• Dynammic programming solves problems by combining the solutions to subproblems.*
• Dynamic programming is applicable when the sub problems are not independent, that is, when sub problems share subsubproblems.*
• A dynamic-programming algorithm solves every subsubproblem just once and then saves its answer in a table.*
• Dynamic programming is typically applied to optimization problems. There are many solution, and we wish to find an optimal one.*

Question 2

What are the 4 steps of dynamic programming?

Answer 2

• 1. Characterize the structure of OPT*
• 2. Recursively define the value of OPT*
• 3. Compute the value of OPT in a bottom-up fashion*
• 4. Construct OPT from computed information*
• Step 4 can be ommited if only the value of an optimal solution is required.*
• When we do perform step 4, we sometimes maintain additional information during step 3 to ease the construction of OPT.*

Question 3

What shall we do if we found a working recursion which is not efficient?(becuase it computes the same subproblem over and over again)

Answer 3

• We arrange for each subproblem to be solved only once, saving its solution.*
• Dynamic programming uses additional memory to save computation time*
• Dynamic programming approach runs in polynomial time when the number of* distinct sub problems involved is polynomial in the input size.

Question 4

There are usually two equivalent ways to implement a dynamic-programming approach. What are they?

Answer 4

top-down with memoization

• we write the procedure recursively in a natural manner, but modified to save the result of each subproblem.(usually in an array)
• this method first checks to see whether it has previously solved this problem. If so, it returns the saved value, else it computes it.

bottom-up method

• this method is derived from the notion that solving any particular subproblem depends only on solving “smaller” subproblems.
• we sort the subproblems by size and solve them in size-order, smallest first. When solving a partricular subproblem we already solved all of the smaller problems its solution depends upon, and we have saved their solutions.

Question 5

Rod cutting problem

can you describe the recursive alogirthm which runs in exponential time?

Answer 5

Question 6

Rod cutting problem

Describe top-down with memoization algorithm

Answer 6

Question 7

Rod cutting problem

describe the bottom-up algorithm

Answer 7

Question 8

• Rod cutting problem*
• describe the extended bottom-up algorithm, where we wish to print the solution.*

Answer 8

Question 9

What are the steps in solving a problem using dynammic programming?

Answer 9

Question 10

Matrix-chain multiplication

give a formal definition of the problem

Answer 10

Question 11

Matrix-chain multiplication

describe the subproblems and OPT

Answer 11

Question 12

Matrix-chain multiplication

describe the formula

Answer 12

Question 13

Matrix-chain problem

What are the base cases?

Answer 13

• The base cases are subproblems which suggest an immidiate result.*
• In the Matrix-chain problem, every instance of the problem with only one matrix is a base case. There is only one solution which is 0 - no multiplication is needed.*

Question 14

• Matrix-chain problem*
• what is the proof for the formula?*
• *notice how we start with OPT[i,j] and using definitions (and a theorem), we end up with a recursive defintion, as in the formula.*

Answer 14

Question 15

Matrix-Chain

describe the top-down solution

Answer 15

Question 16

Matrix-chain

describe the bottom-up algorithm

Answer 16

Question 17

Matrix-chain

can you recall the table-sketch for the matrix-chain problem?

Answer 17

Question 18

What do we need to prove in the bottom-up algorithm?

Answer 18

1. prove that once our algorithm encounters a new subproblem it has already computed the subsubproblems for our subproblem
2. prove that the computation of a subproblem returns the value of OPT(subproblem) we defined in the formula.

Question 19

• Matrix-Chain*
• describe the reconstruction algorithm*

Answer 19

Question 20

The knapsack problem

describe the problem

Answer 20

Question 21

The knapsack problem

define the set of solutions for a typical subproblem and their OPT

Answer 21

Question 22

The knapsack problem

divide the set of solutions into subsets

Answer 22

Question 23

The knapsack problem

describe the structure formula

Answer 23

Question 24

The knapsack problem

• in which two theorems we use in order to prove the formula.*
• Tip: recall the formula; OPT is divided into cases, what is not trivial and needs to be needs to be explained*

Answer 24

Question 25

The knapsack problem

• describe the proof for the 2nd theorem.*
• recall: Normally we prove by defining two sets and show equality between them.*

Answer 25

Question 26

The knapsack problem

describe the proof for the formula structure

Answer 26

Question 27

The knapsack problem

describe the iterative algorithm

Answer 27

Question 28

The knapsack problem

correctness proof

Answer 28

Question 29

The snapsack problem

The run-time for the iteration algorithm is quite bizzare. Describe it

Answer 29

Question 30

The knapsack problem

describe the reconstruction algorithm

Answer 30

Question 31

The knapsack problem

what is the proof for the reconstruction algorithm?

Answer 31

Question 32

Optimal substructure varies across problem domains in two ways, what are they?

Answer 32

1. How many subproblems an optimal solution to the original problem uses
2. How many choices we have in determining which sub problems to use in an optimal solution.

Question 33

The running time of a dynamic problem algorithm depends on the product of two factors:

Answer 33

• The number of subproblems overall
• How many choices we look at for each subproblem

Question 34

If subproblems are not independent we cannot obtain an optimal structure. Give an example of dependence of sub problems in the unweighted longest simple path problem

Answer 34

Assume we decompose the longest simple path from s to v, P= {s,..,k,..v} into two paths:

• longest simple path from s to k
• longest simple path from k to v
• Now, it might happen that both in the first path and the second we pass through vertex t - creating a circle. The 2nd subproblem requires the 1st to not hold any of the vertices of its path. Thus these two are dependent.*
• With shortest path it cannot happen.*
• Consider the path P ={s,…k,…v} and its two subpaths:*
• shortest path from s to k
• shortest path from k to v
• Assume both the shortest path from s to k and the shortest path from k to v pass through vertex t.*
• That means vertex “k” is not needed, we could move from s to t, and from t to k - which is shorter. contradicition.*

Question 35

Important point of “transforming” a dynamic programming problem, to such that can’t be solve dynamically.

Answer 35

Main point is that we turned the subproblems from beind independent to being dependent.