CS502 Quiz 4 by VU Topper RM

Which of the following problems is NOT solved using dynamic programming?

1. Matrix chain multiplication problem
2. Edit distance problem
3. Fractional knapsack problem
4. 0/1 knapsack problem

Correct answer: Fractional knapsack problem

Breadth-first search is a traversal strategy for_________. A. Tree B. Link List C. Array

D. Graph

In a digraph, the number of edges coming in of a vertex is called the

A. Node

B. In-degree

C. Out-degree D. Complete degree

In an undirected graph, we say that an edge is _______________on a vertex if the vertex is an endpoint of the edge. A. Tree B. Directed C. Undirected

D. Incident

Which graph traversal algorithm uses a stack to keep track of vertices?

1. Depth First Search
2. Greedy Algorithm
3. Divide and Conquer
4. Breadth First Search

Correct answer: Depth First Search

In general, a graph G = (V,E) consists of a ___________ and E, a binary relation on V called edges.

A. Finite set of vertices V

B. Infinite set of objects C. Infinite set of nodes D. Infinite set of vertices V

Each time we traverse graph by Breadth-first search algorithm, we count the distance from _________ A. left most node B. neighbors of the starting node

C. starting node

D. right most node

For traversing the graphs, _____________can be visualized as a wave front propagating inward towards root node. A. Binary search B. Linear search

C. Breadth-first search

D. Depth-first Search

In a digraph, the number of edges coming out of a vertex is called the

A. Node B. In-degree

C. Out-degree

D. Complete degree

Brute-force is a simple strategy for computing ______________.

A. shortest path

B. Longest path C. Complete path D. Easiest path In general in comparison with Fractional Knapsack problem,

a. knapsack problem is very easy to solve

b. knapsack problem is hard to solve

c. We cannot compare them d. Both are easy to solve

_______________ is a good way to model some sort of “connection” or “relationship” or “interaction” between pairs of objects taken from a set of objects. A. Vertices B. Tree

C. Graph

D. Node

For a digraph G = (V, E), Sum of in-degree(v) ____________ A. < Sum of out-degree(v)

B. = Sum of out-degree(v)

C. Sum of out-degree(v) D. Not equal to Sum of out-degree(v)

Graphs are important __________ model for many application problems. A. Unpredictable

B. Mathematical

C. Unsystematic D. Haphazard

Which of the following algorithms solves the fractional knapsack problem most effectively?

1. Backtracking
2. Greedy algorithm
3. Divide and conquer

Correct answer: Greedy algorithm