Wednesday, December 5, 2001 Name:____________________

CSE 326 Autumn 2001

Quiz 4

Please use the following notation on this quiz:

q To specify the number of vertices in a graph, write V.

q To specify the number of edges in a graph, write E.

(Much less cumbersome than writing |V| and |E|)

1. (6 points) Average case analysis of graph operations.

Use average case analysis to compute the tightest possible running time bounds.

q Give your answers in terms of the average number of vertices adjacent to a given vertex. (Hint: think of the adjacency list as being analogous to a hash table chain.)

q Use V, E or both as appropriate in your answers.

q Give your answers in big-O notation.

q Assume that accessing a single vertex is an O(1) operation.

q Base each answer on whether the graph is represented as an adjacency list or an adjacency matrix.

	Adjacency List	Adjacency Matrix
Access all vertices adjacent to a given vertex.
Access all edges adjacent to a given vertex.
Given vertices u and v, determine whether (u, v) is an edge in the graph.

2. (10 points) For the following implementation of topological sort, give the big-O running time bound for each statement (in the boxes at right), and for the algorithm as a whole (in the bottom box).

q Assume the graph is represented as an adjacency list.

q Assume each vertex is labeled with its in-degree (# of inbound edges).

q For loop statements, the running time bound should be the number of loop iterations.

q Where appropriate, use your result(s) from Problem 1 to compute the tightest possible running time bounds.

void TopoSort() {

For each vertex v in the list of vertices

If v has in-degree 0, put it in a queue

While the queue is not empty

Dequeue a vertex v and output it

For each vertex u adjacent to v

Reduce u’s in-degree by 1

If u has in-degree 0, enqueue it

}

3. (2 points) Give an example of a directed graph on which topological sort cannot produce a topological ordering.

4. (4 points) Indicate whether each of the following defines an equivalence class.

Yes	No	Reachability in a directed graph.
Yes	No	Adjacency in an undirected graph.
Yes	No	Equality among integers.
Yes	No	Loose inequality (£ or ³) among integers.

5. (4 points) Write the general recurrence relation for Quicksort. Indicate which quantities represent the numbers of elements partitioned above and below the pivot.

6. (2 points) Which condition causes Quicksort best case performance?

7. Derive the running time bound for Quicksort best case performance.
1. (2 points) Write the recurrence for Quicksort best case performance. (Hint: specialize the Quicksort general recurrence from above.)

2. (5 points) Solve the Quicksort best case recurrence and derive the running time bound.

3. (1 point) Which other commonly-used sorting algorithm can be analyzed by the same recurrence?

8. (4 points) Derive the running time bound for InsertionSort. (Hint: use the concept of an “inversion,” defined as integers i, j such that i < j and A[i] > A[j].)

9. (Extra Credit – 5 points) Graph density.

The following definitions apply to the questions below.

q The density d of a non-empty graph is defined as:

d º (# edges) / (# vertices) º E / V

q A complete graph is one in which every vertex is adjacent to every other vertex.

q An unconnected graph is one in which no vertex is adjacent to any other vertex.

q A self-edge is an edge (v, v) that joins a vertex v to itself.

Answer the following questions exactly.

q Don’t use big-O notation.

q Assume that all graphs are non-empty.

q Assume that there are no self-edges.

1. What is the density of an unconnected graph?

2. What is the density of an undirected complete graph?

3. What is the density of a directed complete graph?

4. What is the density of a spanning tree?

5. What relation, if any, exists between graph density, as defined in this problem, and your answers to Problem 1?