Longest Arithmetic Progression

Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that 
A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. 
The sequence S1, S2, …, Sk is called an arithmetic progression if 
Sj+1 – Sj is a constant


{2,3,5,7,8,11}


DP solution with O(n^3). 
Assume, we've optimum solution for array a[0,1,2,....,k]. To get solution for index = k+1, we can put a[k+1] next in a sequence ending with a[j] for 0 <= j <= k. 
So, if diff = a[k+1] - a[j], we need to look up sub-problem solution for index = j to search for diff, and taking the max value to get a maximum sequence.


code input/output:
{2,3,5,7,8,11};
max seq: 2, 5, 8, 11
DP array values:

0 0 0 0 0 0 
1 0 0 0 0 0 
1 1 0 0 0 0 
1 1 2 0 0 0 
1 1 2 1 0 0 
1 1 1 2 3 0 

Dynamic Programming: Longest increasing subsequence

Given a unordered array of numbers, remove the fewest number of numbers to produce the longest ordered sequence. Print count of fewest numbers to be removed, and the remaining sequence. For example, if input is 1 2 3 4 5 6 7 8 9 10, no (zero) numbers are removed, and input is the longest sequence. If input is, 1 2 3 8 10 5 6 7 12 9 4 0, then fewest number of elements to be removed is 5 is the fewest number to be removed, and the longest sequence is 1 2 3 5 6 7 12.



Recurrence.
For 1 <= i <= n,
A(i) = 1 + max{A(j) | 1 <= j < i and aj < ai}.
(We assume max(NULL) == 0.)


Time complexity: O(n2). 


Code input/output:
int [] A = {7, 3, 8, 4, 6};

LIS ends at: 4
MaxLength of LIS:3
Printing DP array: 
1 1 2 2 3 
Printing Previous Array:
-1 -1 1 1 3 
Printing LongestIncreasingSubsequence:
3 4 6 
Fewest numbers to be removed to produce the Longest ordered subsequence:2


int [] B = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
LIS ends at: 15
MaxLength of LIS:6
Printing DP array: 
1 2 2 3 2 3 3 4 2 4 3 5 3 5 4 6 
Printing Previous Array:
-1 0 0 2 0 4 4 6 0 6 8 9 8 9 12 13 
Printing LongestIncreasingSubsequence:
0 2 6 9 11 15 
Fewest numbers to be removed to produce the Longest ordered subsequence:10

Dynamic Programming: Water Tank Problem.

you are given following:
1. An empty tank
2. Unlimited source of water.
3. Some container of certain measurments and a container of 1 litre is always given.


Your job is to fill the tank from source of water using the containers in minimum number of steps.
You cant fill the container with a small amount of water than its size (filling partially is not allowed).
Find the number of steps and print the solution.


e.g.
Tank Size: 80 litre
Containers: 1,3,5,6,25 litre
Solution:
4
5,25,25,25


Tank Size: 71 litre
Containers: 1,3,5,6,25 litre
Solution:
6
3,6,6,6,25,25

Approach:
This problem is similar to the coin change problem, where the number of denominations is infinite.
Please refer:
http://karmaandcoding.blogspot.in/2012/01/coin-change-problem-with-limit-on.html

Code:

int [] container = {1, 3, 5, 6, 25};

fillTheTank(container, 80);
fillTheTank(container, 71);


Output:

Number of containers for 80: 4
25 25 25 5 
Number of containers for 71: 6
25 25 6 6 6 3 

Dynamic Programming: Bounded (1/0) knapsack problem.

This problem is also known as Integer Knapsack Problem (Duplicate Items Forbidden).


During a robbery, a burglar finds much more loot than he had expected and has to decide what to take. His bag (or knapsack) will hold a total weight of at most W pounds. There are n items to pick from, of weight w1.....wn and dollar value v1.....vn. What's the most valuable combination of items he can fit into his bag?


For instance, take Capacity = 10 and
Item Weight Value
1            6      $30
2            3      $14
3            4      $16
4            2      $9


Here repitition is not allowed.


K(w,j) be the max value achievable using knapsack of size w and items 1....j
The answer we seek is K(w,n)


Lets try to express K(w,j) in terms of smaller subproblems
Now here, either j is needed to solve the subproblem or its not needed.
So we have,
K(w,j) = Max { K(w - w[j], j-1) + v[j], K(w, j-1)}


Now algorithm involves, filling out a 2-D table with W+1 rows and n+1 columns.
Time complexity: O(nW).


Code Input:
int [] W = {6, 3, 4, 2};
int [] V = {30, 14, 16, 9};
int C = 10;


Output:
Optimal value for integer knapsack: 46

Dynamic Programming: Unbounded knapsack problem

During a robbery, a burglar finds much more loot than he had expected and has to decide what to take. His bag (or knapsack) will hold a total weight of at most W pounds. There are n items to pick from, of weight w1.....wn and dollar value v1.....vn. What's the most valuable combination of items he can fit into his bag?


For instance, take W = 10 and
Item Weight Value
1            6      $30
2            3      $14
3            4      $16
4            2      $9


Let K(w) = max value achievable with a knapsack of capacity w.


Now if the optimal solution to K(w) includes i, then removing this item from knapsack leaves an optimal solution to K(w-w[i])+v[i], for some i.
As we dont know which i, so we will try all the possibilities.
K(w) = MAX {K(w-w[i] + v[i]} for i:w[i]<w


The maximum over an empty set is 0.


K(0) = 0
for w = 1 to W:
K(w) = max{K(w - wi) + vi: wi <= w}
return K(W)




This algorithm fills in a one-dimensional table of length W + 1, in left-to-right order. Each entry can take up to O(n) time to compute, so the overall running time is O(nW). As always, there is an underlying dag. Try constructing it, and you will be rewarded with a startling insight: this particular variant of knapsack boils down to finding the longest path in a dag!


Code Input:
int [] W = {6, 3, 4, 2};
int [] V = {30, 14, 16, 9};
int M = 10;


Code output:
Printing knapsack for different Ws:
0 0 9 14 18 23 30 32 39 44 48 
Optimal value for unbounded knapsack: 48

Dynamic Programming: Maximum Contiguous Subsequence Sum of At Least Length L.

Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) of length atleast L for which the sum of elements in the subsequence is maximized.


For the following array, where L = 3.
A = {-5, -1, 2, -3, 0, -3, 3,}
The best possible sum of at least length 3 would be 0, where the subsequence is the last three elements (0, -3, 3)


Another Array with L = 2;
A = {0, 5, -3, -1, 2, -4, -1, 7, 8}
Output = 15;


Set sumL to the sum of the first L array elements.
Set runningSum = sumL.
Set maxSum = sumL
For k = L + 1 up to n, the length of the array:
Set sumL = sumL + A(k) - A(k - L)
Set runningSum = max(runningSum + A(k), sumL)
Set maxSum = max(maxSum, runningSum)
Output maxSum


Inputs:
int  [] A = {0, 5, -3, -1, 2, -4, -1, 7, 8};
int L = 2;
int [] B = {-5, -1, 2, -3, 0, -3, 3,};
L = 3;


Output:
Max sum: 15
Indices: i=7 : j=8
Max sum: 0
Indices: i=4 : j=6

Dynamic Programming: Maximum Value Contiguous Subsequence.

Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized.


Recurrence Equations:
For any i and j where (1 <= i < j <= n)
M(j) = Max sum over all windows ending at j.


M(j) = Max { M(j-1) + A[j], A[j] } ie either we extend the optimal window ending at j or start a fresh window with A[j].


Total time complexity: O(n) as there are n sub problems, each of size O(1).


Input Arrays:

int [] A = { -2, 11, -4, 13, -5, 2 };
int [] B = {-15, 29, -36, 3, -22, 11, 19, -5};


Output:

Max Sum: 20
Indices: i=1: j=3
Max Sum: 30
Indices: i=5: j=6

Dynamic Programming: Fibonacci Series.

Dynamic programming algorithms are almost always developed in two distinct stages.


1. Formulate the problem recursively. Write down a recursive formula or algorithm for the whole problem in terms of the answers to smaller subproblems. This is the hard part.


2. Build solutions to your recurrence from the bottom up. 
Write an algorithm that starts with the base cases of your recurrence and works its way up to the final solution, by considering intermediate subproblems in the correct order. This stage can be broken down into several smaller, relatively mechanical steps:


(a) Identify the subproblems. 
What are all the different ways can your recursive algorithm call itself, starting with some initial input? For example, the argument to RECFIBO is always an integer between 0 and n.


(b) Analyze space and running time. 
The number of possible distinct subproblems determines the space complexity of your memoized algorithm. To compute the time complexity, add up the running times of all possible subproblems, ignoring the recursive calls. For example, if we already know Fi1 and Fi2 , we can compute Fi in O(1) time, so computing the first n. Fibonacci numbers takes O(n) time.


(c) Choose a data structure to memoize intermediate results. 
For most problems, each recursive subproblem can be identified by a few integers, so you can use a multidimensional array. For some problems, however, a more complicated data structure is required.


(d) Identify dependencies between subproblems. 
Except for the base cases, every recursive subproblem depends on other subproblems—which ones? Draw a picture of your data structure, pick a generic element, and draw arrows from each of the other elements it depends on. Then formalize your picture.


(e) Find a good evaluation order. 
Order the subproblems so that each subproblem comes after the subproblems it depends on. Typically, this means you should consider the base cases first, then the subproblems that depends only on base cases, and so on. More formally, the dependencies you identified in the previous step define a partial order over the subproblems; in this step, you need to find a linear extension of that partial order. Be careful!


(f) Write down the algorithm. 
You know what order to consider the subproblems, and you know how to solve each subproblem. So do that! If your data structure is an array, this usually means writing a few nested for-loops around your original recurrence. You don’t need to do this on homework or exams.


Of course, you have to prove that each of these steps is correct.
If your recurrence is wrong, or if you try to build up answers in the wrong order, your algorithm won’t work

Dynamic Programming: Edit Distance problem.

The edit distance of two strings, s1 and s2, is defined as the minimum number of point mutations required to change s1 into s2, where a point mutation is one of:

change a letter,
insert a letter, or
delete a letter

The following recurrence relations define the edit distance, d(s1,s2), of two strings s1 and s2:

d('', '') = 0               -- '' = empty string
d(s, '')  = d('', s) = |s|  -- i.e. length of s
d(s1+ch1, s2+ch2)
  = min( d(s1, s2) + if ch1=ch2 then 0 else 1 fi,
         d(s1+ch1, s2) + 1,
         d(s1, s2+ch2) + 1 )

Code output:

S1: partnership
S2: markesshep
Edit Distance: 5

House coloring with red, blue and green.

There are a row of houses, each house can be painted with three colors red, blue and green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. You have to paint the houses with minimum cost. How would you do it?


Note: Painting house-1 with red costs different from painting house-2 with red. The costs are different for each house and each color.


Approach:
Dynamic Programming solution:
we can paint the ith house with blue, red or green.
so we have the following equations:
cost[i,r] = min( cost[i-1,b], cost[i-1,g] ) + cost of painting i with r.
cost[i,g] = min( cost[i-1,b], cost[i-1,r] ) + cost of painting i with g.
cost[i,b] = min( cost[i-1,r], cost[i-1,g] ) + cost of painting i with b.


Final Min Cost = min (cost[n,b], cost[n,r], cost[n,g]);


---------------------------
    R      G       B
---------------------------
1   7      5       10 
---------------------------
2   3      6        1
---------------------------
3   8      7       4
--------------------------
4   6      2       9
--------------------------
5   1      4       7
--------------------------
6   2      3       6
--------------------------


Code output:

Cost matrix leading to the solution: 
0 0 0 
7 5 10 
8 13 6 
14 13 12 
18 14 22 
15 22 21 
23 18 21 
Cost of coloring the house is: 18

Partition an array into 2 parts with equal average.

How do you partition an array into 2 parts such that the two parts have equal average? Each partition may contain elements that are non-contiguous in the array.


We need to solve the problem of finding all possible sum for a subset of size k (for 1<=k<=n/2), where n is total number of items.


Let S1 = sum of partition 1
n1 = # of items in partition 1
S2 = sum of partition 2
n2 = # of items in partition 2
S = S1+S2
n = n1+n2
Since, S1/n1 = S2/n2, it implies S1/n1 = S2/n2, which in turn implies (S1+S2)/(n1+n2) = S/n


Now, we populate a table of size (N/2) x N x S, where each entry T[k][i][j] is 1 if we there exists some subset of size k using the set of elements {1,2,...,i} that sum to j. During the computation of this table entries, if we ever found that j/k = S/n, there exists a way to make a partition with equal average. T[k][i][j] can be generated as a recurrence like :


T[k][i][j] = T[k-1][i-1][j-item_i] || T[k][i-1][j] ;


Time complexity: O(N^2*S), 
Space complexity: O(N*S).


Input Array:
int [] A = {2, 4, 4, 5, 6, 6, 7, 8, 9, 12};
Code Output:

Partition 1: 6 1
Partition 1: 57 9

Coin change problem with limit on number of coins of each denomination.

You have coins with different denominations and you have limited number of each denominations (some maybe zero), how will you determine if you can supply the given change ?


Approach:

Characterize the structure of a coin-change solution.
• Define C[j] to be the minimum number of coins we need to
make change for j cents.
• If we knew that an optimal solution for the problem of
making change for j cents used a coin of denomination di,
we would have:
C[j] = 1 + C[j - di]




C[j] = infinite if j < 0
= 0 if j == 0;
= 1 + min { C[j - D[i]] } if j >= 1;
1<=i<=k


Now here we *DO NOT* have unlimited coins, so we keep one more array of limit of each type of coin denominations.
Let coin denominations be:
int [] D = {50, 25, 10, 1};
Ex for above coin denominations
int [] limit = {2, 1, 2, 5};


Now please refer "makeChangeLimitedCoins" method implementation in the below code for more..


If we want to make change for 30, with the above coin denominations and limit then below code outputs the following:

Printing Coin Value and Change:
1:1
2:2
3:3
4:4
5:5
6: Not Possible
7: Not Possible
8: Not Possible
9: Not Possible
10:1
11:2
12:3
13:4
14:5
15:6
16: Not Possible
17: Not Possible
18: Not Possible
19: Not Possible
20:2
21:3
22:4
23:5
24:6
25:1
26:2
27:3
28:4
29:5
30:6

Given a set of numbers [1-N]. Subsets such that the sum of numbers in the subset is a prime number.

Given a set of numbers [1-N] . Find the number of subsets such that the sum of numbers in the subset is a prime number.
Approach:
For each number in the Sum S, check if there is subset of numbers from 1 to N that sum up to S - Yes that you can do with Subset Sum problem. Recurrence for the same is:

Sum[0,0]=True
For S=1 to L do Sum[0, S]= False
For k=1 to n do
     For S = 0 to L do
           Sum[k, S] = Sum[k-1, S] or Sum[k-1, S - x(k)]

Then for all the subsets Sum Si which can be generated with numbers from 1 to N, check if those are Prime.

Maximum Contiguous Sum in an Array.

Maximum value of a contiguous subsequence.
This problem is only interesting if there are -ve values in the array. We can solve this problem in linear time using Dynamic Programming. There are O(N) subproblems each taking O(1) time. The basic strategy is whenever a subsequence is found which has a -ve sum, the next subsequence can begin after the end of the subsequence which produced the -ve sum.

Code: