Dynamic Programming/Greedy

Question 1

Dynamic Programming

Answer 1

• Algorithmic outline use to solve a certain class of problems
• Usually used to solve problems that can be modelled as a directed acylic graph
• Uses shortest paths in DAG algorithm to compute distance to a subproblem
• Such problems involve making “decisions” across a certain “time” axis

2 Requirements

1. Overlapping subproblems
2. Optimal substructure

Question 2

Subproblem

Answer 2

• An instance of the main problem with a “smaller” input
• Each vertex represents a subproblem
• Each vertex should have a unique input
• Solution to subproblem is usually “distance to” that vertex
• Subprombles must also be acyclic
• Subpromlues usually come in the form:
  
  • Prefix/Suffix ( O(n) )
  • Substring ( O(n2) )

Question 3

Overlapping Subproblems

Answer 3

• A problem is said to have overlapping subproblems if the subproblems repeat
• If subproblems don’t repeat, then its not dp, its divide and conquer

Question 4

Optimal Substructure

Answer 4

• A problem has optimal substructure if the solution to the main problem can be solved by combining solutions to the same problem with “smaller” inputs
• Both greedy and dynamic programming problems must exhibit optimal substructure

Ex:

• Shortest path from A-C = Path(A-B) + Path(B-C)
• optimal solution to the problem can be constructed from optimal solutions to subproblems
• Optimal solutions to a problem incorporate optimal solutions to related subproblems
• Optimal solution to problems contains, within it, optimal solutions to subproblems
• Those subproblems can be solved independently
• Necessary condition for dynamic programming and greedy algorithms
• ex:
  
  • fibo(10) = fibo(9) + fibo(8)
• Steps
  
  • Show that a solution to a subproblem consists of making a choice

Question 5

Memoization

Answer 5

• Using a “memo” to keep track of solutions to a subproblem
• Subproblem dependencies must be acyclic for memoization to work (otherwise, solution would get updated more than once)

Question 6

Recurrence Relationship

Answer 6

• the relationshi betwen subproblems
• the ability to write the solution to one problem in terms of the soluton to other problems

Ex:

• in shortest paths, shortest distance to point D is minimum of all distances to A,B,C + their edges

Question 7

Top Down

Answer 7

• An approach to DP that uses recursion/DFS

Steps

1. Establish recurrence relationship base case
2. Use DFS to minimize distance to vertex (that subproblem) across incoming edges
3. Record solution in memo
4. When unwinding DFS, algorithm will end up considering vertices in toplogical order

Question 8

Bottom Up

Answer 8

• An approach to dp that uses iteration to solve subproblems in topoligical order
• Basically finding shortest paths iteratively

Steps

1. Determine the topological order of the vertices (subproblems)
2. Loop through vertices in topological order
3. At each vertex, minimize over incoming edges, store dist_to (solution) in dp table
4. Final dist_to of incoming adjacent vertices should be known because you’re going in topological order

Question 9

Greedy

Answer 9

• Similar to DP, in theory
• May be implement completed differenly in practice
• Instead of considering all ‘choices’, you select one choice
• Generally, greedy algorithms can be rephrased as DP problems by including all choices

2 Requirements

1. Greedy choice property
2. Optimal substructure

Ex

• Fractional knapsack
  
  • Pour in all the gold, then all the silver, etc.

Question 10

Greedy Choice Property

Answer 10

• Similar to optimal substructure
• Making a greedy choice never eliminates the optimal solution
• This property says that globally optimal solution can obtained by making a locally optimal solution (greedy)