Spring 2006 1

CSE5311 Design and Analysis of Algorithms

SPRING 2006

Questions for Quiz 2

======Quiz: 11:00 –12:30 PM April 27, 2006

NOTE: You will be required to write THREE or FOUR (randomly picked) out of the following ten questions during the Quiz.

======

  1. Consider a set A = {a1, …, an} and collection B1, B2, …, Bm of subsets of A (i.e., Bi A for each i). Now, H is a hitting set for the collection B1, B2, …, Bm if H contains at least one element from each Bi – that is if HBi is not empty for ach I (so H hits all the sets Bi). The hitting set problem is defined as follows: Given A = {a1, …, an}, a collectionB1, B2, …, Bm of subsets of A, and a number k. Is there a hitting set HA for B1, B2, …, Bm so that the size of H is at most k? Prove that the Hitting set is NP-Complete.
  2. Suppose you are given a set of positive integers A = {a1, …, an} and a positive integer B. A subset SA is called feasible if sum of the numbers in S does not exceed B, i.e., . The sum of the numbers in S will be called the total sum S. It is required to select the feasible subset S of A whose total sum is as large as possible. For example, if A = {8,2,4} and B = 11, then the optimal solution is the subset S = {8.2}. Give a polynomial approximation algorithm for this problem with the following guarantee: It returns a feasible set S  A whose total sum is at least half as large as the maximum total sum of any feasible set S  A. Your algorithm (different from that in the text book on pages 652-653) should have a running time of at most O (n log n).
  3. Show that the 3-Coloring problem for graphs is NP-Complete.
  4. Show that the number of distinct binary search trees b(n) that can be constructed for a set of n orderable keys satisfies the recurrence relation, Find the order of growth of b(n). What implication does the complexity have on the exhaustive search algorithm for constructing an optimal binary search tree?
  5. Show how backtracking technique can be used to solve the Hamiltonian circuit problem. An example graph will be given for the quiz.
  6. Show how Branch and Bound technique can be used to solve the 0-1 Knapsack problem. An example problem will be given for the quiz.
  7. Suppose that we have 2n elements <a1,a2,…a2n> and wish to partition them into the n smallest and the n largest. Prove that we can do this in constant time after sorting <a1,a2,…an> and <an+1, an+2,… a2n>.
  8. Give the algorithm for LU decomposition of a given matrix. Solve the following equation.
  1. Consider a set S of n 2 distinct numbers given in unsorted order.
  2. In O(n) time, determine x,y S such that x-yw-z for all w,z S
  3. In O(n log n) time, determine x,yS such that x y and x-y w-z for all w,z  S such that w z.
  4. The Quicksort algorithm is an efficient and popular sorting technique that sorts a list of keys S[1], S[2], . . ., S[n], recursively by choosing a pivot key. The best-case running time of Quicksort is O(n log2n) and its worst-case running time is O(n2). Several improvements and modifications have been proposed to improve Quicksort’s worst-case behavior. Give a randomized algorithm for improving the running time of quicksort.
  5. Give an approximation algorithm for Maximum-Cut via Local Search.

CSE 5311