1. Suppose Warshall’s algorithm is used on a directed graph with vertices 0 . .
ID: 3576284 • Letter: 1
Question
1. Suppose Warshall’s algorithm is used on a directed graph with vertices 0 . . . 25, but is stopped after column 10 in the matrix is processed. Which paths will be represented in the matrix?
A. All paths that start at some vertex in 0 . . . 10 and stop at some vertex in 0 . . . 10.
B. All paths that start at some vertex in 0 . . . 10, stop at some vertex in 0 . . . 10, and have only vertices in 0 . . . 10 in between.
C. All paths that start at some vertex in 0 . . . 25, stop at some vertex in 0 . . . 25, and have only vertices in 0 . . . 10 in between.
D. All paths with no more than 12 edges
2. Suppose that a directed graph is to be stored and then queries for the presence of various edges will be submitted. Which of the following worst-case time bounds for testing whether one edge is present is incorrect? (Vertices are conveniently labeled by numbers 0, 1, . . ., V - 1.)
A. Adjacency lists (ordered): theta(V) B. Adjacency lists (unordered): theta(V)
C. Adjacency matrix: theta(1) D. Compressed adjacency lists (ordered): theta(V)
3. What is the number of strongly connected components in this graph? 2 B. 2 C. 3 A. 1 D. 4Explanation / Answer
Answers
(1) (b) All paths that start at some vertix in 0 ...10 , stop at some vertex in
0 ...10 and have only vertices in 0...10 in between.
(2) (c) Adjacency matrix :theta(1)
(3) (c) 3
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.