Ebook: The Design and Analysis of Algorithms

These are my lecture notes from CS681: Design and Analysis of Algo­ rithms, a one-semester graduate course I taught at Cornell for three consec­ utive fall semesters from '88 to '90. The course serves a dual purpose: to cover core material in algorithms for graduate students in computer science preparing for their PhD qualifying exams, and to introduce theory students to some advanced topics in the design and analysis of algorithms. The material is thus a mixture of core and advanced topics. At first I meant these notes to supplement and not supplant a textbook, but over the three years they gradually took on a life of their own. In addition to the notes, I depended heavily on the texts • A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1975. • M. R. Garey and D. S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness. w. H. Freeman, 1979. • R. E. Tarjan, Data Structures and Network Algorithms. SIAM Regional Conference Series in Applied Mathematics 44, 1983. and still recommend them as excellent references.

---

The design and analysis of algorithms is one of the two essential cornerstone topics in computer science (the other being automata theory/theory of computation). Every computer scientist has a copy of Knuth's works on algorithms on his or her shelf. Dexter Kozen, a researcher and professor at Cornell University, has written a text for graduate study of algorithms. This will be an important reference book as well as being a useful graduate-level textbook.

---

The design and analysis of algorithms is one of the two essential cornerstone topics in computer science (the other being automata theory/theory of computation). Every computer scientist has a copy of Knuth's works on algorithms on his or her shelf. Dexter Kozen, a researcher and professor at Cornell University, has written a text for graduate study of algorithms. This will be an important reference book as well as being a useful graduate-level textbook.
Content:
Front Matter....Pages i-x
Front Matter....Pages 1-1
Algorithms and Their Complexity....Pages 3-8
Topological Sort and MST....Pages 9-12
Matroids and Independence....Pages 13-18
Depth-First and Breadth-First Search....Pages 19-24
Shortest Paths and Transitive Closure....Pages 25-27
Kleene Algebra....Pages 28-33
More on Kleene Algebra....Pages 34-39
Binomial Heaps....Pages 40-43
Fibonacci Heaps....Pages 44-47
Union-Find....Pages 48-51
Analysis of Union-Find....Pages 52-57
Splay Trees....Pages 58-64
Random Search Trees....Pages 65-70
Planar and Plane Graphs....Pages 71-76
The Planar Separator Theorem....Pages 77-83
Max Flow....Pages 84-89
More on Max Flow....Pages 90-95
Still More on Max Flow....Pages 96-100
Matching....Pages 101-105
More on Matching....Pages 106-110
Front Matter....Pages 1-1
Reductions and NP-Completeness....Pages 111-115
More on Reductions and NP-Completeness....Pages 116-121
More NP-Complete Problems....Pages 122-127
Still More NP-Complete Problems....Pages 128-133
Cook’s Theorem....Pages 134-137
Counting Bipartite Matchings....Pages 138-143
Hypercubes and the Gray Representation....Pages 144-150
Csanky’s Algorithm....Pages 151-155
Chistov’s Algorithm....Pages 156-159
Matrix Rank....Pages 160-165
Linear Equations and Polynomial GCDs....Pages 166-170
The Fast Fourier Transform (FFT)....Pages 171-175
Luby’s Algorithm....Pages 176-180
Analysis of Luby’s Algorithm....Pages 181-185
Miller’s Primality Test....Pages 186-190
Analysis of Miller’s Primality Test....Pages 191-196
Probabilistic Tests with Polynomials....Pages 197-200
Back Matter....Pages 201-205
....Pages 206-210