1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Overlapping subproblems vs non overlapping -divide & conquer

  1. Jul 13, 2016 #1
    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."
  2. jcsd
  3. Jul 13, 2016 #2
    Can you provide an example of each - that seems the difference...
  4. Jul 13, 2016 #3


    User Avatar
    Science Advisor
    Gold Member

    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,
    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.
    Last edited: Jul 13, 2016
  5. Jul 14, 2016 #4
    overlapping means pass from the same point sometime? or the one half part pass sometime from first half part?
  6. Jul 14, 2016 #5


    User Avatar
    Science Advisor
    Gold Member

    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).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted