CIS 675: Algorthms – Spring 2019
Homework 3

Version 1 (1 February 2019)

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.

Reading

Chapter 3 of DPV
Engineering a Sort Function by J. Bentley and M.D. McIlroy

Problems

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 $T(0) = 1$ .
(10 points) DPV Problem 2.12
(12 points) PG Problem 337.

Hint: There is an infinite recursion that is possible.

Reference

Fermat’s Little Lemma:
Suppose $p$ is prime and $1\leq a <p$ . Then $a^{p-1} \cong 1 \bmod p$ .
Euler’s Corollary (of Euler’s Theorem):
Suppose $p$ and $q$ are primes with $p\not=q$ and $\gcd(a,p\cdot q)=1$ .
Then $a^{(p-1)(q-1)} \cong 1 \bmod (p\cdot q)$ .
Euclid’s Rule:
Suppose $x \geq y>0$ . Then $\gcd(x, y) = \gcd(y, x \bmod y)$ .
Wikipedia on least common multiples
Wikipedia on the Master Method