Homework 1

**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.

- Chapters 0 and 1 of DPV
- The Big-O-ology writeup

**PG Problem 27***(12 points)** Make use of the binomial theorem- Also, any non-zero number divides zero.

**PG Problem 176.***(12 points)*- Take a look at the solution of problem 171 on page 36 of PG.

**PG Problem 178.***(12 points)*Try a disproof with and such that

on even : is large compaired to and on odd : is small compaired to .

**DPV Exercise 0.1 parts a, b, c, e, f, h, l, and m.***(48 points)*- Make use of the Limit Rule + the Math Facts from the Big-O-ology writeup.

**DPV Exercise 0.2.***(12 points)***DPV Exercise 0.3a.***(Not graded)*- With induction proofs about the Fibonacci numbers you often have
*two*base cases*(because of the two base cases in the Fibonacci inductive definition)*.

- With induction proofs about the Fibonacci numbers you often have
**PG Problem 52.***(Not graded)*

The Math Facts on page 16 of the Big-O-ology writeup is quite helpful for some of these problems.

The answers to these problems

*should*be released on Wednesday January 23. If not, fuss at the instructor.