Search
Next:
Contents
Algorithm Archive
(Work in progress)
Scott Gasch,
scott@wannabe.guru.org
Id
:
alg
.
tex
,
v
1.9 1999/01/03 00:54:49
scott Exp scott
Contents
0.1 Introduction
0.1.1 What's New
0.1.2 What needs work
0.1.3 Conventions
0.1.4 Example Code
0.2 Data Searching and Storage
0.2.1 Linear Search
0.2.1.1 Source Code
0.2.2 Binary Search
0.2.2.1 Analysis
0.2.2.2 Source Code
0.2.2.3 References
0.2.3 Binary Search Trees
0.2.3.1 Inserting and Deleting Nodes
0.2.3.2 Source Code
0.2.3.3 References
0.2.4 Red-Black Trees
0.2.4.1 Insertion Operation
0.2.4.2 Deletion
0.2.4.3 Source Code
0.2.4.4 References
0.2.5 B+-Trees
0.2.5.1 Source Code
0.2.6 Boyer-Moore String Searching
0.2.6.1 Source Code
0.2.6.2 References
0.2.7 Hashing
0.2.7.1 Selecting a Hash Function
0.2.7.2 Dealing with Collisions
0.2.7.3 Choosing a Table Size
0.2.7.4 Source Code
0.2.7.5 One-way hashing
0.2.7.6 References
0.2.8 Skip lists
0.2.8.1 Source Code
0.2.8.2 References
0.2.9 Tries
0.2.9.1 Source Code
0.2.10 Quadtrees and Octrees
0.2.10.1 Octree Source Code
0.3 Sorting Algorithms
0.3.1 The Quicksort
0.3.1.1 Picking a Pivot Value
0.3.1.2 Partitioning
0.3.1.3 Analysis
0.3.1.4 Improvement Strategies
0.3.1.5 Source Code
0.3.1.6 References
0.3.2 The Mergesort
0.3.2.1 Analysis
0.3.2.2 Improvements
0.3.2.3 Source Code
0.3.2.4 References
0.3.3 Heapsort
0.3.3.1 Building a Max-Heap
0.3.3.2 Analysis
0.3.3.3 Operations on a Max-Heap
0.3.3.4 Analysis
0.3.3.5 Source Code
0.3.3.6 References
0.3.4 Benchmarking the Quicksort and the Heapsort
0.3.5 Insertion Sort
0.3.5.1 Analysis
0.3.5.2 Improvements
0.3.5.3 Source Code
0.3.6 Shellsort
0.3.6.1 Analysis
0.3.6.2 Source Code
0.3.7 Selection Sort
0.3.7.1 Analysis
0.3.7.2 Source Code
0.3.8 Bubble Sort
0.3.9 Bucket and Radix Sorting
0.3.9.1 Analysis
0.3.10 The nth Largest
0.3.10.1 Modified Radix Sort
0.3.10.2 Modified Quicksort
0.3.10.3 Source Code
0.4 Graph Algorithms
0.4.1 Graph Representation
0.4.2 Graph Traversal
0.4.2.1 Depth-first traversal
0.4.2.1.1 References
0.4.2.2 Breadth-first traversal
0.4.2.3 Euler Cycles
0.4.2.4 Hamilton Circuits
0.4.3 Floyd's Algorithm - Shortest Paths
0.4.4 Dijkstra's Algorithm - Shortest Path
0.4.4.1 Analysis
0.4.4.2 Source Code
0.4.5 Spanning Trees
0.4.5.1 Prim's Algorithm
0.4.5.1.1 Source Code
0.4.5.2 Kruskal's Algorithm
0.4.5.2.1 Source Code
0.4.6 Transitive Closure
0.5 Miscellaneous Algorithms
0.5.1 Maximum Consecutive Subsequence
0.5.1.1 Divide and Conquer Solution
0.5.1.1.1 Analysis
0.5.1.1.2 Source Code
0.5.1.2 Linear Solution
0.5.1.2.1 Source Code
0.5.2 Permutations
0.5.2.1 Source Code
0.5.2.2 References
0.5.3 Combinations
0.5.3.1 Source Code
0.5.3.2 References
0.5.4 Exponentiation
0.5.5 Julian Calendar Algorithms
0.5.5.1 A Brief History of the Julian Calendar
0.5.5.2 Source Code
0.5.5.3 References
0.5.6 Greatest Common Divisor, Least Common Multiple
0.5.6.1 Source Code
0.5.7 Addition Chaining
0.5.7.1 Source Code
0.5.7.2 Source Code
0.5.7.3 References
0.5.8 Fibonacci Calculation
0.5.8.1 Source Code
0.5.8.2 Source Code
0.5.8.3 References
0.5.9 Cartesian and Polar Coordinates
0.5.9.1 Source Code
0.5.10 Soundex English word-sounding Algorithm
0.5.10.1 Source Code
0.5.10.2 References
0.5.11 Metaphone Algorithm
0.5.11.1 Source Code
0.5.11.2 References
0.5.12 A Pseudo-Random Number Generator
0.5.12.1 Analysis
0.5.12.2 Source Code
0.5.12.3 References
0.5.13 Horner's Rule
0.5.14 Chinese Remainder Theorem
0.5.15 Large Prime Number Generation
0.5.16 Fast Fourier Transform
0.6 Formal Language Parsing Algorithms
0.6.1 Recursive Descent Parsing
0.6.2 Cheatham Sattley Method
0.6.3 Samuelson-Bauer xpression analysis
0.6.3.1 Source Code
0.6.4 Shift-reduce bottom-up parsing
0.7 Operating Systems Algorithms
0.7.1 Dijkstra's Banker's Algorithm for Deadlock Prevention
0.7.1.1 Source Code
0.7.2 Dekker's Algorithm for Mutual Exclusion
0.7.3 Peterson's Algorithm for Mutual Exclusion
0.8 Geometric Algorithms
0.8.1 Convex Hull Problem
0.8.1.1 Gift Wrapping
0.8.1.2 Graham's Scan
0.8.2 Closest Pair Problem
0.8.3 Determining Whether a Point is Inside a Polygon
0.8.3.1 Source Code
0.8.4 Knapsack Problem
0.8.4.1 References
0.9 Data Encryption Algorithms
0.10 Data Compression Algorithms
0.10.1 Run-Length Encoding
0.10.1.1 Source Code
0.10.1.2 References
0.10.2 Integer Coding
0.10.2.1 Source Code
0.10.2.2 References
0.10.3 Huffman Compression
0.10.3.1 Source Code
0.10.3.2 References
0.10.4 Adaptive Huffman Compression
0.10.4.1 References
0.10.5 Sliding Window Compression
0.10.5.1 Source Code
0.10.5.2 References
0.10.6 Lempel-Ziv-Walsh Compression
0.10.7 Arithmetic Compression
0.11 Game-Playing Algorithms
0.11.1 Minimax Search
0.11.2 Alpha-Beta pruning
0.12 Data Integrity
0.12.1 Checksums
0.12.1.1 Source Code
0.12.1.2 References
0.12.2 Weighted Checksums
0.12.2.1 References
0.12.3 Cyclic Redundancy Checks
0.12.3.1 CRC-CCIT
0.12.3.2 CRC-16
0.12.3.3 CRC-32
0.12.3.4 References
Index
About this document ...
Scott Gasch
1999-07-09
Search