Algorithms
Free
Description
Contents
Reviews
Language
English
ISBN
978-1-792-64483-2
Preface
About This Book
Prerequisites
Additional References
About the Exercises
Steal This Book!
Acknowledgments
Caveat Lector!
Table of Contents
Introduction
What is an algorithm?
Multiplication
Lattice Multiplication
Duplation and Mediation
Compass and Straightedge
Congressional Apportionment
A Bad Example
Describing Algorithms
Specifying the Problem
Describing the Algorithm
Analyzing Algorithms
Correctness
Running Time
Exercises
Recursion
Reductions
Simplify and Delegate
Tower of Hanoi
Mergesort
Correctness
Analysis
Quicksort
Correctness
Analysis
The Pattern
Recursion Trees
♥Ignoring Floors and Ceilings Is Okay, Honest
♥Linear-Time Selection
Quickselect
Good pivots
Analysis
Sanity Checking
Fast Multiplication
Exponentiation
Exercises
Backtracking
N Queens
Game Trees
Subset Sum
Correctness
Analysis
Variants
The General Pattern
Text Segmentation (Interpunctio Verborum)
Index Formulation
♥Analysis
Variants
Longest Increasing Subsequence
Longest Increasing Subsequence, Take 2
Optimal Binary Search Trees
♥Analysis
Exercises
Dynamic Programming
Mātrāvṛtta
Backtracking Can Be Slow
Memo(r)ization: Remember Everything
Dynamic Programming: Fill Deliberately
Don't Remember Everything After All
♥Aside: Even Faster Fibonacci Numbers
Whoa! Not so fast!
Interpunctio Verborum Redux
The Pattern: Smart Recursion
Warning: Greed is Stupid
Longest Increasing Subsequence
First Recurrence: Is This Next?
Second Recurrence: What's Next?
Edit Distance
Recursive Structure
Recurrence
Dynamic Programming
Subset Sum
Optimal Binary Search Trees
Dynamic Programming on Trees
Exercises
Greedy Algorithms
Storing Files on Tape
Scheduling Classes
General Pattern
Huffman Codes
Stable Matching
Some Bad Ideas
The Boston Pool and Gale-Shapley Algorithms
Running Time
Correctness
Optimality!
Exercises
Basic Graph Algorithms
Introduction and History
Basic Definitions
Representations and Examples
Data Structures
Adjacency Lists
Adjacency Matrices
Comparison
Whatever-First Search
Analysis
Important Variants
Stack: Depth-First
Queue: Breadth-First
Priority Queue: Best-First
Disconnected Graphs
Directed Graphs
Graph Reductions: Flood Fill
Exercises
Depth-First Search
Preorder and Postorder
Classifying Vertices and Edges
Detecting Cycles
Topological Sort
Implicit Topological Sort
Memoization and Dynamic Programming
Dynamic Programming in Dags
Strong Connectivity
Strong Components in Linear Time
Kosaraju and Sharir’s Algorithm
♥Tarjan’s Algorithm
Exercises
Minimum Spanning Trees
Distinct Edge Weights
The Only Minimum Spanning Tree Algorithm
Borůvka’s Algorithm
This is the MST Algorithm You Want
Jarník’s (“Prim’s”) Algorithm
♥Improving Jarník’s Algorithm
Kruskal’s Algorithm
Exercises
Shortest Paths
Shortest Path Trees
♥Negative Edges
The Only SSSP Algorithm
Unweighted Graphs: Breadth-First Search
Directed Acyclic Graphs: Depth-First Search
Best-First: Dijkstra’s Algorithm
No Negative Edges
♥Negative Edges
Relax ALL the Edges: Bellman-Ford
Moore’s Improvement
Dynamic Programming Formulation
Exercises
All-Pairs Shortest Paths
Introduction
Lots of Single Sources
Reweighting
Johnson's Algorithm
Dynamic Programming
Divide and Conquer
Funny Matrix Multiplication
(Kleene-Roy-)Floyd-Warshall(-Ingerman)
Exercises
Maximum Flows & Minimum Cuts
Flows
Cuts
The Maxflow-Mincut Theorem
Ford and Fulkerson's augmenting-path algorithm
♥Irrational Capacities
Combining and Decomposing Flows
Edmonds and Karp's Algorithms
Fattest Augmenting Paths
Shortest Augmenting Paths
Further Progress
Exercises
Applications of Flows and Cuts
Edge-Disjoint Paths
Vertex Capacities and Vertex-Disjoint Paths
Bipartite Matching
Tuple Selection
Exam Scheduling
Disjoint-Path Covers
Minimal Faculty Hiring
Baseball Elimination
Project Selection
Exercises
NP-Hardness
A Game You Can't Win
P versus NP
NP-hard, NP-easy, and NP-complete
♥Formal Definitions (HC SVNT DRACONES)
Reductions and Sat
3Sat (from CircuitSat)
Maximum Independent Set (from 3Sat)
The General Pattern
Clique and Vertex Cover (from Independent Set)
Graph Coloring (from 3Sat)
Hamiltonian Cycle
From Vertex Cover
From 3Sat
Variants and Extensions
Subset Sum (from Vertex Cover)
Caveat Reductor!
Other Useful NP-hard Problems
Choosing the Right Problem
A Frivolous Real-World Example
♥On Beyond Zebra
Polynomial Space
Exponential Time
Excelsior!
Exercises
Index
Index of People
Index of Pseudocode
Image Credits
Colophon
The book hasn't received reviews yet.
