Discrete Mathematics, Summer 2002

 

Extra Credit Problem

 

This problem will be worth 20% of the entire grade but only for one person who will tell me the right solution first. You can tell me the solution at 9:00pm on Thursday, August 8 right after the exam. If there are several students who think they solved the problem, I will purely randomly choose one. If his/her solution would not be correct, then I will listen to the solution of another student. The solution must be specific enough so that I can easily understand how to code it in a language such as C. One note: make sure that you manage your time appropriately, it is much more important to prepare well for the exam rather than to find a solution to this tricky problem.

 

Here is the description of the problem.

 

You are given a graph, which is described by the number of vertices N and an array of edges of size E. You can assume that you have the following data structure:

 

typedef struct {

            int start; /* index of the start vertex */

            int end; /* index of the end vertex */

} Edge;

 

and that your function that initializes the graph has the following prototype:

InitGraph(int N, Edge edges[], int E);

 

You have to perform an initialization of the graph. You can use as much memory as you want. The running time of your initialization must be proportional to the number of edges E, so in particular it cannot be quadratic on N. And lastly, you must be able to respond to the question whether there is an edge between any two vertices using just several operations, i.e. independent of how big the value E is.