This is the latest offering in the Algorithms series from esteemed author and former Donald Knuth student, Robert Sedgewick. Using C++, Parts 1-4 of Sedgewick's work provide extensive data structures and algorithms for sorting, searching, and related applications. They reflect the third edition's greater emphasis on abstract data types (ADTs). Coverage includes more than 100 key algorithms for sorting, selection, priority queue ADT implementations, and symbol table ADT (searching) implementations. Also included are new implementations of binomial queues, multiway radix sorting, Batcher's sorting networks, randomized BSTs, splay trees, skip lists, and multiway tries.

Robert Sedgewick is the William O. Baker Professor of Computer Science at Princeton University. He is a Director of Adobe Systems and has served on the research staffs at Xerox PARC, IDA, and INRIA. He earned his Ph.D from Stanford University under Donald E. Knuth.

Christopher J. Van Wyk is Professor of Mathematics and Computer Science at Drew University. The author of Data Structures and C Programs (Addison-Wesley, 1988), he has served on the research staff at Bell Laboratories, where he is now a consultant. Robert Sedgewick and Christopher Van Wyk both earned their Ph.D. degrees from Stanford University under Donald E. Knuth.

0201350882AB06262002

Fundamentals

Introduction

3

(24)

Algorithms

4

(3)

A Sample Problem---Connectivity

7

(4)

Union-Find Algorithms

11

(11)

Perspective

22

(2)

Summary of Topics

24

(3)

Principles of Algorithm Analysis

27

(42)

Implementation and Empirical Analysis

28

(5)

Analysis of Algorithms

33

(3)

Growth of Functions

36

(8)

Big-Oh Notation

44

(5)

Basic Recurrences

49

(4)

Examples of Algorithm Analysis

53

(6)

Guarantees, Predictions, and Limitations

59

(10)

Data Structures

Elementary Data Structures

69

(60)

Building Blocks

70

(13)

Arrays

83

(8)

Linked Lists

91

(6)

Elementary List Processing

97

(9)

Memory Allocation for Lists

106

(4)

Strings

110

(6)

Compound Data Structures

116

(13)

Abstract Data Types

129

(72)

Abstract Objects and Collections of Objects

140

(4)

Pushdown Stack ADT

144

(3)

Examples of Stack ADT Clients

147

(6)

Stack ADT Implementations

153

(5)

Creation of a New ADT

158

(8)

FIFO Queues and Generalized Queues

166

(9)

Duplicate and Index Items

175

(4)

First-Class ADTs

179

(13)

Application-Based ADT Example

192

(6)

Perspective

198

(3)

Recursion and Trees

201

(64)

Recursive Algorithms

202

(8)

Divide and Conquer

210

(12)

Dynamic Programming

222

(8)

Trees

230

(10)

Mathematical Properties of Trees

240

(3)

Tree Traversal

243

(6)

Recursive Binary-Tree Algorithms

249

(6)

Graph Traversal

255

(6)

Perspective

261

(4)

Sorting

Elementary Sorting Methods

265

(50)

Rules of the Game

267

(6)

Selection Sort

273

(1)

Insertion Sort

274

(3)

Bubble Sort

277

(2)

Performance Characteristics of Elementary Sorts

279

(6)

Shellsort

285

(8)

Sorting Other Types of Data

293

(6)

Index and Pointer Sorting

299

(8)

Sorting Linked Lists

307

(5)

Key-Indexed Counting

312

(3)

Quicksort

315

(32)

The Basic Algorithm

316

(5)

Performance Characteristics of Quicksort

321

(4)

Stack Size

325

(3)

Small Subfiles

328

(3)

Median-of-Three Partitioning

331

(5)

Duplicate Keys

336

(3)

Strings and Vectors

339

(2)

Selection

341

(6)

Merging and Mergesort

347

(26)

Two-Way Merging

348

(3)

Abstract In-Place Merge

351

(2)

Top-Down Mergesort

353

(4)

Improvements to the Basic Algorithm

357

(2)

Bottom-Up Mergesort

359

(4)

Performance Characteristics of Mergesort

363

(3)

Linked-List Implementations of Mergesort

366

(4)

Recursion Revisited

370

(3)

Priority Queues and Heapsort

373

(44)

Elementary Implementations

377

(4)

Heap Data Structure

381

(2)

Algorithms on Heaps

383

(6)

Heapsort

389

(7)

Priority-Queue ADT

396

(6)

Priority Queues for Index Items

402

(4)

Binomial Queues

406

(11)

Radix Sorting

417

(34)

Bits, Bytes, and Words

419

(4)

Binary Quicksort

423

(4)

MSD Radix Sort

427

(8)

Three-Way Radix Quicksort

435

(4)

LSD Radix Sort

439

(3)

Performance Characteristics of Radix Sorts

442

(5)

Sublinear-Time Sorts

447

(4)

Special-Purpose Sorts

451

(38)

Batcher's Odd-Even Mergesort

453

(5)

Sorting Networks

458

(8)

External Sorting

466

(6)

Sort-Merge Implementations

472

(6)

Parallel Sort/Merge

478

(11)

Searching

Symbol Tables and BSTs

489

(54)

Symbol-Table Abstract Data Type

491

(8)

Key-Indexed Search

499

(3)

Sequential Search

502

(8)

Binary Search

510

(5)

Binary Search Trees (BSTs)

515

(6)

Performance Characteristics of BSTs

521

(4)

Index Implementations with Symbol Tables

525

(4)

Insertion at the Root in BSTs

529

(4)

BST Implementations of Other ADT Functions

533

(10)

Balanced Trees

543

(44)

Randomized BSTs

547

(7)

Splay BSTs

554

(6)

Top-Down 2-3-4 Trees

560

(5)

Red-Black Trees

565

(10)

Skip Lists

575

(8)

Performance Characteristics

583

(4)

Hashing

587

(36)

Hash Functions

588

(9)

Separate Chaining

597

(5)

Linear Probing

602

(6)

Double Hashing

608

(5)

Dynamic Hash Tables

613

(4)

Perspective

617

(6)

Radix Search

623

(46)

Digital Search Trees

624

(4)

Tries

628

(9)

Patricia Tries

637

(9)

Multiway Tries and TSTs

646

(18)

Text String Index Applications

664

(5)

External Searching

669

(38)

Rules of the Game

671

(3)

Indexed Sequential Access

674

(2)

B Trees

676

(15)

Extendible Hashing

691

(12)

Perspective

703

(4)

Index

707

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

This book is intended to survey the most important computer algorithms in use today, and to teach fundamental techniques to the growing number of people in need of knowing them. It can be used as a textbook for a second, third, or fourth course in computer science, after students have acquired basic programming skills and familiarity with computer systems, but before they have taken specialized courses in advanced areas of computer science or computer applications. The book also may be useful for self-study or as a reference for people engaged in the development of computer systems or applications programs, since it contains implementations of useful algorithms and detailed information on these algorithms' performance characteristics. The broad perspective taken makes the book an appropriate introduction to the field. I have completely rewritten the text for this new edition, and I have added more than a thousand new exercises, more than a hundred new figures, and dozens of new programs. I have also added detailed commentary on all the figures and programs. This new material provides both coverage of new topics and fuller explanations of many of the classic algorithms. A new emphasis on abstract data types throughout the book makes the programs more broadly useful and relevant in modern programming environments. People who have read old editions of the book will find a wealth of new information throughout; all readers will find a wealth of pedagogical material that provides effective access to essential concepts. Due to the large amount of new material, we have split the new edition into two volumes (each about the size of the old edition) of which this is the first. This volume covers fundamental concepts, data structures, sorting algorithms, and searching algorithms; the second volume covers advanced algorithms and applications, building on the basic abstractions and methods developed here. Nearly all the material on fundamentals and data structures in this edition is new. This book is not just for programmers and computer-science students. Nearly everyone who uses a computer wants it to run faster or to solve larger problems. The algorithms in this book represent a body of knowledge developed over the last 50 years that has become indispensible in the efficient use of the computer, for a broad variety of applications. From N-body simulation problems in physics to genetic-sequencing problems in molecular biology, the basic methods described here have become essential in scientific research; and from database systems to Internet search engines, they have become essential parts of modern software systems. As the scope of computer applications becomes more widespread, so grows the impact of many of the basic methods covered here. The goal of this book is to serve as a resource for students and professionals interested in knowing and making intelligent use of these fundamental algorithms as basic tools for whatever computer application they might undertake. Scope The book contains 16 chapters grouped into four major parts: fundamentals, data structures, sorting, and searching. The descriptions here are intended to give readers an understanding of the basic properties of as broad a range of fundamental algorithms as possible. The algorithms described here have found widespread use for years, and represent an essential body of knowledge for both the practicing programmer and the computer-science student. Ingenious methods ranging from binomial queues to patricia tries are described, all related to basic paradigms at the heart of computer science. The second volume consists of four additional parts that cover strings, geometry, graphs, and advanced topics. My primary goal in developing these books has been to bring together the fundamental methods from these diverse areas, to provide access to the best methods known for solving problems by computer. You will most appreciate the material in t