Lesson test: Graphs and traversal

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Graphs and traversal

1.[2p]
An undirected graph has 24 million vertices. How many entries would its adjacency matrix hold, in units of $10^{14}$ ?

CorrectNot quite: 5.76

2.[3p]
For a road network with average degree 3, the adjacency list beats the matrix because

memory is $Θ (V + E)$ rather than $Θ (V^{2})$ , and $E$ is close to $V$

Correct

edge lookup is faster in a list

The answer is: memory is $\Theta(V + E)$ rather than $\Theta(V^2)$, and $E$ is close to $V$

matrices cannot store weights

The answer is: memory is $\Theta(V + E)$ rather than $\Theta(V^2)$, and $E$ is close to $V$

lists keep the vertices sorted

The answer is: memory is $\Theta(V + E)$ rather than $\Theta(V^2)$, and $E$ is close to $V$

3.[2p]
An adjacency matrix is the better choice when a graph is dense, with $E$ approaching $V^{2}$ .

True

Correct

False

The answer is: True

4.[3p]
Why does breadth-first search compute fewest-edge distances while depth-first search does not?

The queue removes vertices in non-decreasing order of distance, so each is first reached by a shortest route

Correct

It visits fewer vertices

The answer is: The queue removes vertices in non-decreasing order of distance, so each is first reached by a shortest route

It records a parent for every vertex

The answer is: The queue removes vertices in non-decreasing order of distance, so each is first reached by a shortest route

It uses recursion rather than a loop

The answer is: The queue removes vertices in non-decreasing order of distance, so each is first reached by a shortest route

5.[3p]
In the undirected graph with edges AB, AC, BD, CD, CE, DF, EF, FG, GH, EH, how many edges lie on the shortest path from A to G?

CorrectNot quite: 4

6.[3p]
What does a depth-first search edge leading to a grey vertex mean?

The graph contains a cycle, because that vertex's call is still on the stack

Correct

The vertex has already been finished

The answer is: The graph contains a cycle, because that vertex's call is still on the stack

The graph is disconnected

The answer is: The graph contains a cycle, because that vertex's call is still on the stack

The traversal has to restart from a new source

The answer is: The graph contains a cycle, because that vertex's call is still on the stack

7.[3p]
A must precede B and C, B must precede D, C must precede D and F, D must precede E, F must precede E. Put the vertices in the topological order Kahn's algorithm gives with alphabetical tie-breaking.

Show the answer

a, b, c, d, f, e

8.[3p]
Which of these does a single depth-first search answer in $Θ (V + E)$ ?

Select all that apply

Whether a directed graph contains a cycle

Correct

A topological order of a directed acyclic graph

Correct

The strongly connected components, with extra bookkeeping

Correct

The fewest-edge distance between two vertices

The answer is: Whether a directed graph contains a cycle, A topological order of a directed acyclic graph, The strongly connected components, with extra bookkeeping

9.[3p]
Match each term to its meaning.

DAG
Strongly connected
Sparse graph
Degree

the number of edges at a vertex
the edge count is close to the vertex count
a directed path joins every pair
a directed graph with no cycles

Show the answer

DAG: a directed graph with no cycles Strongly connected: a directed path joins every pair Sparse graph: the edge count is close to the vertex count Degree: the number of edges at a vertex

1.[2p] An undirected graph has 24 million vertices. How many entries would its adjacency matrix hold, in units of 1014?

2.[3p] For a road network with average degree 3, the adjacency list beats the matrix because

3.[2p] An adjacency matrix is the better choice when a graph is dense, with E approaching V2.

4.[3p] Why does breadth-first search compute fewest-edge distances while depth-first search does not?

5.[3p] In the undirected graph with edges AB, AC, BD, CD, CE, DF, EF, FG, GH, EH, how many edges lie on the shortest path from A to G?

6.[3p] What does a depth-first search edge leading to a grey vertex mean?

7.[3p] A must precede B and C, B must precede D, C must precede D and F, D must precede E, F must precede E. Put the vertices in the topological order Kahn's algorithm gives with alphabetical tie-breaking.

8.[3p] Which of these does a single depth-first search answer in Θ(V+E)?

9.[3p] Match each term to its meaning.

1.[2p]
An undirected graph has 24 million vertices. How many entries would its adjacency matrix hold, in units of $10^{14}$ ?

2.[3p]
For a road network with average degree 3, the adjacency list beats the matrix because

3.[2p]
An adjacency matrix is the better choice when a graph is dense, with $E$ approaching $V^{2}$ .

4.[3p]
Why does breadth-first search compute fewest-edge distances while depth-first search does not?

5.[3p]
In the undirected graph with edges AB, AC, BD, CD, CE, DF, EF, FG, GH, EH, how many edges lie on the shortest path from A to G?

6.[3p]
What does a depth-first search edge leading to a grey vertex mean?

7.[3p]
A must precede B and C, B must precede D, C must precede D and F, D must precede E, F must precede E. Put the vertices in the topological order Kahn's algorithm gives with alphabetical tie-breaking.

8.[3p]
Which of these does a single depth-first search answer in $Θ (V + E)$ ?

9.[3p]
Match each term to its meaning.