Solutions to Math Homework 1
1 Problem 1
The algorithm will print GCD and LCM of X and Y .
To prove: GCD(X,Y) is given by
while LCM(X,Y) is given by
Proof: Invariant for GCD computation are 
GCD(X, Y ) =
GCD(x, y). Verify both steps maintain this invariant using the number theory
result that GCD(x,y) = GCD(x-y,y) = GCD(x,y-x). At termination we have
x = y and therefore GCD(x, y) = GCD(x, x) =
Invariant for LCM computation is uy +vx. Verify that both
steps of algorithm
maintain uy+vx as invariant. Therefore from the initialization conditions when
algorithm terminates uy+vx = XY +XY . Now since x = y = GCD(X, Y ) we
get
× GCD(X, Y ) = XY . Using the number theory result we know that
is the LCM.
2 Problem 2(0.1)
3 Problem 3(0.2)
The given function g(n) turns out to be a geometic series
and it evaluates to
(1)
(a) When c < 1, lower bound on Equation 1 can be obtained
by analyzing the
case when n = 0 which is 1. Similarly upper bound is obtained by analyzing
the case when n → ∞ which comes out to be
.
Since we got two constants
bounding Equation 1 g (n) is Ө(1)
(b) When c > 1 similar analysis will produce upper and
lower bounds as cn
which makes g(n) as Ө(cn)
(c) When c = 1, the bound of Ө(n) is straight forward as
each term of g(n)
evaluates to 1 and there are n terms.
4 Problem 4(0.3)
(a) Base case :
Hypothesis :
Induction :
Therefore
(b) Using the generating function derivation shown in class Fibonacci numbers
can be represented as
(2)
where
and
Now choosing c as log
ø we need to prove that
We use induction to prove that.
Base case :
Hypothesis :
Induction :
Using induction hypothesis
Therefore c is given as log ø
(c)Any number in between 0.5 and logø will suffice. Largest is logø .
5 Problem 5(1.31)
(a) N is an n-bit number. N! is given by 1.2.3...N.
Upper Bound : Assuming each number 1,2,3,...,N is represented by n bits, the
result of multiplying N n -bit number will give a number of N n bits where
N = 2n. Hence it is O(N*n)
Lower Bound : Since each number i
(1, 2, ...,N) can be optimally represented
by log i bits , total number of bits in N! is given by
which is log N !.
Using Sterling’s approximation or using a factor argument we know
which implies that total number of bits in N! is lower bounded by N log N. It
turns out to be
Combining both we get ө(N*n)
(b) A simple iterative algorithm to solve the problem is given by:
Input : N
Output : N!
prod = 1
for i = 1 to N
prod = prod * i
return prod
Complexity analysis :We present a worst case bound. Assuming each of the
number 1,2,3,...,N are n-bit long each multiplication computes product of a
i ×n bit number with n bit number. Therefore total time taken by the for-loop
is given by
(n × in) which turns out to be O(N2 × n2)
6 Problem 6(1.32)
Given numbers X and Y, apply Euclid algorithm (page 20) to compute GCD(X,Y).
Followed by that get LCM(X,Y) by
GCD computation takes O(n3)
where n are the number of bits in X, Y. Final LCM computation takes O(n2).
Therefore the algorithm is bounded by O(n3).
| Prev | Next |