Minimize Cash Flow among a given set of friends who have borrowed money from each other

Given a number of friends who have to give or take some amount of money from one another. Design an algorithm by which the total cash flow among all the friends is minimized.
http://www.geeksforgeeks.org/minimize-cash-flow-among-given-set-friends-borrowed-money/

Min Number of Platforms

At a bus-station, you have time-table for buses arrival and departure. You need to find the minimum number of platforms so that all the buses can be accommodated as per their schedule.

Example: Time table is like below:

Bus         Arrival         Departure 
BusA        0900 hrs        0930 hrs
BusB        0915 hrs        1300 hrs
BusC        1030 hrs        1100 hrs
BusD        1045 hrs        1145 hrs

Then the answer must be 3. Otherwise the bus-station will not be able to accommodate all the buses


http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/

Strategy:
Let’s take the same example as described above. Now if we apply dynamic programming and calculate the number of buses at station at any time (when a bus comes or leaves). Maximum number in that pool will be nothing but the maximum number of buses at the bus-station at any time, which is same as max number of platforms required.

So first sort all the arrival(A) and departure(D) time in an int array. Please save the corresponding arrival or departure in the array also. Either you can use a particular bit for this purpose or make a structure. After sorting our array will look like this:

0900    0915    1930    1030    1045    1100    1145    1300
A       A       D       A       A       D       D       D

Now modify the array as put 1 where you see A and -1 where you see D. So new array will be like this:

1       1       -1      1       1       -1      -1      -1

And finally make a cumulative array out of this:

1       2       1       2       3       2       1       0

Your solution will be the maximum value in this array. Here it is 3.



The complexity of this solution depends on the complexity of sorting.

PS: If you have a arriving and another departing at same time then put departure time first in sorted array.

Further Thoughts: You don not need to create a cumulative array or an array with 1 and -1; you just need a counter (cnt) initialized at '0'. Whenever, you find an 'A' in arrival-departure array, increment cnt by 1. Compare it with maximum value (max); if it is greater than max, make max equal to cnt. If you get a 'D' in arrival-departure array, decrement cnt by 1. At the end, return 'max'.

Knapsack Problem

Given a set of items, each with a weight (w_i) and a value (v_i), determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Alternatively,
US Pizza gives you a bowl that can hold 100 gms of salad. You have different salad items each having its own Nutritional Value (NV) and availability. You are supposed to find the way one should fill his bowl so that he gets maximum nutrition. They need not take all of the available quantity. Taking a fraction of the salad item is allowed.
Items          Nutrition Value per Gram         Available
Noodle      10                                                           100 gm
Soyabean  30                                                             15 gm
Macroni     5                                                            100 gm
Fruits         40                                                             10 gm


Strategy:
It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

Define m[i,w] to be the maximum value that can be attained with weight less than or equal to w using items up to i.

We can define m[i,w] recursively as follows:

• m[0,w] = 0
• m[i,0]=0
• m[i,w] = m[i-1,w] if w_i > w (the new item is more than the current weight limit so this element cannot be accepted because it’s weight is larger than w )
• m[i,w] = max(m[i-1,w] ,m[i-1,w-w_i ] + vi) if w_i < = w.


The solution can then be found by calculating m[n,W]. To do this efficiently we can use a table to store previous computations. This solution will therefore run in O(nW) time and O(nW)space. 

Solution to alternate problem:
     All we need to do here is start with the item that provides the highest nutrition/gram and take the maximum available quantity unless the bowl is full. If after this, the bowl still has space, you take the item with the second highest nutrition/gram value. And so on.

I am sure you get the idea. For the given example, you would take 10 gm of Fruits (Full = 10, Remaining = 90), 15 gm of Soyabean (Full = 25, Remaining = 75), and to fill up the rest, with 75 gm of Noodles (Full = 100, Remaining = 0). In this way of selection, you get the maximum nutritional value, 1600 (10*40 + 15*30 + 75*10).

Merge files

Given an array F with size n.Assume the array content F[i] indicates the length of the ith file and we want to merge all these files into one single file.Devise an optimal solution for this

Lets say Given array is F={10,5,100,50,20,15}

Greedy Appraoch---
1.Store filesizes in a priority queue.The key of elements are file lengths.
2.Repeat the following until there is only 1 file
   a.Extract two smallest elements X & Y
   b.Merge X & Y and insert this new file in the priority queue.

Using above approach total cost of merging is 15+30+50+100+200=395
Time complexity:O(nlogn)

Huffman Coding Algorithm

Disucss Huffman coding algorithm and write a C code for this.

Lets assume that after scanning a file we found the following character frequencies

a---12
b---2
c---7
d---13
e---14
f---85

Apply Huffman coding to save space in storing the above characters efficiently.

Longest Common Subsequence

LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.
It is a classic computer science problem, the basis of diff (a file comparison program that outputs the differences between two files), and has applications in bioinformatics.
Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

http://algorithms.tutorialhorizon.com/dynamic-programming-longest-common-subsequence/
http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

Important Variations:
1. Longest Palindromic Subsequence
http://algorithms.tutorialhorizon.com/longest-palindromic-subsequence/
http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/
2.Longest Common Substring
http://algorithms.tutorialhorizon.com/dynamic-programming-longest-common-substring/
3.

Method 1:Recursion

Consider the input strings “AGGTAB” and “GXTXAYB”. Last characters match for the strings. So length of LCS can be written as:
L(“AGGTAB”, “GXTXAYB”) = 1 + L(“AGGTA”, “GXTXAY”)
2) Consider the input strings “ABCDGH” and “AEDFHR. Last characters do not match for the strings. So length of LCS can be written as:
L(“ABCDGH”, “AEDFHR”) = MAX ( L(“ABCDG”, “AEDFHR”), L(“ABCDGH”, “AEDFH”) )
So the LCS problem has optimal substructure property as the main problem can be solved using solutions to subproblems.

int lcs( char *X, char *Y, int m, int n )

{

   if (m == 0 || n == 0)

     return 0;

   if(X[m-1] == Y[n-1])

     return 1 + lcs(X, Y, m-1, n-1);

   else

     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

}

Time complexity of the above naive recursive approach is O(2^n) in worst case and worst case happens when all characters of X and Y mismatch i.e., length of LCS is 0.

Method 2:Dyanamic Programming 




int lcs( char *X, char *Y, int m, int n )

{

   int L[m+1][n+1];

   int i, j;

   /* Following steps build L[m+1][n+1] in bottom up fashion. Note

      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */

   for (i=0; i<=m; i++)

   {

     for (j=0; j<=n; j++)

     {

       if (i == 0 || j == 0)

         L[i][j] = 0;

       else if(X[i-1] == Y[j-1])

         L[i][j] = L[i-1][j-1] + 1;

       else

         L[i][j] = max(L[i-1][j], L[i][j-1]);

     }

   }

   return L[m][n];

}

Time Complexity of the above implementation is O(mn) which is much better than the worst case time complexity of Naive Recursive implementation.