CIS 675: Algorthms – Spring 2019
Homework 1

Version 2 (16 January 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.

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 $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)$ .
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).
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.

on even $n$ :	$g(n)$ is large compaired to $f(n)$ and
on odd $n$ :	$g(n)$ is small compaired to $f(n)$ .