CPSC490: Midterm preparationQuestionsQuestion 1You are required to implement a collection class that supports the following operations.
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 2The 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 3Given 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 4Given a directed graph, determine whether it has cycles. Question 5Given 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. AnswersQuestion 1A 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 2This 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 3First, 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
Question 4DFS 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 };
Question 5The 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. |