Final Exam Flashcards
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?
a) m
b) n + 1 and m
c) n
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?
a) 20
b) 10
What is the expected number of probes for a successful search in hashing by chaining with α as the load factor?
α/2
The capacity of the following cut is ____. (S vertices are bold.)
S ->(5) A ->(4) B ->(3) C ->(2) D ->(1) T
9
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
Back
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
Cross
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
The number of strong components may increase.
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:
a) 10
b) 4
c) 5
( 1/ 1-α)
What is required when calling union(i, j) for maintaining disjoint subsets?
i and j are leaders for different subsets
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:
finish(X) > finish(Y)
The cycle property for minimum spanning trees may be used to find an MST by:
Remove the maximum weight edge in any cycle until only a tree of edges remain.
What is the number of strongly connected components in this graph?
Understand strongly connected components
(includes a picture)
Which algorithm maintains multiple subtrees?
Kruskal’s
Which edge is chosen in a phase of Kruskal’s algorithm?
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)
Before searching for a minimum cut in a network, it is useful to do the following:
Find and record augmenting paths until none remains.
Which person listed below has not won the Turning Award?
a) Dijkstra
b) Goldberg
c) Karp
d) Tarjan
Goldberg
The worst-case time for Prim’s algorithm implemented with a minheap is:
Θ (E log V)
The number of edges in a maximum bipartite matching for the graph below is:
Understand maximum bipartite
(includes picture)
What is the Edmonds-Karp variant?
Using BFS to search a residual network for an augmenting path.
When using two breadth-first searches to find the diameter of a tree, the purpose of the first search is to find:
One end of a diameter
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?
7
A topological ordering of a directed graph may be computed by:
Ordering the vertices by descending finish times after DFS
The number of potential probe sequences when using double hashing with a table with m entries (m is prime) is:
m (m - 1)
When finding the strongly connected components, the number of components is indicated by:
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
In Dijkstra’s algorithm, the final shortest path distance from the source s to a vertex x is known when:
x has its entry extracted from the heap
For which graph representation is querying for the presence of an edge supported by binary search?
Compressed adjacency lists (ordered)
Which disjoint subset implementation implements the find operation in constant time?
Implementation 1
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?
Back
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:
a) 32
b) 29
The relationship of the net flow across a cut and the amount of flow from the source to the sink is?
They are equal
The capacity of the following cut is ____. (S vertices are bold.)
S ->(4) A ->(10) B ->(3) C ->(1) D ->(5) T
12
During a breadth-first search, the status of a white vertex is:
It is undiscovered
During depth-first search on an undirected graph, a cycle is indicated by which edge type?
Back
The worst-case time for the memoryless version of Dijkstra’s algorithm is?
θ (EV)
The capacity of any cut is:
An upper bound on the maximum flow.
During a breadth-first search, the status of a gray vertex is:
It is in the FIFO queue
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?
8
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:
30
The capacity of the following cut is ____. (S vertices are bold.)
S ->(5) A ->(4) B ->(10) C ->(3) D ->(1) T
16
The worst-case time for Dijkstra’s algorithm implemented with a minheap is:
θ (E log V)
Path compression is part of which disjoint subset implementation?
Implementation 3
The capacity of the following cut is ____. (S vertices are bold.)
S ->(1) A ->(4) B ->(5) C ->(3) D ->(10) T
16
Using the values never-used (-1) and recycled (-2) are part of which data structure?
Open Addressing
When a graph is dense, the best way to find a minimum spanning tree is:
Prim’s algorithm using T-table
Dijkstra’a algorithm may be viewed as being a generalization of which technique?
BFS
