# CIS 675: Algorthms – Spring 2019 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.

#### Problems

1. PG Problem 27   (12 points) * Make use of the binomial theorem
• Also, any non-zero number divides zero.
2. PG Problem 176.   (12 points)
• Take a look at the solution of problem 171 on page 36 of PG.
3. PG Problem 178.   (12 points)
• Try a disproof with $f(n) = n$ and $g$ such that

 on even $n$: $g(n)$ is large compaired to $f(n)$ and on odd $n$: $g(n)$ is small compaired to $f(n)$.
4. DPV Exercise 0.1 parts a, b, c, e, f, h, l, and m.   (48 points)
5. DPV Exercise 0.2.   (12 points)

6. 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).
7. PG Problem 52.   (Not graded)

#### Notes

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