CS 410 Fall 99
Homework 3
Due Thursday, October 21

Reading

Read CLR ch. 12, 23.

Written Exercises

  1. CLR 19.2-1 p. 394. Use t=4.
  2. CLR 9.2-2 p. 177.
  3. CLR 9.4-2 p. 182.
  4. 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.
  5. Give an O(N) algorithm to sort N integers in the range [0,N2].

Programming Assignment 2: A Second Chance

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