10. Maximum Sum Increasing Sub-sequence:
Problem: Given an array of numbers, a, find the sub sequence that holds the following properties
Problem: Given an array of numbers, a, find the sub sequence that holds the following properties
- It is in increasing order
- The sum is the maximum
Example: For {1, 101, 2, 3, 100, 4, 5}, the output would be 106 (1 + 2 + 3 + 100).
Recurrence: f(i) = max( f(j) + a[j] ), where, 0<= j < i and a[i] > a[j]
Base case: f(0) = a[0]
Runtime: Number of sub-problems = O(n)
Time to solve a sub-problem = O(n)
Total runtime = O(n ^ 2).
11. Largest Chain
Problem: Given n pairs find the maximum chain. 2 pairs (a, b) and (c,d) can form a chain if b < c.
Example: Given an array of pairs arr, {(5, 24), (39, 60), (15, 28), (27, 40), (50, 90) }, then the longest chain that can be formed is of length 3, and the chain is {(5, 24), (27, 40), (50, 90)}.
Recurrence: f(i) = max( f(j) ) + 1, where 0 <= j < i; arr[j][1] < arr[i][0]
Base case: f(0) = 1
Runtime: Number of sub-problems = O(n)
Time to solve a sub-problem = O(n)
Total runtime = O(n ^ 2)
12. Longest Common Substring
Problem: Given 2 strings, find the longest substring.
Example: Given, ϵABCDE, ϵXBCDG, then longest common substring = BCD. All string starts with empty, ϵ.
Recurrence:
{ if s1[i] == s2[j] then f(i-1, j-1) + 1
f(i, j) = {
{ max( f(i-1, j), f(i, j-1) )
Base case: f(i, j) = 0
Runtime: Number of sub-problems = O(n ^ 2) as we have 2 indices i, j.
Time to solve a subproblem = O(1)
Total runtime = O(n ^ 2)
13. Catalan number
Problem: (n+1) th Catalan number, C_(n+1) = sum ( C_i * C_(n-i) )
Recurrence: See above
base case, C_0 = 1
Runtime: Number of sub-problems = O(n)
Time to solve a sub-problem = O(n)
Total runtime = O(n ^ 2)
14. Count Number of Ways to Reach a Given Score
Problem: The array pts gives the achievable point from any state of a game. Given a point n, find the number of ways those points can be reached.
Recurrence: f(i) = sum(f(i - pts[k])) for all 0 <= k < lenght (pts)
Runtime: Number of sub-problems = O(n)
Time to solve a problem = O(k)
Total Runtime = O(n * k)
Problem: Given n pairs find the maximum chain. 2 pairs (a, b) and (c,d) can form a chain if b < c.
Example: Given an array of pairs arr, {(5, 24), (39, 60), (15, 28), (27, 40), (50, 90) }, then the longest chain that can be formed is of length 3, and the chain is {(5, 24), (27, 40), (50, 90)}.
Recurrence: f(i) = max( f(j) ) + 1, where 0 <= j < i; arr[j][1] < arr[i][0]
Base case: f(0) = 1
Runtime: Number of sub-problems = O(n)
Time to solve a sub-problem = O(n)
Total runtime = O(n ^ 2)
12. Longest Common Substring
Problem: Given 2 strings, find the longest substring.
Example: Given, ϵABCDE, ϵXBCDG, then longest common substring = BCD. All string starts with empty, ϵ.
Recurrence:
{ if s1[i] == s2[j] then f(i-1, j-1) + 1
f(i, j) = {
{ max( f(i-1, j), f(i, j-1) )
Base case: f(i, j) = 0
Runtime: Number of sub-problems = O(n ^ 2) as we have 2 indices i, j.
Time to solve a subproblem = O(1)
Total runtime = O(n ^ 2)
13. Catalan number
Problem: (n+1) th Catalan number, C_(n+1) = sum ( C_i * C_(n-i) )
Recurrence: See above
base case, C_0 = 1
Runtime: Number of sub-problems = O(n)
Time to solve a sub-problem = O(n)
Total runtime = O(n ^ 2)
14. Count Number of Ways to Reach a Given Score
Problem: The array pts gives the achievable point from any state of a game. Given a point n, find the number of ways those points can be reached.
Recurrence: f(i) = sum(f(i - pts[k])) for all 0 <= k < lenght (pts)
Runtime: Number of sub-problems = O(n)
Time to solve a problem = O(k)
Total Runtime = O(n * k)
No comments:
Post a Comment