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