Sample Final CSE 417

1. Give an expression using Big-O notation that describes the behaviour of the following recurrences as closely as you can. (All fractions are assumed to be rounded down to the nearest integer.)

   1. For n >= 2, T(n)<= 3T(n/3)+cn; T(1)=1.

   2. For n >= 3, T(n)<= T(n-2)+log₂ n; T(1)=T(2)=1.

   3. For n >= 2, T(n)<= 3T(n/2)+cn; T(1)=1.

   4. For n >= 2, T(n)<= 4T(n/4)+cn²; T(1)=1.

   5. For n >= 2, T(n)<= 5T(n/3)+cn²; T(1)=1.

2. Suppose that

   • Procedure Middle takes 5 numbers as input and returns the middle value in the list and runs in constant time.

   • Arrays are indexed starting at 0.

   • The value of Position below is always no more than 7n/10.
   Write a recurrence that describes the running time of the Select procedure as a function of n. EXPLAIN how you arrived at your answer.

   Procedure Select(A,n,v)
     if n <= 4 then return A[0]
     m = n/5
     for i=0 to m-1
        j = 5*i
        B[i] = Middle(A[j],A[j+1],A[j+2],A[j+3],A[j+4])
     endfor
     Pivot = Select(B,m,v)
     Position = Partition(A,0,n-1,Pivot)
     return Select(A,Position,v)
   end
   
   
   Procedure Partition(A,Left,Right,Pivot)
     L = Left
     R = Right
     while L < R do
         while A[L] < = Pivot and L < = Right do L=L+1;
         while A[R] > Pivot and R > = Right do R=R-1;
         if L < R then swap A[L] and A[R]
     return R
   end
   

3. Describe an algorithm to determine, given a directed graph G=(V,E), whether or not G is acyclic (that is, whether or not G contains a cycle). Analyze its running time in terms of n, the size of V, and m, the size of E.

4. Dijkstra's algorithm using heaps takes O((m+n)log n) time to find single-source shortest paths in a weighted undirected graph G=(V,E) with n vertices and m edges. If you know that the edges have only weight 1 or 2 then single-source shortest paths can be computed in O(m+n) time. Pick ONE of the following two methods to show this (or surprise me with one of your own):
   

   • Method 1: Describe how to modify the graph and use Breadth-First Search.

   • Method 2: Describe a data structure for use in Dijkstra's algorithm that is more efficient in this special case than the O(log n) time per update that heaps require.

5. Computability.

   1. What are the basic components of a Turing machine?

   2. What does a Turing machine do in a single step?

   3. Which kind of computing device can compute more things, a Turing machine or a C-program? Justify your answer.

   4. What is the Halting Problem?

   5. Why might we care that the Halting Problem is undecidable? That is, what practical impact does it have?

6. NP-completeness. Let HALF-CLIQUE be the following problem: Given an undirected graph G, does G contain a clique that covers at least half the vertices of G? In this question you will show that HALF-CLIQUE is NP-complete, using the fact that CLIQUE is NP-complete.

   1. Show that HALF-CLIQUE is in NP.

   2. Show that CLIQUE is polynomial-time mapping reducible to HALF-CLIQUE using the following function f:
      On input a pair < G,k> where G has n vertices, f outputs < G'> where G' consists of the graph G together with n extra vertices, k of which are isolated (having no edges anywhere) and the remaining n-k of which are each joined to each other and also to every vertex in G.

      NOTE: First describe WHAT you will need to show. A significant component of the credit will be for this portion. Then fill out the details.