# 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.