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(N³).
Which of the following statements is consistent with T(N) Î W(N³)?

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

b) T(N) Î Q(N²). f) T(N) Î O(N⁴).

c) T(N) Î W(N²). g) T(N) Î Q(N⁴).

d) T(N) Î W(N⁴). h) T(N) Î O(N²).

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