[Algorithms][DP] Thinking in DP 3

10. Maximum Sum Increasing Sub-sequence:
Problem: Given an array of numbers, a, find the sub sequence that holds the following properties

1. It is in increasing order
2. 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)

[Story] Only the necessary things!

Oliver is a new driver. He has been trying to understand the basics of driving. Initially it seemed like a lot of rules, road signs and laws to deal with. When you are driving, you need to constantly look in front, look to the front at the left and right side of the road, using mirrors constantly check left and right of the car's back, using rear-view mirror check the back of the car. And every driving experience seemed to be a new experience. To him, all these aspects of driving seemed discrete and hard to relate.

Eventually he realized driving is mostly about doing the things that you absolutely need to do. For instance, driving faster than the speed limit is not necessary, if you want to change a lane and it is not safe to do so at the time then it is not necessary to change lane that moment of time, just take your time, keep going on, when it is safe, change lane. Also, it is not necessary to slam the break suddenly most of the time if you are paying attention.

Driving is about being conscious of the surrounding and do what is necessary. You need to know what is in front of you, what is far ahead, what is on your side and back.

You do not take action abruptly. You do not suddenly change lane or hit the break. If you want to change lane, you need to convey your intentions before hand by putting on turn signals so that other people on the road know what you are going to do. All other drivers will help you if you communicate properly and do not rush.

The intersections and lane changes are interesting parts. When you are on a intersection, this is the place where a road for two drivers overlaps. You need to be alert and let any car on the intersection go first. You need to clear the intersection as soon as you can safely. When you are changing lanes, you are attempting to get into other driver's drive way. Let them know your intention through signals, check blindspots to make absolutely sure that no car is in the place where you are trying to be. You need to speed up little bit while changing lane so that you do not interrupt the other driver's space.

At any given time, there are many people on the road with different state of mind. Some might be on rush, some might be new drivers like Oliver, some might be drunk or some might be having a medical condition. So it is very likely that something unexpected might happen. Some driver can cut in front him without proper signaling. Some pedestrian might be crossing the road dangerously, some driver can ignore the red signal or some driver can honk at him. It is good to accept the unexpected and act accordingly. Should something unexpected happens, he should not let go his cool, instead he should take it easy and accept these unexpectedness, take necessary steps and keep moving on without thinking about the past.


A few things driving teaches us

1. Know the rules of the road. We need to know what means what and should be aware of known incidents.
2. Safety first.
3. Know where you want to go and what you want to do.
4. Be mindful. Know what is in front, on sides and on back. 
5. Do not do anything if you absolutely have to do. For instance, you missed an Exit? Do not try to adjust your route right away and back up from there to exit. Instead keep moving on, take the next exit.
6. Do not take an action abruptly. Have a plan. Let others know what you are trying to do.
7. When sharing space with others, be extra careful (like when you are on an intersection or changing lanes).  
8. Expect the unexpected. Someone will always do something unexpected or stupid. Don't let stupid actions of others take your peace of mind. Take proper actions, keep moving on.

And surprisingly, the above are the basic teaching of Buddha!

[MATHEMATICS] Mendelbrot and Julia set

Background
When we define functions recursively, such as
f(t) = f(t-1) * f(t-1) + c
A few cases might arise, as we keep increasing number of iterations, t.
Converge: Eventually, f(t) might converge to a zero or non-zero number.
Diverge: f(t) might keep getting bigger and bigger.
Periodic: f(t) might oscillate among 2 or more values.
Chaos: f(t) might produce random values.

There are cases where a function behave might differently with the choice of base case and other constants in this case f(0) and c. For,
Example: f(t) = r * f(t - 1) * (1 - f(t - 1))
f(0) = 0.2, r = 1, f(t) converges to zero.
f(0) = 0.2, r = 2, f(t) converges to 0.52
f(0) = 0.2, r = 3, f(t) is a attenuating-oscillating function
f(0) = 0.2, r = 4 f(t) is a chaotic function

For a function, for a specific set of points in a closed boundary used as the choice for f(0) or c, the f(t) might converge or diverge fast or slowly.

Mendelbrot and Julia set
For Mendelbrot set, the function is defined as the following
f(t) = f(t-1) * f(t-1) + c
f(0) = 0 and c is chosen from numbers from complex number domain from the following rectangular boundary,
bottom-left = -2.25 -1.5i
top-right = 0.75 + 1.5i

Algorithm to generate the plot
We count number of iterations, t, for which magnitude(f(t)) reaches to 4. If f(t) converges, we say it took MAX_ITERATIONS to converge. We put computed iteration counts in a 2D array. Plotting the 2D array in 2D plane gives a visualization of the Mendelbrot set. Yellow regions depicts those points that converges so for them iterations count = MAX_ITERATIONS. Darker points say that they diverge very quickly.

f(0) = 0, c ranged from (-0.22 -0.7i to 0.75 -0.21i)

For Julia set, we fix c, and vary f(0) from a complex number boundary.

                              c = -0.35 + 0.65i and f(0) ranged from -2 to +2 in complex plane

c = -0.77 + 0.13i and f(0) ranged from -1 to +1 in complex plane

Reference:

0. Make your own Mendelbrot by Tariq Rashid

1. Github source code

[Algorithms][DP] Dynamic Programming Explained - 1

Dynamic programming systematically checks all possibility of a given problem.

To solve using dynamic programming, we need to come up with a way to recursively solve a problem. The recursion should be of format of DAG, a bigger sub problem should be depended on a smaller subproblem. Dynamic problem will not work if a smaller sub-problem depends on a bigger sub-problem.

Dynamic programming problem is a favorite choice of interviewers, at it tests understanding of recursion of an interviewee.

Steps to apply dynamic programming for a given problem
0. Check if the problem can be solved using recursion. Think if you have n items, can you solve the problem if you already know solution for n-1 th item. Consider each sub problem an optimal solution. If you know an optimal solution to all reachable lower state, how can you reach higher state with that knowledge.
1. If 0 holds, write the problem in terms of smaller problem. Observe how many variables you need. The number of variables determines the dimension of the array you will need to store solution.
2. Guesses is the number of steps your algorithm needs to combine small solutions to big solution.
3. From variables, determine how many sub problems will be there. Remember, recursive function calling is cheap O(1) time if dynamic programming is used. Guesses * number of sub problems will give the order of the algorithm.

Example:
problem: find fibonacci number

Using recursion:
fibonacci(i) = fibonacci(i-1) + fibonacci(i-2)

number variables is 1 (only i). Which means Number of sub problems = n;
Guesses = O(1) [fibonacci(i-1) + fibonacci(i-2) can be evaluated in O(1) time. Recursion is cheap for dp]

O(algorithm) = O(subproblem_count * guesses_at_each_subproblem) = O(n)

Another Example:
Rod cutting problem. An i lengthed rod can be cut in 2 spots. We need to find the maximum profit we can make out of it.

profit(i) = max(profit(j) + profit(i-j)) for all 0 < j < i-1

here # of variables = 1 => # subproblems = n
#guesses = O(n) [need to generate all points from 1 to i-1 for length i]

O(n * n) = O(n ^ 2)

Yet Another Example:
Knapsack problem
profit(i, capacity) = max(
                                         profit(i-1, capacity), //don't take i th element
                                         profit(i-1, capacity-w[i]) + val[i] //take ith element
                             )
we see 2 variables here. #subproblems = item_count * bag_capacity
#guesses = O(1)

O(algorithm) = O(item_count * bag_capacity)

this is a pseudo polynomial runtime. if bag_capacity is increases, we will need bigger array to store the intermediate results.

[AlgorithmS][DP] Thinking in DP -1

5. Longest Increasing sub sequence:
Problem: Given a sequence, find the longest increasing sub sequence. LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.
Recurrence: Given an Input array, I. Build an auxiliary array of same size as I, A such that.
A(i) = max(A(j)) + 1, if an entry is found in I, such that i > j and j >= 0 and I(i) > I(j)
else A(i) = 1
Base case: A(0) = 0
Runtime:
Number of sub-problems = O(n).
Time to solve a sub-problem = O(n), as to build A(i) we need to traverse A(0) through A(i-1).
Total runtime = O(n ^ 2).

6. Given available coin values, {a, b, c} what is the minimum number of coins required to give change for n Cents.
Recurrence: f(n) = min(f(n-a) + f(n-b) + f(n-c)) + 1
base case:
f(0) = 0
f(a) = 1
f(b) = 1
f(c) = 1
f(-coinval) = + infinity
Runtime: Number of sub-problems = O(n), time to solve a sub-problem = O(m), here is m is the size of coin types.
Total runtime = O(m * n)

7. Edit distance
Problem: Given two strings a and b, find minimum number of elementary character operations (insert, delete, replace) to convert a to b.
Example:
f(UTEP, KTEP) = 1 (replace U by K)
f(RATS, BAT) = 2 (replace R by B, delete S)
Recurrence:
f(i, j) = f(i - 1, j - 1) if a[i] == b[j] 
f(i, j) = min(f(i, j - 1), f(i - 1, j), f(i - 1, j - 1)) + 1 if a[i] != b[j]
base case:
f(0, 0) = 0
f(i, 0) = i
f(0, j) = j
Explanation: f(i, j) is the edit distance of string a[0...i] and b[0...j]. Let, a = FIAS, b = FITA.
Here, we want to compute f(3, 3). Here, a[3] != b[3] so we need to insert, delete or replace.
In string a, if we choose to,
insert   A then we need to convert          FIASA -> FITA   >> f(i, j - 1)
delete   S then we need to convert          FIA -> FITA        >> f(i - 1, j)
replace S by A then we need to convert FIAA -> FITA     >> f(i -1, j - 1)
Runtime: Number of subproblems = O(n ^ 2), we are constructing a 2D array.
Time to solve a sub problem = O(1)
Total order = O(n ^ 2)
Naive order: f(i, j) ~ 3f(i-1, j-1) = O(3 ^ n)
                                                                                                    
8. Cutting Rod
Problem: A rod with n length is given. Value of all rod length 1..n is given. Find the maximum profit can be obtained by cutting the rod in optimal way.
Recurrence:
f(n) = max( max(f(n-i) + f(i)) for n > i  > 0, val[n])
base case:
f(0) = 0
Explanation: n = 4. We need to know which one gives the most profit, the max of val[4], f(1) + f(3), f(2) + f(2).
Runtime:
Number of sub-problems = O(n).
Time to solve a sub-problem = O(n), as we need to traverse all the values f(0) to f(n-1).
Total runtime = O(n ^ 2)

9. Subset Sum
Problem: Given a set of numbers, S and a number n, find if any subset of S sums up to n.
Recurrence:
f(i, n) = f(i - 1, n) | f(i - 1, n - S[i])
base case:
f(0, n) = false where n > 0
f(i, 0) = true where i >= 0
Explanation: f(i, n) represents if a subset from S[0...i] sums to n.
f(i - 1, n) is if a subset of S[0...i-1] sums to n.
f(i - 1, n - S[i]) is if a subset of S[0...i-1] sums to n - S[i] if so then including S[i] would sum to n.
Runtime:
Number of sub-problems = O(|S| * n)
Time to solve one sub-problem = O(1)
Total runtime = O(|S| * n)
The order depends on the value n holds, this scenario is known as Pseudo-Polynomial.

[Algorithms][DP] Thinking in DP - 0

We will discuss a few problems and how to solve them using binary programming in this post.

0. n th fibonacci number:
Recurrence relation:
f(n) = f(n-1) + f(n-2)

Base case:
f(0) = 0
f(1) = 1

Complexity:
Number of sub problems = n,
Time to solve one sub problem = 0(1)
Total order = O(n)

Naive complexity: O(2 ^ n), as each recursive call will do full computation instead of using previous computed value.

1. n choose k (binomial coefficient)
Recurrence relationship:
f(n, k) = f(n-1, k-1) + f(n-1, k)
Explanation: 
From ABCD how many combination you can form taking only 3 of them?
Total combinations: ABD, ACD, BCD, ABC.

Ignore D first, compute how many 2 element item can be formed from ABC
AB, AC, BC. We can just add D at last position and we will get
ABD, ACD, BCD, this gives f(n-1, k-1).
Now, lets see how many 3 length String we can form from ABC (still ignoring D). Just 1, ABC.
this gives, f(n-1, k) 

Base case:
f(n, 0) = 1
f(n, n) = 1

Complexity:
From the equations, we will need to fill up a 2D array. Intuitively, it tells the order would be O(n ^ 2).
Number of subproblems: O(n ^ 2) [for each value of i of n, we will have to iterate all the values from 0 to i]
Time to solve one sub-problem: O(1)
Runtime = O(n^2)
Naive Complexity: O(2 ^ n)

2. Longest Common Sub-sequence:
Problem: Find the longest common sub-sequence of two strings.
Recurrence:
f(i, j) = if (a[i] == b[j])
                f(i - 1, j - 1) + 1
             else
                max(f(i, j - 1), f(i - 1, j))

Explanation: a = ABABDCD, b = AXBYCZ are two strings. Note that, the longest common sub-sequence is ABC. f(i, j) means find the length of the longest common sub-sequence in a[0..i] and b[0..j].

Base case: f(n, 0) = f(0, n) = 0
Complexity: O(n ^ 2). Same reasoning as above.
Naive Complexity: O(2 ^ n) if all the f is computed separately.
Backtracking can be applied here as well.
Generate all possible subsets of characters in string a. (2 ^ n)
Generate all possible subsets of characters in string b. (2 ^ n)
Find the sub-string of maximum length of the 2 subsets.

3. Maximum sum contiguous sub array
Problem: Given a 1-D array, find the contiguous sub array with the maximum sum.
Recurrence: At first compute all the sum of starting from i ending at j.
f(i, j) = f(i, j - 1) + f(j, j)
find the cell with the maximum value in it.

Complexity: O(n ^ 2)

4. Maximum size square sub array with all 1s:
Problem: Given a 2D array A holding 0 or 1 in cells, find the maximum sub 2D array that is square and that has all element 1.
Recurrence: Construct an auxiliary 2D array S such that
S(i, j) = min(S(i - 1, j), S(i, j - 1), S(i - 1, j - 1)) + 1 if A(i, j) = 1
S(i, j) = 0 if A(i, j)  = 0
Base case, S(0, j) = A(0, j), S(i, 0) = A(i, 0)
S(i, j) essentially holds the size of the maximum square sub array all holding 1 whose bottom right corner is A(i, j).

After constructing, S, find the S(i, j) with maximum value.

Complexity: O(n ^ 2) as we are constructing a 2D array.

[Algorithms][DP] Dynamic Programming Explaiend

Dynamic Programming (DP) is a technique of solving a problem that depends on a smaller instance of a smaller problem

When DP can be applied:
0. If the best solution of the larger problem can be computed from the best solution of the smaller problem(s). This property is called optimal substructure property.  If you can formulate a recursive equation such as f(n) = f(n-1) + f(n-2), you can solve the bigger problem f(n) with the result from smaller problems, which means the problem shows optimal substructure property. To know if the optimal substructure property exists or not ask the following -
"Can I solve the problem recursively?"

1. DP can be applied on the problems that shows overlapping sub problems. For instance, fibonacci(n) = fibonacci(n-1) + fibonacci(n-2). Lets see the tree structure of this problem,
                                                  f(n)
                                                 /    \
                                           f(n-1)   f(n-2)
                                            /     \         /   \
                                     f(n-2)    f(n-3) .......................

From the tree above, we can see that f(n-2) appears twice. To find if there is overlapping sub-problem property or not ask the following question-
"Am I solving the same problem more than once?"


In short, to check if DP can be applied on a given problem or not, see at first if it can be solved recursively, then see in the recursion tree if any sub-problem is occurring more than once.

Steps on formulating a problem using DP
Lets consider the problem of finding the shortest path in a graph.
0. Find variables that express the problem. To find shortest path, we need a vertex to start from (u) and a vertex we want to reach (v). For this problem u and v are the minimum number of variables to express the problem at hand. DP(u, v) would be state of the problem we want to compute.
1. Find relationship of the main problem with sub-problem states.
DP(u, v) = min(DP(u, k) + DP(k, v)) for all k
3. Build table to memorize sub problem's solutions.

Determining Order of a DP problem
0. Find the total number of sub-problems (s). For the shortest path problem, u would take all possible vertices. So, s = |V|
1. Determine how much work is done to compute a problem (w). Order of a recursive call to a sub-problem would be constant, as for DP it will be only a table look up, so for the shortest path problem,  DP(u, k) + DP(k, v) takes constant time.  We need to iterate through all k reachable from u, so w = degree(u).
3. Runt time, O(DP(u, v)) = s * w = O(|V| + |E|)

Reference:
0. MIT OCW
1. GeeksforGeeks
2. Dr. Fuentes' lecture
3.