Ch-3 Optimal Solution Finding algorithms

By thepks_wojtz4Algo Beginners, Algorithms, C
Reading Time: 3 minutes
 

If you did read the last previous post of Chapter 2 you’ll notice that greedy algorithm make a choice and then stick to it. Suppose if you used the numbers in the previous post as 6, 66, 666, 6666 in this case which one should be picked first? It really doesn’t matter for a greedy algorithm and I encourage you to check which one is picked by Chapter 2 algorithm.

Sometimes though we’re interested in how we reach the solution, in which case greedy algorithms can’t help you since it overlooks other possible choices. Almost all of the time you’ll end up using some form of  Dynamic Programming solution when facing this situation.

Example: - Finding GCD of two numbers

Suppose you’re given two numbers and asked to find GCD of those two numbers. Well first we need to know what’s GCD. 

GCD of two numbers is the largest number which divides both the numbers. You can read more about GCD here. 

Slow - Naive Solution

It’s always good to think in terms of naive solutions first and then figure out a  faster version. Not only does it provides you with base solution but you can also benchmark your fast solution with respect to it.

So the naive solution would be as follows

  • Find the smallest of those two numbers.
  • Loop over all numbers upto this smallest number and check if the current loop number divides both numbers.
  • At the end of loop you’ll have GCD.

In code this could look something like the following,

#include <stdio.h>

int gcd(int a, int b) {
    int maxLoop = a < b ? a : b;
    int gcdVal = -1;
    int i = 0;
    
    //Note that we start from 1 so gcdVal is guaranteed
    //to be set to at least 1 when this loop ends.
    for ( i = 1; i < maxLoop; i++) {
        if (a % i == 0 && b % i == 0)
            gcdVal = i;
    }
    return gcdVal;
}

The problem with above code is that for large numbers this process is going to be very slow however it’ll always provide the correct solution. Now how do we make it faster?

  1. Use a Greedy Algorithm.
  2. Use a Dynamic Programming technique here.

A Greedy Algorithm seems better here since we don’t care about how we reach the end result. All we need to do now is figure out a constraint to apply  for our greedy algorithm so we can skip some of the choices that we go over in the form of our loop.

In this case we can exploit mathematical properties of numbers. We’re going to use Euclid’s Algorithm for this purpose. In easy words it says that,

Given two positive numbers a, b with a>b then GCD of a, b is same as GCD of a-b , b.

Thus all we need to do is

  1. Find the remainder a % b.
  2. If the remainder is 0 then b is the GCD of both a and b
  3. Otherwise, find the GCD of b, remainder. 
  4. Repeat steps 1 to 4.

 

GCD- Faster Euclidian's Algo

#include <stdio.h>

int gcd(int a, int b) {
    int divisor = a > b ? b : a;
    int dividend = a > b ? a : b;
    
    if (divisor == 0)
        return dividend;
    
    return gcd(divisor, dividend % divisor);
}

The above is a recursive solution and we’ll try to convert it into a non-recursive one next. If you see however from the code it’s clear that we’re able to skip a lot of numbers using our greedy strategy.  

Eculid's Algo - Non recursive

#include <stdio.h>

int gcd(int a, int b) {
//until one of a or b is zero
    while (a !=0 && b != 0) {
    //swap a with to be the remainder.
        if (a > b)
            a = a % b;
        else //swap b to be the remainder.
            b = b % a;
    }
    //Since gcd (a,0) = a 
    return a == 0 ? b : a;
}

Leave a Reply