Rizoan Toufiq

Data Structure: Linked List - Part 8

2016-08-18T10:50:00.003-07:00

Circular header linked list হতে একটি node বাদ দেওয়ার পদ্ধতি

সমস্যাঃ একটি node (যার data মান x) header linked list হতে delete (বাদ) দিতে হবে।

সমাধান:প্রথমে আমাকে linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে। ধরি, LOC pointer টি নির্দিষ্ট node কে point করে থাকবে আর LOCP নির্দিষ্ট node এর পূরবর্তী node কে point করে থাকবে। x মান বিশিষ্ট যদি linked list এ না থাকে তাহলে “Not Found” দেখাবে।

কিছু শর্ততে ভাগ করে এখন Deletion পদ্ধতিটি আলোচনা করব।

শর্ত-১ linked list এ কোন node না থাকে, অর্থাৎ head←∧, তখন “Underflow/Empty” দেখাবে।

শর্ত-২ যদি head কে delete করতে হলে অর্থাৎ LOC←head or head↑.INFO = x

তাহলে instruction হবে,

head← head↑.LINK
tail↑.LINK←head

শর্ত-৩ নির্দিষ্ট node (যার data মান x) খুঁজে পাওয়া যায় তাহলে LOC≠head

LOC pointer টি নির্দিষ্ট node কে point করে থাকবে আর LOCP নির্দিষ্ট node এর পূরবর্তী node কে point করে থাকবে। তাহলে instruction হবে,

LOCP↑.LINK ← LOC↑.LINK

যদি LOC tail node কে point করে থাকে তাহলে

tail←LOCP

শর্ত-৪ যদি x মান বিশিষ্ট কোন node পাওয়া না যায় অর্থাৎ LOC=head, তাহলে “Not Found” দেখাবে।
Algorithm:

This algorithm delete a node from a linked list (head pointer) which data field is x.
1. If head = ∧, then: [CASE-I]
                  Write: Empty and exit.
2. if head↑.INFO = x, then: [CASE-II]
              head← head↑.LINK, tail↑.LINK←head and exit.
3. LOC←head↑.LINK and LOCP ← head
4. Repeat step 5 while LOC≠head and LOC↑.INFO≠x
5. LOCP←LOC and LOC←LOC↑.LINK
6. IF LOC≠head then: [CASE-III]
                LOCP↑.LINK←LOC↑.LINK
                If LOC=tail then: tail←LOCP
    ELSE: [CASE-IV]
           Write: Not Found
7. Exit.

Flow Chart:

Program:

#include<stdio.h>
#include<stdlib.h>
struct node{
    int INFO;
    struct node *LINK;
};
int main(){
  struct node *q=NULL,*p=NULL,*head=NULL,*tail=NULL,*LOC=NULL,*LOCP=NULL;
  int i,n=5,x;

  for(i=1;i<=n;i++){
    q = (struct node *)malloc(sizeof(struct node));
    q->LINK = NULL;
    q->INFO = i;

    if(p==NULL)  head = q;
    else
      p->LINK = q;
    p=q;
  }
  p->LINK=head;
  tail=p;

  /*INSERTION (Successor)*/
  printf("Insert the value of target node:");
  scanf("%d",&x);

  q = (struct node *)malloc(sizeof(struct node));
  q->LINK = NULL;
  q->INFO = 10;

  if(head==NULL){
      printf("Empty\n");
  }
  else if (head->INFO==x){
      head = head->LINK;
      tail->LINK=head;
  }
  else{
    LOCP=head;LOC=head->LINK;
    while(LOC->LINK!=head && LOC->INFO!=x){
          LOCP=LOC;
          LOC=LOC->LINK;
    }
    if(LOC!=head){
        LOCP->LINK=LOC->LINK;
        if(LOC==tail) tail=LOCP;
    }
    else
      printf("Not Found\n");

  }

  /*Traverse the CHLL*/
  p=head;
  do{
    printf("%d ",p->INFO);
    p=p->LINK;
  }while(p!=head);

  return 0;
}

Data Structure: Linked List : Part 7

2016-08-18T09:41:00.001-07:00

একটি নতুন node কে Circular header linked list এ সংযুক্ত করার পদ্ধতি

সমস্যাঃ একটি নতুন node linked list এর একটি node (যার data মান x) ও তার পরবর্তি (successor) node এর মাঝে insert (যুক্ত) করতে হবে।

সমাধান:প্রথমে আমাকে linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে। ধরি, LOC pointer টি নির্দিষ্ট node কে point করে আছে। x মান বিশিষ্ট node যদি linked list এ না থাকে তাহলে তা linked list এর শেষে যুক্ত হবে অর্থাৎ LOC pointer শেষ node কে point করে থাকবে।

কিছু শর্ত নিয়ে এখন আলোচনা করব।

শর্ত-১ linked list এ কোন node না থাকে, অর্থাৎ head←∧

q pointer যদি নতুন node কে point করে থাকে তাহলে নতুন node টি head node হবে। তাহলে instruction হবে,

head←q
tail←q
head↑.LINK←q

শর্ত-২ linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে (LOC point করে থাকবে)। যদি node টি tail node না হলে,

q pointer যদি নতুন node কে point করে থাকে তাহলে instruction হবে

q↑.LINK←LOC↑.LINK
LOC↑.LINK←q

শর্ত-৩ linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে (LOC point করে থাকবে)। যদি node টি tail node হলে,

q↑.LINK←head
LOC↑.LINK←q
tail←q

Algorithm

This algorithm insert a new node between the node which data field is x and its successor
1. Call New_Node(q)
2. If head = ∧, then: [CASE-I]
head←q, tail←q, head↑.LINK←q and exit.
3. LOC←head
4. Repeat step 5 while LOC↑.LINK≠head and LOC↑.INFO≠x
5. LOC←LOC↑.LINK
6. q↑.LINK←LOC↑.LINK and LOC↑.LINK←q
7. if LOC=tail then: tail←q;
8. Exit.

FLOW CHART:

Program:

#include<stdio.h>
#include<stdlib.h>
struct node{
    int INFO;
    struct node *LINK;
};
int main(){
  struct node *q=NULL,*p=NULL,*head=NULL,*tail=NULL,*LOC=NULL;
  int i,n=5,x;

  for(i=1;i<=n;i++){
    q = (struct node *)malloc(sizeof(struct node));
    q->LINK = NULL;
    q->INFO = i;

    if(p==NULL)  head = q;
    else
      p->LINK = q;
    p=q;
  }
  p->LINK=head;
  tail=p;

  /*INSERTION (Successor)*/
  printf("Insert the value of target node:");
  scanf("%d",&x);

  q = (struct node *)malloc(sizeof(struct node));
  q->LINK = NULL;
  q->INFO = 10;

  if(head==NULL){
      head=q;
      tail=q;
      head->LINK=q;
  }
  else{
    LOC=head;
    while(LOC->LINK!=head && LOC->INFO!=x){
          LOC=LOC->LINK;
    }
    q->LINK=LOC->LINK;
    LOC->LINK=q;
    if (LOC==tail){
         tail=q;
    }
  }

  /*Traverse the CHLL*/
  p=head;
  do{
    printf("%d ",p->INFO);
    p=p->LINK;
  }while(p!=head);

  return 0;
}

Data Structure: Linked List - Part 6

2016-08-18T06:11:00.001-07:00

একটি নতুন node কে Circular header linked list এ সংযুক্ত করার পদ্ধতি

সমস্যাঃ একটি নতুন node circular linked list এর একটি node (যার data মান x) ও তার পূর্ববর্তী(predecesor) node এর মাঝে insert (যুক্ত) করতে হবে। যদি x মান বিশিষ্ট কোন node পাওয়া না যায় তাহলে নতুন node টি linked list এর শেষে সংযুক্ত করে দিতে হবে।

সমাধান: প্রথমে আমাকে linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে। ধরি, LOC pointer টি নির্দিষ্ট node কে point করে থাকবে আর LOCP নির্দিষ্ট node এর পূরবর্তী node কে point করে থাকবে। x মান বিশিষ্ট যদি linked list এ না থাকে তাহলে তা linked list এর শেষে যুক্ত হবে অর্থাৎ LOCP pointer শেষ node কে point করে থাকবে আর LOC←∧।

কিছু শর্ততে ভাগ করে এখন Insertion পদ্ধতিটি আলোচনা করব।

শর্ত-১ circular linked list এ কোন node না থাকে, অর্থাৎ head←∧

q pointer যদি নতুন node কে point করে থাকে তাহলে নতুন node টি head node হবে। তাহলে instruction হবে,

head←q
tail←q
head↑.LINK←q

শর্ত-২ নতুন node যদি head হিসেবে সংযুক্ত করা লাগে অর্থাৎ LOC←head or head↑.INFO = x

q pointer যদি নতুন node কে point করে থাকে তাহলে instruction হবে,

q↑.LINK ←head
head←q
tail↑.LINK←head

শর্ত-৩ নির্দিষ্ট node (যার data মান x) ও তার পূর্ববর্তী(predecesor) node এর মাঝে insert (যুক্ত) করতে হলে, অর্থাৎ i.e. LOC≠head

q pointer যদি নতুন node কে point করে থাকে তাহলে instruction হবে,

LOCP↑.LINK ←q
q↑.LINK ←LOC

শর্ত-৪ যদি x মান বিশিষ্ট কোন node পাওয়া না যায় অর্থাৎ LOC=head, তাহলে tail node হিসেবে insert হবে।

q pointer যদি নতুন node কে point করে থাকে তাহলে instruction হবে,

tail↑.LINK←q
q↑.LINK←head
tail←q

Algorithm:
This algorithm insert a new node between the node which data field is x and its predecessor

1. Call New_Node(q)
2. If head = ∧, then: [CASE-I]
             head←q, head↑.LINK←q, tail←q, and exit.
3. if head↑.INFO = x, then: [CASE-II]
             q↑.LINK←head, head←q, tail←q and exit.
4. LOC←head↑.LINK and LOCP ← head
5. Repeat step 6 while LOC≠head and LOC↑.INFO≠x
6.    LOCP←LOC and LOC←LOC↑.LINK
7. IF LOC≠head then: [CASE-III]
          LOCP↑.LINK←q and q↑.LINK←LOC
    ELSE: [CASE-IV]
          tail↑.LINK←q, q↑.LINK←head and tail←q.
8. Exit.

FLOW CHART:

Program:

#include<stdio.h>
#include<stdlib.h>
struct node{
    int INFO;
    struct node *LINK;
};
int main(){
  struct node *q=NULL,*p=NULL,*head=NULL,*tail=NULL,*LOC=NULL,*LOCP=NULL;
  int i,n=5,x;

  for(i=1;i<=n;i++){
    q = (struct node *)malloc(sizeof(struct node));
    q->LINK = NULL;
    q->INFO = i;

    if(p==NULL)  head = q;
    else
      p->LINK = q;
    p=q;
  }
  p->LINK=head;
  tail=p;

  /*INSERTION (Predecessor)*/
  printf("Insert the value of target node:");
  scanf("%d",&x);

  q = (struct node *)malloc(sizeof(struct node));
  q->LINK = NULL;
  q->INFO = 10;

  if(head==NULL){
      head=q;
      tail=q;
      head->LINK=q;
  }
  else if(head->INFO ==x){
      q->LINK=head;
      head=q;
      tail->LINK=q;
  }
  else{
    LOC=head->LINK;
    LOCP=head;
    while(LOC!=head && LOC->INFO!=x){
          LOCP=LOC;
          LOC=LOC->LINK;
    }
    if (LOC!=head){
       LOCP->LINK=q;
       q->LINK = LOC;
    }
    else{
      tail->LINK=q;
      q->LINK=head;
      tail=q;
    }
  }

  /*Traverse the CHLL*/
  p=head;
  do{
    printf("%d ",p->INFO);
    p=p->LINK;
  }while(p!=head);

  return 0;
}

Data Structure: Linked List-Part 5

2016-08-18T05:02:00.001-07:00

Circular Header linked list

Header linked list এর শেষ node এর link এ null value থাকে, এখন সেই শেষ node এর link এ প্রথম node এর address থাকলে সেই header linked list কে বলে circular header linked list. একটি tail pointer শেষের node কে point করে থাকবে।

সমস্যাঃ আমরা একটা circular header linked list তৈরি করতে চাই যেখানে ব্যবহারকারি (user) বলে দিবে কতটা Node থাকবে আর তাদের INFO কি কি হবে।

সমাধান: আমরা এর আগে যেভাবে header linked list তৈরি করেছি সেইভাবেই করব, শুধু algorithm শেষ হওয়ার আগে কিছু instruction বেশি লেখব, তা হচ্ছেঃ

p↑.link←head
tail←p

এখানে p pointer টা শেষ node কে point করে আছে।

Algorithm:
This algorithm Create a circular link list where head pointer point the first node of the header linked list.

1. Read n
2. p←∧ and i ← 1
3. Repeat step 4 to 8 while i≤n
4.    New_Node(q);
5.      Read: x;
6.      q↑.INFO←x;
7.      If p=∧ then: head←q
        Else: p↑.LINK←q
8.      p←q;
9. p↑.LINK←head
10. tail←p.
11. Exit

FLOW CHART (Create a Circular Header Linked List):

সমস্যাঃ আমরা এবার circular header linked list traverse করব, আর node এর data print করব।
Algorithm:

This algorithm traverses a circular header link list.
1. p←head
2. Write: p↑.INFO
3. p←p↑.LINK
4. Repeat step 2 and 3 while p≠head
5. Exit

Flow Chart (Traverse A Circular Linked List)

Program:

#include<stdio.h>
#include<stdlib.h>
struct node{
    int INFO;
    struct node *LINK;
};
int main(){
  struct node *q=NULL,*p=NULL,*head=NULL,*tail=NULL;
  int i,n,x;

  printf("Enter Number of Node: ");
  scanf("%d",&n);

  for(i=1;i<=n;i++){
    printf("Enter a value:");
    scanf("%d",&x);

    q = (struct node *)malloc(sizeof(struct node));
    q->LINK = NULL;
    q->INFO = x;

    if(p==NULL){
        head = q;
        printf("Head: %x\n",head);
    }
    else{
      p->LINK = q;
      printf("Current: %x\t INFO:%d Next: %x\n",p,p->INFO,p->LINK);
    }
    p=q;
    printf("Next: %x\t INFO:%d \n",p,p->INFO);
  }
  p->LINK=head;
  tail=p;
  /*Traverse*/
  p=head;
  if(p==NULL) printf("Empty");
  else 
   do{
     printf("%d ",p->INFO);
     p=p->LINK;
   }while(p!=head); 
  return 0;
}

Data Structure: Linked List - Part 4

2016-08-17T11:34:00.001-07:00

Header linked list হতে একটি node বাদ দেওয়ার পদ্ধতি

সমস্যাঃ একটি node (যার data মান x) header linked list হতে delete (বাদ) দিতে হবে।

সমাধান:প্রথমে আমাকে linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে। ধরি, LOC pointer টি নির্দিষ্ট node কে point করে থাকবে আর LOCP নির্দিষ্ট node এর পূরবর্তী node কে point করে থাকবে। x মান বিশিষ্ট যদি linked list এ না থাকে তাহলে “Not Found” দেখাবে। কিছু শর্ততে ভাগ করে এখন Deletion পদ্ধতিটি আলোচনা করব।

শর্ত-১ linked list এ কোন node না থাকে, অর্থাৎ head←∧, তখন “Underflow/Empty” দেখাবে।
শর্ত-২ যদি head কে delete করতে হলে অর্থাৎ LOC←head or head↑.INFO = x

তাহলে instruction হবে,

head← head↑.LINK

শর্ত-৩ নির্দিষ্ট node (যার data মান x) খুঁজে পাওয়া যাবে অর্থাৎ i.e. LOC≠∧

LOCP↑.LINK ← LOC↑.LINK

শর্ত-৪ যদি x মান বিশিষ্ট কোন node পাওয়া না যায় অর্থাৎ LOC=∧, তাহলে “Not Found” দেখাবে।
ALgorithm:

This algorithm delete a node from a linked list (head pointer) which data

field is x.
1. If head = ∧, then: [CASE-I]
            Write: Empty and exit.
2. if head↑.INFO = x, then: [CASE-II]
                head ←head↑.LINK and exit.
3. LOC←head↑.LINK and LOCP ← head
4. Repeat step 5 while LOC≠∧ and LOC↑.INFO≠x
5.                      LOCP←LOC and LOC←LOC↑.LINK
6. If LOC≠∧ then: [CASE-III]
            LOCP↑.LINK←LOC↑.LINK
        Else: [CASE-IV]
         Write: Not Found
7. Exit.

Flow Chart

Program:

#include<stdio.h>
#include<stdlib.h>
struct node{
    int INFO;
    struct node *LINK;
};
int main(){
  struct node *q=NULL,*LOC=NULL,*LOCP=NULL,*head=NULL,*p=NULL;
  int i,n=5,x;
  /*Create A list*/
  for(i=1;i<=n;i++){
    q = (struct node *)malloc(sizeof(struct node));
    q->LINK = NULL;
    q->INFO = i;
    if(p==NULL)
        head = q;
    else
      p->LINK = q;
    p=q;
  }
  /*DELETION*/
  printf("Enter a Value of a node:");
  scanf("%d",&x);
  if(head==NULL){
     printf("Empty\n");
  }
  else if(head->INFO == x)
       head=head->LINK;
  else{
    LOC=head->LINK;LOCP=head;
    while(LOC!=NULL && LOC->INFO!=x){
          LOCP=LOC;
          LOC=LOC->LINK;
    }
    if(LOC!=NULL)
      LOCP->LINK=LOC->LINK;
    else
      printf("Not Found\n");
  }
  /*Traverse*/
  printf("\n\n");
  p=head;
  while(p!=NULL){
   printf("%d ",p->INFO);
   p=p->LINK;
  }

  return 0;
}

Data Structure: Linked List- Part 3

2016-08-17T08:46:00.002-07:00

INSERTION A NEW NODE INTO A HEADER LINKED LIST

সমাধান: প্রথমে আমাকে linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে। ধরি, LOC pointer টি নির্দিষ্ট node কে point করে আছে। x মান বিশিষ্ট node যদি linked list এ না থাকে তাহলে তা linked list এর শেষে যুক্ত হবে অর্থাৎ LOC pointer শেষ node কে point করে থাকবে। কিছু শর্ত নিয়ে এখন আলোচনা করব।

শর্ত-১ linked list এ কোন node না থাকে, অর্থাৎ head←∧

q pointer যদি নতুন node কে point করে থাকে তাহলে নতুন node টি head node হবে। তাহলে instruction হবে,

head←q

শর্ত-২ linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে (LOC point করে থাকবে) অথবা LOC pointer শেষ node কে point করে থাকবে।

q pointer যদি নতুন node কে point করে থাকে তাহলে নতুন node টির link এ LOC point করে থাকা node এর link এর মান চলে আসবে, আর LOC point করে থাকা node এর link এ q চলে আসবে। তাহলে instruction হবে

q↑.LINK←LOC↑.LINK
LOC↑.LINK←q

Algorithm-1.1: This algorithm insert a new node between the node which data field is x and its successor

1. Call New_Node(q)
2. If head = ∧, then: [CASE-I]
head←q and exit.
3. LOC←head 4. Repeat step 5 while LOC↑.LINK≠∧ and LOC↑.INFO≠x
5. LOC←LOC↑.LINK
6. q↑.LINK←LOC↑.LINK and LOC↑.LINK←q
7. Exit.

Flow Chart:

Program:

#include<stdio.h>
#include<stdlib.h>
struct node{
    int INFO;
    struct node *LINK;
};
int main(){
  struct node *q=NULL,*LOC=NULL,*LOCP=NULL,*head=NULL,*p=NULL;
  int i,n=5,x;
  /*Create A list*/
  for(i=1;i<=n;i++){
    q = (struct node *)malloc(sizeof(struct node));
    q->LINK = NULL;
    q->INFO = i;
    if(p==NULL)
        head = q;
    else
      p->LINK = q;
    p=q;
  }

  /*INSERTION*/
  printf("Enter a Value of a node:");
  scanf("%d",&x);

  q = (struct node *)malloc(sizeof(struct node));
  q->LINK = NULL;
  q->INFO = 10; /*Manual Value*/


  if(head==NULL){
     head = q;
  }
  else{
    LOC=head;
    while(LOC->LINK!=NULL && LOC->INFO!=x){
          LOC=LOC->LINK;
    }
    q->LINK=LOC->LINK;
    LOC->LINK=q;
  }

  /*Traverse*/
  printf("\n\n");
  p=head;
  while(p!=NULL){
   printf("%d ",p->INFO);
   p=p->LINK;
  }

  return 0;
}

Data Structure: Linked List- Part 2

2016-08-16T14:23:00.002-07:00

INSERT A NEW NODE INTO A HEADER LINKED LIST

Problem-I: Insert a new node between a node which data field is x and its predecessor. If x is not found in header linked list then, the new node insert at the end of the list.

Solution: The first objective is to find the location of the node which data field is x. Let LOC be the pointer to point the target node and LOCP be the pointer that point the predecessor of the target node. If there is not exist any node which data field is x, then we set LOC←NULL and LOCP point to the last node of the linked list . If the target node is header node then we set LOCP←NULL and LOC←head.

CASE-I: Insert Node, if there is no node in header linked list i.e. head←∧

q is a pointer that point to a new node. The instruction to insert new node as header node will be

head←q

CASE-II: Insert Node as Header node i.e. head↑.INFO = x

q is a pointer that point to a new node. The instruction to insert new node as header node will be

q↑.LINK ←LOC

head←q

CASE-III: Insert Node between the target node and its predecessor i.e. LOC≠∧

q is a pointer that point to a new node. The instruction to insert new node as header node will be

LOCP↑.LINK ←q
q↑.LINK ←LOC

CASE IV: Insert node at the end of the list i.e. LOC=∧

q is a pointer that point to a new node. The instruction to insert new node as header node will be

LOCP↑.LINK←q

ALGORITHM:

Algorithm-1.1: This algorithm insert a new node between

the node which data field is x and its predecessor
1. Call New_Node(q)
2. If head = ∧, then: [CASE-I]
            head←q, head↑.INFO←y and exit.
3. If head↑.INFO = x, then: [CASE-II]
            q↑.LINK←head, head←q, and exit.
4. LOC←head↑.LINK and LOCP ← head
5. Repeat step 6 while LOC≠∧ and LOC↑.INFO≠x
6.                      LOCP←LOC and LOC←LOC↑.LINK
7. IF LOC≠∧ then: [CASE-III]
            LOCP↑.LINK←q and q↑.LINK←LOC
        ELSE: [CASE-IV]
             LOCP↑.LINK←q
8. Exit.

FLOW CHART:

Program:

#include<stdio.h>
#include<stdlib.h>
struct node{
    int INFO;
    struct node *LINK;
};
int main(){
  struct node *q=NULL,*LOC=NULL,*LOCP=NULL,*head=NULL,*p=NULL;
  int i,n=5,x;
  /*Create A list*/
  for(i=1;i<=n;i++){
    q = (struct node *)malloc(sizeof(struct node));
    q->LINK = NULL;
    q->INFO = i;
    if(p==NULL)
        head = q;
    else
      p->LINK = q;
    p=q;
  }

  /*INSERTION*/
  printf("Enter a Value of a node:");
  scanf("%d",&x);

  q = (struct node *)malloc(sizeof(struct node));
  q->LINK = NULL;
  q->INFO = 10; /*Manual Value*/


  if(head==NULL){
     head = q;
  }
  else if(head->INFO==x){
      q->LINK=head;
      head=q;
  }
  else{
    LOC=head->LINK;
    LOCP=head;
    while(LOC!=NULL && LOC->INFO!=x){
          LOCP=LOC;
          LOC=LOC->LINK;
    }
    if (LOC!=NULL){
       LOCP->LINK=q;
       q->LINK = LOC;
    }
    else
      LOCP->LINK = q;
  }

  /*Traverse*/
  printf("\n\n");
  p=head;
  while(p!=NULL){
   printf("%d ",p->INFO);
   p=p->LINK;
  }

  return 0;
}

Data Structure: Linked List - Part 1

2016-08-15T12:02:00.002-07:00

Basic

Data Structure এর সবচেয়ে গুরুত্বপূর্ন বিষয় হচ্ছে linked list. এটা C প্রোগ্রাম শেখার পর নতুন একটা অধ্যায়। এটা খুব ভালোভাবে রপ্ত করতে পারা, প্রথামিক অবস্থায় সামান্য কঠিন আছে। যেহেতু আমাদের C প্রোগ্রামের structure সম্পর্কে ধারনা আছে তাই, একটা Node কি তা structure দিয়ে বললে অনেকের কাছে সহজ হবে। আমরা parallel কিছু array দিয়েও Linked list ব্যাখা করতে পারি, তবে তা পরে আলোচনা করা যাবে। C তে integer type variable কে point করার জন্য ওই ধরনের একটা pointer লাগে। একইভাবে structure type variable কে point করার জন্য ওই ধরনের একটা pointer লাগবে।

এবার তুমি প্রোগ্রাম টা আরো পরিবর্তন করে, তোমার structure এবং pointer সম্পর্কে ধারনা পরিষ্কার করে নিতে পারো। কোডে যদি নিচের মত করে পরিবর্তন করা হয় তাহলে কি হবে তা তোমরা নিজেরা দেখবে।)

এবার আরো এক ধাপ এগিয়ে যায়। এবার আমরা structure এর মাঝেই একই structure type pointer declare করব। এটা করব কেন? এটা করার কারন হচ্ছে আমরা চাচ্ছি structure এর ভেতরের pointer টা দিয়ে অন্য একটা একই ধরনে structure type variable কে point করতে। এই ধরনের pointer কে বলে self reference pointer.

উপরের উদাহরণে struct node type একটা variable a যার LINK pointer struct node type একটা variable b কে point করে আছে। আর b এর LINK pointer কাউকেই point করে নাই। অর্থাৎ আমরা একটা ছোট linked list তৈরি করে ফেলেছি। এবার একটা নতুন term নিয়ে আসি। সেটা হচ্ছে header linked list, যার প্রথম node-টি নাম হচ্ছে header. আর একটা head নামের struct node type এর pointer, point করে থাকবে প্রথম node কে অর্থাৎ a node কে।

এখানে linked list বলতে head pointer কেই বোঝাবে। head pointer এর মান হারিয়ে ফেললেই linked list ধবংস হয়ে যাবে। এই ছোট linked list কে traverse করতে চাইলে আমরা head pointer কখনই সামনের node নিয়ে যাব না। তাই traverse/visit করার জন্য আমরা আরো একটা struct node type এর pointer v নিবো যা প্রথম node কে point করবে, তারপর ওই node এর INFO কে process করে, সামনের node কে point করবে। ধরি, v:=head, তাহলে সামনের node কে point করতে চাইলে আমাকে instruction দিতে হবেঃ v:=v↑.LINK. তাহলে এখন v pointer head এর পরের node কে point করে আছে। তাহলে v কতক্ষণ পর্যন্ত next node এ যেতে থাকবে? উত্তর হচ্ছে, v এর মান NULL না হওয়া পর্যন্ত, কারন শেষ node টি NULL কে point করে আছে। তাহলে এই পর্যায়ে traverse/visit এর algorithm হবেঃ

এই algorithm এর flow chart হবেঃ

Fig. Traverse a header linked list

নিচে code সহ ব্যাখা তুলে ধরা হলঃ

এবার আসি, নতুন একটি node নিতে হলে কি করতে হবে? আমাদেরকে memory allocate করতে হবে। এই memory আমরা system হতে নিব। যদি memory না থাকে তাহলে আমরা memory allocate করতে পারব না। ধরি, আমাদের কাছে যে memory আছে সেগুলো নিয়ে একটা linked list তৈরি করা আছে, যার প্রথম node টি struct node type AV ponter variable দ্বারা point করা আছে।

এখানে AV:=NULL হলে আমরা নতুন node এর জন্য memory আর অবশিষ্ট নেই। আর যদি NULL না হয় তাহলে নিচের চিত্রের মত করে একটা নতুন node নিতে পারব।

নতুন node allocate করার algorithm হবেঃ

নতুন node allocate করার flow chart হবেঃ

আমরা C program এ malloc function এর মাধ্যমে memory allocation করে থাকি, নিচে code এর মাধ্যমে দেখানো হল।

Header Linked List তৈরি করা (Create A Header Linked List)

এবার একটা সমস্যা উল্লেখ করব, তার জন্য algorithm তৈরি করব, তারপর flow chart আঁকব, এবং সর্বশেষে code এর মাধ্যমে implement করব।

সমস্যাঃ আমরা একটা header linked list তৈরি করতে চাই যেখানে ব্যবহারকারি (user) বলে দিবে কতটা Node থাকবে আর তাদের INFO কি কি হবে। Algorithm:

Flow Chart:

CODE IN C:

সমস্যাঃ একটা মান x বিশিষ্ট node, header linked list হতে খুঁজে বের করতে চাই।
Algorithm:

Flow Chart:

Code:

LightOJ 1098 - A New Function

2015-12-03T02:41:00.002-08:00

Problems: LightOJ 1098 - A New Function
Explain:
The function SOD(n) (sum of divisors) is defined as the summation of all the actual divisors of an integer number n.The function CSOD(n) (cumulative SOD) of an integer n, is defined as below:

Let P = 1 - 25

Total: 173

Given Number P = 25, i = 2 , j= P/i = 12
From above calculation, we can find out two relations
First Relation
2+3+4+5+6+7+8+9+10+11+12
= 1+2+3+4+5+6+7+8+9+10+11+12-1
= j*(j+1)/2 - (i-1)*(i-1+1)/2
= j*(j+1)/2 - (i-1)*(i)/2
= (j^2+j - i^2 + i)/2
= ((j-i)(j+i)+(j+i))/2
= ((j+i)(j-i+1))/2 (General Form)
= (14 * 11 )/2 = 77

Second Relation
2x10 = i*(j-i) (General Form)
     = 20

Again
i = 3 , j = P/i = 8

First Relation
3+4+5+6+7+8
= (1+2+3+4+5+6+7+8) - (1+2)
= (j*(j+1)/2 - (i-1)*(i-1+1)/2
= ((j+i)(j-i+1))/2 (General Form)
= (11 * 6 )/2 = 33

Second Relation
3x5 = i*(j-i)
    = 15

Again
i = 4 , j = P/i = 6

First Relation
4+5+6
= (1+2+3+4+5+6) - (1+2+3)
= (j*(j+1)/2 - (i-1)*(i-1+1)/2
= ((j+i)(j-i+1))/2 (General Form)
= (10 * 3 )/2 = 15

Second Relation
4x2 = i*(j-i)
    = 8

Again
i = 5 , j = P/i = 5

First Relation
5
= (1+2+3+4+5) - (1+2+3+4)
= (j*(j+1)/2 - (i-1)*(i-1+1)/2
= ((j+i)(j-i+1))/2 (General Form)
= (10 * 1 )/2 = 5

Second Relation
5x0 = i*(j-i)
    = 0

SUM = 77+20+33+15+15+8+5+0 = 173

Code:
-------

#include <stdio.h>
typedef long long LL;

void solve() {
  LL n,ans = 0;
  LL i,j;

  scanf("%lld",&n);
  for (i = 2; i * i <= n; ++i) {
    j = n / i;
    ans += (i + j) * (j - i + 1) / 2;
    ans += i * (j - i);
  }
  printf("%lld\n", ans);
}

int main() {
  int tc;
  scanf("%d",&tc);
  for (int i = 0; i < tc; ++i) {
    printf("Case %d: ", i + 1);
    solve();
  }
  return 0;
}

Number System - Covert a Decimal Number to Octal and Hex Number

2015-10-23T01:59:00.003-07:00

It is very interesting topic. If we simple think, the process of conversion from decimal number to Octal number, then we can follow the below steps:
1. Let x = 15
2. r[0] = x%8 = 7
3. x = x/8 = 1
4. r[1] = x%8 = 1;
5. x = x/8 = 0
Terminate the algorithm, we find (15)10 = (17)8 [Note: reverse r]
But if we use bit-wise operator, then it makes more interesting and efficient.

1. Let x = 15 = 1111
2. r[0] = last three bits = x&7 = 7
Explain:
1111
0111
-------
0111 (AND)

3. x = right shift by 3 = x>>3
x = (1)

4. r[1] = x&7 = 1
5. x = x>>3 = 0Terminate the algorithm, we find (15)10 = (17)8 [Note: reverse r]

Code:

#include<stdio.h>

int main(){
  int x=0,tx;
  char rx[12];
  int cb=0,i;
  printf("Enter a Number: ");
  scanf("%d",&x);

  tx = x;
  while(tx){
      rx[++cb] = (tx&7);
      tx = tx>>3;
  }

  printf("Result:");
  for (i=cb;i;--i)
       printf("%d",rx[i]);

  return 0;
}

Similarly we can convert a decimal number into Hexadecimal number.
1. Let x = 17
2. r[0] = last four bits = x&15 =1
Explain:
10001
01111
-------
00001 (AND)

3. x = right shift by 4 = x>>4
x = (1)

4. r[1] = x&15 = 1
5. x = x>>4 = 0

Terminate the algorithm, we find (17)10 = (11)16 [Note: reverse r]

code:

#include<stdio.h>

int main(){
  int x=0,tx;
  char rx[12];
  int cb=0,i;
  printf("Enter a Number: ");
  scanf("%d",&x);

  tx = x;
  while(tx){
      rx[++cb] = tx&15;
      tx = tx>>4;
  }

  printf("Result:");
  for (i=cb;i;--i){
      if (rx[i]<9)
        printf("%d",rx[i]);
      else
        printf("%c",rx[i]+'A'-10);
  }
  return 0;
}

Analysis:if r[i] =10
rx[i] +'A' -10 = 'A'

Number Conversion -1 : Decimal to Binary

2015-10-21T10:50:00.002-07:00

At first glance, we think about the below algorithm
1. take input x
2. r[i] = x%2;
3. x = x/2
4. do above steps until x =0

the complexity of this algorithm is O(lgn) , where n = decimal number.

Code

#include<cstdio>
using namespace std;

int main(){
  int x,i;
  bool r[32]={0}; // think about 32 bits number

  printf("Enter a decimal Number: ");
  scanf("%d",&x);
  i = 0;
  while(x){
     r[++i] = x%2;
     x =x/2;
  }

  printf("Result: ");
  while(i){
     printf("%d",r[i--]);
  }

  return 0;
}

Now, we can replace the % and / sign by bitwise operator. How?
x = 1011
Objective: take last one bit into r[i]
x = 1011
0001
-------------
AND 1 --- > r[i]
x = 1011
just make a right shift, we get
x = (101)

code

#include<cstdio>
using namespace std;

int main(){
  int x,i;
  bool r[32]={0}; // think about 32 bits number

  printf("Enter a decimal Number: ");
  scanf("%d",&x);
  i = 0;
  while(x){
     r[++i] = x&1;
     x =x>>1;
  }

  printf("Result: ");
  while(i){
     printf("%d",r[i--]);
  }

  return 0;
}

Although the complexity of this algorithm is O(lgn).

Would we reduce this complexity into O(1)!!!!!! Yes. We can reverse the bits of a number in O(1) if we know the size of the number. We can implement it using look up table.

Code:

#include<stdio.h>

int main(){
  int x=0,tx,c,flag;

  printf("Enter a number : ");
  scanf("%d",&x);

  x = ((x&0xAAAAAAAA) >> 1)| ((x& 0x55555555)<<1);
  x = ((x&0xCCCCCCCC) >> 2)| ((x& 0x33333333)<<2);
  x = ((x&0xF0F0F0F0) >> 4) | ((x& 0x0F0F0F0F)<<4);
  x = ((x&0xFF00FF00) >> 8) | ((x& 0x00FF00FF)<<8);
  x = x >> 16 | x<< 16;

  printf("Result: ");
  tx = x;
  c = 32;
  flag = 1;
  while(c--){
     if (flag ==0) {
        if (tx&1) printf("1");
        else printf("0");
     }
     else{
         if (tx&1){
             flag = 0;
             printf("1");
         }
     }
     tx = tx>>1;
  }

  return 0;
}

Now your task is to use paper and pencil to analysis this code.

UVa 107－The Cat in the Hat

2015-10-20T14:57:00.000-07:00

Problem: 107 - The Cat in the Hat

Explain:
Given, Initial Height of a Cat, IH
The number of worker Cats of height 1, WC1

Objective:
Find, sum of all the cats' heights, SCH =?
Number of Not Working Cat, NWC =?

To understand this problem, Let IH = 216, WC1 = 125

“The smallest Cats are of height one;
These are the cats that get the work done;” [Copied from Uva 107]

If, IH = 1 and WC1 = 1,
This Indicate, TC = 1, NWC = 0
This also indicates the termination condition.
“The number of cats inside each (non-smallest) cat's hat is a constant, N. The height of these cats-in-a-hat is 1/(N+1) times the height of the cat whose hat they are in.” [Copied from Uva 107]
Let Constant N = 5,

Not Working Cat ,NWC	Height of Each Cat, Given, IH = 216	sum of all the cats' heights, SCH
		∑_height = 216
1	The number of cats inside each (non-smallest) cat's (height = 216) hat is 5, Height = (216/(5+1) = 36	∑_height = (216/6)*5 + 216=396
1+5	The number of cats inside each (non-smallest) cat's (height = 36) hat is 5, Height = 36/6 = 6	∑_height = (216/6²)*5² + 396 = 546
1+5+5² = 31	The number of cats inside each (non-smallest) cat's (height = 36) hat is 5, Height = 36/6 = 1	∑_height = (216/6³)*5³ + 546 =671
	Break…..

Challenge:
Find N , i.e.
N^m = WC1 and
(N+1)^m = IH

Code:
======

#include<iostream>
#include<cstdio>
#include<cmath>
#define ERROR 1e-8
using namespace std;

int main(){
  int H, num, m, N;
   #ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
   #endif


  while( scanf( "%d%d", &H, &num ) != EOF && !(H == 0 && num == 0)){
    if( H == 1 && num == 1 ){
      printf( "0 1\n");
      continue;
    }

    m = 1;
    while( H != (int)(pow(pow(num,1.0/m)+1.0, m)+ERROR) ) m++;
    N = (int)(pow(num,1.0/m)+ERROR);
    if( N != 1 ) printf( "%d %d\n", (1-num)/(1-N), (H-num)*N+H );
    else printf( "%d %d\n", m, (H-num)*N+H );
  }
  return 0;
}

Uva 113 - Power of Cryptography

2015-10-19T14:19:00.001-07:00

Problem: 113 - Power of Cryptography

Explain:

Now just use pow() function.

Code:

#include<stdio.h>
#include<math.h>

int main(){
    double n,p;
    while (scanf("%lf%lf", &n, &p) == 2)
        printf("%.0lf\n", pow(p, 1 / n));
    return 0;
}

Uva 112 - Tree Summing

2015-10-19T13:44:00.001-07:00

Problem: 112 - Tree Summing

Explain:
1. Parse Tree *
2. Binary Tree Traversal Algorithm (Recursive algorithm)

Code:

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

enum Token {
  LEFT_BRACKET, RIGHT_BRACKET,
  NUMBER
};

enum Tree {
  NULLNODE, NODE
};

Token getToken(int &token){
  int c = getchar();
  while( c == ' ' || c == '\n' ){
    c = getchar();
  }

  if( c == '(' ) return LEFT_BRACKET;
  if( c == ')' ) return RIGHT_BRACKET;

  int sign = 1;
  if( c == '-' ){
    sign = -1;
    c = getchar();
  }

  token = 0;
  while( isdigit(c) ){
    token = token * 10 + (c - '0');
    c = getchar();
  }

  token *= sign;
  ungetc(c, stdin);/*pushes the char into stdin. now char is available in stdin.*/

  return NUMBER;
}

Tree parseTree(bool &isMatched, int rootSum, int target){
  int token;

  getToken(token); // '('

  if( getToken(token) == RIGHT_BRACKET ){
    return NULLNODE;
  }

  rootSum += token;
  Tree leftSubTree = parseTree( isMatched, rootSum, target );
  Tree rightSubTree = parseTree( isMatched, rootSum, target );

  getToken(token);

  if (isMatched) return NODE;

  if( leftSubTree == NULLNODE && rightSubTree == NULLNODE ){
    if( rootSum == target ){
      isMatched = true;
    }
  }

  return NODE;

}

int main(){
  int target,c;
  //freopen("sample.txt","r",stdin);
  while( scanf("%d", &target) != EOF ){
    bool isMatched = false;
    parseTree(isMatched, 0, target);
    if( isMatched ){
      printf("yes\n");
    }
    else {
      printf("no\n");
    }
  }
  return 0;
}

Longest Common Sub-Sequence

2015-10-19T10:15:00.001-07:00

The longest common subsequence (LCS) problem is very popular in computer science. This problem can be solved by dynamic algorithm. We can define this problem to find the longest subsequence common to all sequences in a set of sequences (often just two sequences).

Let A = {1,3,4,6,8}
B = {7, 3,2,4,6,10,8}

LCS (A,B) = {3,4,6,8} , Length = 4;

Application:

bioinformatics
revision control systems (the management of changes to documents, computer programs, large web sites, and other collections of information)

How can we solve this problem?
if we have two sequence of length n and m, the time complexity of the dynamic Program approach is O(nm).

Here, A = {4,7,6,5,9}
B = {2,3,4,6,5,9}
2 not belongs to A
3 also not belongs to A
4 belong to A 0+1 = 1
4!=7 = > max (0,1) = 1,
.
.
.
finally we get length of LCS i.e. 4

we can print it as following:

#include<stdio.h>
#define max 100
#define MAX(a,b) a<b?b:a
int c[max][max];//table
int R[max],r=0;//R=result,r=lenth

void LCS(int *X,int *Y,int Lx,int Ly){
    int i,j;
 for(i=0;i<Lx;i++)
  c[i][0]=0;
 for(j=0;j<Ly;j++){
  c[0][j]=0;
  printf("%d\t",c[0][j]);
 }
    printf("\n");
    for(i=1;i<Lx;i++){
        printf("%d\t",c[i][0]);
        for(j=1;j<Ly;j++){
     if(X[i]==Y[j]){
      c[i][j] = c[i-1][j-1]+1;
      printf("%d\t",c[i][j]);
     }
     else{
      c[i][j]= MAX(c[i][j-1],c[i-1][j]);
      printf("%d\t",c[i][j]);
     }
  }
  printf("\n");
 }
}

int printLCS(int *X,int *Y,int i,int j){
   if(i==0||j==0)
    return 0;
   else if(X[i]==Y[j]){
    int m= printLCS(X,Y,i-1,j-1);
    printf("%d ",X[i]);
    R[r]=X[i];
    r++;
    return m;
   }
   else{
     if(c[i][j-1]>c[i-1][j])
   return printLCS(X,Y,i,j-1);
  else
   return printLCS(X,Y,i-1,j);
   }
   return 0;
}

int main(){
 int X[]={0,2,3,4,6,5,9};
 int Y[] = {0,4,7,6,5,9};
    /*freopen("LCSout.txt","w",stdout);*/

 LCS(X,Y,7,6);

    printf("\nPrint LCS: ");
 printLCS(X,Y,7,6);

 printf("\n\nResult: \n");
 printf("\tLenth: %d\n\t",r);
 for(int i=0;i<r;i++)
  printf("%d ",R[i]);
    printf("\n");
    return 0;
}

Uva 111 - History Grading

2015-10-19T09:17:00.000-07:00

Problem: Uva 111 History Grading

Explain: LCS Problem , Complexity O(n^2)

code:

#include<stdio.h>
#define max 25
#define MAX(a,b) a<b?b:a

int main(){
 freopen("a.in","r",stdin);
 int c[max][max]={0};/*table*/
 int X[max];
 int Y[max];
 int n,m,i,j,a;

 scanf("%d\n",&n);
    for(i=1;i<=n;i++){
     scanf("%d",&m);
        X[m]=i;
 }
 while(1){
     a= scanf("%d",&m);
     if (a!=1) break;
     Y[m] = 1;
  for(i=2;i<=n;i++){
     scanf("%d",&m);
     Y[m]=i;
  }
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      if(X[i]==Y[j])
      c[i][j] = c[i-1][j-1]+1;
      else
     c[i][j]= MAX(c[i][j-1],c[i-1][j]);
    }
     }
  printf("%d\n",c[n][n]);
 }
 return 0;
}

Linear Congruences

2015-10-12T15:31:00.003-07:00

A congruence of the

where m is a positive integer, a and b are integer and x is a variable, is called a linear congruence.

কেমন করে এটার সমাধান করব? অর্থাৎ কেমন করে আমরা x এর মান বের করব?
একটা equation হচ্ছে,

Uva 497 - Strategic Defense Initiative

2015-10-11T10:26:00.002-07:00

Problem: 497 - Strategic Defense Initiative
Description: Longest Increasing Subsequence

Code:

/*
Algorithm: Longest Increasing Seq.
Complexity: nlgn
*/
#include<stdio.h>
#include<limits.h>
#include<string.h>
#include<stdlib.h>
#define S 100000

int R[S]={0};/*Generated Table*/
int A[S] = {0};/*Input data*/
int Indx[S]= {0}; /*Index of the Table Element*/
int Pre[S]={0}; /*Previous Element*/

void Print(int i){
    if ( i == 0) return;
    else {
        Print(Pre[i]);
        printf("%d\n",A[i]);
    }
    return;
}
/*Complexity lg2^N*/
int BS(int v,int s,int e){
    int mid=0;
    while(s<=e){
         mid = s+((e-s)/2);
         if (v<=R[mid]){
              if(R[mid-1]<v) break;
              e = mid-1;
         }
         else if (v>R[mid]){
            if(R[mid+1]>=v){mid= mid+1;break;}
            s = mid+1;
         }
    }
    return mid;
}

int main(){
    int i,v=0;
    int rc;
    int s,e,mid;/*Binary Search*/
    int N,C=0;
    char ch[10];

    /*freopen("LIS.in","r",stdin);*/

    A[0]=R[0] = INT_MIN;
    Indx[0] = 0;

    scanf("%d",&N);
    getchar();
    gets (ch);
    while(1){
       rc=1;
       i=1;
       while(gets(ch) && strlen(ch)){
           A[i] = atoi(ch);
           v = A[i];
           if(v>R[rc-1]){
              R[rc] = v;
              Indx[rc] = i;
              Pre[i] = Indx[rc-1];
              rc++;
           }
           else if(v<R[rc-1]){/*Binary Search*/
              mid = BS(v,1,rc-1);
              R[mid] = v;
              Indx[mid]= i;
              Pre[i] = Indx[mid-1];
            }
            i++;
        }
        printf("Max hits: %d\n",rc-1);
        i = Indx[rc-1];
        Print(i);
        C++;
        if(C==N) break;
        printf("\n");

        for(i=1;i<=N;i++) Pre[i]=0,Indx[i]=0,R[i]=0;
    }
    return 0;
}

Uva - 231 - Testing the CATCHER

2015-10-11T09:12:00.001-07:00

Problem: 231 - Testing the CATCHER

Explain: Longest Decreasing Subsequence

Code:
-------

/*
Algorithm: Longest Decreasing Seq.
Complexity: nlgn
*/
#include<stdio.h>
#include<limits.h>
#define S 1000000

int R[S]={0};/*Generated Table*/
int A[S] = {0};/*Input data*/
int Indx[S]= {0}; /*Index of the Table Element*/
int Pre[S]={0}; /*Previous Element*/

/*Complexity lg2^N*/
int BS(int v,int s,int e){
    int mid=0;
    while(s<=e){
         mid = s+((e-s)/2);
         /*Remove small*/
         if (R[mid]<=v){
              if (v<R[mid-1]|| v == R[mid-1])break;
              e = mid-1;
         }
         else if (v<R[mid]){
            if(R[mid+1]<v){mid=mid+1;break;}
            s = mid+1;
         }
    }
    return mid;
}


int main(){
    int i,v=0,j;
    int rc;
    int s,e,mid;/*Binary Search*/
    int N=1,flag;

    /*freopen("a.txt","r",stdin);*/

    A[0]=R[0] = INT_MAX;
    Indx[0] = 0;
    flag = 0;
    while(1){
       rc=1;
       for(i=1;;i++){
           scanf("%d",&A[i]);
           if ( A[i] == -1){ if ( i == 1) flag = 1; break;}
           v = A[i];
           if(v<=R[rc-1]){
              R[rc] = v;
              Indx[rc] = i;
              Pre[i] = Indx[rc-1];
              rc++;
           }
           else if(v>R[rc-1]){/*Binary Search*/
              mid = BS(v,1,rc-1);
              R[mid] = v;
              Indx[mid]= i;
              Pre[i] = Indx[mid-1];
            }
        }
        if(flag==1) break;
        if (N >1) printf("\n");
        printf("Test #%d:\n  maximum possible interceptions: %d\n",N++,rc-1);
        for(i=1;i<=N;i++) Pre[i]=0,Indx[i]=0,R[i]=0;
    }
    return 0;
}

Uva 481 - What Goes Up

2015-10-09T12:38:00.000-07:00

Problem : 481 - What Goes Up

Description:
Find out the Longest Increasing Sequences. Complexity: O(nlgn)

Gievn

-7 : -i -7

10: -i -7 10

9 : -i -7 9

2: -i -7 2

3: -i -7 2 3

8: -i -7 2 3 8

8: -i -7 2 3 8

1: -i -7 1 3 8

Length: 4

and Seq: -7 2 3 8

#include<stdio.h>
#include<limits.h>
#define S 100000

int R[S]={0};/*Generated Table*/
int A[S] = {0};/*Input data*/
int Indx[S]= {0}; /*Index of the Table Element*/
int Pre[S]={0}; /*Previous Element*/

void Print(int i){
    if ( i == 0) return;
    else {
        Print(Pre[i]);
        printf("%d\n",A[i]);
    }
    return;
}
/*Complexity lg2^N*/
int BS(int v,int s,int e){
    int mid=0;
    while(s<=e){
         mid = s+((e-s)/2);
         if (v<=R[mid]){
              if(R[mid-1]<v) break;
              e = mid-1;
         }
         else if (v>R[mid]){
            if(R[mid+1]>=v){mid= mid+1;break;}
            s = mid+1;
         }
    }
    return mid;
}

int main(){
    int i,v=0;
    int rc;
    int s,e,mid;/*Binary Search*/

    /*freopen("481.in","r",stdin);*/

    A[0]=R[0] = INT_MIN;
    Indx[0] = 0;
    i=1,rc=1;

    while(scanf("%d", &A[i]) == 1){
       v = A[i];
       if(v>R[rc-1]){
           R[rc] = v;
           Indx[rc] = i;
           Pre[i] = Indx[rc-1];
           rc++;
       }
       else if(v<R[rc-1]){/*Binary Search*/
           mid = BS(v,1,rc-1);
           R[mid] = v;
           Indx[mid]= i;
           Pre[i] = Indx[mid-1];
        }
        i++;
    }

    printf("%d\n-\n",rc-1);
    i = Indx[rc-1];
    Print(i);
    return 0;
}

Longest Decreasing Subsequence

2015-10-09T12:26:00.003-07:00

Read : Longest Increasing Subsequence
Dynamic Programming:

Let Given,
A = { 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 }
0 :   0
Indx: [1]
Pre: [0] /*Note: Parent = NULL , so it is a root node*/

8 :    8
Indx: [2]
Pre: [0]

4 :    8   4
Indx: [2] [3]
Pre: .....[2]

12 : 12 4
Indx: [4] [3]
Pre:..[0]

2 :    12 4 2
Indx: [4] [3] [5]
Pre: ...........[3]

10 : 12 10 2
Indx: [4] [6] [5]
Pre: .... [4]

6 :   12 10 6
Indx: [4] [6] [7]
Pre: ............[6]

14 : 14 10 6
Indx: [8] [6] [7]
Pre:..[0]

1 : 14 10 6 1
9 : 14 10 9 1
5 : 14 10 9 5
13 : 14 13 9 5
3 : 14 13 9 5 3
11 : 14 13 11 5 3
7 : 14 13 11 7 3
15 : 15 13 11 7 3

Length: 5
Seq: 12 10 9 5 3

Another Example:
1 :   1
Indx: [1]
Pre: [0]

6 :   6
Indx: [2]
Pre: [0]

2 : 6 2
Indx: [2] [3]
Pre: ..... [2]

3 : 6 3
Indx: [2] [4]
Pre: .... [2]

5 : 6 5
Indx: [2] [5]
Pre: ......[2]

Length: 2
Seq: 6 5

Code:
--------
input file:

16
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
8
-7 10 9 2 3 8 8 1
5
1 6 2 3 5

0

/*
Algorithm: Longest Decreasing Seq.
Complexity: nlgn
*/
#include<stdio.h>
#include<limits.h>
#define S 100000

int R[S]={0};/*Generated Table*/
int A[S] = {0};/*Input data*/
int Indx[S]= {0}; /*Index of the Table Element*/
int Pre[S]={0}; /*Previous Element*/

void Print(int i){
    if ( i == 0) return;
    else {
        Print(Pre[i]);
        printf("%d ",A[i]);
    }
    return;
}
/*Complexity lg2^N*/
int BS(int v,int s,int e){
    int mid=0;
    while(s<=e){
         mid = s+((e-s)/2);
         /*Remove small*/
         if (R[mid]<=v){
              if (v<R[mid-1]|| v == R[mid-1])break;
              e = mid-1;
         }
         else if (v<R[mid]){
            if(R[mid+1]<v){mid=mid+1;break;}
            s = mid+1;
         }
    }
    return mid;
}


int main(){
    int i,v=0,j;
    int rc;
    int s,e,mid;/*Binary Search*/
    int N;

    freopen("LIS.in","r",stdin);

    A[0]=R[0] = INT_MAX;
    Indx[0] = 0;

    while(1){
       scanf("%d",&N);
       if(N==0) break;

       rc=1;
       for(i=1;i<=N;i++){
           scanf("%d",&A[i]);
           v = A[i];
           if(v<R[rc-1]){
              R[rc] = v;
              Indx[rc] = i;
              Pre[i] = Indx[rc-1];
              rc++;
           }
           else if(v>R[rc-1]){/*Binary Search*/
              mid = BS(v,1,rc-1);
              R[mid] = v;
              Indx[mid]= i;
              Pre[i] = Indx[mid-1];
            }
        }
        printf("Length: %d\n",rc-1);
        printf("Seq: ");
        i = Indx[rc-1];
        Print(i);
        printf("\n\n");

        for(i=1;i<=N;i++) Pre[i]=0,Indx[i]=0,R[i]=0;
    }
    return 0;
}

Longest Increasing Subsequence

2015-10-09T09:23:00.002-07:00

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. he longest increasing subsequence problem is solvable in time O(n log n), where n denotes the length of the input sequence.
Example:
In the first 16 terms of the binary Van der Corput sequence

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

a longest increasing subsequence is

0, 2, 6, 9, 11, 15.

This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,

0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15

are other increasing sub sequences of equal length in the same input sequence [Wiki].
Dynamic Problem:

Explain the procedure to find LIS (Complexity: O(nlgn):
We maintain three array variable , R[], Indx[] and Pre[]
rc = 1;
[1] Take ith element int v, if v > R[rc-1] then R[rc] = v,Indx[rc] =i,Pre[i] =Indx[rc-1]
[2] if v (Use Binary Search)
[3] R[Pos] = v, Indx[Pos] = i, Pre[i] = Indx[Pos-1]

A = {-7 10 9 2 3 8 8 1} [Let index start from 1]
R[0] = INT_MIN, Indx [0] = 0

v=-7, R = {-7} ( because v>R[0] ) Indx = {1}, Pre = {0} root
v = 10, R ={-7 10} , Indx = {1,2}, Pre = {0,1};
v = 9 , R = {-7 9} , Indx = {1, 3} , Pre = {0,1,1}
v = 2, R = {-7 2}, Indx = {1,4}, Pre= {0,1,1,1}
v = 3, R = {-7 2 3}, Indx = {1,4,5}, Pre= {0,1,1,1,4}
v = 8, R = {-7 2 3 8}, Indx = {1,4,5,6}, Pre= {0,1,1,1,4,5}
v= 8, R = {-7 2 3 8}, Indx = {1,4,5,6}, Pre= {0,1,1,1,4,5,0}
v = 1, R = {-7 1 3 8}, Indx = {1,8,5,6}, Pre= {0,1,1,1,4,5,5,0,1}

More Clear:
index: [1] [2] [3] [4] [5] [6] [7] [8]
A     : -7 10 9   2   3   8   8 1
Pre : [0]
Indx: [1]
-7 : -7

Pre : [0] [1]
Indx: [1] [2]
10:    -7 10

Pre : [0] [1]
Indx: [1] [3]

9 :    -7 9

Pre : [0] [1]
Indx: [1] [4]
2 :    -7 2

Pre : [0] [1] [4]
Indx: [1] [4] [5]

3 : -7   2 3

Pre : [0] [1] [4] [5]
Indx: [1] [4] [5] [6]

8 :    -7 2   3 8

Pre : [0] [1] [4] [5]
Indx: [1] [4] [5] [6]
8 :     -7 2   3   8

Pre : [0] [1] [4] [5]
Indx: [1] [8] [5] [6]
1 :    -7 1   3 8
Print: A[Indx[4] =6] - > A[Pre[6]=5] - > A[Pre[5] =4] - > A[Pre[4] =1] - > Pre[1]=0 break
8 3 2 -7 - > -7 2 3 8
input file: LIS.in

16
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
8
-7 10 9 2 3 8 8 1
5
1 6 2 3 5
0

/*
Algorithm: Longest Increasing Seq.
Complexity: nlgn
*/
#include<stdio.h>
#include<limits.h>
#define S 100000

int R[S]={0};/*Generated Table*/
int A[S] = {0};/*Input data*/
int Indx[S]= {0}; /*Index of the Table Element*/
int Pre[S]={0}; /*Previous Element*/

void Print(int i){
    if ( i == 0) return;
    else {
        Print(Pre[i]);
        printf("%d ",A[i]);
    }
    return;
}
/*Complexity lg2^N*/
int BS(int v,int s,int e){
    int mid=0;
    while(s<=e){
         mid = s+((e-s)/2);
         if (v<=R[mid]){
              if(R[mid-1]<v) break;
              e = mid-1;
         }
         else if (v>R[mid]){
            if(R[mid+1]>=v){mid= mid+1;break;}
            s = mid+1;
         }
    }
    return mid;
}

int main(){
    int i,v=0;
    int rc;
    int s,e,mid;/*Binary Search*/
    int N;

    freopen("LIS.in","r",stdin);

    A[0]=R[0] = INT_MIN;
    Indx[0] = 0;

    while(1){
       scanf("%d",&N);
       if(N==0) break;

       rc=1;
       for(i=1;i<=N;i++){
           scanf("%d",&A[i]);
           v = A[i];
           if(v>R[rc-1]){
              R[rc] = v;
              Indx[rc] = i;
              Pre[i] = Indx[rc-1];
              rc++;
           }
           else if(v<R[rc-1]){/*Binary Search*/
              mid = BS(v,1,rc-1);
              R[mid] = v;
              Indx[mid]= i;
              Pre[i] = Indx[mid-1];
            }
        }
        printf("Length: %d\n",rc-1);
        printf("Seq: ");
        i = Indx[rc-1];
        Print(i);
        printf("\n\n");

        for(i=1;i<=N;i++) Pre[i]=0,Indx[i]=0,R[i]=0;
    }
    return 0;
}

Explain the procedure to find LIS (Complexity: O(n^2):

A : Given Data set
Pre : Predecessor of a number
L : Length of the seq save
max: Max length
End: End Element index
Let Index start from 1
A = {1 6 2 3 5} N = 5
i : = 1 , j : = 2 to 5
A[2:5]={6 2 3 5} >A[i] and L[i]+1 > L[j]
i.e. L[1]+1 = 2> L[2] =1 , L[1] = 2, Pre[2] = i =1, max=2, End = 2
L[1]+1 = 2> L[3] =1 , L[3] = 2 , Pre[3] = i =1
L[1]+1 = 2> L[4] =1 , L[4] = 2, Pre[4] = i =1
L[1]+1 = 2> L[5] =1 , L[5] = 2, Pre[5] = i =1
L: [ 1 2 2 2 2 ]
Pre: [ 0 1 1 1 1 ]
max = 2, End = 5

i = 2, j: 3 to 5
A[3:5] = {2 3 5} < A[i] and L[i]+1 > L[j] ------ > false

L: [ 1 2 2 2 2 ]
Pre: [ 0 1 1 1 1 ]

max = 2, End = 5

i = 3, j: 4 to 5
A[3:5] = {3 5} > A[i] and L[i]+1 > L[j]

L: [ 1 2 2 3 3 ]
Pre: [ 0 1 1 3 3 ]
max = 3, End= 5

i = 4, j: 5 to 5
A[3:5] = {5} > A[i] and L[i]+1 > L[j]
L: [ 1 2 2 3 4 ]
Pre: [ 0 1 1 3 4 ]
max = 4, End=5

Given Sq: 1 6 2 3 5
Length: 4
Sq: 1 2 3 5

			j = i+1
			1	6	2	3	5	Check Increasing Value and path Any Node to j and I to j Compare
		L	1	1	1	1	1
		Pre	0	0	0	0	0
i= 1 to N-1	1	L		2	2	2	2
	1	Pre		1	1	1	1
	6	L			2	2	2
	6	Pre			1	1	1
	2	L				3	3
	2	Pre				3	3
	3	L					4
	3	Pre					4
	5
	5

Pre = {0 1 1 3 4}
End = 5 Print - > A[5] - > A [Pre[5] = 4] - > A [Pre [4] = 3] - > A[ Pre[3] = 1] - > A[Pre[1] =0] Break
Max = Max (L) = 4

Another:
A = {-7 10 9 2 3 8 8}

L: [ 1 2 2 2 2 2 2 ]
Pre: [ 0 1 1 1 1 1 1 ]
Max = 2 End : 7

L: [ 1 2 2 2 2 2 2 ]
Pre: [ 0 1 1 1 1 1 1 ]
Max = 2 End : 7

L: [ 1 2 2 2 2 2 2 ]
Pre: [ 0 1 1 1 1 1 1 ]
Max = 2 End : 7

L: [ 1 2 2 2 3 3 3 ]
Pre: [ 0 1 1 1 4 4 4 ]
Max = 3 End : 7

L: [ 1 2 2 2 3 4 4 ]
Pre: [ 0 1 1 1 4 5 5 ]
Max = 4 End : 7

L: [ 1 2 2 2 3 4 4 ]
Pre: [ 0 1 1 1 4 5 5 ]
Max = 4 End : 7

Given Sq: -7 10 9 2 3 8 8
Length: 4
Sq: -7 2 3 8

			j = i+1
			-7	10	9	2	3	8	8	Check Increasing Value and path Any Node to j and I to j Compare
		L	1	1	1	1	1	1	1
		Pre	0	0	0	0	0	0	0
i= 1 to N-1	-7	L		2	2	2	2	2	2
	-7	Pre		1	1	1	1	1	1
	10	L			2	2	2	2	2
	10	Pre			1	1	1	1	1
	9	L				2	2	2	2
	9	Pre				1	1	1	1
	2	L					3	3	3
	2	Pre					4	4	4
	3	L						4	4
	3	Pre						5	5
	8	L							4
	8	Pre							5
	8
	8

Pre = { 0 1 1 1 4 5 5}
End = 6 ( Last change Occur);
A[End = 6] - > A[ Pre [End] = 5] - > A[Pre[5] = 4] - > A[Pre[4]=1] - > A[Pre [1] = 0]
8 3 2 -7 ==> -7 2 3 8

Max = Max(L) = 4

Code:
------

/*Algorithm: LIS
Complexity: O(n^2)
*/
/*
Algorithm: LIS
Complexity: O(n^2)
A [] : Given Data set
Pre [] : Predecessor of a number
L [] : Length of the seq save
max: Max length
End: End Element index
*/
#include <limits.h>
#include<stdlib.h>
#include<stdio.h>
#define S 10000

void print(int *A, int *Pre,int End){
  if ( End == 0) return;
  else{
      print(A,Pre,Pre[End]);
      printf("%d ",A[End]);
  }
  return;
}

int main(){
  int A[S];
  int N = 16;
  int Pre[S],L[S];
  int i,j,max,End;

  freopen("LIS.in","r",stdin);

  while(1){
    scanf("%d",&N);
    if (N==0) break;
    for ( i = 1; i<=N ; i++) scanf("%d",&A[i]);


    /*Algorithm start: O(n^2)*/
    max = INT_MIN;
    End = 0;
    for ( i = 1; i<=N ; i++) Pre[i]=0,L[i]=1;;
    for (i = 1; i <= (N-1); i++){
      for (j = i+1; j <= N; j++){
          if ( A[j]> A[i] && L[i]+1>L[j]){
            Pre[j] = i;
            L[j] = L[i]+1;
            End = j;
            max = L[j];
          }
      }
    }

    /*Print*/
    printf("Given Sq: ");
    for(i=1;i<=N;i++) printf("%d ",A[i]);
    printf("\n");
    printf("Length: %d\n",max);
    printf("Sq: ");
    print(A,Pre,End);
    printf("\n\n\n");
  }
  return 0;
}

Output:

Given Sq: 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
Length: 6
Sq: 0 4 6 9 13 15


Given Sq: -7 10 9 2 3 8 8 1
Length: 4
Sq: -7 2 3 8


Given Sq: 1 6 2 3 5
Length: 4
Sq: 1 2 3 5



Process returned 0 (0x0)   execution time : 0.797 s
Press any key to continue.

Uva 109 - SCUD Busters

2015-10-05T14:04:00.000-07:00

Problem: 109 - SCUD Busters
Description:
[1] Find individual Convex hull for each area (Read:Convex Hull)
[2] Check: Is a Missile falls inside a convex hull, mark it
[3] Sum the area of the marked convex hull

Example:
First Kingdom: Number of Points : 12
(3 3 ) , (4 6) , (4 11) , (4 8) , (10 6) , (5 7), (6 6), (6 3), (7 9) ,(10 4),(10 9), (1 7)

Convex Hull: (4 11) ,(10 9),(10 6),(10 4),(6 3),(3 3) and (1 7)

Area1: 54.00

Second Kingdom: Number of Points: 5

(20 20), (20 40), (40 20), (40 40) and (30 30)

Convex Hull: (20 40), (40 40), (40 20), and (20 20)

Area2 : 400

Third Kingdom: Number of Points: 3

(10 10), (21 10), and (21 13)

Convex Hull: (21 13), (21 10), (10 10)

Area3 = 16.50

Now i am going to missile attack (Boom!!!!)

(5, 5)

Destroy Area1

SUM = 0+area1 = 54.00

(20 12)

Destroy Area3
SUM = 54.00 + 16.50 = 70.50 (ans)

Input:

output:

70.50

Code:

// UVa 109 - SCUD Busters
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

struct point {
 int x, y;
};

point piv;

int cross(point c, point a, point b) {
 int x1 = a.x - c.x;
 int x2 = b.x - c.x;
 int y1 = a.y - c.y;
 int y2 = b.y - c.y;
 return x1 * y2 - x2 * y1;
}

bool operator <(point a, point b) {
 return cross(piv, a, b) < 0;
}

int main() {
 int n = 0, m;
 vector<point> p[20];

 //double area[20];
 double area;
 point hull[20][101];
 int h[20];

 double sol = 0;
 point fire;
 bool alive[101];

 //freopen("109.in","r",stdin);

 cin >> m;
 while (m != -1) {
  for (int j = 0; j < m; j++) {
   point pp;
   cin >> pp.x >> pp.y;
   p[n].push_back(pp);
  }
  n++;
  cin >> m;
 }

    //1. find Convex Hull
 for (int i = 0; i < n; i++) {
  int mn = 0;
  for (int j = 1; j < p[i].size(); j++)
   if (p[i][j].x < p[i][mn].x || p[i][j].x == p[i][mn].x && p[i][j].y < p[i][mn].y)
    mn = j;
  piv = p[i][mn];
  p[i][mn] = p[i][0];
  p[i][0] = piv;
  sort(p[i].begin() + 1, p[i].end());

  p[i].push_back(piv);
  hull[i][0] = p[i][0];
  hull[i][1] = p[i][1];
  h[i] = 2;
  for (int j = 2; j < p[i].size(); j++) {
   while (h[i] >= 2 && cross(hull[i][h[i] - 2], hull[i][h[i] - 1], p[i][j]) > 0)
    h[i]--;
   hull[i][h[i]++] = p[i][j];
  }
 }

    //2. Is Missile land inside a convex hull, then find area and sum
 memset(alive, true, sizeof(alive));
 while (cin >> fire.x >> fire.y) {
  for (int i = 0; i < n; i++)
   if (alive[i]) {
       // Check missile is in convex hull
    bool mark = true;
    for (int j = 1; j < h[i]; j++) {
     if (cross(hull[i][j - 1], hull[i][j], fire) > 0) {
      mark = false;
      break;
     }
    }
    if (mark) {
     alive[i] = false;
                    // Inside- Yes
     area = 0;
              for (int j = 1; j < h[i]; j++)
                area += hull[i][j - 1].x * hull[i][j].y - hull[i][j].x * hull[i][j - 1].y;
                    area =area/2;
     sol += area;
    }
   }
 }
 printf("%.2f\n", abs(sol));

 return 0;
}

Uva 108 - Maximum Sum

2015-10-05T09:23:00.000-07:00

Problem: 108 - Maximum Sum

Description:
We can solve this problem with O(N^3) order. Kadane's algorithm can be used to find the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number). The complexity of Kadane's algorithm for 1D array is O(N).

Read : Maximum subarray problem

Code:
-------

#include<stdio.h>

int main( void ){

    int N;
    int t = 0;
    int a[100][100];
    int pr[100];
    int S = 1<<31, s = 0, k, l,j;
    int i,x,z,f=0;
    /*freopen("108.in","r",stdin);*/

    while((scanf("%d",&N))==1){
   for(i=0;i<N;i++)
  for(j=0;j<N;j++)
   scanf("%d",&a[i][j]);
      S=1<<31;

      /*Kadan 2D algorithm- O(N^3)*/
      for( z = 0; z < N; z++){
        for(i = 0; i < N; i++) pr[i] = 0;
        for(x = z; x < N; x++){
            t = 0;
            s = 1<<31;
            j = 0;
            k = 0; l = 0;
            for(i = 0; i < N; i++){
                pr[i] = pr[i] + a[x][i];
                t = t + pr[i];
                if( t > s){
                    s = t;
                    k = i;
                    l = j;
                }
                if( t < 0 ){
                    t = 0;
                    j = i + 1;
                }
            }
            if( s > S)S = s;

        }
      }
      printf("%d\n",S);
    }

    return 0;
}

Maximum Subarray Problem

2015-10-04T13:09:00.001-07:00

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images. A linear time algorithm was found soon afterwards by Jay Kadane of Carnegie-Mellon University (Bentley 1984). [Wiki]

Example:
[1] A = {-2,1,-1,1,1,-1,2,1,-5}; [assum, 1st element is indicated by 0]
Maximum Value = 4, start index = 1, End index = 7

[2] A = {-2,1,-2,1,1,-1,2,1,-5}; [assum, 1st element is indicated by 0]
Maximum Value = 4, start index = 3, End index = 7

[3] A = {-2,1,-3,4,-1,2,1,-5,-4}; [assum, 1st element is indicated by 0]
Maximum Value = 6, start index = 3, End index =6

[4] A = {2,3,5,4,6,3,5,4,6};
Maximum Value = 38, start index = 0, End index =8

[5] A = {-1,-2,-3,-4,-5,-6,-7,-8,-9}
Maximum Value = -1, start index = 0, End index =0

Explaination:
if consider sum is equal to or grater than zero, then we have to follow this algorithm:

if -infinite < sum < +infinite then we have to follow this algorithm:

How we find the range of the index:

Kadane's algorithm

[1] Iterative Solution (here max_Index and min_index is not consider here]

/*
Problem: Maximum subarray problem
Ref: https://en.wikipedia.org/wiki/Maximum_subarray_problem
Variable Defination
max_e = maximum end here
max_so = maximum so far
input range INT_MIN < = xi < = INT_MAX
*/
#include<stdio.h>

int max(int a, int b){return (a > b)?a:b;}

int main(){
   int a[] = {-2,1,-2,1,1,-1,2,1,-5};
   int N=9,i;
   int max_e,max_so;

   /*Print Array*/
   printf("Array: { ");
   for (i = 0; i<N ; i++)
            printf("%d ",a[i]);
   printf("} \n\n");


   /*Kadan's Algorithm*/
   max_e= max_so =a[0];
   for(i=1;i <N;i++){
       max_e = max(a[i], max_e + a[i]);
       max_so = max(max_so, max_e);
   }


   printf("Maximum Sum of Continuous Sub-Array: %d\n",max_so);

  return 0;
}

[2] Recursive Method:

/*
Variable Defination
N = Number of Total Element
a[] = array
GS = Global Starting Index
GE = Global End Index
CMax = Current Maxumum Sum
CSI = Current Start Index
CEI = Current End Index
Max = Final Maximum Number
Ref: http://www.algorithmist.com/index.php/Kadane%27s_Algorithm
*/
#include<stdio.h>

int GS = 0, GE =0;

int Kadane (int *a,int N,int Max){
    int CMax,CSI,CEI;

    CMax = 0;
    CSI = 0;

    for (CEI = 0; CEI < N ; CEI++){

        CMax = CMax + a[CEI];

        if(CMax > Max){
          GS  = CSI, GE = CEI;
          Max = Kadane(a,N,CMax);
        }

        if(CMax < 0) {
            CMax = 0;
            CSI = CEI + 1;
        }
    }
    return Max;
}


int main(){
    int a[] = {-2,1,-3,4,-1,2,1,-5,-4};
    int N=9,Max;
    int i;

    Max = Kadane(a,N,a[0]);

    /*Display*/
    printf("Array [0-%d]: { ",N-1);
    for (i = 0; i<N ; i++)
            printf("%d ",a[i]);
    printf("} \n\n");
    printf("Max Sum: %d, Start Index: %d End Index: %d \n",Max,GS,GE);

    return 0;
}

[3] Iterative Method:

/*
Variable Defination
N = Number of Total Element
a[] = array
S = Starting Index
E = End Index
CMax = Current Maxumum Sum
CSI = Current Start Index
CEI = Current End Index
Max = Final Maximum Number
Ref: http://alexeigor.wikidot.com/kadane
*/
#include<stdio.h>
#include<limits.h>


int main(){
   int a[] = {-2,-1,-3,4,-1,2,1,-5,-4};

   int N=9,i;

   int Max=1<<31,S=0,E=0;

   int Cmax=0,CSI=0;
   int CEI;


   printf("Array: { ");
   for (i = 0; i<N ; i++)
            printf("%d ",a[i]);
   printf("} \n\n");



   for(CEI = 0; CEI < N; CEI++){
     Cmax = Cmax + a[CEI];
     if( Cmax > Max){
        Max = Cmax;
        E = CEI;
        S = CSI;
      }
      if( Cmax < 0 ){
         Cmax = 0;
         CSI = CEI + 1;
      }
    }

    printf("%d %d-%d\n",Max,S,E);

   return 0;
}

[4] My Designed Algorithm for 1D array O(N)[Nice to Play with it]:

[S = 0 , E = N-1]
1. Remove starting and End Minus value (SET S and E)
2. if all are positve then sum = ADD(all Element) break
3. if all are negative then sum = MAX(all Element) break
4. For i = S to E begin
5.     sum = 0;
6.     if a[i] < 0 then a[i] = sum + a[i],sum = 0;
7.     else sum = sum+a[i];
8. end
9. to be continue from 1 to 8 untile S > E
10. Return sum;

Example-1:
----------

{-2,1,-1,1,1,-1,2,1,-5}; -- > S = 0 , E =8

{-2,1,-1,1,1,-1,2,1,-5}; -- > S = 1, E = 7

{-2,0,(1+-1),0,0,(-1+1+1),0,(2+1),-5}
{-2,0,0,0,0,1,0,3,-5} --- > S = 3, E = 7

sum = Add (a, 3, 7) = 4

Example - 2:
==============
{-2,1,-2,1,1,-1,2,1,-5};-- > S = 0 , E =8

{-2,1,-2,1,1,-1,2,1,-5};-- > S = 1 , E =7

{-2,0,(-2+1),0,0,(-1+1+1),0,(2+1),-5};-- > S = 3 , E =7
{-2,0,-1,0,0,1,0,3,-5};-- > S = 3 , E =7
{-2,0,-1,0,0,1,0,3,-5};-- > S = 4 , E =7

sum = ADD (a,4,7) = 4

Example - 3
============
{-2,1,-3,4,-1,2,1,-5,-4}; -- > S =0 E =8

{-2,1,-3,4,-1,2,1,-5,-4}; -- > S =1 E =6

{-2,0,-2,0,3,0,3,-5,-4}; -- > S =3 E =6

{-2,0,-2,0,3,0,3,-5,-4}; -- > S =4 E =6

sum = ADD (a,4,6) = 6

#include<stdio.h>

int max(int *a,int s,int e){
    int m = a[s];
    int i;
    for (i=s+1;i<=e;i++)
        if (m<a[i]) m = a[i];

    return m;
}

int ADD(int *a,int s,int e){
    int sm = 0,i;
    for (i=s;i<=e;i++) sm+=a[i];

    return sm;
}

int main(){
   int a[] = {-2,1,-3,4,-1,2,1,-5,-4};


   int N=9;
   int i,sum,flag;

   int S = 0, E = N-1,PS = 0,PE =0;

   while (S<E){
          /*Eliminate starting minus value*/
          i = S;
          PS = S;
          while(a[i]<0&&i<=E) i = i+1;
          S = i;

          printf("S: %d\n",S);
          if (S>E){ sum = max(a,PS,E); break;}



          /*Eliminate End minus value*/
          i= E;
          PE = E;
          while(a[i]<0 && i>S) i = i-1;
          E = i;
          printf("E: %d\n",E);

          if(S == PS && E == PE){ sum = ADD(a,S,PE); break;}


          /*Process*/
          sum = 0;
          flag = 0;
          for (i = S; i<=E; i++){
             if (a[i]<0){
                   a[i] = sum+a[i];
                   sum = 0;
                   if (flag ==0){S = i;flag = 1;}
             }
             else{
                sum = sum + a[i];
                a[i] = 0;
             }
          }

          if (flag == 0)/*All are positive value*/
               S = i;
          a[E] = sum;

          printf("S: %d\n",S);

          for (i = 0; i<N ; i++)
            printf("%d ",a[i]);
          printf("\n\n");
   }

   printf("Sum: %d",sum);
   return 0;
}

[5] Kadane's 2D algorithm O(N3)

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main( void )
{
    int N;
    int t = 0;
    int a[100][100];
    int pr[100];
    int S = 1<<31, s = 0, k, l, x1 = 0,x2 = 0,y1 = 0,y2 = 0,j;
 
    cin >> N;
 
    for( int i = 0; i < N; i++)
        for( j = 0; j < N; j++)
            cin >> a[i][j];
 
    for( int z = 0; z < N; z++)
    {
        for(int i = 0; i < N; i++) pr[i] = 0;
 
        for(int x = z; x < N; x++)
        {
            t = 0;
            s = 1<<31;
            j = 0;
            k = 0; l = 0;
            for(int i = 0; i < N; i++)
            {
                pr[i] = pr[i] + a[x][i];
                t = t + pr[i];
                if( t > s)
                {
                    s = t;
                    k = i;
                    l = j;
                }
                if( t < 0 )
                {
                    t = 0;
                    j = i + 1;
                }
            }
            if( s > S)
            {
                S = s;
                x1 = x;
                y1 = k;
                x2 = z;
                y2 = l;
            }
        }
    }
 
    cout << x1 << " " << y1 << " " << x2 << " "  << y2 << endl;
    cout << S;
 
    return 0;
}

Ref: http://alexeigor.wikidot.com/kadane