Sunday, January 28, 2018

Codility - Lesson 16 Greedy algorithms

Source Link: 
https://app.codility.com/programmers/lessons/16-greedy_algorithms/

Some Notes: 

Greedy programming is a method by which a solution is determined based on making the locally optimal choice at any given moment. In other words, we choose the best decision from the viewpoint of the current stage of the solution.

Depending on the problem, the greedy method of solving a task may or may not be the best approach. If it is not the best approach, then it often returns a result which is approximately correct but suboptimal.

16.1. The Coin Changing problem

For a given set of denominations, you are asked to find the minimum number of coins with which a given amount of money can be paid. That problem can be approached by a greedy algorithm that always selects the largest denomination not exceeding the remaining amount of money to be paid. As long as the remaining amount is greater than zero, the process is repeated.

t turns out that the greedy algorithm is correct for only some denomination selections, but not for all.
For example, for coins of values 1, 2 and 5 the algorithm returns the optimal number of coins for each amount of money, but for coins of values 1, 3 and 4 the algorithm may return a suboptimal result.

16.1: The greedy algorithm for finding change.
1 def greedyCoinChanging(M, k):
2 n = len(M)
3 result = []
4 for i in xrange(n - 1, -1, -1):
5 result += [(M[i], k // M[i])]
6 k %= M[i]
7 return result

The time complexity of the above algorithm is O(n) as the number of coins is added once for every denomination.

Codility - Lesson 16 Greedy algorithms - 2. MaxNonoverlappingSegments

Source Link: https://app.codility.com/programmers/lessons/16-greedy_algorithms/max_nonoverlapping_segments/ Question: Located on a line ...