第1页 / 共448页
第2页 / 共448页
第3页 / 共448页
第4页 / 共448页
第5页 / 共448页
第6页 / 共448页
第7页 / 共448页
第8页 / 共448页
Algorithms (Jeff Erickson).pdf
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
Analysis
Sanity Checking
Fast Multiplication
Exponentiation
Exercises
Backtracking
N Queens
Game Trees
Subset Sum
Correctness
Analysis
Variants
The General Pattern
String 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 Structure
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
Koraraju 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 Teaching Assignment
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 Sat)
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
Image Credits
Colophon
Algorithms
JeffErickson
0th edition (pre-publication draft) — December 29, 2018
0 1 2 3 4 5 6 7 8 9 — 27 26 25 24 23 22 21 20 19 18
© Copyright 2019 Jeff Erickson
c b
This work is available under a Creative Commons Attribution 4.0 International License.
For license details, see http://creativecommons.org/licenses/by/4.0/.
Download this book at http://jeffe.cs.illinois.edu/teaching/algorithms/
or http://algorithms.wtf
Please report errors at https://github.com/jeffgerickson/algorithms
Portions of our programming are mechanically reproduced,
and we now begin our broadcast day.
For Kim, Kate, and Hannah
with love and admiration
And for Erin
with thanks
for breaking her promise
Incipitprologusinlibroalghoarismidepracticaarismetrice.
—IoannisHispalensis[JohnofSeville?],
Liberalgorismidepraticaarismetrice(c.1135)
ShallItellyou,myfriend,howyouwillcometounderstandit?
Goandwriteabookuponit.
—HenryHome,LordKames(1696–1782),
inalettertotoSirGilbertElliot
Theindividualisalwaysmistaken. Hedesignedmanythings,anddrewinother
personsascoadjutors,quarrelledwithsomeorall,blunderedmuch,and
somethingisdone;allarealittleadvanced,buttheindividualisalwaysmistaken.
Itturnsoutsomewhatnewandveryunlikewhathepromisedhimself.
—RalphWaldoEmerson,“Experience”,Essays,SecondSeries(1844)
WhatIhaveoutlinedaboveisthecontentofabooktherealizationofwhosebasic
planandtheincorporationofwhosedetailswouldperhapsbeimpossible;whatI
havewrittenisasecondorthirddraftofapreliminaryversionofthisbook
—MichaelSpivak,prefaceofthersteditionof
DifferentialGeometry,VolumeI(1970)
Preface
AboutThisBook
This textbook grew out of a collection of lecture notes that I wrote for various
algorithms classes at the University of Illinois at Urbana-Champaign, which I
have been teaching about once a year since January 1999. Spurred by changes
of our undergraduate theory curriculum, I undertook a major revision of my
notes in 2016; this book consists of a subset of my revised notes on the most
fundamental course material, mostly reflecting the algorithmic content of our
new required junior-level theory course.
Prerequisites
The algorithms classes I teach at Illinois have two significant prerequisites:
a course on discrete mathematics and a course on fundamental data structures.
Consequently, this textbook is probably not suitable for most students as a first
i
P
ii
course in data structures and algorithms. In particular, I assume at least passing
familiarity with the following specific topics:
• Discrete mathematics: High-school algebra, logarithm identities, naive
set theory, Boolean algebra, first-order predicate logic, sets, functions,
equivalences, partial orders, modular arithmetic, recursive definitions, trees
(as abstract objects, not data structures), graphs (vertices and edges, not
function plots).
• Proof techniques: direct, indirect, contradiction, exhaustive case analysis,
and induction (especially “strong” and “structural” induction). Chapter 0
uses induction, and whenever Chapter n−1 uses induction, so does Chapter n.
• Iterative programming concepts: variables, conditionals, loops, records,
indirection (addresses/pointers/references), subroutines, recursion. I do not
assume fluency in any particular programming language, but I do assume
experience with at least one language that supports both indirection and
recursion.
• Fundamental abstract data types: scalars, sequences, vectors, sets, stacks,
queues, maps/dictionaries, ordered maps/dictionaries, priority queues.
• Fundamental data structures: arrays, linked lists (single and double,
linear and circular), binary search trees, at least one form of balanced binary
search tree (such as AVL trees, red-black trees, treaps, skip lists, or splay
trees), hash tables, binary heaps, and most importantly, the difference
between this list and the previous list.
• Fundamental computational problems: elementary arithmetic, sorting,
searching, enumeration, tree traversal (preorder, inorder, postorder, level-
order, and so on).
• Fundamental algorithms: elementary algorism, sequential search, binary
search, sorting (selection, insertion, merge, heap, quick, radix, and so
on), breadth- and depth-first search in (at least binary) trees, and most
importantly, the difference between this list and the previous list.
• Elementary algorithm analysis: Asymptotic notation (o, O, Θ, Ω, ω),
translating loops into sums and recursive calls into recurrences, evaluating
simple sums and recurrences.
• Mathematical maturity: facility with abstraction, formal (especially recur-
sive) definitions, and (especially inductive) proofs; writing and following
mathematical arguments; recognizing and avoiding syntactic, semantic,
and/or logical nonsense.
The book briefly covers some of this prerequisite material when it arises in
context, but more as a reminder than a good introduction. For a more thorough
overview, I strongly recommend the following freely available references:
AdditionalReferences
• Margaret M. Fleck. Building Blocks for Theoretical Computer Science, un-
published textbook, most recently revised January 2013. Available from
http://mfleck.cs.illinois.edu/building-blocks/.
• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer. Mathematics for
Computer Science, unpublished lecture notes, most recent (public) revision
June 2018. Available from https://courses.csail.mit.edu/6.042/spring18/.
(I strongly recommend searching for the most recent revision.)
• Pat Morin. Open Data Structures, most recently revised January 2016 (edition
0.1Gβ). A free open-content textbook, which Pat maintains and regularly
updates. Available from http://opendatastructures.org/.
AdditionalReferences
Please do not restrict yourself to this or any other single reference. Authors and
readers bring their own perspectives to any intellectual material; no instructor
“clicks” with every student, or even with every very strong student. Finding the
author that most effectively gets their intuition into your head takes some effort,
but that effort pays off handsomely in the long run.
The following references have been particularly valuable sources of intuition,
examples, exercises, and inspiration; this is not meant to be a complete list.
• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and
Analysis of Computer Algorithms. Addison-Wesley, 1974. (I used this textbook
as an undergraduate at Rice and again as a masters student at UC Irvine.)
• Thomas Cormen, Charles Leiserson, Ron Rivest, and Cliff Stein. Introduction
to Algorithms, third edition. MIT Press/McGraw-Hill, 2009. (I used the first
edition as a teaching assistant at Berkeley.)
• Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. Algo-
rithms. McGraw-Hill, 2006. (Probably the closest in content to this book,
but considerably less verbose.)
• Jeff Edmonds. How to Think about Algorithms. Cambridge University Press,
2008.
• Michael R. Garey and David S. Johnson. Computers and Intractability:
A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
• Michael T. Goodrich and Roberto Tamassia. Algorithm Design: Foundations,
Analysis, and Internet Examples. John Wiley & Sons, 2002.
• Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.
Borrow it from the library if you can.
• Donald Knuth. The Art of Computer Programming, volumes 1–4A. Addison-
Wesley, 1997 and 2011. (My parents gave me the first three volumes for
Christmas when I was 14. Alas, I didn’t actually read them until much later.)
iii
P
iv
• Udi Manber.
Introduction to Algorithms: A Creative Approach. Addison-
Wesley, 1989. (I used this textbook as a teaching assistant at Berkeley.)
• Ian Parberry. Problems on Algorithms. Prentice-Hall, 1995 (out of print).
Downloadable from https://larc.unt.edu/ian/books/free/license.html after
you agree to make a small charitable donation. Please honor your agreement.
• Robert Sedgewick and Kevin Wayne. Algorithms. Addison-Wesley, 2011.
• Robert Endre Tarjan. Data Structures and Network Algorithms. SIAM, 1983.
• Class notes from my own algorithms classes at Berkeley, especially those
taught by Dick Karp and Raimund Seidel.
• Lecture notes, slides, homeworks, exams, video lectures, research papers,
blog posts, and full-fledged MOOCs made freely available on the web by
innumerable colleagues around the world.
AbouttheExercises
Each chapter ends with several exercises, most of which I have used at least
once in a homework assignment, discussion/lab section, or exam. The exercises
are not ordered by increasing difficulty, but (generally) clustered by common
techniques or themes. Some problems are annotated with symbols as follows:
• nRed hearts indicate particularly challenging problems; many of these have
appeared on qualifying exams for PhD students at Illinois. A small number
of really hard problems are marked with nlarger hearts, and a few open
problems are marked with nenormous hearts.
• oBlue diamonds indicate problems that require familiarity with material
from later chapters, but thematically belong where they are. Problems that
require familiarity with earlier material are not marked, however; the book,
like life, is cumulative.
• pGreen clubs indicate problems that require familiarity with material out-
side the scope of this book, such as finite-state machines, linear algebra,
probability, or planar graphs. These are rare.
• mBlack spades indicate problems that require a significant amount of grunt
work and/or coding. These are rare.
• Orange stars indicate that you are eating Lucky Charms that were manu-
factured before 1998. Ew.
These exercises are designed as opportunities to practice, not as targets for their
own sake; the goal of these problems not to solve these particular problems,
but to practice exercising a particular skill, or solving a type of problem. Partly
for this reason, I don’t provide solutions to the exercises; the solutions are not
the point. In particular, there is no “instructor’s manual”; if you can’t solve a
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
