masthead

The Algorithm Design Manual

Author

Steven S. Skiena
Department of Computer Science
State University of New York at Stony Brook

Overview

Most professional programmers are not well equipped to tackle algorithm design problems. "The Algorithm Design Manual" by Steve Skiena of SUNY Stony Brook, is uniquely designed to provide access to combinatorial algorithms technology for computer professionals and students. Skiena has taken some of the "mystery" out of finding the right algorithm for the job, by drawing heavily on the author's own real-world experiences. Thus the work takes on a very practical character, as reflected in its title: "Manual". The Book is divided into two parts, the first being a general guide to techniques for the design and analysis of computer algorithms. The second is a reference section, comprising the catalog of algorithmic resources, implementations, and an extensive bibliography.

The primary audience for this book/CD-ROM combination is the working professional who uses algorithms on a regular or occasional basis and has need for a handy reference. A major feature of this book is the inclusion of a complete "catalog" of important algorithmic problems. By browsing this catalog, readers can quickly identify what the problem they have encountered is called, what is known about it, and how they should proceed if they need to solve it. Nothing like this catalog exists in the computing literature for general computer algorithms.

This work can also readily be used as a textbook or course supplement in standard courses on algorithm design. Pedagogic features include pen-and paper exercises, "team projects", independent student projects, "take home" lessons (goals) at the beginning of chapters. Other teaching and learning aids reside on the accompanying CD-ROM. The multi-platiform CD-ROM contains a full hypertext version of the book, with a comprehensive on-line index, and all of the code/algorithms residing on the author's web site at Stony Brook in the "Algorithm Repository" there: www.cs.sunysb.edu/~algorith/. URLs for all cited implementations mirroring the Stony Brook web site and algorthim repository are included. Also included on the CD-ROM are 10 hours of audio lectures presented by the author, and series of slides which instructors can use to help teach their courses. There is additional useful information and updates which are available through accessing the author's web site.


Table of Contents

Part I Techniques
Chapter 1 Introduction to Algorithms
1.1 Correctness and Efficiency
1.2 Expressing Algorithms
1.3 Keeping Score
1.4 The Big Oh Notation
1.5 Growth Rates
1.6 Logarithms
1.7 Modeling the Problem
1.8 About the War Stories
1.9 War Story: Psychic Modeling
1.10 Exercises
Chapter 2 Data Structures and Sorting
2.1 Fundamental Data Types
2.2 Specialized Data Structures
2.3 Sorting
2.4 Applications of Sorting
2.5 Approaches to Sorting
2.6 War Story: Stripping Triangulations
2.7 War Story: Mystery of the Pyramids
2.8 War Story: String em Up
2.9 Exercises
Chapter 3 Breaking Problems Down
3.1 Dynamic Programming
3.2 Limitations of Dynamic Programming
3.3 War Story: Evolution of the Lobster
3.4 War Story: Whats Past is Prolog
3.5 War Story: Text Compression for Bar Codes
3.6 Divide and Conquer
3.7 Exercises
Chapter 4 Graph Algorithms
4.1 The Friendship Graph
4.2 Data Structures for Graphs
4.3 War Story: Getting the Graph
4.4 Traversing a Graph
4.5 Applications of Graph Traversal
4.6 Modeling Graph Problems
4.7 Minimum Spanning Trees
4.8 Shortest Paths
4.9 War Story: Nothing but Nets
4.10 War Story: Dialing for Documents
4.11 Exercises
Chapter 5 Combinatorial Search and Heuristic Methods
5.1 Backtracking
5.2 Search Pruning
5.3 Bandwidth Minimization
5.4War Story: Covering Chessboards
5.5 Heuristic Methods
5.6 War Story: Annealing Arrays
5.7 Parallel Algorithms
5.8 War Story: Going Nowhere Fast
5.9 Exercises
Chapter 6 Intractable Problems and Approximations
6.1 Problems and Reductions
6.2 Simple Reductions
6.3 Satisfiability
6.4 Difficult Reductions
6.5 Other NP-Complete Problems
6.6 The Art of Proving Hardness
6.7 War Story: Hard Against the Clock
6.8 Approximation Algorithms
6.9 Exercises
Chapter 7 How To Design Algorithms
Part II Resources
Chapter 8 A Catalog of Algorithmic Problems
8.1 Data Structures
8.2 Numerical Problems
8.3 Combinatorial Problems
8.4 Graph Problems - polynomial-time problems
8.5 Graph Problems - hard problems
8.6 Computational Geometry
8.7 Set and String Problems
Chapter 9 Algorithmic Resources
9.1 Software Systems
9.2 Data Sources
9.3 Textbooks
9.4 On-Line Resources
9.5 Professional Consulting Services
1997/496 pages/Hardcover
ISBN 0-387-94860-0



About the Author

Steve Skiena is currently an Associate Professor of Computer Science at the State University of New York, Stony Brook where he has been since 1988. Back to top

To Order

Back to top
Back to TELOS Catalog

Back to TELOS Home Page