Reverse a linked list every "given num" nodes

#include<stdio.h>
#include<stdlib.h>
struct node
  {
    int val;
    struct node* next;
  };
struct node *current=NULL,*temp=NULL,*prev=NULL,*header1=NULL,*header2=NULL,*header3=NULL;
struct node* head=NULL,*A=NULL,*B=NULL,*C=NULL,*last=NULL;
struct node* createlist(struct node* header);
void print(struct node* header);
main()
 {
int number;
   int x,sum;
   char ch;
   int i=1;
   int flag=1;
   header1=malloc(sizeof(struct node));
   header1->next=NULL;
   printf("\n enter the value to be put in the header node" );
   scanf("%d",&x);
   header1->val=x;
   createlist(header1);
   print(header1);
   printf("\n enter after how many nodes reversal");
   scanf("%d",&number);
   A=B=C=head=header1;
   while(B!=NULL)
   {
       for(i=1;i<=number-1;i++)
       {
         if(A==head)
         {
             A=A->next;
             printf("\n a data %d",A->val);
         }

            B=A->next;
            A->next=head;
            C->next=B;
            head=A;
            A=B;
            if(last!=NULL)
               last->next=head;
       }
       last=C;       C=A;
       if (flag) { header1=head; flag=0;}
       head=A;
   }
   print(header1);
 }
struct node* createlist(struct node* header)
{
    int x;char ch;
     current=header;
   temp=header;
   do
    {
      current=malloc(sizeof(struct node));
      printf("\n enter the value to be put in it \n");
      scanf("%d",&x);
      current->val=x;
      temp->next=current;
      temp=current;
      getchar();
      printf("\n want  MORE \n");
      scanf("%c",&ch);
      printf("\n char entered is %c",ch);
    }while(ch=='y');
  current->next=NULL;
  current=header;
}

void print(struct node* header)
{
current=header;
 while(current!=NULL)
  {
   printf("\n value is %d",current->val);
   current=current->next;
  }
}

Find substring

Write a C program that takes two strings (string a, string b) and gives the first occurrence of string b in string a.

#include<stdio.h>
#include<stdlib.h>
#include<stddef.h>
#include<string.h>
int comparelen(char *st1, char* st2);
void main()
{
    int len1,len2;
    char str1[]="ABCDEFGHIJ";
    char str2[]="HIJK";
    char* ptr=str1;
    int t=1,pos=0;
    printf("\n strings are %s %s",str1,str2);
    getchar();
    len1=strlen(str1);
    len2=strlen(str2);
        printf("\n strings are %d %d",len1,len2);
        getchar();               
        getchar();
        while(pos<=(len1-len2) && (t!=0))
        {
            t=comparelen(ptr,str2);
            printf("\n pos and t %d %d",pos,t);
            if(t==-1)
            {
                ptr++;
                pos=pos+1;
            }
            else if(t==0)
            {
                printf("\n found at pos %d",pos);
                getchar();
            }
        }
        if(t==-1)
        {
            printf("\n not found at all");
            getchar();
        }
}

int comparelen(char *st1, char* st2)
{
    for(int i=0;i<strlen(st2);i++)
    {
        if(st1[i]==st2[i])
        {
            st1++; st2++;
        }
        else
            return -1;
    }
    return 0;
}

Merge sort

Merge sort
This one is also based on divide and conquer strategy just like quick sort.Dividing the array into two subarrays of size n/2. Then recursively solve two subarrays and then combine them using merge.Keep dividing the array recursively in 2 parts till left with subarray of one element.Then call merge to combine two subarrays.Starting with combining two subarrays of size 1, merge compares two to put them in sorted sequence.
Try the following snippet:
#include<stdio.h>
#define MAX_SIZE 10
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right);
void main()
{
 int arr[MAX_SIZE];
 int temp[MAX_SIZE];
 int i,pos;

 for(i=0;i<MAX_SIZE;i++)
 {
  printf("\n enter the element : : %d ",i+1);
  scanf("%d",&arr[i]);
 }
m_sort(arr, temp, 0, MAX_SIZE - 1);

  for(i=0;i<MAX_SIZE;i++)
 {
  printf("\n element %d",arr[i]);
 }
  getchar();
  getchar();

}

void m_sort(int numbers[], int temp[], int left, int right)
{
        int mid;
        if (right > left)
        {
            mid = (right + left) / 2;
            m_sort(numbers, temp, left, mid);
            m_sort(numbers, temp, mid+1, right);
            merge(numbers, temp, left, mid+1, right);
        }
}

void merge(int numbers[], int temp[], int left, int mid, int right)
{
            int i, left_end, num_elements, tmp_pos;
            left_end = mid - 1;
            tmp_pos = left;
            num_elements = right - left + 1;
        while ((left <= left_end) && (mid <= right))
        {
            if (numbers[left] <= numbers[mid])
                {
                        temp[tmp_pos] = numbers[left];
                        tmp_pos = tmp_pos + 1;
                        left = left +1;
                }
                else
                {
                        temp[tmp_pos] = numbers[mid];
                        tmp_pos = tmp_pos + 1;
                        mid = mid + 1;
                }
        }

        while (left <= left_end)
                {
                        temp[tmp_pos] = numbers[left];
                        left = left + 1;
                        tmp_pos = tmp_pos + 1;
                }
        while (mid <= right)
                {
                        temp[tmp_pos] = numbers[mid];
                        mid = mid + 1;
                        tmp_pos = tmp_pos + 1;
                }
                for (i = 0; i <= num_elements; i++)
                {
                    numbers[right] = temp[right];
                        right = right - 1;
                }
        }

Quick Sort

Quick Sort
Worst case = theta (n2)
average case thete(nlogn)
It works on divide and conquer strategy.
Divide an array A[p...r] in A[p....q-1] and A[q+1....r] such that each element in A[p...q-1] is less than A[q] and those in A[q+1...r] are greater than A[q].
Sort the two subarrays recursively.
Pivot element is chosen against which comparisons are made and two regions are maintained which contain elements less than the pivot element and other region contains elements greater than it. At last pivot element is swapped with the element at the position next to region 1.


Try following code snippet:

#include<stdio.h>
#define MAX_SIZE 10
 void Quick_sort(int *a,int p, int r);
  int Partition(int *a,int start,int end);
void main()
{
 int arr[MAX_SIZE];
 int i,pos;

 for(i=0;i<MAX_SIZE;i++)
 {
  printf("\n enter the element : : %d ",i+1);
  scanf("%d",&arr[i]);
 }

 Quick_sort(arr,0,MAX_SIZE-1);
  for(i=0;i<MAX_SIZE;i++)
 {
  printf("\n element %d",arr[i]);
 }
  getchar();
  getchar();

}

void Quick_sort(int *a,int p, int r)
 {
     int index;
     if(p<r)
     {
        index=Partition(a,p,r);
         Quick_sort(a,p,index-1);
         Quick_sort(a,index+1,r);
     }
 }

 int Partition(int *A,int start,int end)
 {
int x=A[end];
int i =start-1;
int temp;
for(int j=start;j<end;j++)
{
  if(A[j]<=x)
     {
  i=i+1;
temp=A[i];
A[i]=A[j];
A[j]=temp;

}
}
temp=A[i+1];
A[i+1]=A[end];
A[end]=temp;
return i+1;
 }

Heap Sort

Heap - It is almost an array object that is almost complete binary tree where it is filled on all levels except possibly the lowest.
Max heap and min heap are the two kind of heaps.
Max-Heap is the one which has the largest element at the root.
A[Parent(i)]>= A[i]

For Heap sort
Max Heapify : Left(i) and Right(i) are max heaps but A[i] may be smaller than its children. This process aims at sinking down a[i] to its appropriate position. Element at root is compared with elements in left and right and is swapped with the larger of two.

Building heap out of the array involves doing Max-heapify from pos=n/2-1 to 0 as all the other nodes in the tree are leaves and hence are one element heap only.Property of max-heap has to be maintained at all the child nodes also, if there are any.

Heapsort works by maintaining a max heap of the array. Thus the largest element is at the root. Swap the root element with the one at A[heapsize]. Thus decreasing the heap size by 1. Now let the element which  reached the root sink to its appropriate position using Max_heapify. Keep repeating till we have two elements in last. The array will go sorted in its position

Try the following snippet :

#include<stdio.h>
#define MAX_SIZE 10
void build_max_heap(int *a,int j);
int heap_size=MAX_SIZE;
void main()
{
 int arr[MAX_SIZE];
 int arr1[MAX_SIZE];
 int i,pos;

 for(i=0;i<heap_size;i++)
 {
  printf("\n enter the element : : %d ",i+1);
  scanf("%d",&arr[i]);
 }

 for(pos=((heap_size/2)-1);pos>=0;pos--)
 {
   build_max_heap(arr,pos);
 }

for(i=0;i<MAX_SIZE;i++)
 {
    printf("\n arr[0] %d",arr[0]);
    arr1[i]=arr[0];
    heap_size=heap_size-1;
    arr[0]=arr[heap_size];
    printf("\n arr1[i] %d arr[0] %d",arr1[i],arr[0]);
    build_max_heap(arr,0);
 }

 for(i=0;i<MAX_SIZE;i++)
 {
  printf("\n element is %d",arr1[i]);
 }
 getchar();
 getchar();

}

void build_max_heap(int *a,int j)
{
 int largest;
 int left,right,temp;
 //int sub=diff;
 largest=j; 
 left=2*(j+1)-1;
 right=2*(j+1);
 printf("\n j %d a[j]%d ",j,a[j]);
 //printf("\n MAX_SIZE-diff %d ",MAX_SIZE-sub);

 if(left < (heap_size))
        printf("\n left %d a[left] %d",left,a[left]);
 if(right < (heap_size))
        printf("right %d a[right] %d",right,a[right]);
 if((left >=(heap_size)) && (right >=(heap_size)))
         return;
 if(left<(heap_size) && a[left]>a[j])
     {
       printf("\n in left ");
       largest=left;
     }
  
 if(right<(heap_size) && a[right]>a[largest])
     {
       printf("\n in right");
       largest=right;
     }
   temp=a[j];
   a[j]=a[largest];
   a[largest]=temp;

   if(j!=largest)
       build_max_heap(a,largest);

 return;
}

Hyperthreading technology

This is a term for Symmetric Multithreading(SMT) on Intel processors. SMT is a strategy which allows several threads to run concurrently by providing multiple physical processors. Actual idea behind is to create a representation of multiple logical processors on the same physical processor to the operating system. Each logical processor has its own architecture state like general purpose and machine state registers, has its own interrupt handling while share the resources like caches and buses of the physical processor.
This is a feature provided in hardware and not software i.e hardware only must provide the handling for interrupts and representation of the architecture state for each logical processor.

A typical SMT architecture

While there is no such need to design operating systems differently for SMT architecture but still performance gains can occur if OS has some knowledge of it. For instance if there is a system with two physical processors each with two logical processor, then if two processes are to be scheduled, then rather than scheduling them on the two logical processors of the same physical processor , it would be a better idea to schedule each on one of the logical processors of the two physical processor . If OS has the knowledge that it is operating on such a system , then it can be of benefit.

Insertion Sort

To explain this method of sorting, I would take the example of playing cards.It's like we have a card in left hand and all other cards lie on the table. We pick one of the cards lying on the table and compare with the one in our hand and place it ahead or behind it. This way what we will get is a sorted list of 2 in our hand. And now if we pick another card from the table and place it in its proper sorted position in the cards in our hand, we will have again a sorted list in our hand which is incrementing one at a time at its position only. So insertion sort is one simple way of sorting.
Like we have numbers given as : 8 3 2 1 5
The first element is assumed to be sorted and serve as the one against which comparison making will be started as explained earlier in the case of playing cards, this would serve as the first card in the left hand.

First Pass :  would scan second element and will put it at its right position, doing comparisons with the element earlier to it.
                                                 3 8 2 1 5

Second Pass : Scans the third element , compare with 2 elements before it and find its place.
                       3 8 2 1 5 = = = =  3 2 8 1 5  = = = =  2 3 8 1 5

Third Pass :    2 3 8 1 5 = = = = 2 3 1 8 5 = = = = 2 1 3 8 5 = = = = 1 2 3 8 5

Fourth Pass : 1 2 3 8 5 = = = = 1 2 3 5 8

The array goes sorted.

Try following cpp code

#define MAX 10
#include<iostream>
using namespace std;
int main()
{
    int arr[MAX];
    int i,j,temp;
    for(i=0;i<MAX;i++)
    {
        cout<<"\n enter the element ["<<i+1<<"]: : ";
        cin>>arr[i];
    }

    for(j=1;j<MAX;j++)
    {
        i=j-1;
        temp=arr[j];
        while(i>=0 && temp<arr[i])
        {
            arr[i+1]=arr[i];
            i--;
           
        }
        arr[i+1]=temp;
    }
            cout<<"\n ********* SORTED ARRAY INSERTION SORT ********* \n \n ";

    for(i=0;i<MAX;i++)
    {
        cout<<"\n element ["<<i+1<<"] is ";
        cout<<arr[i];
    }
getchar();
getchar();

}

to see an output like

Output for code above

For Insertion sort the worst-case running time is θ(n2), and the best-case running time is θ(n).
Insertion sort uses no extra memory, it sorts in place.

Bubble Sort

We gonna talk this time about Bubble Sort. Loops are very famous with sorting algorithms. Finding complexities, run time is another thing that we are supposed to know for these sorting algorithms.
For bubble sort, it goes like we scan a list of say numbers or any items, compare the two adjacent elements and swap the two if they are not in order. We might wish the list to be ascending or descending because.
Assuming ascending order, the first pass through the array will place the largest element at the end of the array. And the array under analysis now will be one element short and the process of placing the largest element at the end of the list under scan goes on till we are left with two element array where no comparison is to be made and the largest element is the only element under analysis.
Lets take an example
 5 3 1 7 2
First pass :      3 5 1 7 2  = = = =  3 1 5 7 2 = = = = 3 1 5 7 2 = = = = 3 15 2 7

Second Pass , 4 elements under scan since 7 is the largest element and has reached the last position
                      1 3 5 2 7 = = = = 1 3 5 2 7 = = = = 1 3 2 5 7

Third Pass :     1 3 2 5 7 = = = = 1 2 3 5 7 ( 3 elements were under scan since 5 has reached its position in second pass)

Fourth pass : 1 2 3 5 7

I have tried it in a C program as

Bubble sort as it appeared on my editor

I have used Visual C++ version 5.0 for compilation . You can try with any that you are comfortable with.
For this code, you might expect an output like following:

Output on doing F5. Press any character after seeing this screen.

The complexity for best or the worst or an average case even will be of order of O(n²) only for bubble sort.
No of comparisons in last pass would be 1 and in the first pass as n-1 , thus summing up the number of comparisons as :


Therefore, bubble sort is not a practical sorting algorithm when n is large.
Try this at your end to make it more clear.
#include<stdio.h>
#define MAX_SIZE 10
void main()
{
 int arr[MAX_SIZE];
 int i,j,k;
 int temp;
 printf("\n enter the array elements");
 for(i=0;i<MAX_SIZE;i++)
  {
      printf("\n enter the %d element :: ",i+1);
   scanf("%d",&arr[i]);
  }
 for(j=0;j<MAX_SIZE-1;j++)
  {
   for(k=0;k<MAX_SIZE-1-j;k++)
    {
         //  printf("\n nidhi k k+1 %d %d arr[k] %d arr[k+1] %d",k,k+1,arr[k],arr[k+1]);

     if(arr[k]>arr[k+1])
     { 
      temp=arr[k];
      arr[k]=arr[k+1];
      arr[k+1]=temp;
     }
    }
  }
 for(i=0;i<MAX_SIZE;i++)
  {
   printf("\n  nidz element[%d ] is : %d ",i+1,arr[i]);
  }
 getchar();
 getchar();

}
 You can ask me more at nidhibatra11@gmail.com also.

Lets Start!

Hi :) This first post on this blog hopefully would introduce me and this blog fairly to you. You can read into my profile to know more about me. And about the blog I will say that I am coming up with it supposing that I will serve some technical ideas, arguments or concepts spiced up with my own way of taking them and experimenting with them. This ought not be that disappointing as it might be sounding at this moment ;) We will keep on swirling through different areas of computer science and technology and the latest developments in it, also through some underlying basics, and through some practical nature of it, and through some theories, and whatever will come across not so silly mind of mine. We can question, answer, suggest, discuss or even argue to find a better answer to the questions. Not lengthening it anymore, I will be ending the first post with a quote which says like "There is great meaning in life for those who are willing to journey."