hn-classics/_stories/2008/16377259.md

created_at	title	url	author	points	story_text	comment_text	num_comments	story_id	story_title	story_url	parent_id	created_at_i	_tags	objectID	year
2018-02-14T17:04:10.000Z	The Algorithm Design Manual (2008)	http://www.algorist.com/	Chris2048	182			34					1518627850	story author_Chris2048 story_16377259	16377259	2008

Source

The Algorithm Design Manual

The Algorithm Design Manual, 2nd Edition

Steven Skiena

| ----- | | Teaching Resources | Algorithm Repository | Consulting Services |

• By Language
  • C
  • C++
  • C#
  • Java
  • FORTRAN
  • Python
  • Mathematica
  • Pascal
  • ADA
  • Lisp
  • Binary
• By Problem
  • 1.1 Data Structures
    • Dictionaries
    • Priority Queues
    • Suffix Trees and Arrays
    • Graph Data Structures
    • Set Data Structures
    • Kd-Trees
  • 1.2 Numerical Problems
    • Solving Linear Equations
    • Bandwidth Reduction
    • Matrix Multiplication
    • Determinants and Permanents
    • Constrained and Unconstrained Optimization
    • Linear Programming
    • Random Number Generation
    • Factoring and Primality Testing
    • Arbitrary Precision Arithmetic
    • Knapsack Problem
    • Discrete Fourier Transform
  • 1.3 Combinatorial Problems
    • Sorting
    • Searching
    • Median and Selection
    • Generating Permutations
    • Generating Subsets
    • Generating Partitions
    • Generating Graphs
    • Calendrical Calculations
    • Job Scheduling
    • Satisfiability
  • 1.4 Graph Problems -- polynomial-time problems
    • Connected Components
    • Topological Sorting
    • Minimum Spanning Tree
    • Shortest Path
    • Transitive Closure and Reduction
    • Matching
    • Eulerian Cycle / Chinese Postman
    • Edge and Vertex Connectivity
    • Network Flow
    • Drawing Graphs Nicely
    • Drawing Trees
    • Planarity Detection and Embedding
  • 1.5 Graph Problems -- hard problems
    • Clique
    • Independent Set
    • Vertex Cover
    • Traveling Salesman Problem
    • Hamiltonian Cycle
    • Graph Partition
    • Vertex Coloring
    • Edge Coloring
    • Graph Isomorphism
    • Steiner Tree
    • Feedback Edge/Vertex Set
  • 1.6 Computational Geometry
    • Robust Geometric Primitives
    • Convex Hull
    • Triangulation
    • Voronoi Diagrams
    • Nearest Neighbor Search
    • Range Search
    • Point Location
    • Intersection Detection
    • Bin Packing
    • Medial-Axis Transformation
    • Polygon Partitioning
    • Simplifying Polygons
    • Shape Similarity
    • Motion Planning
    • Maintaining Line Arrangements
    • Minkowski Sum
  • 1.7 Set and String Problems
    • Set Cover
    • Set Packing
    • String Matching
    • Approximate String Matching
    • Text Compression
    • Cryptography
    • Finite State Machine Minimization
    • Longest Common Substring
    • Shortest Common Superstring
• Algorithm Links
  • Algorithm Lectures
  • Algorithm Design Manual Information
  • CSE 373 Course page
  • NIST Dictory of Algorithms and Data Structures
  • World of Mathematics
  • Programming Challenges
  • Audio Algorithm Lectures
  • Graduate Study Opportuinties

---

Second Edition now available!

| ----- | | Errata |
| Programs |
| Credits |
| Solution Key/Wiki |

This newly expanded and updated second edition continues to take the "mystery" out of designing algorithms, and analyzing their efficacy and efficiency. Expanding on the first edition, the book now serves as the primary textbook of choice for algorithm design courses while maintaining its status as the premier practical reference guide to algorithms for programmers, researchers, and students.

The reader-friendly Algorithm Design Manual provides straightforward access to combinatorial algorithms technology, stressing design over analysis. The first part, Techniques, provides accessible instruction on methods for designing and analyzing computer algorithms. The second part, Resources, is intended for browsing and reference, and comprises the catalog of algorithmic resources, implementations and an extensive bibliography. Buy the book directly from Springer to ensure integrity.

---

Learn/Teach Algorithms the Skiena Way!

| ----- | | Audio/ Video
Lectures |
| Author's
Course Page |
| Lecture Notes |

The second edition contains enough material to serve as the textbook for a standard Introduction to Algorithms course. I assume the reader has completed the equivalent of a second programming course, typically titled Data Structures or Computer Science II.

The book, and associated supporting material, stresses design over analysis. A full set of lecture slides integrated with audio and video lectures are freely available on line. Let me help teach your course! I received the 2001 IEEE Computer Science and Engineering Teaching Award and have been been teaching undergraduate algorithm classes for almost twenty years.

I have made several pedagogical improvements throughout the book. Textbook-oriented features include:

• More Leisurely Discussion -- The tutorial material in the first part of the book has been doubled over the previous edition. The pages have been devoted to more thorough and careful exposition of fundamental material, instead of adding more specialized topics.
• False Starts -- Algorithms textbooks generally present important algorithms as a fait accompli, obscuring the ideas involved in designing them and the subtle reasons why other approaches fail. The war stories illustrate such development on certain applied problems, but I have expanded such coverage into classical algorithm design material as well.
• Stop and Think -- Here I illustrate my thought process as I solve a topic-specific homework problem---false starts and all. I have interspersed such problem blocks throughout the text to increase the problem-solving activity of my readers. Answers appear immediately following each problem.
• More and Improved Homework Problems -- This edition of The Algorithm Design Manual has twice as many homework exercises as the previous one. Exercises that proved confusing or ambiguous have been improved or replaced. Degree of difficulty ratings (from 1 to 10) have been assigned to all problems.
• Self-Motivating Exam Design -- In my algorithms courses, I promise the students that all midterm and final exam questions will be taken directly from homework problems in this book. This provides a ``student-motivated exam,'' so students know exactly how to study to do well on the exam. I have carefully picked the quantity, variety, and difficulty of homework exercises to make this work; ensuring there are neither too few or too many candidate problems.
• Take-Home Lessons -- Highlighted ``take-home'' lesson boxes scattered throughout the text emphasize the big-picture concepts to be gained from the chapter.
• Links to Programming Challenge Problems -- Each chapter's exercises will contain links to 3-5 relevant ``Programming Challenge'' problems from http://www.programming-challenges.com. These can be used to add a programming component to paper-and-pencil algorithms courses.
• More Code, Less Pseudo-code -- More algorithms in this book appear as code (written in C) instead of pseudo-code. I believe the concreteness and reliability of actual tested implementations provides a big win over less formal presentations for simple algorithms. Full implementations are available for study at courseweb.

---

| ----- | | First Edition Errata |

First Edition

I was gratified by the warm reception the first edition of The Algorithm Design Manual received since its publication. It ultimately went through ten printings and generated numerous errata, which remain available here.

The first edition came with a CD-ROM, with mirrors of the algorithm repository and my audio/video lecture notes. Updated and improved versions of these resources are available on line, rendering the CD-ROM unnecessary (although I fondly recall the fellow who asked me for an extra copy so their child could have one when they grew up).

This CD-ROM was also the source of the pirated online version from Indonesia. The Amazon Kindle edition is better.

Reviews of The Algorithm Design Manual include:

• From Steve Yegge -- Get that Job at Google": `` My absolute favorite for this kind of interview preparation is Steven Skiena's The Algorithm Design Manual. More than any other book it helped me understand just how astonishingly commonplace (and important) graph problems are ? they should be part of every working programmer's toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. But the gold mine is the second half of the book, which is a sort of encyclopedia of 1-pagers on zillions of useful problems and various ways to solve them, without too much detail. Almost every 1-pager has a simple picture, making it easy to remember. This is a great way to learn how to identify hundreds of problem types.''
• From Programming Stuff: ``The book teaches you how to extract the relevant information from a problem, how to transform a given problem into a well-researched problem, how to select the best data structure for the job and how to really improve algorithms. .. That's what makes the book so different and yet so valuable.''

---

From the Publisher

Written by a well-known algorithms researcher who received the IEEE Computer Science and Engineering Teaching Award, this new edition of The Algorithm Design Manual is an essential learning tool for students needing a solid grounding in algorithms, as well as a special text/reference for professionals who need an authoritative and insightful guide.

Quotes

"...the book is an algorithm-implementation treasure trove, and putting all of these implementations in one place was no small feat. The list of implementations [and] extensive bibliography make the book an invaluable resource for everyone interested in the subject." --ACM Computing Reviews

"It has all the right ingredients: rich contents, friendly, personal language, subtle humor, the right references, and a plethora of pointers to resources." ** -- P. Takis Metaxas, Wellesley College**

"This is the most approachable book on algorithms I have." -- Megan Squire, Elon University, USA