CSC 372
Sample Test 3

1. Suppose a weighted graph has N vertices labeled 0 .. N-1. Dijkstra’s algorithm finds the shortest paths from any given vertex to all other vertices. This set of paths (edges and vertices does form a spanning tree of the graph.) Give an example where the following statement is not true:

Given a weighted graph with five vertices, the set of shortest paths from vertex 0 to all other vertices forms a minimum spanning tree.

2. Correctly describe the Jarnik-Prim Algorithm for minimum spanning tree without any mention of avoiding a cycle in the production of such a tree.

3. Given the following adjacency matrix of an unweighted, connected, undirected graph

|0 1 2 3 4 5 6

----------------------

0 |0 1 0 0 1 0 0

1 |1 0 1 0 0 0 0

2 |0 1 0 1 1 1 0

3 |0 0 1 0 0 0 1

4 |1 0 1 0 0 0 0

5 |0 0 1 0 0 0 1

6 |0 0 0 1 0 1 0

a. Print out the node values in a depth-first search beginning at 0.

b. Print out the node values in a breadth-first search beginning at 0.

4. Consider the following statement:

An undirected, connected graph with N nodes and N edges must have a cycle.

Explain why this is true.

5. Consider the hash function

int Hash( int value ) {

Insert the following values (from left to right) into the hash tables:

44 57 88 84 94 68 101 104 25 23 80

a. Using linear probing with probe = 1

c. How many collisions did you experience in these insertions? ____

d. Using quadratic probing

e. How many collisions did you experience in these insertions? _____

c. Using internal chaining with size 13 instead of 20 in the hash function

6. Why is the following statement generally true?

Although deleting from a list-implementation of a priority queue is less expensive than deleting from a heap, that cost is significantly saved from the high cost of insertion into a list-implementation of a priority queue over inserting into a heap.

7. Consider the following bucket sorting routine. Assume that the array called "ARR" has only values between 0 and Q-1 in it.

void Bucket_Sort ( int ARR[ N ] ) {

int I, J, K;

int HELPER[Q];

for ( I = 0; I < Q; I++ )

HELPER[I] = 0;

for ( I = 0; I < N; I++ )

HELPER[ ARR[ I ] ]++;

K = 0;

for ( I = 0; I < Q; I++ ) {

for ( J = K; J < HELPER[ I ]; J++ )

ARR[ J ] = I;

K += HELPER[ I ];

}

}

Show exactly how many executable statements there are in the Bucket_Sort in terms of N and Q. Show how you calculated your answer.

8. Suppose we have the following double node structure (as in a doubly linked list, that is circular with a dummy head node):

struct Node {

float info;

Node * next, * previous;

Node ( float inf, Node * nex, Node * previou ) {info = inf; next = next; previous = previous; }

} list;

Suppose such a "list" has already been created. Suppose we want to insert a floating point number "item" in a new node AFTER the node pointed to by pointer "p". Code the following function:

void Insert ( float item, Node * p ) { //inserting item in a new node after the node pointed to by p.

9. If insertion sort has fewer comparisons than quick sort for small arrays, could that comparison with quick sort also be true with bubble sort and selections sort? Why or why not?

10. In laboratory 1, we "implemented" the list as an array. That, of course, limited the size of the list and also caused some confusion about how to relate the position of the cursor to the actual index in the array (usually "cursor-1"). However, the Find function was the only function that was O(N), where N would be the size of the array. All the others except for printing routines and remove, had a constant number of steps (no loops). If we had implemented the list as an ordinary linked list (list ending in NULL with only a single pointer in each node), which routines would now have to have loops and be O(N)? Why?