CPSC490: Midterm preparation

Questions

Question 1

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]
Elements are inserted into the collection using the Insert operation. Two collections can be combined using the Combine operation to obtain a new collection with the elements of both collections. The collection MAY contain duplicate elements. Print() is the only access to the elements in the collection, and is NOT required to print the elements in sorted order. It is not even required to group duplicate objects together when printing.

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.


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 (Xi, Yi, Ri), one for each puddle. Xi, and Yi are the Cartesian coordinates of puddle i; Ri 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).


Scroll Down for answers.



















































Answers

Question 1

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 a Java LinkedList or a 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.


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.

struct ltcustom
{
    bool operator()( const string &s, const string &t ) const
    {
        if( d[s] < d[t] ) return true;
        if( d[x] > d[t] ) return false;
        return s < t;
    }
};
...
sort( vertices.begin(), vertices.end(), ltcustom() );

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.

enum { WHITE, GRAY, BLACK };
map< int, vector< int > > graph;
map< int, int > colour;

void dfs( int u )
{
    if( colour[u] == GRAY ) throw 1; // Found a cycle
    if( colour[u] == BLACK ) return; // Been here before
    colour[u] = GRAY;
    for( int i = 0; i < graph[u].size(); i++ )
        dfs( graph[u][i] );
    colour[u] = BLACK;
}

void main()
{
    ... //Fill in the graph
    ... //Set the colour of every vertex to WHITE
    try
    {
        for( all vertices v )
            if( colour[v] == WHITE )
                dfs( v );
        return;
    } catch( int e ) { cout << "HAVE CYCLE\n"; }
}

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.