Homework 3, due Thursday, Feb 9, in class.
Do the following exercises in the GT Book, all in chapter 4:
Do the following (twelve) R-4.x exercises, where
x = 6, 7, 12, 15-19, 21, 28, 29, 34
Also do C-4.11
Some modifications to these:
In R-4.21 instead of the current columns in the book:
[1 sec, 1hr, 1month, 1century]
I want you to use the following columns instead:
[1 sec, 17 minutes, 12 days, 32 years]
The reason is that in this way the time in column i is about 1000x the time in column (i-1),
so it's easier to give answers without using the calculator.
You do not have to be exact. In fact, you can be wrong up to a factor of 5x, so you should
give us only the order of the value, i.e. 10^{300,000}, and not the exact value like
2.1425*10^{300,000}, etc.
In C-4.11, assume that addition and multiplication are primitive operations, but
dont assume that there's a primitive operation that computes an exponentiation.
(Such assumption would be unjustified by any hardware or software we know of.)
Note that R-4.28 is implied by the claim I stated in the lecture, namely that every
polynomial of degree d is O(n^d). However, you cannot "solve" this one by just stating
that it's implied by this claim. Either show that this claim is true in general or show
that this particular case of it is.
*Scoring*:
R-12 and 21 are 15 points
R-27, 28, and C-11 are 10 points
All the others are 5 points