Who Am I and Who Is My Parrent

An Unix Process got created, but it know its name (its ID) and who created it. How will is know its ID ?

In Unix Operating System, a process is a living entity.A process is a program in execution.

How does a Process knows its ID, also know as Process-ID. 

[incomplete]

Reverse Linked List - Recursion - with code

#include <iostream>

using namespace std;

struct node {
        int data;
        struct node *next;
};

typedef struct node NODE;

class linklist {
        private:
                NODE *head;
        public:
                linklist():head(NULL) {}
                void push(int);
                void display();
                void reverse();
                NODE* reverse_driver(NODE*, NODE*);
};

void linklist::push(int data) {
        NODE *tmp = new NODE;
        tmp->data = data;
        tmp->next = NULL;

        if (head == NULL) {
                head = tmp;
        } else {
                NODE *curr = head;
                while (curr->next != NULL) {
                        curr = curr->next;
                }
                curr->next = tmp;
        }
}

void linklist::display() {
        NODE *curr = head;
        cout<<"HEAD: ";
        while (curr != NULL) {
                cout<<curr->data<<"->";
                curr = curr->next;
        }
        cout<<"NULL\n";
}

void linklist::reverse() {
        if (head != NULL) {
                NODE *last = reverse_driver(head, head->next);
                // make the last_node->next to NULL
                head->next = NULL;

                // change the head to the last
                head = last;
        } 
}

NODE* linklist::reverse_driver(NODE *currnode, NODE *nextnode) {
        if (nextnode != NULL) {
                NODE *last = reverse_driver(nextnode, nextnode->next);
                nextnode->next = currnode;
                return last;
        } else {
                // Last Node - to be set as Head node
                return currnode;
        }
}

int main () {
        linklist ll;

        ll.push(10);
        ll.push(20);
        ll.push(30);
        ll.push(40);

        ll.display();
        ll.reverse();
        ll.display();
        return 0;
}

The 2-Key Case

About 10 and a half years back, when I was an summer student in IMSC (Institute of Mathematical Science) my mentor(Dr. Venkatesh Raman) asked a question to ponder during my first weekend in the institute and let him know how to solve it.

Before I go into the problem: I will give a background for it.

Predominately, there are 2 problem in Computer Science: Searching and Sorting. "How to do it efficiently ?"

"implicit data structures" - these data structures uses very little or no extra spaces other than the "data elements".

For example, "linked list" which use 1 pointer per "data elements" will amount to the "Space Complexity" of SizeOf(data_elements) + ((Number of data_elements) * SizeOf(Pointer)).

ie.. if the input is N integers, the "Space Complexity" of the integer linked list = N + N (pointers for each integer)
= 2*N

The Space Complexity of a Binary Search Tree (BST) = N + 2 N (2 pointers for each data_element)
= 3*N

But, a Sorted Array is an "Implicit Data Structure", it does not store any extra space. Whereas if you take the "Time Complexity" of both BST and Sorted Array for searching an element in the Collection, it takes same time which is lg(N).

lg = log N to the base 2

Reverse Linked List - Recursion

2 weeks back I was asking someone to write a code for Reversing a Linked List. I just tried one with Recursion:

 #include <iostream>
 
 using namespace std;
 
 struct node {
     int data;
     struct node *next;
 };
 
 typedef struct node NODE;
 
 class linklist {
     private:
         NODE *head;    
     public:
         linklist():head(NULL) {}
         void push(int);
         void display();
         void reverse();
         NODE* reverse_driver(NODE*, NODE*);
 };
 
 void linklist::push(int data) {
     NODE *tmp = new NODE;
     tmp->data = data;
     tmp->next = NULL;
 
     if (head == NULL) {
         head = tmp;
     } else {
         NODE *curr = head;
         while (curr->next != NULL) {
             curr = curr->next;
         }
         curr->next = tmp;
     }
 }
 
 void linklist::display() {
     NODE *curr = head;
     cout<<"HEAD: ";
     while (curr != NULL) {
         cout<<curr->data<<"->";
         curr = curr->next;
     }
     cout<<"NULL\n";
 }
 
 void linklist::reverse() {
     if (head != NULL) {
         NODE *last = reverse_driver(head, head->next);
         // make the last_node->next to NULL
         head->next = NULL;
 
         // change the head to the last
         head = last;
     } 
 }
 
 NODE* linklist::reverse_driver(NODE *currnode, NODE *nextnode) {
     if (nextnode != NULL) {
         NODE *last = reverse_driver(nextnode, nextnode->next);
         nextnode->next = currnode;
         return last;
     } else {
         // Last Node - to be set as Head node
         return currnode;
     }
 }
 
 int main () {
     linklist ll;
 
     ll.push(10);
     ll.push(20);
     ll.push(30);
     ll.push(40);
 
     ll.display();
     ll.reverse();
     ll.display();
     return 0;
 }
 

Convert Code to HTML - Perl

Convert the Code into HTML - Perl:

 #! /usr/bin/perl
 use warnings;
 use strict;
 
 my $lineno=0;
 
 print "<pre>";
 foreach my $strline (<STDIN>) {
     print "<a name=\"line$lineno\">";
     printf "%3d", $lineno;
     print "</a>";
     print " <font color=\"#0000FF\">";
     chomp($strline);
     $strline =~ s/&/&amp/g;
     $strline =~ s/</&lt/g;
     $strline =~ s/>/&gt/g;
     $strline =~ s/\t/    /g;
     print $strline;
     print "</font>";
     print "<br>";
     $lineno++;    
 }
 
 print "</pre>\n";
 

If you swap the substitutions statements are shuffled, you will not get the desired output.

Bignum For C++

Sometime back I was solving problems from Project Euler(http://projecteuler.net/). I was using an array of tools like Sage, Mathematica, bc (arbitrary precision calculator - yet powerful)..

But, most of the problems needs a bit of computation(programming). So, I started searching for a BigNum library for my favorite programming language C++. Eventually, I found one GMP (GNU Multi Precision) library. Later on I found that GMP is one of the fastest BigNum library available and it is also the backbone for most of the tools I was using for solving Euler problems.

GMP library can be got from http://gmplib.org/. If you need C++ extension for the GMP library, you configure it with the following command:

./configure --prefix=/usr/local --enable-cxx

This command will create 2 library files (libgmp.so and libgmpxx.so) and copy it to the /usr/local/lib location.

Don't forget to add the path to your LD_LIBRARY_PATH. Enjoy BigNUm computing :-)