CS 302 Assignment 2
Due date: Thursday, February 3, 2005, 8:30 AM in class.
All written assignments must be handwritten (not typed or printed from a
computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4
paper. Write your name on each sheet, and do not fold the pages or crimp the
corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on the due date.
Work the following problems from your textbook:
-
Problem 2.1 on page 62.
-
Problem 2.7 on page 62. You don't have to give an analysis: just the
answer. I want the best possible "Big O" answer. That means that, if
it's O(n) and you write O(n log n), your answer is correct, but it will
be marked wrong.
-
Problem 2.14 on page 64.
-
Problem 2.25 on page 69.
-
Problem 2.21 on page 69. (This is harder than 2.25, so that's why it's
out of order.)
(a) I want the asymptotic running time in terms of N.
(b) Then, assume that the number N has n digits, and give me the asymptotic
running time in terms of n. (Those two answers will be radically different.)
(b) is much harder than (a).
You may assume that a multiplication or division of any two numbers takes
only one time step, regardless of the size of the numbers. (This assumption
is actually very unrealistic for extremely large numbers.)
Hint: If your answer (to either part) is faster than the obvious answer,
you must either explain it perfectly, or give me the url of the website
that you got the clue from. (It's out there.)
-
Nothing to turn in for this problem. Just think about it.
Consider this code fragment.
The running time is Theta(log log n). We will eventually use that function,
but not for a while. Nevertheless, it comes up surprisingly often.
-
Nothing to turn in for this problem. Just think about it.
Ravan mentioned "log star" in class. We will eventually use that function,
but not for a while. Nevertheless, it comes up surprisingly often.
Consider this code fragment.
The running time is Theta(log*n).