CPSC490: Midterm preparation

Questions

Question 1

Design a datastructure that can support these operations:

• Insert( int )
• Erase( int )
• GetMax()
• GetMin()

The structure should be able to handle thousands of operations per second.

Question 2

The street is full of circular puddles. You are a 5-year-old kid standing in the center of puddle number 1. You want to get to puddle number n, but you want to minimize your dry land walking distance.

Your input is the number n, followed by n triples of integers (X_i, Y_i, R_i), one for each puddle. X_i, and Y_i are the Cartesian coordinates of puddle i; R_i is its radius. Write an algorithm that will print the minimum distance you have to walk on dry land.

Question 3

Given an unweighted graph G and a source vertex s, output the vertices of G, sorted first by their depth with respect to s and then (if depths are equal) alphabetically. The vertices are specified as distinct strings.

Question 4

Given a directed graph, determine whether it has cycles.

Question 5

Given a weighted, directed graph, where each vertex can be either red, blue or gray, return the shortest distance between the red side and the blue side (i.e. the shortest path from some red vertex to some blue vertex).

Question 6

You are given

• a graph G = (V, E), with |V| <= 10,
• two vertices, s and t, in V, and
• an integer k (0 < k < |V|).

Give an algorithm that will print a path from s to t in G of length exactly k if one exists. If not, print "No Way". Please specify the data structure(s) you use to represent the graph.

Question 7

You are required to implement a collection class that supports the following operations.

• void Insert( int element ) [in constant time]
• Collection Combine( Collection C1, Collection C2 ) [in constant time]
• void Print() [in linear time]

Which data structure(s) would you use to implement this class? Give a short description of how each of the 3 operations will be implemented to conform to the constant time restriction.

Answers

Question 1

If each operation requires O(log(n)) time in the number of elements, this should be good enough to satisfy the speed requirement. A datastructure that can perform all four operations in O(log(n)) time is a (balanced) binary search tree (BST).

To actually implement a BST in C++, the simplest approach is to use a set<int> (which is implemented as a red-black tree). Insert() can be done using insert(), Erase() - via the erase() member function, GetMax() - by dereferencing the rbegin() iterator and GetMin() - by dereferencing the begin() iterator.

Quenstion 2

This is a standard single-source shortest path problem. Here, the puddles are the vertices. The source vertex is puddle number 1. The destination vertex is puddle number n. Think of edges as being the straight-line segments, connecting the centers of a pair of puddles. Draw an edge between every pair of puddles. The weight of an edge in this case is the dry-land distance between the two puddles, i and j, given by the formula

d(i,j) = sqrt( (Xi - Xj)2 + (Yi - Yj)2 ) - Ri - Rj;

With this in mind, run a shortest-path algorithm (for example, Dijkstra's) and print the answer.

Question 3

First, run BFS on the graph with s being the source. This will produce a depth array d[] that will contain the depth of every vertex in G, with respect to s.

Next, create an array (or a vector) of all the vertices and sort it using a custom comparator function as illustrated below.

Question 4

DFS is perfectly suited for this job, but DFS is not the only possible solution.

Pick any vertex of G and call dfs() with that vertex as the source. As you may remember, DFS keeps a record of the visited (seen) vertices. If you look in the book, there is a slight generalization of this idea. Each vertex is given a colour - either white, grey or black. White vertices have not been visited yet. Grey vertices are being visited right now (they correspond to the stack frames of calls to dfs()). Black vertices are those that have already been processed (dfs() has seen this vertex and returned from it).

Suppose dfs() is in the middle of its job of traversing the graph and it is now at the vertex u. Suppose also that a vertex v is gray. That means that there is a path from the source to v, and there is also a path from v to u. Now what if dfs() encounters an edge from u to v? Since there is already a path from v to u, that would mean that we have found a cycle! Thus, if dfs() is ever called with a grey vertex as a parameter, we can stop immediately and declare to have found a cycle.

One small detail to note here is that since the graph is not guaranteed to be connected, dfs() might not visit all of the vertices. If there are still white vertices left after dfs() returns, we will need to call dfs() again on all of the white vertices.

The code below illustrates the algorithm above. Here, dfs() will terminate normally if it does not find a cycle and it will throw an exception if it does find one. This makes the code shorter.

Question 5

The trick is to convert the graph to a form in which a known shortest-path algorithm can be applied. To do this, add two vertices, s and t. Add an edge of weight 0 from s to every red vertex. Add an edge of weight 0 from every blue vertex to t. The colours of s and t are irrelevant (and meaningless). Now find the shortest path from s to t using, for example, the Bellman-Ford algorithm with s as the source. Return the length of the shortest path found.

Question 6

Taking the adjacency matrix to the k'th power will compute the number of walks of length k from s to t. This doesn't help us because (1) it doesn't give us a walk, only the number of them and (2) we are interested in a path, not a walk.

Note, however, that we only have 10 vertices, so the length of the path is at most 9. This means that we should consider a brute force solution. We know that the path starts with s and ends with t. What is left is to figure out the k-2 vertices in the middle. How many ways are there to choose k-2 vertices, in some order, out of the 8 remaining ones? There are 8 choices for the first vertex, 7 for the second one, ..., and 11-k for the last one. The worst case is when we have to use all 8 vertices, which gives us 8 factorial (40320) permutations to check. Checking a path means verifying that we have all of the 9 required edges to connect the neighbouring vertices on the path. If we find a configuration that works, we print it; otherwise, at the end we print "No Way".

Can we do better than an exponential-time algorithm? Not really. Consider the case when s is equal to t, and k is n-1. Then the problem is asking for a cycle that visits each vertex once - a Hamiltonian cycle. Thus, if we had a polynomial-time algorithm for this problem, we would be able to solve Hamiltonian cycle in polynomial time, too, which is highly unlikely.

One possible implementation of the brute force solution would build the path recursively. Let used[i] be true for all vertices that are already used on the path. Then the recursive function can start with a partial path from s and append one vertex to it, until the length is k.

int path[16];
bool used[16];
bool graph[16][16], n, k;

bool bruteForce( int u, int pathLen )
{
    // are we done? (base case)
    if( pathLen == k )
    {
        if( path[pathLen - 1] == t )
        {
            /* Print the path[] */
            return true;
        }
        return false;
    }

    // not done: try all neighbours, v, of u that are not already used
    for( int v = 0; v < n; v++ ) if( !used[v] && graph[u][v] )
    {
        // append v to the path
        path[pathLen] = v;
        used[v] = true;

        // recurse, like in DFS
        if( bruteForce( v, pathLen + 1 ) ) return true;

        // recursion didn't work: unmark v, so it can be used again
        // this is the important difference between DFS and this
        // brute force algorithm. This line is what makes the running
        // time exponential.
        used[v] = false;
    }
    return false;
}

int main()
{
    // initialize the graph[][] and n
    // set used[] to false for all vertices
    // set k to the required path length
    // set t to the destination vertex

    if( !bruteForce( s, 0 ) ) cout << "No Way" << endl;

    return 0;
}

Question 7

A linked list would do the job. The list would be kept in unsorted order. To insert an element, add it to the front (or the back) of the list. To combine two lists, splice them by connecting the last element of the first list to the first element of the second list. To print, traverse the list.

You could use an STL list to do this job. There are methods that will allow you to splice two lists. It's probably just as easy to implement a linked list from scratch.