NAME (use capital letters):
Data Structures and Algorithms
COSC 336 Mock Test 2
Instructions: Time 120 minutes. All the questions have equal weight. If you use an algorithm that was discussed in class you can refer to it by its name and no further description is needed.
Question 1. The input is an array a[1], . . . , a[n] of size n containing natural numbers between 1 and n. Describe an O(n) algorithm that determines if the array contains 2 consecutive integers.
Question 2. (a) Give the definition of a tree. Definition. A tree is a graph that
(b) Give a brief description in plain English of an algorithm that on input a graph G (represented using the adjacency-list approach) determines if G is a tree or not. What is the running time of your algorithm? (Note: if you are using an algorithm that was discussed in class you dont have to describe it, just say that you are using it, and indicate its role. Note that your algorithm needs to check 2 properties that make a graph to be a tree.)
Question 3. In the following hash table, we insert elements using hashing with open addressing with quadratic probing. Elements have as keys integer numbers, and the hash function for the i-th probe is given by hash(x, i) = (x + i2)%11. We insert, in the given order, the elements with the following keys: 46, 58, 57, 39. Indicate, where these elements will be placed in the table.
index
value
0
1
2
3
4
5
6
7
8
9
10
Question 4. In a jar, there are n nuts and n matching bolts. All the bolts (and of course all the nuts) have different sizes, but the sizes are very close to each other. The only type of operation that you are allowed to do is the compare-nut-bolt operation in which the input is a bolt and a nut and you can check if the bolt enters into the nut or not. Present in plain English a method that only uses the compare-nut-bolt operation to sort the nuts and separately the bolts in increasing order of their sizes. (HINT: you can use the idea of Quicksort.)
a3b1c 11511
7e4f Figure 1: Graph for questions 5,6.
Question 5. (a) Do a DFS traversal of the graph in Figure 1 starting at node a. Whenever you have a choice between several nodes, use the alphabetical order. List the nodes in the order in which they are visited. (Note: I have written the first two nodes, you need to add the other ones.)
a, b,
(b) Do a BFS traversal of the graph in Figure 1 starting at node b. Whenever you have a choice between several nodes, use the alphabetical order. List the nodes in the order in which they are visited.(Note: I have written the first two nodes, you need to add the other ones.)
b, a,
Question 6. (a) Construct a minimum spanning tree of the graph in Figure 1 using Kruskal algorithm. Whenever you have a choice between several edges, use the alphabetical order. List the edges in the order in which they are introduced in the tree. (Note: I have written the first edge, you need to add the other ones.)
(a, d),
(b) Construct a minimum spanning tree of the graph in Figure 1 using Prim¡¯s algorithm starting at node a. Whenever you have a choice between several nodes, use the alphabetical order. List the edges in the order in which they are introduced in the tree.(Note: I have written the first edge, you need to add the other ones.)
(a, d),
d
Question 7. . We have computed the shortest path between all the nodes in a weighted graph. Then all the edges increase their costs by adding the same value c > 0. Will the shortest paths change? If your answer is NO, prove so, if the answer is YES, give an example of a graph where at least one shortest path changes.
Question 8. A connected graph G has 4 vertices and 4 edges of costs 1, 2, 3 and respectively 4. (a) Show that G is not a tree.
(b) Show that G has a single minimum spanning tree. (Hint: For example, think how Prim¡¯s algorithm constructs the minimum spanning tree).
(c) Draw a connected graph G with 4 nodes and 4 edges of costs 1,2,3,4, respectively, so that the minimum spanning tree contains the edge of cost 4. The 4 nodes are below, you need to draw the 4 edges and indicate their cost.
a
c
b
d
Question 9. Present an algorithm for the following problem. The input is a weighted graph G, two vertices s and t, and a positive number k. The goal is to find a path from s to t such that all edges along the path have weight ¡Ü k (if there is such a path), or to print ¡±no good path¡±, if there is no such path.
Question 10. The graph below represents a network and the capacities are the number written on edges. The source is node a, and the target is node e. We use the Ford-Fulkerson method to find the max flow. The questions below are about the first iteration of the method.
a3b2c 1511
7
d
e
(a) Indicate one augmenting path.
(b) How much flow can be pushed on the path you indicated at (a)?
(c) Draw the residual graph Gf for the flow you have indicated at (b).