CPSC448: Final exam preparation questions

These are the questions that did not make it to the final exam.

Questions

Question 1

You have an 8x8-cell chessboard and a chess knight on cell S on the board. There are other pieces on the board; they do not move. What is the shortest number of moves the knight will need to get to cell T? Two pieces can not share a cell. The knight always moves in the following way:

  • It has to start going up/down/left or right
  • It will always travel exactly 3 cells
  • It must turn by 90 degrees exactly once on the way (so it can travel at most 2 cells in any given up/down/left/right direction).

Each of the knight's moves is a jump - other pieces never obstruct its motion unless the piece is occupying the cell to which the knight is jumping.

Write at algorithm that will determine the smallest number of jumps required or will print "Impossible".

Question 2

Write an algorithm that, given a graph G, will print ALL the possible minimum spanning trees of G. It does not need to be efficient.

Question 3

Write an algorithm that, given an undirected graph G, will determine whether G is a tree.

Question 4

[Deleted]

Question 5

Given a collection of N primes and a number M, what is the largest integer smaller than M that can be constructed as a product of some of the N primes, if each prime can be used at most once? at most twice? You can assume M is at most a million.

Question 6

Given a string of decimal digits, determine the smallest base in which this string represents a perfect cube. If no base smaller than 100 works, print "Impossible".

Question 7

Given a black-and-white picture (as a table of pixels), count the number of black spots in it. A black spot is a collection of black pixels such that from any pixel in the spot there is a black path to any other pixel in the spot. The path can not go diagonally.

Question 8

Given a directed, acyclic graph, print, for each pair of vertices, the number of different paths between them. The algorithm has to be O(n^4) in the number of vertices.

Question 9

Rate these problems in the order of computational difficulty.

  1. Determining the number of positive integers less than n that are not relatively prime to n.
  2. Testing the primality of n.
  3. Finding the LCM of n and n + 7.
  4. Factoring n.

Question 10

Write a RECURSIVE routine that, given a word, will print all of it's letter-permutations alphabetically, for example, given "loon", it will print

lnoo
lono
loon
nloo
nolo
nool
olno
olon
onlo
onol
ooln
oonl

Question 11

Write an algorithm that, given a set of integers, will find the subset with the largest even total sum. Some (or all) of the given integers can be negative.

Scroll down to see the answers

Answers

Question 1

The question is asking for a shortest path of some sort. If we consider each cell as a vertex, then the edges will be the possible knight moves. For example, the cell (2,3) would have an edge to (and from) the cell (4,4), assuming that there are no pieces occupying either cell. This graph is unweighted, so the most natural algorithm to use is BFS. Having realized this, the graph itself is not necessary anymore; we can just use the board directly. S is the source, and is the first cell/vertex added to the BFS queue. At each step, at most 8 more vertices will be added to the queue. BFS will stop when T is found or when the queue is empty (no path to T was found). Here is the algorithm.

queue q;
q.push( S );
depth[S] = 0;
while( !q.empty() )
{
    Cell c = q.top();
    if( c == T )
    {
        printf( "The shortest path is %d jumps long.\n", depth[T] );
        break;
    }

    // Add all of c's knight-neighbours to q
    for( int dx = -2; dx <= 2; dx++ )
        for( int dy = -2; dy <= 2; dy++ )
            if( dx * dx + dy * dy == 5 &&      // XXX: Knight's move
                !occupied[c.x + dx][c.y + dy] )
            {
                Cell d( c.x + dx, c.y + dy );
                q.push( d );
                depth[d] = depth[c] + 1;
            }

    q.pop();
}
if( q.empty() ) printf( "No path from S to T.\n" );

Question 2

The first question to ask yourself is, "How can a graph have more than one minimum spanning tree?" Think of Kruskal's algorithm. If there are n vertices, it will pick the n-1 smallest edges and call that the minimum spanning tree. That means that if G's edges all have different weights, there is only one minimum spanning tree. The only place where there is any ambiguity is when the algorithm is picking its next edge. If there are two edges with the same weight, Kruskal's algorithm does not specify which one should be picked - either one will do the job.

[The rest of solution deleted. It was wrong. This question is too hard.]

Question 3

By definition, a tree is a connected acyclic graph, so there are two things to check - that G is connected and that G is acyclic. Both can be verified simultaneously by a run of DFS. The graph is connected if and only if DFS reaches all the vertices. The graph is acyclic if and only if DFS does not find any back edges. To detect back edges, we need to use three colours for each vertex - white vertices have not been reached yet, gray vertices are being processed (are on the DFS stack now), and black vertices have been dealt with (all of their neighbours have been visited). Because G is undirected, each edge corresponds to two entries in the adjacency matrix. dfs() has to make sure it does not call itself recursively on the same edge is has just traversed. This is the purpose of the 'pred' variable in the code below. Here is the algorithm in detail.

bool graph[][];     // Adjacency matrix
typedef enum { WHITE, GRAY, BLACK } colour_t;
colour_t colour[];
int blackCount, n;

void dfs( int u, int pred = -1 )
{
    if( colour[u] == BLACK ) return;
    if( colour[u] == GRAY ) throw -1;

    colour[u] = GRAY;
    for( int v = 0; v < n; v++ )
        if( graph[u][v] && v != pred )
            dfs( v, u );
    colour[u] = BLACK;
    blackCount++;
}

void main()
{
    /* Populate 'graph' */
    /* Set n to be the number of vertices */
    for( int i = 0; i < n; i++ ) colour[i] = WHITE;
    blackCount = 0;

    try
    {
        dfs( 0 );
        if( blackCount < n ) throw -2;
        printf( "Is a tree.\n" );
    }
    catch( int e )
    {
        printf( "Is not a tree.\n" );
    }
}

Question 5

If you replace multiplication with addition and "primes" with "numbers", this is exactly the coins/partition problem we discussed in class. Create a bool table of size M. Set all of its entries to false. Set entry number 1 to true. Take the primes one at a time and for each one update the table right-to-left possibly setting some entries true.

for( int i = 0; i < M; i++ ) table[i] = false;
table[1] = true;
for each given prime p
    for( int i = M - 1; i; i-- )
        if( table[i] && i * p < M )
            table[i * p] = true;
for( int i = M - 1; i; i-- )
    if( table[i] ) return i;

To deal with the case when each prime can be used twice, simply repeat the inner 'for' loop twice.

Question 6

This is almost precisely problem Y from assignment 7 (Squares). The idea is to try all bases from 2 to 100, compute the number represented by the digits in that base and check whether it is a cube. One caveat to watch out for is that no number in base b can have a digit that is larger than b-1 See the solution to problem Y on how to use Horner's rule to evaluate the numbers. Checking whether n is a cube can be done like this.

int r = ( int )pow(n, 1.0/3);
if( r * r * r == n ) { /* n is a perfect cube */ }
else { /* n is not a perfect cube */ }

Problem 7

This is much like problem J from assignment 3 (The Seasonal War). Look throught the image; when you find a black pixel, use DFS to colour it (and its neighbours) white and count this as one black spot.

bool image[m][n];     // false = white, true = black

void dfs( int x, int y )
{
    if( x < 0 || y < 0 || x >= m || y >= n )
        return;
    if( !image[x][y] ) return;
    image[x][y] = false;
    dfs( x - 1, y );
    dfs( x + 1, y );
    dfs( x, y - 1 );
    dfs( x, y + 1 );
}

void main()
{
    /* Read the image into 'image' */
    /* the image is assumed to be m*n */
    int cnt = 0;
    for( int x = 0; x < m; x++ )
        for( int y = 0; y < n; y++ )
            if( image[x][y] )
            {
                dfs( x, y );
                cnt++;
            }
    return cnt;
}

Question 8

One (not the most efficient) way of doing this is to notice that "the number of paths" could be viewed as "the number of paths of length 0", plus "the number of paths of length 1", plus "the number of paths of length 2", etc. Since the graph is acyclic, the longest path will have length "number of vertices minus one". The number of paths of length k between u and v is precicely the [u][v]'th entry of the k'th power of the graph's adjacency matrix.

Start with the identity matrix (which gives all the paths of length zero). Multiply it by G's adjacency matrix n-1 times (n is the number of vertices in G), and add up the [u][v]'th entries in all of these matrix powers. This will give the total number of paths between u and v in G.

int matrix[n][n];

// Load identity into 'matrix'.
memset( matrix, 0, sizeof( matrix ) );
for( int i = 0; i < n; i++ ) matrix[i][i] = 1;

int cnt = 0;
for( int k = 0; k < n; k++ )
{
    cnt += matrix[u][v];
    /**
     * Multiply 'matrix' by G's adjacency matrix and
     * store the result in 'matrix'.
     **/
}
return cnt;

Since matrix multiplication is O(n3), this algorithm is O(n4). With a bit of linear algebra knowledge, we could notice that since we only care about the u'th row of the matrices, we can just keep that row and multiply it by the adjacency matrix. This will improve the algorithm's performance to O(n3).

Question 9

3. Finding the LCM of n and n + 7
O(log(n)) with Euclid's algorithm.
2. Testing the primality of n.
O(log6(n)) with Agrawal-Kayal-Saxena or about O(log(n)) with Rabin-Miller.
4. Factoring n.
About O(n1/3) with Number Field Sieve. No polynomial-time algorithms are known ("polynomial time" here means "polynomial in log(n)").
1. Determining the number of positive integers less than n that are not relatively prime to n.
This is the definition of n - phi(n). As far as I know, computing phi(n) relies on factoring, so it is no easier than factoring.

Question 10

The problem is to generate all permutations of the letters while avoiding duplicates. Here is an algorithm that almost works.

void perm( string &s, int i )
{
    cout << s << endl;
    for( int j = i; j < s.size(); j++ )
    {
        if( s[i] == s[j] ) continue;    // Avoid duplicates
        swap( s[i], s[j] );
        perm( s, i + 1 );
        swap( s[i], s[j] );
    }
}

void main()
{
    string s; cin >> s;
    sort( s.begin(), s.end() );
    perm( s, 0 );
}

This does generate all the permutations and it does avoid duplicate words, but it does not print them alphabetically. (try running it on the string "abcd"). To ensure the strings are printed alphabetically, some extra swapping will be required, and the code starts getting trickier. This is why this question did not make it to the final exam. ;-)

Question 11

There is a greedy algorithm that will do the job. We will build the set incrementally. First, add all the positive even numbers because they can never make the sum odd. Next, add all the positive odd numbers in pairs because a pair of odd numbers adds up to an even number. What if there are an odd number of positive odd numbers? We'll have to discard one. It makes sense to discard the smallest one because it is contributing the least to the total sum. This is it. We have the answer.

In practice, it is easier to go from the other side. Take all the positive numbers. If there is an odd number of odd ones in there, throw away the smallest odd one and return the rest. This is what the algorithm below does.

/* Assume 'nums' is the input vector. */
vector< int > ans;
int smallestOdd = -1, numOdds = 0;
for( int i = 0; i < nums.size(); i++ )
{
    if( nums[i] > 0 )
    {
        if( nums[i] % 2 )
        {
            numOdds++;
            if( smallestOdd < 0 || nums[i] < smallestOdd )
                smallestOdd = nums[i];
        }
        ans.push_back( nums[i] );
    }
}
if( numOdds % 2 )
{
    /* Remove 'smallestOdd' from 'ans' */
}
return ans;