• AlgorithmDesign

• ProblemSolvingTechniques

• AlgorithmDesignTechniques

Basic procedure for solving problems with a computer:

1. If there are a limited number (e.g., less than 2⁴⁰) possible solutions, try them all. This gives the BruteForce approach. Even if there aren't a limited number of solutions, this approach may be the best we can do.

2. Apply Polya's Principle: Given a hard problem, find an easier problem whose solution will help solve the hard problem. Some variants:

   1. Reduce to a smaller problem or problems of the same type as the original. This is a good approach for algorithms, because computers don't get bored solving the smaller subproblems using exactly the same procedure, and eventually we whittle them down to something small enough to just solve directly. Two special cases of this as defined by LevitinBook: ¹

      1. DivideAndConquer splits the problem evenly, giving recurrences of the form T(n) = 2T(n/2) + f(n).

      2. DecreaseAndConquer knocks a tiny piece of the problem, knocking its size down by at least one, but possible not much more than that. This gives recurrences of the form T(n) = T(n-1) + f(n), which usually yield higher running times than an even split.

   2. Reduce to a different problem, typically by transforming the input in some way. LevitinBook calls this TransformAndConquer. Sorting the input sometimes helps. Other problems can be reduced to highly adaptable algorithms like LinearProgramming or GraphAlgorithms.

3. For CombinatorialOptimization problems, try DynamicProgramming or the GreedyMethod.

4. If all else fails, prove that you can't do it, or can't do it efficiently, then resort to ApproximationAlgorithms or BruteForce.

The goal for today's lecture is to sketch out BruteForce and the various forms of reduction; we will see more details of these and other techniques later.