California State University, Chico
Department of Computer Science

CSCI 356: Design and Analysis of Algorithms
Comprehensive Core Examination Fall 2003

Show all work for problems as partial credit is given for partial solutions:

  1. Without using the Master Theorem deduce the order of T(n) where

  2. (a) Describe the "greedy" method of algorithm design.

    (b) To what general type of problems can the greedy method be applied?

    (c) Describe the minimum cost spanning tree problem for weighted graphs.

    (d) Give a greedy method for solving this problem.

  3. (a) What is a cycle in a directed graph?

    (b) What does it mean to say that a problem is "NP"?

    The "acyclic" problem is to determine whether a directed graph is cycle-free.

    (c) Explain why the acyclic problem for graphs is (or is not) NP

    (d) Explain why the acyclic problem for graphs is (or is not) NP hard