Enhanced descriptions from Syndetics:

A textbook for a senior undergraduate course in discrete algorithms for students of computer science or mathematics who have completed a course in continuous algorithms or numerical analysis. Many opportunities are provided for students to write, debug, and use programs that are nontrivially recursive. Annotation copyrighted by Book News, Inc., Portland, OR

Table of contents provided by Syndetics

• Preface (p. vii)
• Preface to the Second Edition (p. ix)
• 0 What this Book Is About (p. 1)
• 0.1 Background (p. 1)
• 0.2 Hard versus Easy Problems (p. 3)
• 0.3 A Preview (p. 6)
• 1 Mathematical Preliminaries (p. 9)
• 1.1 Orders of Magnitude (p. 9)
• 1.2 Positional Number Systems (p. 19)
• 1.3 Manipulations with Series (p. 23)
• 1.4 Recurrence Relations (p. 27)
• 1.5 Counting (p. 34)
• 1.6 Graphs (p. 39)
• 2 Recursive Algorithms (p. 49)
• 2.1 Introduction (p. 49)
• 2.2 Quicksort (p. 51)
• 2.3 Recursive Graph Algorithms (p. 61)
• 2.4 Fast Matrix Multiplication (p. 76)
• 2.5 The Discrete Fourier Transform (p. 80)
• 2.6 Applications of the FFT (p. 91)
• 2.7 A Review (p. 94)
• 2.8 Bibliography (p. 98)
• 3 The Network Flow Problem (p. 99)
• 3.1 Introduction (p. 99)
• 3.2 Algorithms for the Network Flow Problem (p. 101)
• 3.3 The Algorithm of Ford and Fulkerson (p. 102)
• 3.4 The Max-Flow Min-Cut Theorem (p. 108)
• 3.5 The Complexity of the Ford-Fulkerson Algorithm (p. 110)
• 3.6 Layered Networks (p. 113)
• 3.7 The MPM Algorithm (p. 119)
• 3.8 Applications of Network Flow (p. 121)
• 4 Algorithms in the Theory of Numbers (p. 127)
• 4.1 Preliminaries (p. 127)
• 4.2 The Greatest Common Divisor (p. 130)
• 4.3 The Extended Euclidean Algorithm (p. 134)
• 4.4 Primality Testing (p. 138)
• 4.5 Interlude: The Ring of Integers Modulo n (p. 141)
• 4.6 Pseudoprimality Tests (p. 146)
• 4.7 Proof of Goodness of the Strong Pseudoprimality Test (p. 150)
• 4.8 Factoring and Cryptography (p. 154)
• 4.9 Factoring Large Integers (p. 157)
• 4.10 Proving Primality (p. 159)
• 5 NP-Completeness (p. 165)
• 5.1 Introduction (p. 165)
• 5.2 Turing Machines (p. 174)
• 5.3 Cook's Theorem (p. 179)
• 5.4 Some Other NP-Complete Problems (p. 186)
• 5.5 Half a Loaf ... (p. 191)
• 5.6 Backtracking (I): Independent Sets (p. 195)
• 5.7 Backtracking (II): Graph Coloring (p. 199)
• 5.8 Approximate Algorithms for Hard Problems (p. 203)
• Hints and Solutions for Selected Problems (p. 209)
• Index (p. 217)

Reviews provided by Syndetics

CHOICE Review

Wilf offers a delightful, nonstandard work (1st ed., 1986) discussing algorithms and their complexity for some problems in discrete mathematics. He essentially begins with an interesting selection of problems that range from "easy" to "hard" and from the traditional (Quicksort and some graph theory problems) to the nontraditional (matrix multiplication and the Fourier transform). In each case, a standard algorithm is discussed and analyzed, and then one or more improvements are treated. The following two chapters include 20 years of algorithmic development for the network flow problem and algorithms in number theory leading to cryptography. The author's conversational style contributes to the enjoyment of reading the thorough discussions of the algorithms and their analyses. In addition, what distinguishes this book from others in the field is the author's numerous insights on how to construct improvements and why further improvements may not be possible. At the end, "having found out something about what people know and what people don't know, the reader will have enjoyed the trip through this subject and may be interested in helping to find out a little more." ^BSumming Up: Highly recommended. Upper-division undergraduates through faculty. D. S. Larson Gonzaga University