CSE MENTOR

Difference between Backtracking Vs Branch and Bound

October 14, 2023 CSE MENTORS 0

<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0-lqiJ2k-GDhd0b67lfCgKlX7hamDF255HfgKVoH3BhP03Q0IFs1VBrsEDa8xZSvh289DuXdTmcNu-m1-A0a93WCaiwPV2a6Ns6jBsNEvXkjtUITgMnA4ofOcGjL2vMmgsTbKupkNFXrJS5wKhxUnO7KKY1LzgAoAaiGRtTRJwd2AcxwHv2aW8EB-bQg/s1024/Study-Materials-1024x548.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="548" data-original-width="1024" height="171" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0-lqiJ2k-GDhd0b67lfCgKlX7hamDF255HfgKVoH3BhP03Q0IFs1VBrsEDa8xZSvh289DuXdTmcNu-m1-A0a93WCaiwPV2a6Ns6jBsNEvXkjtUITgMnA4ofOcGjL2vMmgsTbKupkNFXrJS5wKhxUnO7KKY1LzgAoAaiGRtTRJwd2AcxwHv2aW8EB-bQg/s320/Study-Materials-1024x548.png" width="320" /></a></div> <h3>Backtracking and Branch and Bound Comparison Chart</h3>
<table class="tablepress tablepress-id-87" style="width: 76.0503%;">
<thead>
<tr class="row-1 odd">
<th class="column-1" style="text-align: center; width: 52.5132%;">Backtracking</th>
<th class="column-2" style="text-align: center; width: 46.6931%;">Branch and Bound</th>
</tr>
</thead>
<tbody class="row-hover">
<tr class="row-2 even">
<td class="column-1" style="width: 52.5132%;">Backtracking is used to solve decision problems</td>
<td class="column-2" style="width: 46.6931%;">Branch and bound are used to solve optimization problems</td>
</tr>
<tr class="row-3 odd">
<td class="column-1" style="width: 52.5132%;">Backtracking is traced by DFS</td>
<td class="column-2" style="width: 46.6931%;">Branch and Bound are traced by BFS and DFS</td>
</tr>
<tr class="row-4 even">
<td class="column-1" style="width: 52.5132%;">Backtracking contains the feasibility function.</td>
<td class="column-2" style="width: 46.6931%;">Branch and Bound contain the bounding function.</td>
</tr>
<tr class="row-5 odd">
<td class="column-1" style="width: 52.5132%;">Backtracking is more efficient.</td>
<td class="column-2" style="width: 46.6931%;">Branch-and-Bound is less efficient.</td>
</tr>
<tr class="row-6 even">
<td class="column-1" style="width: 52.5132%;">Applications:
<ul><li>N Queen Problem,</li><li>Graph coloring problem,</li><li>Hamiltonian cycle problem,</li><li>Knapsack Problem,</li><li>Sum of subsets problem</li></ul>
</td>
<td class="column-2" style="width: 46.6931%;">Applications:
<ul><li>Job sequencing problem</li><li>Traveling salesman problem</li><li>Knapsack problem</li></ul>
</td>
</tr>
</tbody>
</table>

Materials Difference between Backtracking Vs Branch and Bound

Backtracking and Branch and Bound Comparison Chart Backtracking Branch and Bound Backtracking is used to solve decision problems...

NEC B.Tech CSE 3-1 DAA Video Tutorial

October 14, 2023 CSE MENTORS 0

An Algorithm is a sequence of steps to solve a problem. Design and 
Analysis of Algorithm is very important for designing algorithm to solve
 different types of problems in the branch of computer science and 
information technology. This tutorial introduces the fundamental 
concepts of Designing Strategies, Complexity analysis of Algorithms, 
followed by problems on Graph Theory and Sorting methods. This tutorial 
also includes the basic concepts on Complexity theory.<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPABfUGLzVwhOkcK1C2Dz0b0z-hNgOtyL_q4kCTMNLHrLTkZOJFIkbwzYj4MZ2v28uR-SukC_H8D9T1y2scNA2_Mwi5KSQYoEpQGtngVwI5ywd63VW2wqyEzPtxMtlF-1Y-6D5ZpB9ctZKlRegF0vSvX70aWwlAFQGHFJrxtpynFlDwvaBgw_GscSCyL4/s1200/design-and-analysis-of-algorithms-0-1666549021.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="700" data-original-width="1200" height="187" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPABfUGLzVwhOkcK1C2Dz0b0z-hNgOtyL_q4kCTMNLHrLTkZOJFIkbwzYj4MZ2v28uR-SukC_H8D9T1y2scNA2_Mwi5KSQYoEpQGtngVwI5ywd63VW2wqyEzPtxMtlF-1Y-6D5ZpB9ctZKlRegF0vSvX70aWwlAFQGHFJrxtpynFlDwvaBgw_GscSCyL4/s320/design-and-analysis-of-algorithms-0-1666549021.jpeg" width="320" /></a></div>Note: Click on the topic to watch video  UNIT-I<a href="https://www.youtube.com/watch?v=6Ds9U56KIC8" target="_blank">1. Algorithm Specification</a>2. <a href="https://www.youtube.com/watch?v=nmoQ6ZKId3k" target="_blank">Performance Analysis -Space complexity</a>3. <a href="https://www.youtube.com/watch?v=sn1ugY-jzQE" target="_blank">Performance Analysis -Time complexity</a>4. <a href="https://www.youtube.com/watch?v=A03oI0znAoc" target="_blank">Asymptotic Notations (Big-oh notation).</a> 5. <a href="https://www.youtube.com/watch?v=Nd0XDY-jVHs" target="_blank">Asymptotic Notations (Omega notation).</a> 6. <a href="https://www.youtube.com/watch?v=cFZ_0jXaaAQ" target="_blank">Asymptotic Notations (Theta notation). </a><a href="https://www.youtube.com/watch?v=-PlqXj50ZZc" target="_blank">7. Small O Notifications</a>   UNIT-II (Divide and Conquer)1. <a href="https://www.youtube.com/watch?v=2Rr2tW9zvRg" target="_blank">General method</a>2. Binary search   2.1. <a href="https://www.youtube.com/watch?v=C2apEw9pgtw" target="_blank">Binary search Iterative Method</a>   2.2. <a href="https://www.youtube.com/watch?v=uEUXGcc2VXM" target="_blank">Binary search Recursive Method</a>  2.3. <a href="https://www.youtube.com/watch?v=3LvSqpI5BOg" target="_blank">Time Complexity Analysis </a> 3. Merge sort   3.1. <a href="https://www.youtube.com/watch?v=mB5HXBb_HY8&t=48s" target="_blank">Merge sort Example </a>   3.2. <a href="https://www.youtube.com/watch?v=279cymdrmdg" target="_blank">Merge sort Time Complexity </a> 4. Quick sort   4.1. <a href="https://www.youtube.com/watch?v=7h1s2SojIRw&t=12s" target="_blank">Quick sort Example</a>  4.2. <a href="https://www.youtube.com/watch?v=-qOVVRIZzao" target="_blank">Quick sort Time Complexity </a> 5. Strassen’s matrix multiplication.  5.1. <a href="https://www.youtube.com/watch?v=0oJyNmEbS4w&t=1170s" target="_blank">Introduction to Strassen’s matrix multiplication.</a> 5.2.<a href="https://www.youtube.com/watch?v=dEq9QuNpQ6E" target="_blank"> Example of Strassen’s matrix multiplication.</a>Note: Algorithm, example, and Time Complexity are important while writing Exam.    UNIT-III (Greedy method)1. <a href="https://www.youtube.com/watch?v=ARvQcqJ_-NY&t=24s" target="_blank">General method</a> 2. <a href="https://www.youtube.com/watch?v=oTTzNMHM05I" target="_blank">Knapsack problem</a>3. <a href="https://www.youtube.com/watch?v=zPtI8q9gvX8" target="_blank">Job sequencing with deadlines</a> 4. Minimum cost spanning trees   4.1. <a href="https://www.youtube.com/watch?v=4ZlRH0eK-qQ" target="_blank">Prim's Algorithm </a>       4.1.1. <a href="https://www.youtube.com/watch?v=aTlloolNQec" target="_blank">Prim's Algorithm Time Complexity </a>   4.2. <a href="https://www.youtube.com/watch?v=4ZlRH0eK-qQ" target="_blank">Kruskals Algorithm </a>      4.2.1.<a href="https://www.youtube.com/watch?v=iDYZK0_7zk0" target="_blank">Kruskals Algorithm Time Complexity </a> 5. <a href="https://www.youtube.com/watch?v=XB4MIexjvY0" target="_blank">Single source shortest paths</a>UNIT-IV(Dynamic Programming) 1.<a href="https://www.youtube.com/watch?v=5dRGRueKU3M" target="_blank">The General method</a>2. <a href="https://www.youtube.com/watch?v=oNI0rf2P9gE&t=433s" target="_blank">All pairs shortest path problem Example</a>     2.1. <a href="https://www.youtube.com/watch?v=HAFAD8XbXps" target="_blank">All pairs shortest path problem Algorithm Analysis</a> 3.<a href="https://www.youtube.com/watch?v=wAy6nDMPYAE" target="_blank">Optimal binary search trees</a>4. <a href="https://www.youtube.com/watch?v=nLmhmB6NzcM" target="_blank">0/1 knapsack Problem</a> 5. <a href="https://www.youtube.com/watch?v=uJOmqBwENB8" target="_blank">Reliability design</a>6. <a href="https://www.javatpoint.com/travelling-sales-person-problem" target="_blank">The Travelling sales person problem</a>7. <a href="https://www.youtube.com/watch?v=_WncuhSJZyA" target="_blank">Matrix-chain multiplication</a> UNIT-VBacktracking: <a href="https://www.youtube.com/watch?v=DKCbsiDBN6c" target="_blank">The General method</a><a href="https://www.youtube.com/watch?v=xFv_Hl4B83A" target="_blank">N-Queen problem</a><a href="https://www.youtube.com/watch?v=kyLxTdsT8ws" target="_blank">Sum of subsets</a><a href="https://www.youtube.com/watch?v=052VkKhIaQ4" target="_blank">Graph coloring</a><a href="https://www.youtube.com/watch?v=dQr4wZCiJJ4" target="_blank">Hamiltonian cycles</a> Branch and Bound: <a href="https://www.youtube.com/watch?v=3RBNPc0_Q6g" target="_blank">The method</a><a href="https://www.youtube.com/watch?v=yV1d-b_NeK8&t=383s" target="_blank">0/1 knapsack problem </a> <a href="https://www.youtube.com/watch?v=1FEP_sNb62k" target="_blank">Travelling sales person problem.</a><h2 style="text-align: center;">Differences between different methodologies </h2>1. <a href="https://csementor.blogspot.com/2023/10/difference-between-greedy-algorithm-and-divide-and-conquer-algorithm.html" target="_blank">Difference between divide and conquer Vs Greedy Method </a>2. <a href="https://csementor.blogspot.com/2023/10/difference-between-divide-and-conquer-and-dynamic-programming.html" target="_blank">Difference between divide and conquer Vs Dynamic Programming</a> 3.<a href="https://csementor.blogspot.com/2023/10/greedy-approach-vs-dynamic-programming.html" target="_blank"> Difference between Greedy Method  Vs Dynamic Programming </a>4. <a href="https://csementor.blogspot.com/2023/10/difference-between-backtracking-and-branch-and-bound.html" target="_blank">Difference between Backtracking Vs Branch and Bound  </a>

Materials NEC B.Tech CSE 3-1 DAA Video Tutorial

An Algorithm is a sequence of steps to solve a problem. Design and Analysis of Algorithm is very important for designing algorithm to solv...

Difference between Greedy Method Vs Dynamic Programming

October 14, 2023 CSE MENTORS 0

Greedy approach and dynamic programming are two different algorithmic
 approaches that can be used to solve optimization problems. Here are 
the main differences between these two approaches:
<h3>Greedy approach:</h3>
<ol><li>The greedy approach makes locally optimal choices at each step with the hope of finding a global optimum.</li><li>The greedy approach does not necessarily consider the future consequences of the current choice.</li><li>The greedy approach is useful for solving problems where making locally optimal choices at each step leads to a global optimum.</li><li>The greedy approach is generally faster and simpler than dynamic programming.</li></ol>
<h3>Dynamic programming:</h3>
<ol><li>Dynamic programming is a bottom-up algorithmic approach that builds 
up the solution to a problem by solving its subproblems recursively.</li><li>Dynamic programming stores the solutions to subproblems and reuses 
them when necessary to avoid solving the same subproblems multiple 
times.</li><li>Dynamic programming is useful for solving problems where the optimal
 solution can be obtained by combining optimal solutions to subproblems.</li><li>Dynamic programming is generally slower and more complex than the greedy approach, but it guarantees the optimal solution.</li><li>In summary, the main difference between the greedy approach and 
dynamic programming is that the greedy approach makes locally optimal 
choices at each step without considering the future consequences, while 
dynamic programming solves subproblems recursively and reuses their 
solutions to avoid repeated calculations. The greedy approach is 
generally faster and simpler, but may not always provide the optimal 
solution, while dynamic programming guarantees the optimal solution but 
is slower and more complex.</li></ol><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0-lqiJ2k-GDhd0b67lfCgKlX7hamDF255HfgKVoH3BhP03Q0IFs1VBrsEDa8xZSvh289DuXdTmcNu-m1-A0a93WCaiwPV2a6Ns6jBsNEvXkjtUITgMnA4ofOcGjL2vMmgsTbKupkNFXrJS5wKhxUnO7KKY1LzgAoAaiGRtTRJwd2AcxwHv2aW8EB-bQg/s1024/Study-Materials-1024x548.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="548" data-original-width="1024" height="171" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0-lqiJ2k-GDhd0b67lfCgKlX7hamDF255HfgKVoH3BhP03Q0IFs1VBrsEDa8xZSvh289DuXdTmcNu-m1-A0a93WCaiwPV2a6Ns6jBsNEvXkjtUITgMnA4ofOcGjL2vMmgsTbKupkNFXrJS5wKhxUnO7KKY1LzgAoAaiGRtTRJwd2AcxwHv2aW8EB-bQg/s320/Study-Materials-1024x548.png" width="320" /></a></div>

<h2>Greedy approach:</h2>
<blockquote>
A Greedy algorithm is an algorithmic paradigm that builds up a 
solution piece by piece, always choosing the next piece that offers the 
most obvious and immediate benefit. So the problems where choosing 
locally optimal also leads to a global solution is the best fit for 
Greedy. <div id="GFG_AD_gfg_mobile_336x280"></div>
</blockquote>
Example: In Fractional Knapsack Problem the local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to global optimal solution because we allowed taking fractions of an item. Characteristics of Greedy approach:  A problem that can be solved using the Greedy approach follows the below-mentioned properties: Optimal substructure property. <ul><li>Minimization or Maximization of quantity is required.</li><li>Ordered data is available such as data on increasing profit, decreasing cost, etc.</li><li>Non-overlapping subproblems.</li></ul> <h2 style="text-align: left;">Dynamic Programming:</h2><blockquote>
Dynamic programming is mainly an optimization over plain recursion.
 Wherever we see a recursive solution that has repeated calls for the 
same inputs, we can optimize it using Dynamic Programming. The idea is 
to simply store the results of subproblems so that we do not have to 
re-compute them when needed later. This simple optimization reduces time
 complexities from exponential to polynomial.
</blockquote>
Example: If we write a simple recursive solution for
 Fibonacci Numbers, we get exponential time complexity and to optimize 
it by storing solutions of subproblems, time complexity reduces to 
linear this can be achieved by Tabulation or Memoization method of Dynamic programming. 
<h3>Characteristics of Dynamic Programming:</h3>A problem that can be solved using Dynamic Programming must follow the below mentioned properties:  <ul style="text-align: left;"><li>Optimal substructure property. </li><li>Overlapping subproblems.</li></ul><div> Below are some major differences between Greedy method and Dynamic programming: <figure class="table">
<table>
<thead>
<tr>
<th>
Feature
</th>
<th>Greedy method</th>
<th>Dynamic programming</th>
</tr>
</thead>
<tbody>
<tr>
<td>
Feasibility 
</td>
<td>In a greedy Algorithm, we make whatever choice seems best at the moment in the hope that it will lead to global optimal solution.</td>
<td>In Dynamic Programming
 we make decision at each step considering current problem and solution 
to previously solved sub problem to calculate optimal solution .</td>
</tr>
<tr>
<td>
Optimality
</td>
<td>In Greedy Method, sometimes there is no such guarantee of getting Optimal Solution.</td>
<td>It is guaranteed that Dynamic Programming will generate an optimal 
solution as it generally considers all possible cases and then choose 
the best.</td>
</tr>
<tr>
<td>
Recursion
</td>
<td>A greedy method follows the problem solving heuristic of making the locally optimal choice at each stage.</td>
<td>A Dynamic programming is an algorithmic technique which is usually 
based on a recurrent formula that uses some previously calculated 
states.</td>
</tr>
<tr>
<td>
Memoization                                   
</td>
<td>It is more efficient in terms of memory as it never look back or revise previous choices</td>
<td>It requires Dynamic Programming table for Memoization and it increases it’s memory complexity.</td>
</tr>
<tr>
<td>
    Time        complexity                    
</td>
<td>Greedy methods are generally faster. For example, Dijkstra’s shortest path algorithm takes O(ELogV + VLogV) time.</td>
<td>Dynamic Programming is generally slower. For example, Bellman Ford algorithm takes O(VE) time.</td>
</tr>
<tr>
<td>
Fashion
</td>
<td>The greedy method computes its solution by making its choices in a 
serial forward fashion, never looking back or revising previous choices.</td>
<td>Dynamic programming computes its solution bottom up or top down by synthesizing them from smaller optimal sub solutions.</td>
</tr>
<tr>
<td>
Example
</td>
<td>Fractional knapsack .   </td>
<td>0/1 knapsack problem   </td>
</tr>
</tbody>
</table>
</figure>
</div>

Materials Difference between Greedy Method Vs Dynamic Programming

Greedy approach and dynamic programming are two different algorithmic approaches that can be used to solve optimization problems. Here are ...

Difference between divide and conquer Vs Greedy Method

October 14, 2023 CSE MENTORS 0

Greedy algorithm and divide and conquer algorithm are two common 
algorithmic paradigms used to solve problems. The main difference 
between them lies in their approach to solving problems.
<h3>Greedy Algorithm:</h3>
<ol><li>The greedy algorithm is an algorithmic paradigm that follows the 
problem-solving heuristic of making the locally optimal choice at each 
stage with the hope of finding a global optimum.</li><li>In other words, a greedy algorithm chooses the best possible option 
at each step, without considering the consequences of that choice on 
future steps. Greedy algorithms are useful for solving optimization problems that can be divided into smaller subproblems. Greedy algorithms may not always find the optimal solution, but they are usually faster and simpler than other algorithms.</li><li>Greedy algorithm is defined as a method for solving optimization problems by taking decisions that result in the most evident and immediate benefit irrespective of the final outcome. It is a simple, intuitive algorithm that is used in optimization problems.</li></ol>
<h3>Divide and Conquer Algorithm:</h3>
<ol><li>The divide and conquer algorithm is an algorithmic paradigm that 
involves breaking down a problem into smaller subproblems, solving each 
subproblem recursively, and then combining the solutions to the 
subproblems to solve the original problem. In other words, the divide
 and conquer algorithm solves a problem by dividing it into smaller 
subproblems, solving each subproblem independently, and then</li><li>combining the solutions to the subproblems to solve the original problem. Divide
 and conquer algorithms are useful for solving problems that can be 
divided into smaller subproblems that are similar to the original 
problem.</li><li>Divide and conquer algorithms are generally slower than greedy 
algorithms, but they are more likely to find the optimal solution. In
 summary, the main difference between greedy algorithms and divide and 
conquer algorithms is in their approach to solving problems. Greedy 
algorithms make locally optimal choices at each step, while divide and 
conquer algorithms divide a problem into smaller subproblems and solve 
each subproblem independently. Greedy algorithms are faster and simpler 
but may not always find the optimal solution, while divide and conquer 
algorithms are slower but more likely to find the optimal solution.</li></ol>
A typical Divide and Conquer algorithm solves a problem using the following three steps:
<blockquote>
<ul><li>Divide: This involves dividing the problem into smaller sub-problems.</li><li>Conquer: Solve sub-problems by calling recursively until solved.</li><li>Combine: Combine the sub-problems to get the final solution of the whole problem.</li></ul></blockquote><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0-lqiJ2k-GDhd0b67lfCgKlX7hamDF255HfgKVoH3BhP03Q0IFs1VBrsEDa8xZSvh289DuXdTmcNu-m1-A0a93WCaiwPV2a6Ns6jBsNEvXkjtUITgMnA4ofOcGjL2vMmgsTbKupkNFXrJS5wKhxUnO7KKY1LzgAoAaiGRtTRJwd2AcxwHv2aW8EB-bQg/s1024/Study-Materials-1024x548.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="548" data-original-width="1024" height="171" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0-lqiJ2k-GDhd0b67lfCgKlX7hamDF255HfgKVoH3BhP03Q0IFs1VBrsEDa8xZSvh289DuXdTmcNu-m1-A0a93WCaiwPV2a6Ns6jBsNEvXkjtUITgMnA4ofOcGjL2vMmgsTbKupkNFXrJS5wKhxUnO7KKY1LzgAoAaiGRtTRJwd2AcxwHv2aW8EB-bQg/s320/Study-Materials-1024x548.png" width="320" /></a></div>  
<h2>Difference between the Greedy Algorithm and the Divide and Conquer Algorithm:</h2>
<figure class="table">
<table>
<thead>
<tr>
<th>Sl.No</th>
<th>
Divide and conquer
</th>
<th>
Greedy Algorithm
</th>
</tr>
</thead>
<tbody>
<tr>
<td>
1
</td>
<td>Divide and conquer is used to obtain a solution to the given problem, it does not aim for the optimal solution.</td>
<td>The greedy method is used to obtain an optimal solution to the given problem.</td>
</tr>
<tr>
<td>
2
</td>
<td>In this technique, the problem is divided into small subproblems. 
These subproblems are solved independently. Finally, all the solutions 
to subproblems are collected together to get the solution to the given 
problem.</td>
<td>In Greedy Method, a set of feasible solutions are generated and pick up one feasible solution is the optimal solution.</td>
</tr>
<tr>
<td>
3
</td>
<td>Divide and conquer is less efficient and slower because it is recursive in nature.</td>
<td>A greedy method is comparatively efficient and faster as it is iterative in nature.</td>
</tr>
<tr>
<td>
4
</td>
<td>Divide and conquer may generate duplicate solutions.</td>
<td>In the Greedy method, the optimal solution is generated without 
revisiting previously generated solutions, thus it avoids the 
re-computation </td>
</tr>
<tr>
<td>
5
</td>
<td>Divide and conquer algorithms mostly run in polynomial time.</td>
<td>Greedy algorithms also run in polynomial time but take less time than Divide and conquer</td>
</tr>
<tr>
<td>
6
</td>
<td>Examples: Merge sort,  Quick sort,  Strassen’s matrix multiplication.</td>
<td>Examples: Fractional Knapsack problem,  Activity selection problem,  Job sequencing problem<a href="https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/">.</a></td>
</tr>
</tbody>
</table>
</figure>

Materials Difference between divide and conquer Vs Greedy Method

Greedy algorithm and divide and conquer algorithm are two common algorithmic paradigms used to solve problems. The main difference between...

Difference between divide and conquer Vs Dynamic Programming

October 14, 2023 CSE MENTORS 0

Divide and conquer solves problems by breaking them into smaller subproblems, while dynamic programming solves problems by breaking them into overlapping subproblems and reusing their solutions.<div _ngcontent-sc166="" id="target-content"><div id="exam-info-container"><div class="card lms-custom-style ui-js-external-links" id="target-content-html">
<div class="table-responsive">
<table>
<tbody>
<tr class="table-head-bg-color">
<td>
Divide and Conquer
</td>
<td>
Dynamic Programming
</td>
</tr>
<tr>
<td>
Breaks problems into smaller subproblems
</td>
<td>
Breaks problems into overlapping subproblems
</td>
</tr>
<tr>
<td>
Solves subproblems independently
</td>
<td>
Reuses solutions of overlapping subproblems
</td>
</tr>
<tr>
<td>
Typically uses recursion
</td>
<td>
Typically uses iteration
</td>
</tr>
<tr>
<td>
No shared information between subproblems
</td>
<td>
Stores solutions in a table for future reference
</td>
</tr>
<tr>
<td>
Subproblems are solved sequentially
</td>
<td>
Subproblems can be solved in any order
</td>
</tr>
<tr>
<td>
Often results in redundant computations
</td>
<td>
Avoids redundant computations through memoization
</td>
</tr>
<tr>
<td>
Generally has a higher time complexity
</td>
<td>
Generally has a lower time complexity
</td>
</tr>
<tr>
<td>
Can be more intuitive for certain problems
</td>
<td>
Can be more efficient for problems with overlapping subproblems
</td>
</tr>
<tr>
<td>
Examples: Merge sort, Quick sort
</td>
<td>
Examples: Fibonacci sequence, Shortest path problems
</td>
</tr>
<tr>
<td>
May not exploit optimal substructure
</td>
<td>
Exploits optimal substructure to find optimal solutions
</td>
</tr>
<tr>
<td>
Requires combining results of subproblems
</td>
<td>
Requires identifying and solving overlapping subproblems
</td>
</tr>
<tr>
<td>
May involve merging or combining subproblem solutions
</td>
<td>
May involve selecting or choosing among subproblem solutions
</td>
</tr>
<tr>
<td>
Suitable for problems that can be divided into independent parts
</td>
<td>
Suitable for problems that can be solved by breaking them into overlapping subproblems
</td>
</tr>
<tr>
<td>
May require additional space for recursive calls
</td>
<td>
May require additional space for storing solutions in a table
</td>
</tr>
<tr>
<td>
Can have a higher space complexity
</td>
<td>
Can have a lower space complexity
</td>
</tr>
<tr>
<td>
Examples: Binary search, Maximum subarray problem
</td>
<td>
Examples: Longest common subsequence, Knapsack problem
</td>
</tr>
<tr>
<td>
Often uses a "divide," "conquer," and "combine" approach
</td>
<td>
Often uses a "divide," "solve," and "combine" approach
</td>
</tr>
<tr>
<td>
Requires solving all subproblems
</td>
<td>
Requires solving only necessary subproblems
</td>
</tr>
<tr>
<td>
May involve solving subproblems with the same parameters multiple times
</td>
<td>
Avoids redundant computation by storing and reusing solutions
</td>
</tr>
<tr>
<td>
May result in a simpler implementation
</td>
<td>
May require careful formulation and identification of subproblems
</td>
</tr>
<tr>
<td>
May not be suitable for problems with overlapping subproblems
</td>
<td>
Well-suited for problems with overlapping subproblems
</td>
</tr>
<tr>
<td>
No explicit storage of solutions
</td>
<td>
Solutions are explicitly stored in a table or array
</td>
</tr>
<tr>
<td>
Examples: Binary exponentiation, Closest pair problem
</td>
<td>
Examples: Matrix chain multiplication, Longest increasing subsequence
</td>
</tr>
<tr>
<td>
May have a higher memory overhead
</td>
<td>
May have a lower memory overhead
</td>
</tr>
<tr>
<td>
Generally used when the subproblems are independent
</td>
<td>
Generally used when the subproblems overlap
</td>
</tr>
<tr>
<td>
Can have a higher number of recursive calls
</td>
<td>
Can have a lower number of recursive calls
</td>
</tr>
<tr>
<td>
Examples: Mergesort, Binary search tree operations
</td>
<td>
Examples: Fibonacci series, Travelling salesman problem
</td>
</tr>
<tr>
<td>
May require a more detailed analysis of subproblems
</td>
<td>
Requires careful identification of overlapping subproblems
</td>
</tr>
<tr>
<td>
Breaks the problem into smaller, non-overlapping parts
</td>
<td>
Breaks the problem into overlapping subproblems
</td>
</tr>
</tbody>
</table>
</div></div></div></div><div _ngcontent-sc166="" id="target-content"><div id="exam-info-container"><div class="card lms-custom-style ui-js-external-links" id="target-content-html"><h2>Key Difference Between Divide and Conquer and Dynamic Programming</h2>
<ul><li>Approach:
<ul><li>Divide and Conquer: Breaks a problem into smaller subproblems and solves them independently.</li><li>Dynamic Programming: Breaks a problem into overlapping subproblems 
and solves them recursively or iteratively, storing their solutions.</li></ul>
</li><li>Subproblem Dependency:
<ul><li>Divide and Conquer: Subproblems are independent of each other.</li><li>Dynamic Programming: Subproblems can overlap or share common subproblems.</li></ul>
</li><li>Solution Utilization:
<ul><li>Divide and Conquer: Does not utilize previously solved subproblem solutions.</li><li>Dynamic Programming: Utilizes previously solved subproblem solutions by storing them for reuse.</li></ul>
</li><li>Solution Construction:
<ul><li>Divide and Conquer: The solution is obtained by combining the solutions of independent subproblems.</li><li>Dynamic Programming: The solution is built by solving and combining overlapping subproblems iteratively or recursively.</li></ul>
</li><li>Problem-Solving Order:
<ul><li>Divide and Conquer: Solves the subproblems in a top-down manner.</li><li>Dynamic Programming: Solves the subproblems in a bottom-up manner.</li></ul>
</li><li>Time Complexity:
<ul><li>Divide and Conquer: May take longer to solve the problem.</li><li>Dynamic Programming: Typically takes a shorter time to solve the problem.</li></ul>
</li><li>Subproblem Nature:
<ul><li>Divide and Conquer: Works well when subproblems are independent.</li><li>Dynamic Programming: Works well when subproblems overlap or share common subproblems.</li></ul>
</li><li>Example Algorithms:
<ul><li>Divide and Conquer: Merge Sort, Quick Sort.</li><li>Dynamic Programming: Fibonacci series, Knapsack problem.</li></ul>
</li><li>Memory Usage:
<ul><li>Divide and Conquer: Can be more memory-efficient in certain cases.</li><li>Dynamic Programming: May require more memory due to the storage of subproblem solutions.</li></ul>
</li><li>Approach Complexity:
<ul><li>Divide and Conquer: Generally simpler to understand and implement.</li><li>Dynamic Programming: Can be more complex to understand and implement.</li></ul> <div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0-lqiJ2k-GDhd0b67lfCgKlX7hamDF255HfgKVoH3BhP03Q0IFs1VBrsEDa8xZSvh289DuXdTmcNu-m1-A0a93WCaiwPV2a6Ns6jBsNEvXkjtUITgMnA4ofOcGjL2vMmgsTbKupkNFXrJS5wKhxUnO7KKY1LzgAoAaiGRtTRJwd2AcxwHv2aW8EB-bQg/s1024/Study-Materials-1024x548.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="548" data-original-width="1024" height="171" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh0-lqiJ2k-GDhd0b67lfCgKlX7hamDF255HfgKVoH3BhP03Q0IFs1VBrsEDa8xZSvh289DuXdTmcNu-m1-A0a93WCaiwPV2a6Ns6jBsNEvXkjtUITgMnA4ofOcGjL2vMmgsTbKupkNFXrJS5wKhxUnO7KKY1LzgAoAaiGRtTRJwd2AcxwHv2aW8EB-bQg/s320/Study-Materials-1024x548.png" width="320" /></a></div> <div _ngcontent-sc166="" id="target-content"><div id="exam-info-container"><div class="card lms-custom-style ui-js-external-links" id="target-content-html"><h2>Similarities Between Divide and Conquer and Dynamic Programming</h2>
<ul><li>Both Divide and Conquer and Dynamic Programming are algorithmic design paradigms used to solve complex problems.</li><li>Both paradigms involve breaking down the problem into smaller sub-problems to make it more manageable.</li><li>Both paradigms can be used to optimize solutions by using previously computed results to avoid redundant computations.</li><li>Both Divide Conquer and Dynamic Programming can result in efficient 
and optimal solutions, depending on the problem and the specific 
approach used.</li><li>Both paradigms can be used in various fields, such as computer science, mathematics, engineering, and more.</li><li>Both Divide Conquer and Dynamic Programming have trade-offs, such as
 time and space complexity, that must be considered when selecting the 
appropriate paradigm for a particular problem.</li><li>Both paradigms can be used in combination with other algorithmic 
design paradigms, such as Greedy Algorithms and Backtracking, to solve 
complex problems.</li></ul></div></div></div>  
</li></ul></div></div></div>

Materials Difference between divide and conquer Vs Dynamic Programming

Divide and conquer solves problems by breaking them into smaller subproblems, while dynamic programming solves problems by breaking them...

CSE MENTOR

Difference between Backtracking Vs Branch and Bound

NEC B.Tech CSE 3-1 DAA Video Tutorial

Difference between Greedy Method Vs Dynamic Programming

Difference between divide and conquer Vs Greedy Method

Difference between divide and conquer Vs Dynamic Programming

Materials

Syllabus

Question Papers

Popular Posts