In the previous chapter, we learned about hash tables and binary search trees. In this chapter, we will explore algorithm design paradigms. These design patterns can be seen as the generic methods or approaches that motivate the design of a class of algorithms.
Just as an algorithm is a higher abstraction than a computer program, an algorithm design paradigm is an abstraction higher than an algorithm. The choice of an algorithm paradigm is an important one when designing an algorithm.
This chapter will focus on the following three algorithm paradigms:
- Greedy
- Divide and conquer
- Dynamic programming
By becoming familiar with these higher abstractions, you can make more informed decisions when designing algorithms.
There are obviously more algorithm design paradigms, but these three already cover a broad range of problems. Some other paradigms we're not talking about in this book are backtracking and prune and search. There are even paradigms focused on specific branches of computer science. The sweep line algorithms, in computational geometry, is an example of this.
By the end of this chapter, you will be able to:
- Describe greedy, divide and conquer, and dynamic programming algorithm paradigms
- Analyze common problems solved by using the described paradigms
- List the properties of a problem to be solved by each paradigm
- Solve some well-known problems that explain the applicability of each paradigm