Homework 1: Due Monday, October 15 (or email me if you need time till Wednesday).

<p>

First part:  Chapter 2, problems 2.1, 2.2, 2.3, and 2.4.

<p>

Second part:  Prove both parts of proposition 3.6 on page 57.  In other words, prove the following two lemmas about negligible functions:

<ul>
<li>
If e1 and e2 are two negligible functions then e3, where e3(n)
= e1(n)+e2(n), is also a negligible function.
<li>
If e is a negligible function and p is a polynomial then e',
where e'(n) = p(n)*e(n), is also a negligible function.
</ul>

<p>
Bonus points: Chapter 2, problems 2.12 and 2.13.