Divide and Conquer and Dynamic Programming Algorithms

Often students get confused what are differences between divide and conquer and dynamic programming. Since they solve problems in similar nature. Divide the problem into sub-problems combine them to get solution. Here I list the differences  between divide and conquer and dynamic programming in a table and also  made quizzes so that you can practice questions.

Divide and ConquerDynamic Programming
Examples-
Quick Sort, Binary Search, Merge Sort
Examples- Matrix Chain Multiplication, Bellman Ford for Shortest Path
Uses top-down approach to solve problems.Uses bottom-up approach to solve problems.
Partition the problem into independent sub-problems.Partition the problem into dependent sub-problems.
It recomputes sub-problems many times.Dynamic programming solves the sub-problems
once and keep them into a table.

 

Test your memory

#1 Dynamic programming uses

#2 Divide and conquer uses

#3 Dynamic programming divides the problems into

#4 Divide and conquer divides the problems into

#5 Dynamic programming is used to solve the type of problems

finish

Results

-
Share to Your Friend
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
Share to Your Friend
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Share to Your Friend
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Be the first to comment on "Divide and Conquer and Dynamic Programming Algorithms"

Leave a comment