Chapter 9 Other Algorithmic Techniques
PREREQUISITES
Before beginning this chapter, you should be able to- Write and explain an algorithm
- Describe the class NP
- Describe growth rates and order
- Use random number tables and generators (Appendices A and B)
- Write a recursive algorithm
GOALS
At the end of this chapter, you should be able to- Explain the approximation algorithm concept
- Explain approximation algorithms for some class NP problems
- Explain the four types of probabilistic algorithms
- Use arrays to improve algorithm efficiency
STUDY SUGGESTIONS
As you are working through the chapter, you should rework the examples to
make sure you understand them. You should specifically trace through the
algorithms and input data presented to try to recreate the results given. You