Algorithms and Complexity

by Wilf; Herbert S.

• ISBN13: 9781568811789
• ISBN10: 1568811780
• Edition: 2nd
• Format: Hardcover
• Copyright: 2002-12-09
• Publisher: Taylor & Franci
• More Book Details

Summary

Algorithms & Complexity, 2nd Edition is an introductory textbook on the design and analysis of algorithms. The author uses a careful selection of a few topics to illustrate the tools for algorithm analysis. Recursive algorithms are illustrated by Quicksort, FFT, fast matrix multiplication, and others. Algorithms associated with the network flow problem are fundamental in many areas of graph connectivity, matching theory etc. Algorithms in number theory are discussed with some applications to public key encryption. The final chapter is about NP completeness, the theory of a renowned family of seemingly very difficult computational problems that are bound together by familial ties, including a precise formulation of the concept and the statements and proofs of some of the main theorems.

Table of Contents

Preface	vii
Preface to the Second Edition	ix
What this Book Is About	1	(8)
Background	1	(2)
Hard versus Easy Problems	3	(3)
A Preview	6	(3)
Mathematical Preliminaries	9	(40)
Orders of Magnitude	9	(10)
Positional Number Systems	19	(4)
Manipulations with Series	23	(4)
Recurrence Relations	27	(7)
Counting	34	(5)
Graphs	39	(10)
Recursive Algorithms	49	(50)
Introduction	49	(2)
Quicksort	51	(10)
Recursive Graph Algorithms	61	(15)
Fast Matrix Multiplication	76	(4)
The Discrete Fourier Transform	80	(11)
Applications of the FFT	91	(3)
A Review	94	(4)
Bibliography	98	(1)
The Network Flow Problem	99	(28)
Introduction	99	(2)
Algorithms for the Network Flow Problem	101	(1)
The Algorithm of Ford and Fulkerson	102	(6)
The Max-Flow Min-Cut Theorem	108	(2)
The Complexity of the Ford-Fulkerson Algorithm	110	(3)
Layered Networks	113	(6)
The MPM Algorithm	119	(2)
Applications of Network Flow	121	(6)
Algorithms in the Theory of Numbers	127	(38)
Preliminaries	127	(3)
The Greatest Common Divisor	130	(4)
The Extended Euclidean Algorithm	134	(4)
Primality Testing	138	(3)
Interlude: The Ring of Integers Modulo n	141	(5)
Pseudoprimality Tests	146	(4)
Proof of Goodness of the Strong Pseudoprimality Test	150	(4)
Factoring and Cryptography	154	(3)
Factoring Large Integers	157	(2)
Proving Primality	159	(6)
NP-Completeness	165	(44)
Introduction	165	(9)
Turing Machines	174	(5)
Cook's Theorem	179	(7)
Some Other NP-Complete Problems	186	(5)
Half a Loaf	191	(4)
Backtracking (I): Independent Sets	195	(4)
Backtracking (II): Graph Coloring	199	(4)
Approximate Algorithms for Hard Problems	203	(6)
Hints and Solutions for Selected Problems	209	(8)
Index	217