# CS 410 Fall 99

Homework 3

Due Thursday, October 21

## Reading

Read CLR ch. 12, 23.

## Written Exercises

- CLR 19.2-1 p. 394. Use t=4.
- CLR 9.2-2 p. 177.
- CLR 9.4-2 p. 182.
- Suppose you want to maintain a set of intervals. Intervals will be given by their two
endpoints; that is, the interval [5,9] is the set of numbers between 5 and 9 (the two ends
included). The operations you will have to do are Insert(x,y) and Count(i). Insert(x,y)
inserts the new interval [x,y], and Count(i) outputs the number of intervals that contain
point i. For example, for the set of intervals [1,5], [3,7], [4,6] we have Count(5) = 3
and Count(2) = 1. Note that we do not need Search and Delete. Design a data structure that
allows you to do both Insert and Count in O(log n) time, where n is the number of
intervals in the set. You may use any data structure that has been discussed in class
without explaining how it works. Hint: Note that Count(i) can be computed as the number of
intervals with low end point at most i minus the number of intervals with high end point
less than i.
- Give an O(N) algorithm to sort N integers in the range [0,N
^{2}].

## Programming Assignment 2: A Second Chance

Click here for information on how to get points
back on programming assignment 2.