dynamic programming

Question 1

what is dynamic programming

Answer 1

Dynamic Programming is an algorithm design technique
for optimization problems
– Often minimizing or maximizing an answer
- Reusing computation

Question 2

Contrast the Divide and Conquer and Dynamic Programming
approaches to solving problems

Answer 2

Like Divide & Conquer, DP solves problems by combining
solutions to subproblems, they are recursive

Unlike Divide & Conquer, subproblems are not independent. Overlapping or repeated subproblems, DP has optimization, DP has storage

D&C solves independent subproblems recursively, while DP solves overlapping subproblems and stores their solutions

Question 3

Identify when Dynamic Programming should be used to solve a problem

Answer 3

Properties of a problem that can be solved
with DP

• Simple Subproblems
  – We should be able to break the original problem to
  smaller subproblems that have the same structure
• Optimal Substructure of the problems
  – The solution to the problem must be a composition
  of subproblem solutions
• Subproblem Overlap
  – Same subproblems are solved multiple times during
  the computation process

Question 4

Define the Principle of Optimality

Answer 4

• The principle of optimality is applied in a problem if
  an optimal solution for a problem includes optimal solutions
  for all sub-problems
• If the principle holds, we can provide a recursive solution
  and obtain optimal solutions from smaller ones

Question 5

what is the difference between memoization and tabulation in DP?

Answer 5

memoization uses a top down approach, while tabulation uses a bottom up approach

Question 6

what does matrix chain multiplication solve

Answer 6

given n matrices, what is the least expensive order to multiply them in

Question 7

what does the knapsack problem solve

Answer 7

how to maximize the total value of items while the total weight remains below the limit

Question 8

what does longest common subsequence problem solve

Answer 8

To find one of the longest common subsequences of a pair of sequences

Question 9

what does optimal binary search trees solve

Answer 9

Want to build a binary search tree (BST) with
minimum expected search cost.

Expected search cost is based on probability that we are searching for a given value, and its height.