Assignment3 - D.P Flashcards
Weighted activities problem with initial cost
Describe the problem
Note: description of a problem contains:
- An instance
- A legal solution
- An optimal solution(what we shall find)
Weighted activities problem with initial cost
describe:
- A typical sub problem
- The corresponding set of solutions
- Define corresponding OPT value
NOTE:
we should first think of the subsets which construct the set of solutions. Then define a subproblem. “which solutions for sub problems can help you find the solution for opt quite immidietly?”
Weighted activities problem with initial cost
divide the set of solutions into subsets and construct the formula
Weighted activities problem with initial cost
what is the proof for the formula construct?
Weighted activities problem with initial cost
describe the iterative algorithm
Weighted activities problem with initial cost
what is the run-time of the iterative algorithm?
Weighted activities problem with initial cost
describe the reconstruction algorithm
Always remember the base case!
Weighted activities problem with initial cost
- what is the assumption used in the proof of the reconstruction algorithm. Recall, we always proof relying on the assumption.*
- what is the correctness theorem?*
- what is the helping theorem?*
- The assumption:*
- The value contained in M[i] is OPT(i)*
- Correctness theorem:*
Based on the assumption, the algorithm returns an optimal solution for the problem.
- Helping theorem:*
- Based on the assumption, for every k([0,n]) the recover(k) call returns a solution I in Sol(k) with the value M[k].*
Weighted activities problem with initial cost
how is the main theorem and helping theorem proved, in the reconstruction algorithm?
The thrifty traveler
recall the formal definition
The thrifty traveler
define Sol and OPT
The thrifty traveler
describe the subsets of the solution set
The thrifty traveler
what is the construction formula?
The thrifty traveler
describe the proof for the construction formula
The thrifty traveler
describe the algorithm and the construction algorithm
