Algorithms: Greedy, Dynamic, D, and C
Algorithms: Greedy, Dynamic, D, and C
Here is a short rundown of a few algorithms you might find useful.
Join the DZone community and get the full member experience.
Join For FreeThe open source HPCC Systems platform is a proven, easy to use solution for managing data at scale. Visit our Easy Guide to learn more about this completely free platform, test drive some code in the online Playground, and get started today.
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.
Managing data at scale doesn’t have to be hard. Find out how the completely free, open source HPCC Systems platform makes it easier to update, easier to program, easier to integrate data, and easier to manage clusters. Download and get started today.
Like This Article? Read More From DZone
Opinions expressed by DZone contributors are their own.
{{ parent.title || parent.header.title}}
{{ parent.tldr }}
{{ parent.linkDescription }}
{{ parent.urlSource.name }}