##
This **preview** shows page *1-2*
out of 5 **pages**.

*View Full Document*

End of preview. Want to read all 5 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

ICS 161 — Algorithms — Spring 2005 — Final ExamPlease answer the following eight questions on the answer sheets provided. Answers written onother pages or on the wrong sheet will not be scored. Be sure to write your name and studentID on all three answer sheets. You may continue your answers on the back of the same answersheet. No books, notes, or calculators may be used during the exam.1. (10 points) Use the Master Method to solve the following two recurrences. Write your answersusing O notation.(a) Q( f) = 2Q( f/2) + log2( f)(b) H(m) = 3H(m/2) + m32. (15 points) The following recursive algorithm sorts a sequence of n numbers. Write down arecurrence describing the running time of the algorithm as a function of n. You do not need tosolve your recurrence.def triplesort(seq):if n <= 1: returnif n == 2:replace seq by [min(seq),max(seq)]returntriplesort(first 2n/3 positions in seq)triplesort(last 2n/3 positions in seq)triplesort(first 2n/3 positions in seq)3. (15 points) Suppose you have an undirected graph with weighted edges, and perform a depth-first search, such that the edges going out of each vertex are always explored in order by weight,smallest first. Is the depth first search tree resulting from this process guaranteed to be a minimumspanning tree? Explain why, if it is, or, if it isn’t, provide a counterexample (specifying the startvertex for the DFS and showing both trees).4. (15 points) We are given as input a sequence L of n numbers, and must partition it into asfew contiguous subsequences as possible such that the numbers within each subsequence addto at most 100. For instance, for the input [80,-40,30,60,20,30] the optimal partition has twosubsequences, [80] and [-40,30,60,20,30]. Let C[i] denote the number of subsequences in theoptimal solution of the subproblem consisting of the first i numbers, and suppose that the lastsubsequence in the optimal solution for all of L has k terms; for instance, for the same exampleas above, C[3] = 1 (the subproblem [80,-40,30] needs only one subsequence) and k = 5 (theoptimal solution for L has five numbers in the last subsequence). Write a formula showing howto compute C[n] from k and from earlier values of C.5. (10 points) How much time would the longest common subsequence algorithm described inclass use to find the longest common subsequence of two strings, one of which has length s andthe other of which has length t? Use O notation.6. (15 points) Suppose you wish to compute the convex hull of n points, all of which have integercoordinates in the range from 1 to n. Describe how to modify the convex hull algorithm describedin class so that it solves this problem in O(n) time.7. (20 points) In the VERTEX COVER decision problem, we are given as input a graph G and anumber k, and must test whether G has a vertex cover with k or fewer vertices; that is, a set of kor fewer vertices that are adjacent to all edges in the graph. This problem is NP-complete.(a) If VERTEX COVER has no polynomial time solution (that is, if P6=NP), can there exist apolynomial time algorithm that takes as input a graph G and finds the vertex cover of G with thesmallest number of vertices? Why or why not?(b) If VERTEX COVER has no polynomial time solution (that is, if P6=NP), can there exista polynomial time algorithm that takes as input a graph G and finds the vertex cover of G withthe largest number of vertices? Why or why not?8. (20 points) Consider the graph below.(a) Write the vertices in an optimal vertex cover for this graph.(b) Write the vertices in the vertex cover produced by the 2-approximation algorithm de-scribed in class for this problem, assuming that it considers the edges in the order of the alpha-betical ordering of their labels.(c) What approximation ratio does the algorithm achieve on this particular input?(d) Why doesn’t your answer to (c) contradict the ratio of 2 already proven for this algorithm?ICS 161 S05 — Answer Sheet 1Name:Student ID:Please answer question 1 in the space below.Please answer question 2 in the space below.Please answer question 3 in the space below.1: 2: 3: 4: 5: 6: 7: 8:total:ICS 161 S05 — Answer Sheet 2Name:Student ID:Please answer question 4 in the space below.Please answer question 5 in the space below.Please answer question 6 in the space below.ICS 161 S05 — Answer Sheet 3Name:Student ID:Please answer question 7 in the space below.Please answer question 8 in the space

View Full Document