Showing posts with label 4-marks. Show all posts
Showing posts with label 4-marks. Show all posts

Sunday, November 21, 2010

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;

Thursday, November 18, 2010

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);
                }
            }
        }
    }
}