Algorithms in C, Parts 1-4

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. 0201314525T04062001