2022 July 21
  • Problem: you have a classroom and want to hold as many classes there as possible. You hold all of them, because some overlap. How do you pick what set of classes to hold so that you get the biggest set of classes as possible? . Pick the class that ends the soonest. That is the first class. Now, pick a class that starts after this first one. One more time, pick the class that ends the soonest. Keep doing that until you fill the schedule. That is a greedy algorithm.

  • Greedy algorithms are simple: at each step, pick the local optimal move/solution. Then, at the end, you will have the globally optimal solution.

  • Problem: suppose you’re starting a radio show for a country that has 50 states, and you want to reach listeners on all of them. You want to minimize the number of stations you play on (because each one costs money). You have a list of stations, where each line has a station and on which states it is available. Each station covers 2 or 3 states, and there’s overlap between them. How do you figure out the smallest set of stations you can play on to cover all 50 states? . Pick the station that covers the most states that haven’t been covered yet. It’s OK if it covers some states that have already been covered. Repeat until all the states are covered. That is an approximation algorithm. This runs on O(n^2) time (n is the number of radio stations)

  • When processing the exact solution takes much time, an approximation algorithm will work. They are evaluated by how fast they are and how close they are to the optimal solution.

  • Sometimes, an exact algorithm can take exponential times to run compared with a greedy one. So, taking into account that, sometimes greedy algorithms can have a lower Big-O notation, making them more ideal to solve problems than an “exact” one.

NOTE: The original content(s) that inspired this one can be found at:
All copyright and intellectual property of each one belongs to its' original author.