From Mohammed J. Zaki

IntroAlgorithms: HW2

HW2 ( Due: Fri Feb 2nd, 11:59:59pm)

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