Homework 3

**Abbreviations**

**DPV**=*Algorithms*, by S. Dasgupta, C. Papadimitriou, and U. Vazirani, McGraw-Hill, 2007.**PG**= Problems on Algorithms, 2/e, by Ian Parberry and William Gasarch.

Chapter 3 of DPV

Engineering a Sort Function by J. Bentley and M.D. McIlroy

You many make use of the rsa.hs code to help with calculations.

**Notation:** A[i..j] names the subarray A[i], A[i+1], … A[j].

(10 points) DPV Problem 1.33

(20 points) DPV Problem 1.36

(12 points) DPV Problem 1.45(b).

(36 points) DPV Problem 2.5, parts a, b, c, d, e, and i.

Obvious hint, use the [Master Theorem]. However, for part i, the Master Theorem will work; instead use a simple induction argument with .

(10 points) DPV Problem 2.12

(12 points) PG Problem 337.

*Hint:*There is an infinite recursion that is possible.

**Fermat’s Little Lemma**:

Suppose is prime and . Then .**Euler’s Corollary (of Euler’s Theorem):**

Suppose and are primes with and .

Then .**Euclid’s Rule:**

Suppose . Then .