Algorithms
Free

Algorithms

By Jeff Erickson
Free
Book Description

This textbook grew out of a collection of lecture notes written for various algorithms classes at the University of Illinois at Urbana-Champaign. 


  • Introduction 

  • Recursion

  • Backtracking

  • Dynamic Programming

  • Greedy Algorithms

  • Basic Graph Algorithms

  • Depth-First Search

  • Minimum Spanning Trees 

  • Shortest Paths 

  • All-Pairs Shortest Paths

  • Maximum Flows & Minimum Cuts

  • Applications of Flows and Cuts

  • NP-Hardness

A paperback editions and more lecture notes are available on the Author's website.


Table of Contents
  • 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.
You May Also Like
Also Available On
Categories
Curated Lists