Algorithms in C++, Parts 1-4 Fundamentals,

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.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Algorithms in C++, Parts 1-4 Fundamentals, Data Structure, Sorting, Searching

Summary

Author Biography

Table of Contents

Supplemental Materials