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]

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