About the Book
Parts 1-4 of Robert Sedgewick's work
provide extensive coverage of fundamental 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. Increased quantitative information gives students a more
solid basis for comparing algorithms, and hundreds of new exercises reinforce
their learning. Algorithms and data structures described in the book are
expressed in concise implementations in C, so that students can both appreciate
their fundamental properties and test them on real applications.
Features
Related Books
Algorithms/Advanced Data
Structures - Programming Courses (Algorithms/Advanced
Data Structures)
Table of Contents
I. FUNDAMENTALS.
Introduction.
Algorithms.
A Sample Problem -- Connectivity.
Union-Find Algorithms. Perspective.
Summary Of Topics.
Principles Of Algorithm Analysis.
Empirical Analysis.
Predictions And Guarantees.
Growth Of Functions.
Big-Oh Notation.
Example: Connectivity Algorithms.
Computational Complexity.
Perspective.
II. DATA STRUCTURES.
Elementary Data Structures.
Types And Structures.
Arrays.
Linked Lists.
Elementary List Processing.
Storage Allocation For Lists.
Strings.
Compound Structures.
Perspective.
Trees And Recursion.
Properties Of Trees.
Representing Binary Trees.
Representing Forests.
Traversing Trees.
Elementary Recursive Programs.
Divide-And-Conquer.
Depth-First Search.
Removing Recursion.
Elementary Abstract Data Types.
Pushdown Stack Adt.
Stack Adt Implementations.
Queue Adts And Implementations.
String Adt And Implementations.
Set Adt And Implementations.
Amortized Growth For Array Implementations.
III. SORTING.
Elementary Sorting Methods.
Rules Of The Game.
Selection Sort.
Insertion Sort.
Bubble Sort.
Performance Characteristics Of Elementary
Sorts.
Shellsort.
Sorting Other Types Of Data.
Index And Pointer Sorting.
Sorting Linked Lists.
Distribution Counting.
Quicksort.
The Basic Algorithm.
Performance Characteristics Of Quicksort.
Stack Size.
Small Subfiles.
Median-Of-Three Partitioning.
Equal Keys.
Strings And Vectors.
Selection.
Mergesort.
Two-Way Merging.
Abstract Implace Merge.
Top-Down Mergesort.
Improvements To The Basic Algorithm.
Bottom-Up Mergesort.
Performance Characteristics Of Mergesort.
Linked-List Implementations Of Mergesort.
Recursion Revisited.
Priority Queues And Heapsort.
Elementary Implementations.
Heap Data Structure.
Algorithms On Heaps.
Heapsort.
Priority-Queue Abstract Data Type.
Indirect Priority Queues.
Binomial Queues.
Radix Sorting.
Bits, Bytes, And Words.
Binary Quicksort.
Msd Radix Sort.
Three-Way Radix Quicksort.
Lsd Radix Sort.
Performance Characteristics Of Radix
Sorts.
Sublinear-Time Sorts.
Special-Purpose Sorts.
Batcher's Odd-Even Mergesort.
Sorting Networks.
External Sorting.
Sort-Merge Implementations.
Parallel Sort/Merge.
IV. SEARCHING.
Symbol Tables And Bsts.
Symbol-Table Abstract Data Type.
Key-Indexed Search.
Sequential Search.
Binary Search.
Binary Search Trees.
Performance Characteristics Of Bsts.
Index Implementations With Symbol
Tables.
Insertion At The Root In Bsts.
Bst Implementations Of Other Adt Functions.
Balanced Trees.
Randomized Bsts.
Splay Bsts.
Top-Down 2-3-4 Trees.
Red-Black Trees.
Skip Lists.
Performance Characteristics.
Hashing.
Hash Functions.
Separate Chaining.
Linear Probing.
Double Hashing.
Dynamic Hash Tables.
Perspective.
Radix Searching.
Digital Search Trees.
Tries.
Patricia.
Multiway Tries And Tsts.
Text String Index Applications.
External Searching.
Indexed Sequential Access.
B-Trees.
Extendable Hashing.
Virtual Memory.
Program Index.
List Of Figures.
Index.
Epilogue. |
