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;

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:
23456789101

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:
234+506789101


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

Saturday, November 20, 2010

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

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

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

Count Out (The Josephus Problem)

This problem was given in class.

n children are arranged in a circle and m words are used to count out the children in rounds. The last child wins.


The Problem
Given n children and m words and a starting position (say child 1), who wins?


This is a variation of the Josephus problem.


Here is a Java solution. Simply call josephus(n, m, s) to run.



   /**
     * Performs the counts in rounds and returns the index of the winner.
     * circle is assumed to be an array of size n.
     * @param n The number of children
     * @param m The number of words
     * @param start The starting position
     * @return
     */
    private int josephus(int n, int m, int start){
        initialize(n);
        int i = start;
        while(circle[i] != i){            
            int pos = i;
            int prev = pos;
            for(int j = 1; j < m; j++){
                prev = pos;
                pos = circle[pos];
            }
            //remove current position
            circle[prev] = circle[pos];
            i = circle[pos];
        }
        return i;
    }


The initialize(n) method simply initializes the circle array  so that each  position 0 points to position 1, position 1 points to position 2 etc. That is, position i points to position i + 1. This indicates that the circle is full. To drop a child out at position i, then position i - 1 will point to position i + 1.



    /**
     * Initializes the circle array.
     * m <= n
     * @param n Number of persons
     *
     */
    private void initialize(int n){
        circle = new int[n];
        for (int i = 0; i < n - 1; i++){
            circle[i] = i + 1;
        }
        circle[n-1] = 0;
    }



Course Outline

For my own sanity I have decided to put together a list of everything that was mentioned in class up to this point. It should help with planning how we are going to prepare for exams.


  1. Mathematical Background

    Alsuwaiyel Chapter 2.
  2. Recurrence Relations

  3. Proof by Induction

    Alsuwaiyel Chapter 5
  4. Asymptotic Notation

    The order of an Algorithm. Big-O, Ω, Θ small-o.
  5. Greedy Algorithms

    • Knapsack Problem
    • Coin Change Problem
    • Dijkstra's Algorithm
    • Prim's Algorithm
    • Kruskal's Algorithm
    • Huffman Codes
  6. Dynamic Programming


    • Best Sum Problem
    • Longest Common Subsequence
    • Shortest Path Problems - All Pairs
    • Matrix Chain Multiplication
    • Assembly Line Scheduling
  7. Backtracking

    • 3 Colouring Problem
    • 8 Queen Problem
  8. String Matching


    • Naive (brute force approach)
    • Knuth-Morris-Pratt (KMP) Algorithm and the prefix function

  9. Disjoint Sets

  10. Other Things that I have not categorized

    • Bellman-Ford Algorithm and Relaxation
    • Floyd-Warshall Algorithm
    • Transitive Closure
    • Magic Squares - siamese technique for odd ordered sqaures, LUX for singly even ordered squares.

Thursday, November 11, 2010

Maximum-sum contiguous subvector

Question

Given an array A[1..n] of n real numbers, write programming code which implements an O(n)-time algorithm for finding the maximum-sum contiguous subvector. For example, in the array
{11, -21, 39, 6, -33, 38, 77, -73, -3, 64}
the maximum sum (122) is obtained by summing the third through seventh elements; your code should print 122 3 7.

Solution

Maximum sum in any contiguous subvector
/* Precondition: x[1..n] is an array of floating-point (real) numbers. */
procedure MaxSumContigVector (x[1..n]: float)
// Returns the maximum sum of a continuous subarray drawn from x.
MaxSoFar := 0.0
MaxEndingHere := 0
i := 1
while i ≠ n + 1 do
MaxEndingHere := max(0.0, MaxEndingHere + x[i])
MaxSoFar := max(MaxSoFar, MaxEndingHere)
i := i + 1
end
return MaxSoFar
source:
http://www.cse.sc.edu/~mgv/csce350sp04/lectureNotes/maxsumcontigvector.html

Welcome to the Algorithm Design place

The intention is for this blog to become a single source for all source-code, algorithms and strategies related to one mission (for now): PASSING THIS COURSE.

Hopefully, we'll all learn something useful about algorithms, about running time, about recurrence relations and triangles and knapsack.