Greedy Algorithms

Structure of a Greedy Algorithm:-

  1. Eager decision property: A worldwide (generally speaking) ideal arrangement can be reached by picking the ideal decision at each progression.
  2. Ideal foundation: An issue has an ideal base if an ideal answer for the whole issue contains the ideal answers for the sub-issues.

Restrictions of Greedy Algorithms:-


  1. Dijkstra’s Algorithm:-

Where you shouldn’t use Greedy approach?

Greedy vs Divide & Conquer vs Dynamic Programming

  1. Optimises by making the best choice at the moment
  2. Doesn’t generally track down the ideal arrangement, yet is quick
  3. Requires basically no memory
  1. Upgrades by separating a subproblem into less difficult adaptations of itself and utilizing multi-stringing and recursion to address
  2. Continuously tracks down the ideal arrangement, however is more slow than Greedy
  3. Requires some memory to recollect recursive calls
  1. Same as Divide and Conquer, yet advances by reserving the responses to each subproblem as not to rehash the computation twice.
  2. Continuously tracks down the ideal arrangement, however could be inconsequential on little datasets.
  3. Requires a ton of memory for remembrance/classification

Minimum Spanning Trees Using Prim’s Algorithm:-

  1. Make another tree with a solitary vertex (picked haphazardly)
  2. Of the multitude of edges not yet in the new tree, track down the base weighted edge and move it to the new tree.
  3. Rehash stage 2 until all vertices are in the tree

Is Greedy Optimal? Does Greedy Always Work?

  • Pick 3 divisions of coins. 1p, x, and under 2x yet more than x. We’ll pick 1, 15, 25.
  • Ask for change of 2 * second denomination (15)
[5, 0, 1]

Conclusion :-




Computer Science Student

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Nothing is Random, Not Even Rolling a Die

A group of dice rolling

Jigsaw Puzzles: Basic Number Theory Saves the Day

What’s wrong with the logic in counting?

McRoberts et al. 2013.

Build a Math Brain Through Deliberate Training

The Fascinating Idea Of Infinity

kids staring at a clock

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Shashwat Singh Raghav

Shashwat Singh Raghav

Computer Science Student

More from Medium

Linear Search[Algorithm without complexity]

Huffman Coding

C++ Datastructures and Algorithms Final Exam Solutions

An Introduction to Parallel Algorithms: Part 1.