Log In
Or create an account ->
Imperial Library
Home
About
News
Upload
Forum
Help
Login/SignUp
Index
About This eBook
Title Page
Copyright Page
Preface
Scope
Use in the Curriculum
Algorithms of Practical Use
Programming Language
Acknowledgments
Dedication Page
Notes on Exercises
Contents
Part One: Fundamentals
Chapter One. Introduction
1.1 Algorithms
1.2 A Sample Problem: Connectivity
Exercises
1.3 Union–Find Algorithms
Exercises
1.4 Perspective
Exercises
1.5 Summary of Topics
Chapter Two. Principles of Algorithm Analysis
2.1 Implementation and Empirical Analysis
Exercises
2.2 Analysis of Algorithms
Exercises
2.3 Growth of Functions
Exercises
2.4 Big-Oh Notation
Exercises
2.5 Basic Recurrences
Exercises
2.6 Examples of Algorithm Analysis
Exercises
2.7 Guarantees, Predictions, and Limitations
Exercise
References for Part One
Part Two: Data Structures
Chapter Three. Elementary Data Structures
3.1 Building Blocks
Exercises
3.2 Arrays
Exercises
3.3 Linked Lists
Exercises
3.4 Elementary List Processing
Exercises
3.5 Memory Allocation for Lists
Exercises
3.6 Strings
Exercises
3.7 Compound Data Structures
Exercises
Chapter Four. Abstract Data Types
4.1 Abstract Objects and Collections of Objects
Exercises
4.2 Pushdown Stack ADT
Exercises
4.3 Examples of Stack ADT Clients
Exercises
4.4 Stack ADT Implementations
Exercises
4.5 Creation of a New ADT
Exercises
4.6 FIFO Queues and Generalized Queues
Exercises
4.7 Duplicate and Index Items
Exercises
4.8 First-Class ADTs
Exercises
4.9 Application-Based ADT Example
Exercises
4.10 Perspective
Chapter Five. Recursion and Trees
5.1 Recursive Algorithms
Exercises
5.2 Divide and Conquer
Exercises
5.3 Dynamic Programming
Exercises
5.4 Trees
Exercises
5.5 Mathematical Properties of Binary Trees
Exercises
5.6 Tree Traversal
Exercises
5.7 Recursive Binary-Tree Algorithms
Exercises
5.8 Graph Traversal
Exercises
5.9 Perspective
References for Part Two
Part Three: Sorting
Chapter Six. Elementary Sorting Methods
6.1 Rules of the Game
Exercises
6.2 Selection Sort
Exercises
6.3 Insertion Sort
Exercises
6.4 Bubble Sort
Exercises
6.5 Performance Characteristics of Elementary Sorts
Exercises
6.6 Shellsort
Exercises
6.7 Sorting of Other Types of Data
Exercises
6.8 Index and Pointer Sorting
Exercises
6.9 Sorting of Linked Lists
Exercises
6.10 Key-Indexed Counting
Exercises
Chapter Seven. Quicksort
7.1 The Basic Algorithm
Exercises
7.2 Performance Characteristics of Quicksort
Exercises
7.3 Stack Size
Exercises
7.4 Small Subfiles
Exercises
7.5 Median-of-Three Partitioning
Exercises
7.6 Duplicate Keys
Exercises
7.7 Strings and Vectors
Exercises
7.8 Selection
Exercises
Chapter Eight. Merging and Mergesort
8.1 Two-Way Merging
Exercises
8.2 Abstract In-place Merge
Exercises
8.3 Top-Down Mergesort
Exercises
8.4 Improvements to the Basic Algorithm
Exercises
8.5 Bottom-Up Mergesort
Exercises
8.6 Performance Characteristics of Mergesort
Exercises
8.7 Linked-List Implementations of Mergesort
Exercises
8.8 Recursion Revisited
Exercises
Chapter Nine. Priority Queues and Heapsort
Exercises
9.1 Elementary Implementations
Exercises
9.2 Heap Data Structure
Exercises
9.3 Algorithms on Heaps
Exercises
9.4 Heapsort
Exercises
9.5 Priority-Queue ADT
Exercises
9.6 Priority Queues for Index Items
Exercises
9.7 Binomial Queues
Exercises
Chapter Ten. Radix Sorting
10.1 Bits, Bytes, and Words
Exercises
10.2 Binary Quicksort
Exercises
10.3 MSD Radix Sort
Exercises
10.4 Three-Way Radix Quicksort
Exercises
10.5 LSD Radix Sort
Exercises
10.6 Performance Characteristics of Radix Sorts
Exercises
10.7 Sublinear-Time Sorts
Exercises
Chapter Eleven. Special-Purpose Sorting Methods
11.1 Batcher’s Odd–Even Mergesort
Exercises
11.2 Sorting Networks
Exercises
11.3 External Sorting
Exercises
11.4 Sort–Merge Implementations
Exercises
11.5 Parallel Sort–Merge
Exercises
References for Part Three
Part Four: Searching
Chapter Twelve. Symbol Tables and Binary Search Trees
12.1 Symbol-Table Abstract Data Type
Exercises
12.2 Key-Indexed Search
Exercises
12.3 Sequential Search
Exercises
12.4 Binary Search
Exercises
12.5 Binary Search Trees (BSTs)
Exercises
12.6 Performance Characteristics of BSTs
Exercises
12.7 Index Implementations with Symbol Tables
Exercises
12.8 Insertion at the Root in BSTs
Exercises
12.9 BST Implementations of Other ADT Functions
Exercises
Chapter Thirteen. Balanced Trees
Exercises
13.1 Randomized BSTs
Exercises
13.2 Splay BSTs
Exercises
13.3 Top-Down 2-3-4 Trees
Exercises
13.4 Red–Black Trees
Exercises
13.5 Skip Lists
Exercises
13.6 Performance Characteristics
Exercises
Chapter Fourteen. Hashing
14.1 Hash Functions
Exercises
14.2 Separate Chaining
Exercises
14.3 Linear Probing
Exercises
14.4 Double Hashing
Exercises
14.5 Dynamic Hash Tables
Exercises
14.6 Perspective
Exercises
Chapter Fifteen. Radix Search
15.1 Digital Search Trees
Exercises
15.2 Tries
Exercises
15.3 Patricia Tries
Exercises
15.4 Multiway Tries and TSTs
Exercises
15.5 Text-String–Index Algorithms
Exercises
Chapter Sixteen. External Searching
16.1 Rules of the Game
16.2 Indexed Sequential Access
Exercises
16.3 B Trees
Exercises
16.4 Extendible Hashing
Exercises
16.5 Perspective
Exercises
References for Part Four
Index
Code Snippets
← Prev
Back
Next →
← Prev
Back
Next →