282 Design & Analysis of Efficient Algorithms - Fall 2013
Instructor: Henry Kautz
Assigment 1
Due: start of class on Thursday Sept 12
Reading: [DPV] Chapter 0; Chapter 1, only Sec 1.1 and 1.2.3; Chapter 2, skip Sec 2.3 and 2.6
Be sure to follow Homework Rules at http://www.cs.rochester.edu/u/www/courses/282/fall2013/
Chapter 0 Problems:
1. [DVP] 0.1
2. [DVP] 0.2 (Hint for (a): multiply series by c and substract from original series).
Chapter 1 Problems:
3. [DVP] 1.3
4. [DVP] 1.4
5. [DVP] 1.5
6. [DVP] 1.8
7. [DVP] 1.17. Your analysis should assume infinite precision integers.
The recursive algorithm for computing exp(x,y) is:
function exp(x,y)
if y = 0 then return 1
z = exp(x, y >> 1)
if y is even then
return z*z
else
return x*z*z
end
The operator "y >> 1" means to shift the binary representation of y one bit to the
right, discarding the low-order bit. It implements y / 2, rounding down.
8. Modify the exp(x,y) algorithm from problem 7 so that it is more efficient for
the common special case when y is a power of 2. You may use the bitwise operators
<< (shift left), >> (shift right), & (bitwise AND), == (bitwise comparison). Each
runs in time that is linear in the number of bits in its arguments.
Chapter 2 Problems:
9. [DVP] 2.3
10. [DVP] 2.4
11. [DVP] 2.5
12. [DVP] 2.11
13. [DVP] 2.12
Extra-credit Challenge Problems:
[DVP] 1.30
[DVP] 1.33
[DVP] 2.6 (Note that if you knew the length of the array in advance, this would
just be binary search.)
[DVP] 2.31