I&C SCI 161 Study Guide - Final Guide: Subsequence, Memory Stick, Longest Common Subsequence Problem

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 161
• Professor: all

Document Summary

Ics 161 algorithms spring 2005 final exam. Please answer the following eight questions on the answer sheets provided. Answers written on other pages or on the wrong sheet will not be scored. Be sure to write your name and student. You may continue your answers on the back of the same answer sheet. No books, notes, or calculators may be used during the exam: (10 points) use the master method to solve the following two recurrences. Write your answers using o notation. (a) q( f ) = 2q( f /2) + log2( f ) (b) h(m) = 3h(m/2) + m3: (15 points) the following recursive algorithm sorts a sequence of n numbers. Rst search, such that the edges going out of each vertex are always explored in order by weight, smallest rst. For instance, for the input [80,-40,30,60,20,30] the optimal partition has two subsequences, [80] and [-40,30,60,20,30]. Please answer question 1 in the space below.