Do you think IIT Guwahati certified course can help you in your career?
Introduction
Divide & Conquer and Dynamic Programming are two important algorithmic paradigms used to solve complex problems in computer science. Divide & Conquer breaks down a problem into smaller subproblems, solves them independently, and combines their solutions to solve the original problem. Dynamic Programming, on the other hand, solves problems by breaking them down into overlapping subproblems and storing the results to avoid redundant calculations.
What is Divide And Conquer?
Divide and conquer is a programming strategy of dividing a complex problem into small, simple subproblems. Then the sub-problems are computed parallelly. The solutions of the subproblems are combined to generate the final result. Dividing helps to break a complex problem into smaller manageable problems. It is implemented using recursion.
Working of Divide & Conquer
The steps involved in divide and conquer are:
Divide: Dividing given problem into sub-problems using recursion.
Conquer: Recursively solving the sub-problems. The direct result is generated if the results are small.
Combine: The results of the subproblems that are part of the recursion are combined to solve the problem.
Advantages Of Divide And Conquer
Parallelism: In this approach, we independently solve the subproblems. It helps in the execution of multi-processor and shared-memory systems. Thus, different subproblems can run on different processors.
Memory Usage: It provides efficient use of memory caches. Using the cache memory solves subproblems without using the slower main memory.
Reduces Difficulty: Here, we Divide the problem into smaller problems. This helps reduce the difficulty of the problem. Thus, making it more efficient than the brute force method.
Disadvantages Of Divide And Conquer
It is majorly implemented using recursion, making it slow.
The system can crash if recursion is carried out beyond the CPU stack.
Due to the large recursive base case, the recursion overhead can become very small.
What is Dynamic Programming?
It is the programming technique of dividing a given problem into smaller subproblems. It is used to find the optimal solution for a problem. It is similar to divide and conquer. Here, a sub-problem is solved just once. It is used to solve optimization problems.
The two properties that suggest the use of dynamic programming are:
Overlapping Sub-Problem: Here, we divide a problem into sub-problems. It is used when the solution of a subproblem is required repeatedly. Example calculating Fibonacci numbers.
Optimal Sub Structure: Here, we divide a problem into sub-problems. It is used if the optimal solution is calculated from the results of its sub-problems. Example Shortest path-finding question.
Working on Dynamic Programming
The steps involved in solving dynamic programming problems are:
Define a small problem and find an optimum solution to this problem. In our example, this is the same as finding the best path from the last intersection to the office.
To define a small sub-problem and find its optimal solution.
Enlarge the scope of this small problem and find the optimal solution to this new problem.
Continuing the above step, we get a sufficiently large problem. The problem now beholds the original problem.
Define the stopping conditions carefully.
Use the results of smaller problems to calculate the original problem result.
Advantages Of Dynamic Programming
Solution: It always gives an optimal solution for a problem.
Efficient: It uses overlapping subproblems to solve the problem. Thus, helps to increase efficiency by preventing overhead calculations.
Application: It can be applied to a variety of problems. These problems can be path-finding or optimization.
Disadvantages Of Dynamic Programming
Memory: It stores the solutions to the overlapping subproblems. Thus, requires a huge memory to solve problems.
Complexity: It is difficult to implement. As the problem gets larger, the number of subproblems increases. Thus, increasing the complexity of the solution.
Difference Between Divide & Conquer and Dynamic Programming
Parameters
Divide and Conquer
Dynamic Programming
Definition
It is a programming strategy of dividing a complex problem into small, simple subproblems.
It is a programming strategy of dividing a complex problem into small, simple overlapping subproblems.
Time
It is time-consuming as it solves a problem more than once. Thus, doing more work.
It solves a sub-problem exactly once. Therefore, less time-consuming.
Approach
It follows a top-down approach. Recursion is typically used.
It can follow a top-down or a bottom-up approach. Iterations are typically used.
Dependency
Sub-problems are independent of each other.
It has overlapping sub-problems.
Space
It does not store the intermediate result. Thus, less space is required.
It stores the results of the intermediate sub-problems. Thus, more space is required.
Simplicity
It is more intuitive and easy to understand.
It is less intuitive and difficult to implement.
Example
It is used in problems like Binary Search, Quick Sort, and Merge Sort.
It is used in problems like Longest common subsequence, Matrix Chain Multiplication, etc.
Frequently Asked Questions
Why is divide and conquer faster?
Divide-and-conquer algorithms are faster because they break a problem into smaller subproblems, solve them independently, and combine the solutions. This often leads to more efficient use of resources and can leverage parallel processing.
Can we use backtracking in dynamic programming?
Backtracking can be used in conjunction with dynamic programming when there are multiple solutions, and you need to explore all possibilities before committing to one. This combination is often used in optimization problems and complex decision-making scenarios.
What is memoization in Dynamic Programming?
Memoization is a dynamic programming approach. It is used to solve complex recursive problems. It is used to optimize the recursion. It involves storing the sub-problem results. It helps to avoid repeated computation.
What are the conditions for solving a problem using Divide and Conquer?
The necessary conditions are the given problem must be divisible into smaller sub-problems. The sub-problems must be easy problems. The complexity of combining the results must be comparable to other algorithms.
Conclusion
The article taught us about Dynamic Programming and Divide and Conquer techniques. We discussed the difference between divide and conquer and dynamic programming.
237+ registered 
