1. Introduction

This chapter briefly reviews some of the main concepts used throughout the rest of the book. Section 1.1 describes the interfaces implemented by all the data structures described in this book. It should be considered required reading. The remaining sections discuss asymptotic (big-Oh) notation, probability and randomization, the model of computation, and the sample code and typesetting conventions. A reader with or without a background in these areas can easily skip them now and come back to them later if necessary.