Algorithm and Data Structure Review

Dynamic Programming (optimally plan processes)

Dynamic programming is a very powerful algorithmic paradigm in which a problem is solved by identifying a collection of subproblems and tackling them one by one, smallest first, using the answers to small problems to help figure out larger ones, until the whole lot of them is solved.

When solving a problem by dynamic programming, the most crucial question is, what are the subproblems?

The “base cases” of dynamic programming are the very smallest subproblems.

Every dynamic program has an underlying directed acyclic graphs (DAG) structure: think of each node as representing a subproblem, and each edge as a precedence constraint on the order in which the subproblems can be tackled. Having nodes U1, …, Uk point to V means “subproblem V can only be solved once the answers to U1, …, Uk are known”.

The reason why recursion works better with divide-and-conquer (DAC) than dynamic programming (DP) is that in DAC, a problem is expressed in terms of subproblems that are substantially smaller (half the size). In a typical DP formulation, a problem is reduced to subproblems that only slightly smaller. Efficiency is therefore obtained by explicitly enumerating the distinct subproblems and solving them in the right order.

The knapsack problem generalizes a wide variety of resource-constrained selection tasks. (replace “weight” for bag with “CPU time” or “bandwidth”)

 

To be continue…

Advertisements

About liyao13

Yao Li is a web and iOS developer, blogger and he has a passion for technology and business. In his blogs, he shares code snippets, tutorials, resources and notes to help people develop their skills. Donate $5 to him for a coffee with PayPal at About Me page and read more professional and interesting technical blog articles. Follow him @Yaoli0615 at Twitter to get latest tech updates.
This entry was posted in CS Research&Application, Uncategorized and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s