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 15 Caterpillar Method

Source Link: 
https://app.codility.com/programmers/lessons/15-caterpillar_method/

Some Notes:
The Caterpillar method is a likeable name for a popular means of solving algorithmic tasks.  We remember the front and back positions of the caterpillar, and at every step either of them is moved forward.

15.1. Usage example
For example, in the following sequence we are looking for a subsequence whose total equals s = 12.



Let’s initially set the caterpillar on the first element. Next we will perform the following steps: 

• if we can, we move the right end (front) forward and increase the size of the caterpillar;

• otherwise, we move the left end (back) forward and decrease the size of the caterpillar.

In this way, for every position of the left end we know the longest caterpillar that covers elements whose total is not greater than s. If there is a subsequence whose total of elements equals s, then there certainly is a moment when the caterpillar covers all its elements.

15.1: Caterpillar in O(n) time complexity. 
1 def caterpillarMethod(A, s): 
2 n = len(A) 
3 front, total = 0, 0 
4 for back in xrange(n): 
5 while (front < n and total + A[front] <= s): 
6 total += A[front] 
7 front += 1 
8 if total == s: 
9 return True 
10 total -= A[back] 
11 return False

Notice that at every step we move the front or the back of the caterpillar, and their positions will never exceed n. Thus we actually get an O(n) solution.

Codility - Lesson 14 Binary Search Algorithm

Source Link:
https://codility.com/programmers/lessons/14-binary_search_algorithm/

Some Notes:
The binary search is a simple and very useful algorithm whereby many linear algorithms can
be optimized to run in logarithmic time.

In a binary search we use the information that all the elements are sorted.

Let’s see how the number of candidates is reduced, for example for the value x = 31.



For every step of the algorithm we should remember the beginning and the end of the remaining
slice of the array (respectively, variables beg and end). 

The middle element of the slice can easily be calculated as mid = (beg+end) / 2.

14.1: Binary search in O(log n).
1 def binarySearch(A, x):
2 n = len(A)
3 beg = 0
4 end = n - 1
5 result = -1
6 while (beg <= end):
7 mid = (beg + end) / 2
8 if (A[mid] <= x):
9 beg = mid + 1
10 result = mid
11 else:
12 end = mid - 1
13 return result

In subsequent iterations the number of candidates is halved, so the time complexity is O(log n).

Codility - Lesson 13 Fibonacci Numbers

Source Link:
https://codility.com/programmers/lessons/13-fibonacci_numbers/

Some Notes: 
The first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two.



The first twelve Fibonacci numbers are:



Notice that recursive enumeration as described by the definition is very slow.

Enumeration of the Fibonacci numbers can be done faster simply by using a basis of dynamic programming. 

We can calculate the values F0, F1, . . . ,Fn based on the previously calculated numbers (it is sufficient to remember only the last two values).

13.2: Finding Fibonacci numbers dynamically.
1 def fibonacciDynamic(n):
2 fib = [0] * (n + 2)
3 fib[1] = 1
4 for i in xrange(2, n + 1):
5 fib[i] = fib[i - 1] + fib[i - 2]
6 return fib[n]

The time complexity of the above algorithm is O(n).