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?
c) What is the last subscript for the tailTab?

Answer 1

a) m
b) n + 1 and m
c) n

Question 2

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

Answer 2

a) 20
b) 10

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

9

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?
a) the number of strong components may remain the same
b) the number of strong components may increase
c) the number of strong components may decrease
d) the graph acquires a cycle

Answer 7

The number of strong components may increase.

Question 8

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

Answer 8

a) 10
b) 4
c) 5
( 1/ 1-α)

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
(or)
The unprocessed edge (x, y) of smallest weight such that find(x) != find(y)

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
(or)
The number of times the vertex color table is scanned during 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

For which graph representation is querying for the presence of an edge supported by binary search?

Answer 26

Compressed adjacency lists (ordered)

Question 27

Which disjoint subset implementation implements the find operation in constant time?

Answer 27

Implementation 1

Question 28

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 **Z** to **X**, then what type will it be?

Answer 28

Back

Question 29

Suppose an instance of bipartite matching has 4 vertices in the left column, 8 vertices in the right column, and a) 20 edges. b) 17 edges. The number of edges in the corresponding instance of network flow is:

Answer 29

a) 32 b) 29

Question 30

The relationship of the net flow across a cut and the amount of flow from the source to the sink is?

Answer 30

They are equal

Question 31

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

Answer 31

12

Question 32

During a breadth-first search, the status of a white vertex is:

Answer 32

It is undiscovered

Question 33

During depth-first search on an undirected graph, a cycle is indicated by which edge type?

Answer 33

Back

Question 34

The worst-case time for the memoryless version of Dijkstra's algorithm is?

Answer 34

θ (EV)

Question 35

The capacity of any cut is:

Answer 35

An **upper** bound on the **maximum** flow.

Question 36

During a breadth-first search, the status of a gray vertex is:

Answer 36

It is in the FIFO queue

Question 37

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

Answer 37

8

Question 38

Suppose an instance of bipartite matching has 5 vertices in the left column, 8 vertices in the right column, and 17 edges. The number of edges in the corresponding instance of network flow is:

Answer 38

30

Question 39

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

Answer 39

16

Question 40

The worst-case time for Dijkstra's algorithm implemented with a minheap is:

Answer 40

θ (E log V)

Question 41

Path compression is part of which disjoint subset implementation?

Answer 41

Implementation 3

Question 42

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

Answer 42

16

Question 43

Using the values *never-used* (-1) and *recycled* (-2) are part of which data structure?

Answer 43

Open Addressing

Question 44

When a graph is dense, the best way to find a minimum spanning tree is:

Answer 44

Prim’s algorithm using T-table

Question 45

Dijkstra'a algorithm may be viewed as being a generalization of which technique?

Answer 45

BFS