[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Basic problem solving techniques.

1. Feynman's Algorithm

Supposedly used by the physicist [Richard_Feynman]:

  1. Write down the problem.
  2. Think very hard.
  3. Write down the solution.

For mere mortals (i.e., everybody except Richard Feynman), this often works about as well as the [Underpants_Gnomes]'s business plan.

2. Polya's Principles

If you can't solve a problem, then there is an easier problem you can solve: find it. ---[George_Polya]

George Polya described in his 1957 book How to Solve It (HowToSolveIt) a set of heuristics for solving problems. A basic outline of his approach is pretty similar to Feynman's Algorithm:

  1. Make sure you understand the problem.
  2. Come up with a plan for solving the problem.
  3. Check that the plan works.

If the last step fails, try the second step again. If the last step fails in a particularly spectacular way, you may need to go back to the first step as well. You may need to go through many iterations of this process, especially if you are dealing with a research problem that has never been solved before.

What makes Polya's method a little more tractable than Feynman's is that he expands a bit on step 2, suggesting a number of heuristics for finding solutions. Translated into ComputerScience terms, some of these are:

Many of these heuristics are suspiciously similar to AlgorithmDesignTechniques described in LevitinBook. One heuristic to consider in a classroom setting, especially if you are (a) stuck, (b) worried that you don't understand the problem, or (c) think that the problem ought to be related to something you've seen before but aren't sure, is: Have I talked to a TA about this problem?

If an algorithmic problem seems really difficult, you can also ask Can I show that this problem has no solution? The answer to this question is usually no (since nobody knows how to prove non-existence of good algorithms except in some limited special cases), but using techniques from ComputationalComplexityTheory you can sometimes come close.


CategoryAlgorithmNotes


2014-06-17 11:58