DEV Community: Hmm

CLRS - Foundations - 2

Hmm — Thu, 20 Oct 2022 16:38:07 +0000

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)));

The only hard point for me is to get bit value from sum of two elements of the arrays, (a[i]+b[i]+carry) %2.

Bye , Gonna eat dinner .

CLRS - Foundations - 1

Hmm — Sun, 16 Oct 2022 02:43:37 +0000

The Roles of Algorithms in computing

Page 5 - 10

What is algorithm ?
- An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.

-Learned about how algorithms is playing a crucial role in development of humanity

The Human Genome Project has made great progress toward the goals of identifying all the 100,000 genes in human DNA, determining the sequences of the 3 billion chemical base pairs that make up human DNA, storing this information in databases, and developing tools for data analysis. Just think about it !
- What is data structure ?
A data structure is a way to store and organize data in order to facilitate access and modifications
- Learned about parallelism
- An brief introduction to NP-complete problems and why are they so interesting
No one knows whether or not efficient algorithms exist for NP-complete problems. Second, the

set of NP-complete problems has the remarkable property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them

Introduction to Algorithms

Hmm — Sat, 15 Oct 2022 08:12:49 +0000

Algorithms - The heart of computer science .

The idea of algorithm fascinates me , It seems like machine between input and output .

I am currently learning Full stack development through The Odin Project ( An open source community of developers ) and in the free time I have decided to learn algorithms . I am not very good in solving algorithmic problems so decided to start reading the book Introduction to Algorithms .

It may takes many years to complete it but I will write summary of every few paragraph/pages and link some exercises that I find helpful to understand the concepts better.

I will try to write the summary as brief as I can and in such way so I/(we ?) can refer these articles in future.

From now every next article related to CLRS will have a tag of CLRS.

Thanks .

Parameter Passing

Hmm — Sat, 18 Jun 2022 00:59:25 +0000

In C++ there are 3 ways to pass parameter to function -

Pass by Value
Pass by Reference
Pass by Pointers

I will discuss one of them here.

Pass by Value

In pass by value , each function have their own local variables and the variables have their own local scope.

#include <iostream>
using namespace std;

void swap( int a , int b){
int temp = a;
a = b; 
b = temp;
cout<< "Values inside swap function , a is "<<a<<" and b is "<<b<<endl;
}

int main(){
int a = 10 ;
int b = 20;
cout<<"Before swapping a is "<<a<<" and b is "<<b<<endl;
swap(a,b);
cout<<"After swapping a is "<<a<<" and b is "<<b<<endl;

return 0;
}

Here if we run this code , we'll find that the values are only swapped in the swap function but when the activation record of swap function is delete when code control comeback to main function , the values of "a" and "b" are unchanged . That's because both "main" and "swap" function have their own "a" and "b" variables.

Pass by value is a good choice when we want to return the result without changing the value of original variables . For example :-

int add(int a, int b){
return a+b;
}

We will learn Pass by Reference next time.