Topological Sort Is a Greedy Algorithm

QuizAlgorithmsCSE 4081/5211Fall 2004

Points 30 (2 per question)

Topological sort is a greedy algorithm. True / False (True)

Quicksort exchanges elements, including the equal elements, which are on the wrong side of pivot’s correct position. True / False (True)

The greedy algorithm for the Multi-processor scheduling problem does not always find the correct answer. True / False (True)

In the bin-packing problem each bin is presumed to be of size ____. (one/equal)

The greedy algorithm for the Rational knapsack problem does not always find the correct result. True / False (False)

If a polynomial algorithm has its asymptotic time complexity as a function of an input value (e.g., the dynamic programming algorithm of the 0-1 Knapsack problem), then the algorithm is called ______(Pseudo-polynomial algorithm)

A Theta(n log n) algorithm is more efficient than a Theta(n^2) algorithm for solving the same problem. True / False (True)

A graph with only one odd degree node (all other nodes have even degree) can have a Euler circuit starting with that node. True / False (False)

The number of edges of a connected tree with n nodes is ____ (n-1)

Djikstra’s algorithm is a greedy algorithm because it ______

(picks up the node with shortest path from the source in each iteration)

A matrix chain product problem has a chain of four matrices ABCD. Show the order for the matrix chains in which the minimum costs will be calculated in the dynamic programming algorithm, e.g., the algorithm will first start with initializing for chains of length one (A), (B), (C) and (D) (all values being zero for these cases). Answer: (A) (B) (C) (D) (AB) ….

(Ans: (A), (B), (C), (D), (AB), (BC), (CD), (ABC), (BCD), (ABCD))

There are three columns in a variable-length page and the following articles are to be placed in the columns such that the page length is minimal. Articles have no pre-assigned ordering for placement on the page, and they may not be split across the columns. The list of the lengths of the articles in inches is {3, 5, 1, 7, 10, 6, 2, 3}. Mention which problem is it akin to (that has a greedy approximate algorithm)? ______

(The Multi-processor Last Finish Time problem or the “Multi-processor” problem)

On a graph (V, E) with V as the set of nodes and E as the set of edges represented as adjacency lists, what is the complexity of the following psudo-code (|V|=n, |E|=e):

For each node v in V

For each node w adjacent to v

Print (v,w)

End loops;

(Theta(n+e) or Theta(e), Big O instead of Theta is always acceptable as a notation)

All NP-complete problems belong to the NP-class of problems. True / False (True)

The set of NP-complete problems and that of P-class problems overlap to a non-empty set. True / False (False)