CSC 477/677 Assignment 2
Due date, February 5, 2004, 4:00 PM.
All assignments must be handwritten
(not typed or printed from a computer file)
in your own handwriting, on 8.5 by 11 inch paper. Write your name on
each sheet, and do not fold the pages or crimp the corners.
Turn the pages in to me or to the graduate assistant on the due date.
-
Work problem 4.1 on page 139 of your textbook.
-
Work problem 4.2 on page 140 of your textbook.
-
Compute the asymptotic complexity of the procedure joe,
in terms of the value of its input n.
You must give the answer using Theta.
-
Work problem 4.6 on page 140 of your textbook.
-
Euclid's algorithm for finding the greatest common divisor of
two non-negative integers is mentioned on page 2 of your textbook,
and is described in pseudocode on page 71.
Suppose that n and m are two
positive integers, and that m < n.
How many steps does it take Euclid's algorithm to compute the
greatest common divisor of n and m?
I want the answer expressed asymptotically in terms of n,
for example, O(n) or Theta(n),
or O(log n), or whatever.
You may assume that it takes one time step to do any operation,
such as mod, or to do an assignment.
You must give the sharpest possible answer.
If the correct answer is Theta(n) and you
write O(n), for example,
you will lose points, even though technically your answer
is correct, because it is not the sharpest possible answer.
Do not give a proof that your answer is correct.
Back to
Course Page