- Author: Herbert S. Wilf
- Format: PDF
- Price: free
This is an introductory textbook, suitable for classroom use, on the design and analysis of algorithms, complexity, methods for solving problems on computers and the costs (usually in running time) of using those methods.
The first edition was available in print from 1986 to 1994. The copyright has been returned to the author and he has made it available to the public, free of charge. He also allows reproduction of the book for educational purposes, but you can not distribute it from the internet in any form.
There is a second edition of this book available for purchase, with the only major difference being the inclusion of solutions to most of the exercises that are presented.
Chapters include:
- Hard vs easy problems
- Mathematical Preliminaries
- Orders of magnitude
- Positional number systems
- Manipulations with series
- Recurrence relations
- Counting
- Graphs
- Quicksort
- Recursive graph algorithms
- Fast matrix multiplication
- The discrete Fourier transform
- Applications of the FFT
- Algorithms for the network flow problem
- The algorithm of Ford and Fulkerson
- The max-flow min-cut theorem
- The complexity of the Ford-Fulkerson algorithm
- Layered networks
- The MPM Algorithm
- Applications of network flow
- The greatest common divisor
- The extended Euclidean algorithm
- Primality testing
- Interlude: the ring of integers modulo n
- Pseudoprimality tests
- Proof of goodness of the strong pseudoprimality test
- Factoring and cryptography
- Factoring large integers
- Proving primality
- Turing machines
- Cook’s theorem
- Some other NP-complete problems
- Half a loaf
- Backtracking (I): independent sets
- Backtracking (II): graph coloring
- Approximate algorithms for hard problems
