Final Exam

Question 1

Suppose the compressed adjacency list representation is used for a directed graph with n vertices and m edges.
a) What is the value stored at the last entry of the tailTab?
b) What is the number of entries in the two tables?

Answer 1

a) m
b) n + 1 and m

Question 2

What is the expected number of probes for an unsuccessful search in hashing by chaining when there are 2000 items stored in a structure with 100 linked lists?

Answer 2

20

Question 3

What is the expected number of probes for a successful search in hashing by chaining with α as the load factor?

Answer 3

α / 2

Question 4

The capacity of the following cut is ____. (S vertices are bold.)
S ->(5) A ->(4) B ->(3) C ->(2) D ->(1) T

Answer 4

16

Question 5

Suppose a depth-first search on a directed graph yields a path of tree edges from vertex X to vertex Y and a path of tree edges from vertex X to Z. If there is also an edge from Y to X, then what type will it be?
a) back
b) cross
c) forward
d) tree

Answer 5

Back

Question 6

Suppose a depth-first search on a directed graph yields a path of tree edges from vertex X to vertex Y and a path of tree edges from vertex X to Z. If there is also an edge from Y to Z, then what type will it be?
a) back
b) cross
c) forward
d) tree

Answer 6

Cross

Question 7

Which of the following cannot occur when additional edges are included in a directed graph?

Answer 7

The number of strong components may increase.

Question 8

For a double hash table with α = 0.9 (without deletions), the upper bound on the expected number of probes for unsuccessful search is:

Answer 8

10

Question 9

What is required when calling union(i, j) for maintaining disjoint subsets?

Answer 9

i and j are leaders for different subsets

Question 10

Suppose a directed graph has a path from vertex X to vertex Y, but no path from vertex Y to vertex X. The relationship between the finish times for depth-first search is:

Answer 10

finish(X) > finish(Y)

Question 11

The cycle property for minimum spanning trees may be used to find an MST by:

Answer 11

Remove the maximum weight edge in any cycle until only a tree of edges remain.

Question 12

What is the number of strongly connected components in this graph?

Answer 12

Understand strongly connected components
(includes a picture)

Question 13

Which algorithm maintains multiple subtrees?

Answer 13

Kruskal’s

Question 14

Which edge is chosen in a phase of Kruskal’s algorithm?

Answer 14

A minimum-weight edge that keeps the result free of cycles

Question 15

Before searching for a minimum cut in a network, it is useful to do the following:

Answer 15

Find and record augmenting paths until none remains.

Question 16

Which person listed below has not won the Turning Award?
a) Dijkstra
b) Goldberg
c) Karp
d) Tarjan

Answer 16

Goldberg

Question 17

The worst-case time for Prim’s algorithm implemented with a minheap is:

Answer 17

Θ (E log V)

Question 18

The number of edges in a maximum bipartite matching for the graph below is:

Answer 18

Understand maximum bipartite
(includes picture)

Question 19

What is the Edmonds-Karp variant?

Answer 19

Using BFS to search a residual network for an augmenting path.

Question 20

When using two breadth-first searches to find the diameter of a tree, the purpose of the first search is to find:

Answer 20

One end of a diameter

Question 21

Suppose that there is only one path from vertex 5 to vertex 10 in a directed graph:
5 -> 7 -> 4 -> 3 -> 2 -> 10
During the scan of which column will Warshall’s algorithm record the presence of this path?

Answer 21

7

Question 22

A topological ordering of a directed graph may be computed by:

Answer 22

Ordering the vertices by descending finish times after DFS

Question 23

The number of potential probe sequences when using double hashing with a table with m entries (m is prime) is:

Answer 23

m (m - 1)

Question 24

When finding the strongly connected components, the number of components is indicated by:

Answer 24

The number of restarts for the second depth-first search

Question 25

In Dijkstra’s algorithm, the final shortest path distance from the source s to a vertex x is known when:

Answer 25

x has its entry extracted from the heap

Question 26

Completed Tests:
Fall17 T3
Fall18 T3