Log In
Or create an account -> 
Imperial Library
  • Home
  • About
  • News
  • Upload
  • Forum
  • Help
  • Login/SignUp

Index
Algorithms in a Nutshell 2E 1. Thinking Algorithmically
Understand the Problem Naive Solution Intelligent Approaches
Greedy Divide and Conquer Parallel Approximation Generalization
Summary
2. The Mathematics of Algorithms
Size of a Problem Instance Rate of Growth of Functions Analysis in the Best, Average, and Worst Cases
Worst Case Average Case Best Case
Performance Families
Constant Behavior Log n Behavior Sublinear O(nd) Behavior for d < 1 Linear Performance n log n Performance Quadratic Performance Less Obvious Performance Computations Exponential Performance
Benchmark Operations Lower and Upper Bounds References
3. Algorithm Building Blocks
Algorithm Template Format
Name Input/Output Context Solution Analysis Variations
Pseudocode Template Format Empirical Evaluation Format Floating-Point Computation
Performance Rounding Error Comparing Floating Point Values Special Quantities
Example Algorithm
Name and Synopsis Input/Output Context Solution Analysis
Common Approaches
Greedy Divide and Conquer Dynamic Programming
References
4. Sorting Algorithms
Overview
Terminology Representation Comparable Elements Stable Sorting Criteria for Choosing a Sorting Algorithm
Transposition Sorting
Insertion Sort Context Solution Analysis
Selection Sort Heap Sort
Context Solution Analysis Variations
Partition-based Sorting
Context Solution Analysis Variations
Sorting Without Comparisons Bucket Sort
Solution Analysis Variations
Sorting with Extra Storage
Merge Sort Input/Output Solution Analysis Variations
String Benchmark Results Analysis Techniques References
5. Searching
Sequential Search
Input/Output Context Solution Analysis
Binary Search
Input/Output Context Solution Analysis Variations
Hash-based Search
Input/Output Context Solution Analysis Variations
Bloom Filter
Input/Output Context Solution Analysis
Binary Search Tree
Input/Output Context Solution Analysis Variations References
6. Graph Algorithms
Graphs
Data Structure Design
Depth-First Search
Input/Output Context Solution Analysis Variations
Breadth-First Search
Input/Output Context Solution Analysis
Single-Source Shortest Path
Input/Output Solution Analysis
Dijkstra’s Algorithm For Dense Graphs
Variations
Comparing Single Source Shortest Path Options
Benchmark data Dense graphs Sparse graphs
All Pairs Shortest Path
Input/Output Solution Analysis
Minimum Spanning Tree Algorithms
Solution Analysis Variations
Final Thoughts on Graphs
Storage Issues Graph Analysis
References
7. Path Finding in AI
Game Trees Minimax
Input/Output Context Solution Analysis
NegMax
Solution Analysis
AlphaBeta
Solution Analysis
Search Trees
Representing State Calculate available moves Using Heuristic Information Maximum Expansion Depth
Depth-First Search
Input/Output Context Solution Analysis
Breadth-First Search
Input/Output Context Solution Analysis
A*Search
Input/Output Context Solution Analysis Variations
Comparing Search Tree Algorithms References
8. Network Flow Algorithms
Network Flow Maximum Flow
Input/Output Solution Analysis Optimization Related Algorithms
Bipartite Matching
Input/Output Solution Analysis
Reflections on Augmenting Paths Minimum Cost Flow Transshipment
Solution
Transportation
Solution
Assignment
Solution
Linear Programming References
9. Computational Geometry
Classifying Problems
Input data Computation Nature of the task Assumptions
Convex Hull Convex Hull Scan
Input/Output Context Solution Analysis Variations
Computing Line Segment Intersections LineSweep
Input/Output Context Solution Analysis Variations
Voronoi Diagram
Input/Output Solution Analysis References
10. Spatial Tree Structures
Nearest Neighbor queries Range Queries Intersection Queries Spatial Tree Structures
KD-Tree Quad Tree R-Tree
Nearest Neighbor
Input/Output Context Solution Analysis Variations
Range Query
Input/Output Context Solution Analysis
QuadTrees
Input/Output Solution Analysis Variations
R-Trees
Input/Output Context Solution Analysis References
11. Emerging Algorithm Categories
Variations on a Theme Approximation Algorithms
Input/Output Context Solution Analysis
Parallel Algorithms Probabilistic Algorithms
Estimating the Size of a Set Estimating the Size of a Search Tree
References
12. Epilogue
Principle: Know Your Data Principle: Decompose the Problem into Smaller Problems Principle: Choose the Right Data Structure Principle: Make the Space versus Time Trade-off Principle: If No Solution Is Evident, Construct a Search Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution Principle: Writing Algorithms Is Hard—Testing Algorithms Is Harder Principle: Accept Approximate Solution When Possible Principle: Add Parallelism to Increase Performance
A. Benchmarking
Statistical Foundation Example
Java benchmarking solutions Linux benchmarking solutions Python benchmarking solutions
Reporting Precision
About the Authors Copyright
  • ← Prev
  • Back
  • Next →
  • ← Prev
  • Back
  • Next →

Chief Librarian: Las Zenow <zenow@riseup.net>
Fork the source code from gitlab.

This is a mirror of the Tor onion service:
http://kx5thpx2olielkihfyo4jgjqfb7zx7wxr3sd4xzt26ochei4m6f7tayd.onion