CLRS - Foundations - 2

#algorithms #programming

Page 11 - 22

Importance of efficient algorithms - assuming that the algorithm to solve the problem takes f(n) microseconds , have a look at the table . Having an algorithms of O(n!) can only solve for maximum input size of 17 if given time of 1 century . Just imagine !

Have a look at the table and you will appreciate the importance of good algorithms.

considering f(n) will take 1 microsecond to execute

Insertion Sort

Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left, as illustrated in At all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table

Here is the example

Here is the code for insertion sort , from what I have understood insertion sort is an inplace algorithm which means it don't need extra space to sort the array.

// C program for insertion sort
#include <math.h>
#include <stdio.h>
/* Function to sort an array
using insertion sort*/
void insertionSort(int arr[], int n)   // n is the size of array
{
    int i, key, j;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        /* Move elements of arr[0..i-1],
        that are greater than key,
        to one position ahead of
        their current position */
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Loop variant and correctness of an algorithm

Initialization: It is true prior to the first iteration of the loop.

Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.

Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Here is one interesting question I have found in the exercise

Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an array of size (n+1) C

Think about it before moving forward

def sumBin(a,b,n):
    c=[None]*(n+1)
    carry=0
    for i in range(n-1,-1,-1):

        c[i+1] = (a[i]+b[i]+carry) %2
        if((a[i]+b[i]+carry) >=2):
            carry = 1
        else:
            carry = 0

    c[0] =carry

    return c


a = [1,1,0,1,1]

b=[1,1,1,1,0]

print(sumBin(a,b,len(a)));