Undergrad Overlapping subproblems vs non overlapping -divide & conquer

[lsepolis123f]

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."

 

[lsepolis123f]

Can you provide an example of each - that seems the difference...

 

[QuantumQuest]

Can you provide an example of each - that seems the difference...

I'll give an answer in the context of Computer Science.

Think of the Mergesort algorithm for example. This is a divide-and-conquer algorithm. An outline of its steps is:

- Divide array into two halves.
- Recursively sort each half.
- Merge two halves to make sorted whole.

Its recurrence relation has two parts: $T(n) \leq 0$ if n = 1 or $T(n)\leq T(\lceil{n/2}\rceil) + T(\lfloor{n/2}\rfloor) + n$ otherwise,
where T(n) = number of comparisons to mergesort an input of size n. Its solution in terms of Big - Oh notation is $T(n) = O(n log_2{n})$.
Can you see that the subproblems, that this algorithm goes into, are non overlapping? In order to see this clearly, you have to follow the recursion on each half, till there are just two elements left - for each half, before merging takes charge.

Now, for dynamic programming, the key concept is optimal substructure. I would recommend to take a look into the Wikipedia page https://en.wikipedia.org/wiki/Dynamic_programming. A classic example in Computer Science, is Dijkstra's algorithm for the shortest path problem. It is a bit tricky to understand why the sub-problems are overlapping in this case, if you don't understand the method we proceed in dynamic programming first.

Now, all that said, Divide-and-Conquer and Dynamic Programming are mathematical methods, so they are used in pure mathematical problems as well. Dynamic programming in this context is a mathematical optimization method.

 

[lsepolis123f]

overlapping means pass from the same point sometime? or the one half part pass sometime from first half part?

 

[QuantumQuest]

overlapping means pass from the same point sometime? or the one half part pass sometime from first half part?

Let me clarify this more. When we say overlapping subproblems of a problem, we basically mean subproblems that are potentially reused several times or the recursive procedure we use - essentially algorithm, solves the same subproblem over and over instead of generating new subproblems. This is the case for dynamic programming and the subproblems solved during the course of a running algorithm in this method, are intimately related.

On the other hand, non - overlapping subproblems of a divide-and-conquer algorithm are separate (see my previous post for this).