Review Questions for the Final Exam

CS409 - Spring 2000

The exam will take place at 3pm in Olin 245 on Tuesday, May 16.  I will try to arrive early so that we can start right at 3:00pm.

The use of extra material is not permitted during the exam (i.e., no textbook, no notes, no calculator, etc.).

The exam includes material covered from the entire course.  See the Schedule for a list of topics covered in lecture and for the corresponding readings.  The exam will attempt to gauge your knowledge and understanding of course concepts. You should understand the terms used in the course and understand how the various data structures, algorithms, and reductions work, but you shouldn't need to memorize specific code given in the text or in lecture.

The review questions given here are not meant to exhaust the possible topics for exam questions.  Check the previous set of review questions (Solutions to Review Questions for Midterm) the online schedule, and consider reviewing the homework assignments.

Review Questions

  1. Fill in the table below with the expected time for each operation. Use big-O notation. The operations are insert (place a new item in the data structure), member (test if a given item is in the data structure), and findMin (return the value of the minimum item in the data structure). You are to use the standard implementation for each of these data structures, although you can use O(1) extra space if you find it useful to do so.
    Data Structure insert member findMin
    sorted array      
    unsorted array      
    balanced tree (red/black tree)      
    hashing      
    priority queue using a heap      
    sorted linked list      
    unsorted linked list      

     

  2. Briefly explain why sorting with comparisons requires Omega(n log n) time.

     

  3. For this problem, you are to answer some questions about the following graph. 
    		       (e)             (f)
			|		|
			|		|
			|17		|15
			|		|
		3	|	10	|     1
       (A)-------------(c)-------------(g)---------(h)
	|		|		|	  /
	|		|		|	/
	|7		|9		|11   /5
	|		|		|   /
	|	12	|	14	| /
       (b)-------------(d)-------------(i)
    1. In what order are edges added to the Minimum Spanning Tree (MST) using Kruskal's Algorithm (merging subtrees)? List the edges by giving their endpoints.
    2. In what order are edges added to the MST using Prim's Algorithm (growing a single tree) starting from vertex A?

     

  4. Consider the following flow network with source s and sink t. 
    		       (e)------------>(t)
			^	8	^
			|		|
			|17		|15
			|		|
		3	|	10	|     1
       (a)------------>(c)------------>(g)<--------(h)
	^		^		^           ^
	|		|		|           |
	|7		|9		|11         |5
	|		|		|           |
	|	12	|	14	|           |
       (s)------------>(d)------------>(i)----------
    1. What is the maximum flow?
    2. What is the minimum cut?  Where is it?

     

  5. Consider the following decision problem (we'll call it the Graph Value Problem).
    Input: An undirected graph G with n vertices, a list L of n nonnegative integers, and a bound b.
    Question: Is there a way to assign the numbers in L to the vertices of G such that (1) each number is assigned to exactly one vertex and (2) the graph's value is < b?  The value of the graph is the sum of all the edge values; each edge value is the product of the numbers assigned to its endpoint vertices.
    1. Show that the graph value problem is in NP.
    2. Show that Graph-Value is NP-complete by showing that Vertex-Cover reduces to Graph-Value.
    3. Suppose we disallow zero-values.  Is the problem still NP-complete?

     

  6. [from Goodrich & Tomassia] Consider a sequence of n operations where each operation is either a red operation or a blue operation.  The first operation is red and the second is blue.  The running time of a blue operation is always constant.  The running time of the first red operation is constant, but each successive red operation takes twice as long as the previous red operation.  What is the amortized time of the red and blue operations under the following conditions?
    1. There are always Theta(1) blue operations between successive red operations.
    2. There are always Theta(sqrt(n)) blue operations between successive red operations.
    3. The number of blue operations between a red operation and the next red operation is always twice as many as there were between the previous red operation and the current read operation.

     

  7. Suppose we know A<B (i.e., A reduces to B in linear time) and B<C where A, B, and C are all problems. Further, suppose we know that the running time for B is Theta(n log n).
    1. What can be said about the running time for A?

    2. What can be said about the running time for C?

     

  8. In a graph, a cycle is a path that comes back to its initial vertex. A simple cycle is a cycle with no repeated vertices. A Hamiltonian cycle is a simple cycle that visits every vertex of the graph. Consider the following two problems; each takes as input a graph G with n vertices.
        Problem HC: Does G have a Hamiltonian cycle?
        Problem B: Does G have a simple cycle of length exactly floor(n/2)?  (The floor function just rounds its input down to the nearest integer.)
    Problem HC is known to be NP-complete. Show that Problem B is also NP-complete.

    9.  

  9. Problem 6.1 on page 160 of the text. (Show that Vertex Cover is still NP-complete even when all vertices in the graph are restricted to even degree.)

     

  10. Problem 6.2 on page 160 of the text. (Show that Set Cover is NP-complete by making use of Vertex Cover.)