Algorithmic Network Analysis - Quiz I

A computational problem is considered tractable if:

• It has a high storage space requirement

     

   

   

• It can be solved in exponential time

• There exists an efficient algorithm for solving it

• It involves complex mathematical operations

What measure of complexity is commonly used to describe the least amount of time needed to solve a problem?

 

 

 

   

•  Best-case complexity

• Worst-case complexity

• Average-case complexity

• Polynomial complexity

The tiling problem is an example of: 

 

   

 

• A tractable problem

• An efficient algorithm

• Intractable problem

• Polynomial complexity

What is the first step in a depth-first search (DFS) of a graph?

   

   

   

   

• Select the vertex with the highest degree as the starting vertex.

• Select a first vertex to visit and label it.

• Sort all the vertices in descending order of their degrees.

• Visit all vertices and mark them unvisited.

In a graph represented by adjacency lists, in what order are the vertices adjacent to a given vertex listed?

   

• In decreasing order of their degrees

• In increasing order of their degrees

• In increasing order of their subscripts

   

• In decreasing order of their subscripts

In a DFS forest, what structure is each component of the forest?

 

   

• A directed acyclic graph (DAG)

• A disconnected subgraph

• A rooted tree

• A cycle

What does the depth-first search index (Dfi) of a vertex represent?**

 

   

 

• The distance from the starting vertex

• The number of back edges connected to the vertex

• The degree of the vertex in the graph

• The order in which the vertex was first visited during DFS

   

In a connected graph, what does the set of edges in a BFS traversal form?

   -

 

 

   -

• A subgraph

• A spanning tree

• A connected component

• A cycle

If all vertices adjacent to the current active vertex have been visited in DFS, what does the algorithm do next?

 

 

   

• Selects the vertex with the smallest index

• Backtracks to the previous vertex

• Moves to a random unvisited vertex

• Stops the search

A graph in which any two distinct points are adjacent is called a null graph.

• True

• False