Data Structures and Algorithms 1

The design and analysis of data structures and efficient algorithms has gained considerable importance in recent years. The concept of "e;algorithm"e; is central in computer science, and "e;efficiency"e; is central in the world of money. I have organized the material in three volumes and nine chapters. Vol. 1: Sorting and Searching (chapters I to III) Vol. 2: Graph Algorithms and NP-completeness (chapters IV to VI) Vol. 3: Multi-dimensional Searching and Computational G- metry (chapters VII and VIII) Volumes 2 and 3 have volume 1 as a common basis but are indepen- dent from each other. Most of volumes 2 and 3 can be understood without knowing volume 1 in detail. A general kowledge of algorith- mic principles as laid out in chapter 1 or in many other books on algorithms and data structures suffices for most parts of volumes 2 and 3. The specific prerequisites for volumes 2 and 3 are listed in the prefaces to these volumes. In all three volumes we present and analyse many important efficient algorithms for the fundamental computa- tional problems in the area. Efficiency is measured by the running time on a realistic model of a computing machine which we present in chapter I. Most of the algorithms presented are very recent inven- tions; after all computer science is a very young field. There are hardly any theorems in this book which are older than 20 years and at least fifty percent of the material is younger than 10 years.