Skip to main content

Chapter 10: How To Design Algorithms

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives​

  • Explain the main ideas and vocabulary in How To Design Algorithms.
  • Work through the source examples for How To Design Algorithms without depending on raw chunk order.
  • Use How To Design Algorithms as selective reference when learner modules point back to The Algorithm Design Manual.

Prerequisites​

  • Earlier prerequisite concepts leading into Chapter 10: How To Design Algorithms.

Module targets​

  • module-04-dynamic-programming

AI companion modes​

  • Explain simply
  • Socratic tutor
  • Quiz me
  • Challenge my understanding
  • Diagnose my confusion
  • Generate extra practice
  • Revision mode
  • Connect forward / backward

Source-of-truth note​

This unit is anchored to The Algorithm Design Manual and the source chapter "Chapter 10: How To Design Algorithms". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment​

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance​

  • Primary source: The Algorithm Design Manual
  • Source chapter 10: Chapter 10: How To Design Algorithms
  • Raw source file: 141-10-how-to-design-algorithms.md

Merged source​

How To Design Algorithms​

10 How to Design Algorithms

examples can be found, can I show that it always works well?​

iii. How fast does my heuristic come up with an answer? Does it have a simple implementation?

  1. Is my problem in the catalog of algorithmic problems in the back of this

book?

(a) What is known about the problem? Is there an implementation available that I can use?

(b) Did I look in the right place for my problem? Did I browse through all pictures? Did I look in the index under all possible keywords?

(c) Are there relevant resources available on the World Wide Web? Did I do a Google web and Google Scholar search? Did I go to the page associated with this book,http://www.cs.sunysb.edu/∼algorith?

  1. Are there special cases of the problem that I know how to solve?

(a) Can I solve the problem efficiently when I ignore some of the input parameters?

(b) Does the problem become easier to solve when I set some of the input parameters to trivial values, such as 0 or 1?

(c) Can I simplify the problem to the point where Icansolve it efficiently?

(d) Why can't this special-case algorithm be generalized to a wider class of inputs?

(e) Is my problem a special case of a more general problem in the catalog?

  1. Which of the standard algorithm design paradigms are most relevant to my

problem?

(a) Is there a set of items that can be sorted by size or some key? Does this sorted order make it easier to find the answer?

(b) Is there a way to split the problem in two smaller problems, perhaps by doing a binary search? How about partitioning the elements into big and small, or left and right? Does this suggest a divide-and-conquer

algorithm?​

(c) Do the input objects or desired solution have a natural left-to-right order, such as characters in a string, elements of a permutation, or leaves of a tree? Can I use dynamic programming to exploit this order?

(d) Are there certain operations being done repeatedly, such as searching, or finding the largest/smallest element? Can I use a data structure to speed up these queries? What about a dictionary/hash table or a heap/priority queue?

(e) Can I use random sampling to select which object to pick next? What about constructing many random configurations and picking the best one? Can I use some kind of directed randomness like simulated annealing to zoom in on the best solution?

(f) Can I formulate my problem as a linear program? How about an integer program?

(g) Does my problem seem something like satisfiability, the traveling salesman problem, or some other NP-complete problem? Might the problem be NP-complete and thus not have an efficient algorithm? Is it in the

problem list in the back of Garey and Johnson [GJ79]?​
  1. Am I still stumped?

(a) Am I willing to spend money to hire an expert to tell me what to do? If so, check out the professional consulting services mentioned in Section 19.4 (page 664).

(b) Why don't I go back to the beginning and work through these questions again? Did any of my answers change during my latest trip through the list?

Problem-solving is not a science, but part art and part skill. It is one of the​

skills most worth developing. My favorite book on problem-solving remains P´olya's

How to Solve It[P´57], which features a catalog of problem-solving techniques that are fascinating to browse through, both before and after you have a problem.