- #1
lsepolis123f
- 13
- 0
In dynamic programming vs divide-and-conquer
We have
overlapping subproblems vs non overlapping subproblems
How distinguished, in other words what means overlapping subproblems...?
Discrete Mathematics and Its Applications Seventh Edition Kenneth H. Rosen
Ch.8 Advanced Counting Techniques
"We will discuss two ways that recurrence relations play important roles in the study of algorithms. First, we will introduce an important algorithmic paradigm known as dynamic programming. Algorithms that follow this paradigm break down a problem into overlapping subproblems. The solution to the problem is then found from the solutions to the subproblems through the use of a recurrence relation. Second, we will study another important algorithmic paradigm, divide-and-conquer. Algorithms that follow this paradigm can be used to solve a problem by recursively breaking it into a fixed number of non overlapping subproblems until these problems can be solved directly.The complexity of such algorithms can be analyzed using a special type of recurrence relation. In this chapter we will discuss a variety of divide-and-conquer algorithms and analyze their complexity using recurrence relations."
We have
overlapping subproblems vs non overlapping subproblems
How distinguished, in other words what means overlapping subproblems...?
Discrete Mathematics and Its Applications Seventh Edition Kenneth H. Rosen
Ch.8 Advanced Counting Techniques
"We will discuss two ways that recurrence relations play important roles in the study of algorithms. First, we will introduce an important algorithmic paradigm known as dynamic programming. Algorithms that follow this paradigm break down a problem into overlapping subproblems. The solution to the problem is then found from the solutions to the subproblems through the use of a recurrence relation. Second, we will study another important algorithmic paradigm, divide-and-conquer. Algorithms that follow this paradigm can be used to solve a problem by recursively breaking it into a fixed number of non overlapping subproblems until these problems can be solved directly.The complexity of such algorithms can be analyzed using a special type of recurrence relation. In this chapter we will discuss a variety of divide-and-conquer algorithms and analyze their complexity using recurrence relations."