## Assignment 1, Chapter 2

Problems: 2.1-3, 2.3-5, 2-3, due Sept 17, 2004. To make sure you have
the right problems, note that the problems begin with:
- 2.1-3: Consider the
*searching problem*: ... Write
pseudocode for *linear search*...
- 2.3-5: Referring back to the searching problem (see Exercise
2.1-3), ...
*Binary search*...
- 2-3:
*Correctness of Horner's rule*

**Note that there are differences in the problem statements between
the various editions of the text!**
Revised Solution (Previous solution set
solved the wrong set of problems.)

## Assignment 2, Chapter 3

Problems 3-2, 3-4, due September 24, 2004.
Solution

## Assignment 3, Chapter 4

Problems 4.2-3, 4-1, due October 1, 2004.
Solution

## Assignment 4, Chapter 5

Problems 5.2-4, 5-1, due October 15, 2004.
#### Hint for 5-1

We are implementing an approximate counter data structure, that
supports two operations, INCREMENT and VALUE. For our
purposes, there will be a sequence of INCREMENT's followed by a
single VALUE that, ideally, returns the number of INCREMENT's. The
idea is that our counter is internally bumped up
only some of the time. In the example of part b, the value
represented is increased by 100 with probability 1/100 each time an
INCREMENT operation is applied.
To analyze this situation, let V_n, a random variable, denote the
value represented by the counter after the n'th increment. So V_n
only takes values among {n_0,n_1,...,}. Try to write V_n as the sum
of X_j's, where the X_j's are independent random variables that are
simple to handle. (That is, you have to figure out what X_j should
be. The random variables X_j could be indicator random variables or
something similar.)

Solution

Midterm I Solution

## Assignment 5, Chapter 11

11-2 and 11-4, due Nov 5. Solution
## Assignment 6, Chapters 15--16

Homework due Monday, Nov 15: 15.4-5, 15-3, 16.3-8. See
note. Solution.