DynamicProgramming_and_DivideAndConquer

6 flashcards · Computer Science · by marvinamari

1. What are the steps to dynamic programming solution?

   Start with generic solution then apply problem specific details. Find the subproblem Define subproblem in words Define problem in terms of indexes e.g. (i, j) Add applicable constraints i.e. including or excluding last character. Find Recurrence Include base case State your ranges Define current problem as a relationship of smaller subproblems. i.e. T(i, j) in terms T(i-1, j), T(i, j-1) Write algorithm pseudocode Must include base case and return answer Analyze Runtime.

2. What are indications you are answering a LIS (Longest Increasing Subsequence) problem?

   The problem only has one array Problem is comparing to itself Problem only looks back one element at a time

3. What are the two variations of LIS (Longest Increasing Subsequence)?

   LIS with O(n) lookback: used if you need to check ALL previous elements used if you need to check ALL previous elements > or < some requirement. Running time O(n2)O(n^2)O(n2) LIS with O(1) lookback. used if you need to check one element back used if you need to check a constant number of elements back. used if your restriction moves forward with i. used when you need to carry the max, sum, count, etc forward, since you carry the answer forward you only compare against i-1. Running time O(n)O(n)…

4. What are indications you are answering a LCS (Longest Common Subsequence) problem?

   The problem is comparing between two arrays. Problem is looking for something in common. Solutions normally a 2D table.

5. What is the Masters Theorem and how do you know if you can use it?

   Masters theorem is a methodology to solve recurrences. You know you can use the Masters theorem because the recurrence must be of the form: 1"> T(n)=aT(nb)+f(n);a≥1,b>1T(n) = aT(\frac{n}{b}) + f(n) ; a \geq 1 , b > 1T(n)=aT(bn​)+f(n);a≥1,b>1

6. Describe the 3 cases of the Masters Theorem

   Case1 IF: f(n)=O(nlogba−ϵ)f(n) = O(n^{log_ba - \epsilon})f(n)=O(nlogb​a−ϵ) for some 0"> ϵ>0\epsilon > 0ϵ>0 THEN: T(n)=θ(nlogba)T(n) = \theta(n^{log_ba})T(n)=θ(nlogb​a) Example: T(n)=9T(n3)+nT(n) = 9T(\frac{n}{3}) + nT(n)=9T(3n​)+n here a=9;b=3;f(n)=na=9; b=3; f(n)=na=9;b=3;f(n)=n logba=log39=2log_ba = log_39 = 2logb​a=log3​9=2 O(nlog39−ϵ)=O(n2−ϵ)O(n^{log_39-\epsilon}) = O(n^{2-\epsilon})O(nlog3​9−ϵ)=O(n2−ϵ) let ϵ=1\epsilon =1ϵ=1 since case says it must be > 0, therefore O(n2−1)=O(n)O(n^{2-1}) =…