Q1. (10 points; 5 points per part) Give an algorithm (pseudo code, with explanation) to compute \(2^{2^n}\) in linear time, assuming multiplication of **arbitrary** size integers takes unit time. What is the bit-complexity if multiplications do not take unit time, but are a function of the bit-length.

Q2. (10 points total; 5 points per part) Consider the problem of computing N! = 1 · 2 · 3···N.

(a) If N is an n-bit number, how many bits long is N! in O() notation (give the tightest bound)?

(b) Give an algorithm to compute N! and analyze its running time.

Q3. (10 points; 5 points per part) Find the GCD of 1492 and 1776, using a) the prime factorization method and using Euclid's method, and b) express the GCD as an integer linear combination of the two inputs.

Retrieved from http://www.cs.rpi.edu/~zaki/www-new/pmwiki.php/IntroAlgorithms/HW2

Page last modified on January 30, 2018, at 12:11 PM