Ch- 1. Beginning Algorithm Studying

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

Overcoming Fear of Algorithms

When most of us hear computer and programming algorithms for the first time, or even say after programming since a long time, many of us are frightened. The reason simply being not we don’t understand the fact that there are going to be problems which we can’t solve even after a lot of practice. 

Most algorithms we do study did took time to develop and what we need to learn is the techniques that have proven to work. It’s also possible that none of the technique does work on a problem but that’s alright. Whatever your reason to study algorithm design just be prepared mentally that it’s OK to not be able to crack a problem. 

What exactly do I need to look for

To really answer this question think about  any problem that you’ve solved in the past. It can be as simple as trying to change a light bulb! Obviously we weren’t born with the steps of changing the light bulb but we probably saw someone doing it and then with a little bit of practice we are able to do it ourselves.

Now the steps in changing a light bulb are fairly fixed and are optimized enough. However it’s possible that sometimes we might need to change the light bulb in a completely different setting, i.e. the surroundings where it’s installed is different from what we’re used to or maybe it’s a new kind of light bulb (app controlled) etc.

Whenever we’re presented with a new problem what we usually do is try to break it down in what can be done fairly easily and what is completely new. Sometimes it’s possible to do it while at others it’s not. Much like solving real life problems study of computer algorithms provides us with tools that’ve been proven to work but there’s no guarantee that they’ll work. But with a set of tools and a some steps on how to use those tools we’ve a scientific way of trying to tackle a programming problem.

Problem 1 - Finding Maximum number in a set of numbers

We’ve been given a set of numbers and we want to find the maximum number in that set of numbers.

Solution:

From our experience with world we know that we need to compare two items to figure out the bigger of the two. In order to find the biggest in a set of items we just repeat this procedure.

Important Points:

  1. In the solution proposed above we didn’t tried to solve the whole problem at once. We broke it down to how to find the biggest of two items.
  2. See if we can repeat the solution proposed to a smaller sub-problem. In this case, yes we can simply repeat this step.

So we can write this algorithm as

Max(N):

  1. Pick a number and assume it’s the biggest.
  2. Compare it to another number in the set which has NOT yet been checked.
  3. If the number is found to be greater than our assumption, make it the biggest.
  4. REPEAT steps 2 till 4 until all numbers have been examined in the set.

Code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdint.h>
#include <inttypes.h>
#include <assert.h>

#define ARRAY_SIZE(X) \
(sizeof(X) / sizeof(X[0]))

static int64_t* test_random_setup(int count) {
    int64_t *test_data = (int64_t*)calloc(count, sizeof(int64_t));
    //We assume we can get test_data allocated.
    unsigned int seed = (unsigned int) time(NULL);
    
    srand(seed);
    while(count > 0) {
        count--;
        test_data[count] = rand_r(&seed);
    }
    return test_data;
}

/*
 * Algorithm
 */
int64_t find_max_inset(int64_t *set, int count) {
    int i = 0;
    int64_t max = -1;
    //This is our premise
    //We assume the first number is the maximum.
    if (count > 0)
        max = set[0];
        
    //Since we assume that first number is maximum 
    //we only need to check all other except this first one. 
    //This choice doesn't make any difference to the
    //working of this algorithm and is only done here 
    //to avoid additional code to check if the number
    //being examined has been seen before or not.
    for (i = 1; i < count; i++) {
        //This is our algorithmic condition
        if (set[i] > max)
            max = set[i];
    }
    return max;
}

//These are some test cases with known
//results. So we can check if the algorithm
//truly works or not.

void test_assertions() {
    int64_t test_data [] = {-1, 39, 34, 2, 4, 9248, -909, 1990, 4334};
    
    assert(find_max_inset(test_data, ARRAY_SIZE(test_data)) == 9248);
}

//Use command line args for count of input data.

int main(int argc, char *argv[]) {
    int count = 100;
    int i = 0;
    int64_t *test_data = NULL;
    
    if (argc != 2) {
        printf("Usage %s: <count>\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    
    sscanf(argv[1], "%d", &count);
    
    test_data =  test_random_setup(count);
    test_assertions();
    
    //Print all numbers first in a grid.
    for (i = 0; i < count; i++ ) {
        if (i % 8 == 0)
            printf("\n");
        printf("%10" PRId64"  ", test_data[i]);
    }
    printf("\nLargest number is %" PRId64 "\n",
        find_max_inset(test_data, count));
        
    return EXIT_SUCCESS;
}

Leave a Reply