True, False, or Unknown

Answer the following questions with T for True, F for False, or U for Unknown. "Unknown" means that nobody knows (not just that you don't know).
  1. A (n2) algorithm is faster than a (n3) algorithm for all values of n.
  2. For integers a, b, and c, it is possible to find ab (mod c) in O(log2 c) time.
  3. It is possible to multiply two n-digit numbers in O(log n) time.
  4. It is possible to write a C program that accepts another C program as input and prints "no" if and only if the second program would never call exit().
  5. If co-NP != NP, then P != NP.
  6. If P != NP, then there is not a polynomial time algorithm for COMPOSITE-NUMBER
  7. n! = (2n)
  8. It is not possible to find the prime factors of an integer n in less than (n) steps.
  9. There exist 1000-city instances of the Travelling Salesman Problem for which the optimal tour can be computed exactly in reasonable time (i.e., less than a day).
  10. Generating all combinations of n items taken k takes at least (n 2n) time.

Short Answer

  1. Consider the following C functions: 
    void matrix_add1 (int A[], int B[], int n) {
	int	i, j;

	for (i=0; i<n; i++) for (j=0; j<n; j++)
		A[i] = A[i] + B[i];
}

void matrix_add2 (int A[], int B[], int n) {
	int	i, j;

	for (j=0; j<n; j++) for (i=0; i<n; i++) 
		A[i] = A[i] + B[i];
}
    Which one will take less time for large values of n, and why? Assume they are compiled with no optimizations.
  2. Suppose the minimum degree t for a B-Tree is 4. What is the maximum number of keys this tree can have? What is the minimum number of keys this tree can have? For any internal node, what is the maximum number of children it can have? For any internal node, what is the minimum number of children it can have?
  3. A strongly connected component of a directed graph is a set of vertices S such that if a is in S and b is in S, then there is a path from a to b in the graph. Suppose a graph has exactly one strongly connected component, including all of the vertices. Briefly characterize the transitive closure of this graph.
  4. Briefly describe how Dÿkstra's Algorithm can be used to find the transitive closure of a directed graph.
  5. Recall the keys for the RSA cryptosystem: P = (e,n) is the public key, S = (d,n) is the private key, n is the product of two large primes p and q, and d is the multiplicative inverse of e modulo (p-1)(q-1). Describe how encryption of a message is done. Describe how decryption of a message is done.
  6. Describe a situation in which repeated applications of Dÿkstra's Algorithm would be faster than using Floyd's Algorithm. Why is it faster in this case?
  7. Consider the following decision problem:
    Problem: YES
    Instance: A positive integer n
    Question: Is it true that either n is odd or n is even?
    Note that the answer is always "yes." This problem is not NP-hard. Why not?
  8. In Warshall's Algorithm, what is the difference between the adjacency matrix for the original graph and the first matrix (t(0)) in the sequence of matrices leading to the final result? What is the significance of this difference?
  9. What is a tight lower bound for the time required to find the transitive closure of a graph with n vertices?

Analysis of Algorithms

  1. Recall the definition of the Travelling Salesman Problem:
    Problem: TSP
    Instance: A graph G=(V,E), a function w:E -> R giving the weight of an edge, a vertex v0 in V and a number k in R.
    Question: Is there a path through G starting at vertex v0 such that the length of that path is at most k?
    Consider the following greedy algorithm for solving TSP: 
    Greedy-Solve-TSP (G, v0, k)
	length = 0
	unmark all the vertices
	mark v0 as visited
	u = v0
	while there exist unmarked vertices do:
		find an unmarked vertex w such that the
		f (u, w) is a minimum,
		i.e., find the closest unmarked vertex w
		to u
		sum = sum + weight of (u, w)
		mark w as visited
	end while
	sum = sum + weight of (w, v0)
	if sum <= k then
		return "yes"
	else
		return "no"
	end if
    Assume "marking" is done with an extra Boolean field in the data structure for each vertex.
  2. Consider the following algorithm for B-Tree Search: 
    B-Tree-Search (x, k) // search starting at node x for key k
        i = 1

        while i <= n[x] and k > keyi[x] do
                i++
        end while

        if i <= n[x] and k = keyi[x] then 
                return (x, i)
        
        if leaf[x] then return null

        Disk-Read (ci[x])
        return B-Tree-Search (ci[x], k)
    What is a tight asymptotic upper bound, in terms of the minimum degree t and the number of keys in the entire B-Tree n, on the number of times the statement i++ is executed?
  3. Consider the following array v: 
    i       0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
v[i]    0  0  3  3  2  0  4  8  8  7   0   6  10   7  13  12
    v[0..15] represents disjoint sets from the Union/Find with path compression algorithm.