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

## Assignment 3, Chapter 4

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

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

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.