I&C SCI 161 Midterm: ICS 161 Midterm 1

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

Document Summary

Ics 161 algorithms winter 2005 first midterm. Please answer the following six 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. Why or why not: (15 points) use the master method to solve the recurrence x(n) = 9x(n/3) + n2 log n. use. You may assume that x has at most n digits, and that each division and modulus by 10 operation may be performed in time o(n), faster than general-purpose division and modulus operations. Finding the prime factors of a composite number. Computing discrete logarithms modulo a composite number. Please answer question 1 in the space below. Please answer question 2 in the space below. Please answer question 3 in the space below. Please answer question 4 in the space below.