Test Review

Question 1

A breadth-first search algorithm uses a :

Answer 1

QUEUE

Question 2

The worse case asympotitc complexity of Dijkstra’s algorithm in a dense graph is :

Answer 2

O(V^2)

Question 3

If an undirected graph has the same weight for every edge, then both the single-source shortest path problem and the minimal spanning tree problem for the graph can be solved in:

Answer 3

Linear Time

Question 4

TRUE or FALSE

The greedy algorithm for the fractional knapsack problem takes a fractional amount of at most one item.

Answer 4

TRUE

Question 5

Prim’s Algorithm can work with

Answer 5

Positive and Negative Weights.

Question 6

TRUE or FALSE

All dynamic programming algorithms have the same asympotitc complexity.

Answer 6

FALSE.

Bellman Ford: O(V*E)
Dijkstra’s: O(E log V)

Question 7

If a depth-first traversal of a directed graph yeilds no back edges,

Answer 7

Then the graph is acyclic

Question 8

When a priority queue is implemented using a binary heap data structure, what is the complexity of insertion and removal:

Answer 8

Insertion: O(log n)
Removal: O(log n)

Question 9

When a priority queue is implemented using a simple array, what is the complexity of insertion and removal:

Answer 9

Insertion: O(1)
Removal: O(n)

Question 10

Name a graph algorithm for which the implementation of a priority queue as a binary heap is best when the graph is sparse, but implementation of priority queue as a simple array is best when the graph is dense.

Answer 10

Dijkstra’s
Prim’s Minimal Spanning

Question 11

Most efficient algoirthm for Single-source shortest path problem in an unweighted graph.

Answer 11

Breadth-First Search
O(V+E)

Question 12

Most efficient algorithm for Single-source shortest problem path in a graph with non-negative edge weights.

Answer 12

Dijkstra’s Algorithm.
O(V log V) In Sparse.

Question 13

Most efficient algorithm for single-source shorest path problem in a graph with negative wegiths but no negative-weight cycles.

Answer 13

Bellmann Ford
O(V*E) In Sparse.

Question 14

What is the asympotitc complexity of the fastest algorithm for finding the strongly-connected components of a directed graph.

Answer 14

DFS: O(V+E)

Question 15

What is the asymptotic complexity of the Bellman-Ford algorithm as a function of the size of the graph G = (V,E)?

Answer 15

O(V*E)

Question 16

Describe a similarity and difference of “Divide and Conquer” and “Dynamic Programming”

Answer 16

Similaries: Recursively divide the problem into subproblems and solve the subproblems.

Difference:
- D+C solves the subproblem and you’ll never see it again.
- DP solves the subproblem but you might use result again, so you store result in table for later use.

Question 17

Identify 3 important characteristics of any dynamic programming algorithm that are illustrated by this algorithm.

Answer 17

1. There a table with an entry for each subproblem.
2. Every entry in the table has the distance we are optimizing.
3. Every entry also has a pointer to the parent node.
4. There is a recurrence relation.