The following represents a solution to the Data Structures and Algorithms portion of the Spring 1999 Ph.D. Qualifying Examination. There were three parts. A sufficient answer for passing each part is given below and is high-lighted in bold. Psuedo-code procedures are also given for parts two and three which, by themselves, are not sufficient responses.

 

1) Adjacency List for a graph with p vertices and E edges.

A 1-dimensional array Node with p entries. For each vertex i, 1 ≤ i < p, there will be a linked list of nodes containing the neighbors of vertex i that are larger than i. The fields in each node x will be Val(x) and Next(x) where Val(x) contains the label of a neighbor of node i and Next(x) will be NIL or the name (location or pointer) of another node containing a neighbor of vertex i. Further, i < Val(x) < Val(next(x)), when next(x) ≠ NIL. The name of the first node for vertex i is in Node(i).

(Supporting "pictures" can be helpful, but are not sufficient.)

 

2) Algorithm to initialize an Adjacency List to a particular graph on p vertices and E edges in O(E) time.

a) Read in values p and E followed by E edges consisting of a pair of vertices i and j.

{We may assume i < j (or it will be forced.) This step requires O(p+E) time.}

b) Radix sort the edges with the second (i.e., final) pass constructing the Adj. List.

{The larger labels are used in the first pass. A temporary "bucket," Temp(k), will contain all neighbors of vertex k that are less than k.

Then, the smaller labels are used in the second pass. Using an empty set of buckets {Node(1), ...., Node(p)}, distribute the items from the temporary buckets, one bucket at a time from the largest (p) to the smallest (1, actually 2 is sufficient). This ensures items going into bucket Node(i) are in increasing order and are all larger than i.

Each pass of the radix sort is a single "bucket sort" and requires E comparisons. So, this step requires O(p+E) time.

The total is O(p+E).

A psuedo-code procedure for (2):

For 1 £ k £ p set Node(k) ¬ Temp(k) ¬ NIL

{First pass of the radix sort.}

For 1 £ k £ E

Read the edge (i, j) {assume i < j}

Add i to j's list {using Temp(j)}

{Second pass of the radix sort.}

For k = p downto 2 do

While Temp(k) ¹ NIL Do {bucket k items go to Adjacency List}

x ¬ Temp(k), Temp(k) ¬ Next(x)

i ¬ Val(x), Val(x)¬ k

Next(x) ¬ Node(i), Node(i) ¬ x

3) Algorithm to determine the existence of an ascending path from node i to node j.

Use a modified Depth-First-Search (DFS) from vertex i. All vertices between i and j are first marked as "unvisited" and the DFS visits nodes until either 1) j is encountered, or 2) all reachable vertices between i and j have been visited and j was not encountered.

  1. Mark vertices from i to j as "unvisited" and set a Boolean variable Found to FALSE.
  2. Perform a DFS from vertex i.

For each unvisited vertex encountered, mark it as "visited."

While Found = FALSE,

For each "unvisited" neighbor less than j,

perform a DFS from that vertex.

If a neighbor is j, set Found to TRUE and exit.

Since a DFS requires a time proportional to the number of edges encounteered, this algorithm is in O(min{t2, E}), where t = |i–j|.

A psuedo-code procedure for (3):

DFS (a)

Visited(a) ¬ TRUE

x ¬ Node(a)

While x ¹ NIL and Found = FALSE Do

k ¬ Val(x)

x ¬ Next(x)

If k < j and Visited (k) = FALSE, then DFS (k)

else if k = j then Found ¬ TRUE

else if k > j then x ¬ NIL

End

Path(i, j)

For i £ k £ j set Visited(k) ¬ FALSE

Found ¬ FALSE

DFS(i)

If Found then {report a path exists.}

else {report no path exists}

End