CPSC 5115                                                Algorithm Analysis and Design
Mid–Term Exam                                                                          Fall 2007

THIS IS DUE BACK TO ME ON OR BEFORE 9:00 PM on TUESDAY, OCTOBER 2.

1.   (16 points)  You are given an algorithm and told that its time complexity is T(N) Î W(N3).
Which of the following statements is consistent with T(N) Î W(N3)?

a)      T(N) Î O(N3).                      e)         T(N) Î Q(N3).

b)      T(N) Î Q(N2).                      f)          T(N) Î O(N4).

c)      T(N) Î W(N2).                      g)         T(N) Î Q(N4).

d)      T(N) Î W(N4).                      h)         T(N) Î O(N2).

The next four questions concern the undirected graph described as follows.
V(G) = {1, 2, 3, 4, 5}
E(G) = { (1, 2),  (1, 4),  (2, 3),  (2, 5),  (3, 4),  (4, 5) }

2.   (8 points)    Show the complete set of adjacency lists for this graph.
There is one adjacency list for each vertex.

3.   (16 points)  Do a depth–first search of this graph, beginning at vertex 3.
For your answer, show the auxiliary data structures: the mark and back arrays.

4.   (16 points)  Do a breadth–first search of this graph, beginning at vertex 3.
For your answer, show the auxiliary data structures: the mark and back arrays.

5.   (4 points)    This graph is a connected graph:            TRUE              FALSE.

6.   (20 points)  You are given two arrays, each of which is sorted.  Array A has M elements and array B has
N elements.  It is possible that M = N, but likely that M ¹ N.  The arrays
can be declared as A[1 .. M] and B[1 .. N].  Each array is sorted low to high, so that
A[1] < A[2] < … < A[M]
B[1] < B[2] < … < B[N].  Neither array has duplicates; the inequalities are strict.

It is possible that some elements of the A array are equal to elements of the B array.

Write an algorithm that counts the number of entries in one array that are also in the other.

This must have linear time complexity; T(M, N) Î Q [minimum (M, N)].  The simple solution, with a double
loop has time complexity T(M, N) Î Q (M·N), is not an acceptable answer.   HINT: Think of Mergesort.

We end with two TRUE/FALSE questions.

7.   (10 points)  A spanning tree of a graph can contain cycles.   TRUE  FALSE

8.   (10 points)  A spanning subgraph of a graph must be connected.  TRUE    FALSE