Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Algorithms: Greedy, Dynamic, D, and C

DZone's Guide to

Algorithms: Greedy, Dynamic, D, and C

Here is a short rundown of a few algorithms you might find useful.

· Big Data Zone
Free Resource

Effortlessly power IoT, predictive analytics, and machine learning applications with an elastic, resilient data infrastructure. Learn how with Mesosphere DC/OS.

Greedy Algorithms

So, the greedy algorithms are those, in which best optimal solution is to be chosen at every stage.

The solution is build piece by piece.Greedy algorithms are better than dynamic programming, if applicable. As not every problem could be solved by a greedy method. For ex.0-1 knapsack problem can not be solved by greedy method.

Other problems that could be solved by greedy method are- Kruskal's MST, Prim's MST, Activity selection.

Dynamic Programming

Dynamic Programming is a paradigm that solves a given problem by breaking it into subproblems and stores the result of subproblems to avoid computing the same results again and again.

The main properties of a problem to be solved by this method are-:

1-Overlapping subproblem

2-Optimal sub Structure

For ex A fibonacci problem needs that to compute the factorial of 5 we must compute factorial of 2 , 3, 4 . So computing these again & again could be a mess, So these values are stored in lookup, and are looked before computing , if available they are restored from lookup otherwise calculated.

For ex- LCS , 0-1 Knapsack

Divide & Conquer

 Like Greedy and Dynamic Programming, D&C is also a paradigm. A typical D&C also solves the problem with 3 steps:

1. Divide: Break the problem into subproblems

2. Conquer: Recursively solve problems

3.Combine: Join the solutions

For example: Binary search, Quick Sort, Merge Sort.

Learn to design and build better data-rich applications with this free eBook from O’Reilly. Brought to you by Mesosphere DC/OS.

Topics:
data structures ,algorithms ,big data

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}