Algorithm Design Techniques

So far, we have been concerned W~i~th the efficient implementation of algorithms. We have seen that when an algorithm is given, the actual data structures need not be specified. It is up to the programmer to choose the approriate data structure in order to make the running time as small as possible.

In this chapter, we sW~i~tch our attention from the implementation of algorithms to the design of algorithms. Most of the algorithms that we have seen so far are straightforward and simple. Chapter 9 contains some algorithms that are much more subtle, and some require an argument (in some cases lengthy) to show that they are indeed correct. In this chapter, we W~i~ll focus on five of the common types of algorithms used to solve problems. For many problems, it is quite likely that at least one of these methods W~i~ll work. Specifically, for each type of algorithm we W~i~ll

• See the general approach.

• Look at several examples (the exercises at the end of the chapter provide many more examples).

• Discuss, in general terms, the time and space complex~i~ty, where appropriate.