Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, 3rd edition

Published by Addison-Wesley Professional (August 22, 1997) © 1998

  • Robert Sedgewick Princeton University
Products list
  • Available for purchase from all major ebook resellers, including InformIT.com
Products list

Details

  • A print text
  • Free shipping
  • Also available for purchase as an ebook from all major ebook resellers, including InformIT.com
Products list

Details

  • A print text

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, randomised 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.

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.

Need help? Get in touch