Strongly connected graph

You are given a directed graph G with n vertices labeled 1 to n.  If, for any pair of vertices I and j, I is reachable from j and vice versa, we say that G is strongly connected.  You are given a matrix T such that T[i,j] = 1 if there is an edge from vertex i to vertex j and 0, otherwise.  Using T, write programming code which returns true if G is strongly connected and false, otherwise.

Solution
//use an understanding of Floyd-warshall to solve:

Floyd-Warshall
procedure FloydWarshallWithPathReconstruction ()
   for k := 1 to n
       for i := 1 to n
           for j := 1 to n
               if path[i][k] + path[k][j] < path[i][j] then
                path[i][j] := path[i][k]+path[k][j];

           next[i][j] := k;

procedure GetPath (i,j)
   if path[i][j] equals infinity then
       return "no path";
   int intermediate := next[i][j];
   if intermediate equals 'null' then
       return " ";   /* there is an edge from i to j, with no vertices between */
   else
       return GetPath(i,intermediate) + intermediate + GetPath(intermediate,j);

Thus, this produces the solution:

//given an Adjacency Matrix, A

int[,] strongly = new int[n, n];

for k=1 to n

for i=1 to n

for j= 1 to n

strongly[i,j] = (strongly[i,j] <> 9999 || (strongly[i,k] <> 9999 && strongly[k, j] <> 9999)) ? 1 : 0;

for i=1 to n

for j= 1 to n

if (strongly[i, j] != 1) return false;

return true;

Coin changing

Consider a country whose coins are minted with denominations of {d1, d2, ..., dn} cents (n<= 10).  It is required to make change for m cents (m <= 100) using the minimum number of coins.

Write programming code that correctly determines the minimum number of coins needed to make change for m cents using denominations {d1, 2, ..., dn}.  You must use the following idea:

To find the minimum for k cents, consider the minimum number of coins at each of (k-d1), (k-d2), ... (k-dn) cents.  Find the smallest of these, (s say).  Suppose it is found at (k-di).  Then the minimum number of coins for k cents is s+1, using the coins at (k-di) plus coin di.

Data is supplied in the following order: n d1 d2 ... dn m

Output the minimum number of coins required to make change for m cents followed by the value of each coin.  The coins can be printed in any order. [10].

Solution
//assumes: n, denom, CoinTable has been initialized
void solve()
    {
           for(int j = 0; j<=n; j++)
                   CoinTable[0][j] = 9999; //set the cost of using no denomination to “infinity”
          
           for(int i = 0; i <denom.length; i++)
                   CoinTable[i][0] = 0;  //set the cost of using 0 coins to 0
   
           for(int i=1; i< denom.length; i++)

                   for(int j=1; j<=n; j++)

                           if ( j-denom [i] < 0 ) CoinTable[i][j] = CoinTable[i-1][j];

                           else C[i][j] = Math.min(CoinTable[i-1][j], CoinTable[i][j-denom [i]]+1   );

   
    }

private void printCoins(int n, int m)
    {

           if( n < 1 || m < 1 )   return;

           if( CoinTable[n][m] == CoinTable[n-1][m] )

           {

                   printCoins(n-1,m);

           }

           else

           {

                   System.out.println("uses : "+denom [n]);

                   printCoins(n,m-denom [n]);

           }   

    }

Cars around a track

n cars (n <= 50) are positioned around a circular track.  The total amount of fuel in the cars is enough for one car to drive around the entire track.  It is required to find such a car.  For each car i, you are given f[i] (the distance which can be travelled wth thte fuel n the car) and d[] (the distance to the next car).
1. Prove that there exists at least one car, x, with enough fuel to get to the next car [2].
2. If the fuel from car y is transferred to car x and y is removed from the track, the problem remains the same with one less car.  Based on this observation, write code which reads values for n, f[i], d[i] (i=1, n) and prints the number of the car which can be used to drive around the track. [8]



/* transfer fuel from the car following i to car i, this car may not necessarily be the i+1th car, since cars are being
removed as fuel is transferred from them, so it is the current car following I at this time.
To handle this we create a circular list in the array so:

2

3

4

5

6

7

8

9

10

1

Location 1 contains 2 which is the next car number
Location 2 contains 3 the next car number and so on.
Let’s say Fuel gets transferred from car 4 then we remove the pointer to car 4 and transfer the value in the next cell
to this location so the array becomes:

2

3

4+5

0

6

7

8

9

10

1

for (int i=1; i<=m, i++){
read(x) = f[i]
read(y) = d[i]; //load data
}

for (int j=1; j<n; j++){ //remove n-1 cars

for (int i=1; i<=n; i++){
if (f[i] >= d[i])
break;
}

nc = (i mod n) + 1 //count circularly around cars
while (f [nc] ==0){ //car has been removed
nc = nc mod n + 1;
} // end while
f [i] += f[nc];
d[i] += d[nc]; //transfer fuel
f[nc] = 0;       // set fuel to 0 in car it has been taken from
}// end for

Shortest path (deriving)

A graph G contains n vertices {1, 2, ... n} and is represented by its adjacency matrix, A.
Write code to transform A, such that, A[i, j] is the shortest path from vertex i, to vertex j.

Given that n = 4 and A is
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 ∞
3 ∞ 9 0

derive the matrix of shortest paths, showing the matrix after each of the 4 major steps.

Solution

for k = 1 to n
for i = 1 to n
for j=1 to n
A[i, j] = min(A[i, j], A[i, k] + A[k, j]) [2 marks]

A:
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 ∞
3 ∞ 9 0

k=1:
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 ∞
3 ∞ 7 0

k=2:
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 12
3 ∞ 7 0

k=3:
0 ∞ 4 16
∞ 0 ∞ 7
18 5 0 ∞
3 12 9 0

k=4:
0 ∞ 4 16
10 0 14 7
18 5 0 ∞
3 12 9 0

[5 marks]

Solve T(n) = 2T(n-1) + a, assuming T(0) = 1

Solution
T(n) = 2T(n-1) + a
= 2{2(T(n-2) + a} + a
= (2^2)T(n-2) + a (2^2 + 1)
... = (2^k)T(n-k) + a (2^k - 1)
When n-k = 0, we get
T(n) = (2^k) + a (2^k - 1)

Proof
T(0) = 2^0 + a (2^0 - 1) = 1 (formula true for n=1)
Assume true fro 1...k
T(k+1) = 2T(k) + a
= 2{2^k + a (2^k -1) + a}
= 2^(k+1) + 2a(2^k -1) + a
= 2^(k+1) + a(2^(k+1) -1)
therefore the formula is true for (k+1) and so for all n

Also see: http://math.stackexchange.com/questions/9731/prove-by-induction-tn-2tn-2-2

Memoized "Triangle" Problem

Write a 'memoized' recursive solution to the "Triangle" problem.  Assume that the data consists of a number of rows followed by the numbers for the triangle, from top to bottom.  Write a main method which reads the data and calls the recursive function which returns the highest sum obtained on a path from the apex to the base of the triangle.

Solution
int highestSum(int i, int j)
{
int left, right;
if (M[i , j] != -1) return M[i, j];
left = highestSum(i+1, j);
right = highestSum(i+1, j+1);
if (left > right)
M[i, j] = tri[i, j] + left;
else
M[i, j] = tri[i, j] + right;
return M[i, j];
}

Longest Common Subsequence

Here is an implementation of the Longest Common Subsequence (LCS) problem that was discussed in class.

The Problem
You are given a sequence X = {x1, x2, ..., xm} consisting of m elements and a sequence Y = {y1, y2, ..., yn} consisting of n elements. It is required to find the LCS of X and Y. The elements of the subsequence need not be contiguous.

Here is my solution:



public class LCS {


    int[][] T;
    char[] X;
    char[] Y;


    /**
     * @param args
     */
    public static void main(String[] args) {
        new LCS();
    }


    public LCS() {
        initialize();
        process();
        printLCS(X.length, Y.length);
    }


    /**
     * Does the main processing of the LCS.
     */
    public void process() {
        for (int i = 1; i <= X.length; i++) {
            for (int j = 1; j <= Y.length; j++) {
                if (X[i - 1] == Y[j - 1]) {
                    T[i][j] = 1 + T[i - 1][j - 1];
                } else {
                    T[i][j] = Math.max(T[i][j - 1], T[i - 1][j]);
                }
            }
        }
    }


    /**
     * Sets up two arrays of characters
     */
    public void initialize() {
        X = "ABCBDAB".toCharArray();
        Y = "BDCABA".toCharArray();
        T = new int[X.length + 1][Y.length + 1];
        for (int i = 0; i <= X.length; i++) {
            T[i][0] = 0;
        }
        for (int i = 0; i <= Y.length; i++) {
            T[0][i] = 0;
        }
    }


    public void printResult() {
        for (int i = 0; i <= X.length; i++) {
            for (int j = 0; j <= Y.length; j++) {
                System.out.print(T[i][j]);
            }
            System.out.println();
        }
    }


    public void printLCS(int i, int j) {
        if (i == 0 || j == 0) {
            return;
        } else {
            if (X[i - 1] == Y[j - 1]) {
                printLCS(i - 1, j - 1);
                System.out.print(String.format("%c ", X[i - 1]));
            } else {
                if (T[i - 1][j] > T[i][j - 1]) {
                    printLCS(i - 1, j);
                } else {
                    printLCS(i, j - 1);
                }
            }
        }
    }
}