[TECH] The C v C++ Flame which I have been looking for this time from *Linus*

I was doing a Google search with keywords "C++ sucks" and found a flame on the git mailing list. Linus was totally angry by some guy who suggests that "git should have been written in c++ rather c". See the flame here

I have been looking for this kind of stuff from long time when I advocate that why I always stick to writing code in things like C,Perl and shell scripts. I feel that I have total control on the program if I write code in C in which I can deal with the virtual address's but unfortunately as the abstraction increases you cannot have the control on the actual code. I guess its not only me but *You cannot convince any hacker to use c++*

[TECH] A simple UNIX based algorithm to run a set of tasks in parallel.

Given a set of tasks T={t₁,t₂....,t_n} such that these tasks can be run independently in parallel, however we have a limited set of resources and our constraint is K which tells us the maximum number of process's which can run in parallel. Our problem now is to realize this in UNIX using standard system calls like fork and wait.

I came across this recently and I came across the same thing several times before. Some examples of the contexts which would need this are as follows.

• Running test cases (regressions) in parallel, suppose we have several thousands of test cases for a product and we wish to run on a machine which can run K tests at any given instance.
• Making builds in parallel
• Parallel crawling/web indexing (which was my motivation to write this)

Download this code

$#ARGV == 1 or die("USAGE: perl parallel_runner.pl {file_with_commands} {no.of.process's}");
$command_file = $ARGV[0];
open(CMD_FILE,$command_file) or die("$!");
$max_process = $ARGV[1];
($max_process < 256) or die("Too many process's....use less number");
%child_hash;
$process_count = 0;
while(<CMD_FILE>){
 $cmd = $_;
 if($cmd =~ /^\#/){
  next;
 }
 if($process_count < $max_process){
  $pid = fork();
  if($pid < 0 ){
   die("$! : RESOURCE ERRORS");
  }elsif($pid == 0){
   system("$cmd");
   exit(0);
  }else{
   $child_hash{$pid} = 1;
   $process_count++;
  }
 }

 if($process_count==$max_process){
  $pid = wait();
  if($child_hash{$pid} == 1){
   $child_hash{$pid} = 0;
  }elsif($pid == -1){
   print "No childs to wait?? Confused...quitting\n";
   last;
  } 
  $process_count--;
 }
}
print "Done creating process's...now waiting for childs...\n";
$i = 0;
while($i < $max_process){
 $pid = wait();
 if($pid == -1){
  last;
 }
 $i++;
}

[TECH] Computing all the derivatives of a 'n' degree polynomial at point 'x=a' in O(nlog(n)) time.

I came across this problem recently, basically you are given a polynomial f(x) = a_nxⁿ+a_n-1x^n-1+....a₀ and you need to evaluate all its derivatives at a given point say x=a. I guess one of the suggested algorithms for this problem runs in O(nlog²(n)). But I found an idea to solve this in just O(nlog(n)). The following is the brief description of my algorithm

The idea is that we can post this as a simple multiplication of two n degree polynomials, the coefficients resulting from the multiplication will be the evaluated derivatives at a given point x=k. And as we might know that we can use FFT to multiply two n-degree polynomials in O(nlog(n))

• STEP1: Compute the values of k²,k³....,kⁿ in O(n) time. Also compute the values of n!,(n-1)!,....2! incrementally. The runtime of this step is O(n)
• STEP2: Create polynomial p(x) = (n!a_n)x^n-1+((n-1)!a_n-1)x^n-2+.....a₁.
• STEP 3: Create polynomial g(x) = (k^n-1/(n-1)!)x+(k^n-2/(n-2)!)x²+(k^n-3/(n-3)!)x³+.... +kx^n-1 .
• STEP 4: Multiply p(x) and g(x) using FFT in O(nlog(n) time.
• STEP 5: Clearly coefficient of x^n-i+1 gives the value of i^th derivative.

[TECH] What does computing the edit distance between a string and its reverse tell us?

I came across a problem recently which asks for the following "Given a string find out the minimum number of characters to be inserted to make it a palindrome, and also give the string". There might be several ways to solve this problem I have a simple algorithm to solve this problem in O(n²). The observation is the following reccurence.

Let LCS^r[x,y] = longest common sub sequence between S_1...x and S^r_1...y , where S^r is the reverse of the string S.
Let X=x₁x₂....x_k be the be the palindrome with minimum # of inserted characters to make it a palindrome, then X has to be formed from S as follows.
1. Find a index k in S such that the cost of transforming S[1..k] to S[k+1...n] is minimum and the palindrome would be X = S'[1...k]S'^r[k+1...n] or X = S'[1..k-1]S[k]S'^r[k+1..n]
2. The index k such that LCS^r[k][len-k] is maximum.
3. Get the code here

/*Builds the LCS between the forward and backwards and finds
a index 'p' which will give minimum # of operations to transform
forward string to backward string.*/
void FindLCSReverse(char *str,unsigned int len){
    int i,j;
    int current_min,max_lcs;
    int imax,jmax,palindex,palindex_r;
    unsigned int operations;
    char path=0;
    for(i=0;i<len;i++){
        LCS[i][0] = 0;
    }
    for(j=0;j<len;j++){
        LCS[0][j] = 0;
    }
    for(i=1;i<len;i++){
        for(j=1;j<len;j++){
            /*use len-j to access other string*/
            if(buf[i] == buf[len-j]){
                LCS[i][j] = LCS[i-1][j-1]+1;
            }else{
                LCS[i][j] = (LCS[i-1][j]>LCS[i][j-1])?LCS[i-1][j]:LCS[i][j-1];
            }
        }
    }
    /*Compute the p which gives minimum inserts to transform 
     *forward string to backward
     */
    max_lcs=0;
    imax=len-1;jmax=0;
    for(i=len-1;i>=1;i--){
        if(LCS[i][len-i-1] > max_lcs){
            max_lcs = LCS[i][len-i-1];
            imax = i;
            jmax = len-i-1;
        }
        if(i>0 && LCS[i-1][len-i-1] >= max_lcs){
            max_lcs = LCS[i-1][len-i-1];
            imax = i-1;
            jmax = len-i-1;
        }
    }
    /*Now find the actual string*/
    i=imax;
    j=jmax; 

    palindex_r=0;
    while(i!=0 || j!=0){
        if(i>0 && j>0){
            if(buf[i] == buf[len-j]){
                palindrome_rev[palindex_r++] = buf[i];
                i--; j--;
                continue;
            }
            current_min = (LCS[i-1][j] > LCS[i][j-1])?LCS[i-1][j]:LCS[i][j-1];
            if(current_min == LCS[i-1][j]){
                if(current_min == LCS[i][j-1] && buf[i] < buf[len-j]){
                    palindrome_rev[palindex_r++] = buf[len-j];
                    j--;
                }else{
                    palindrome_rev[palindex_r++] = buf[i];
                    i--;
                }
            }else if(current_min == LCS[i][j-1]){
                if(current_min == LCS[i-1][j] && buf[len-j] < buf[i]){
                    palindrome_rev[palindex_r++] = buf[i];
                    i--;
                }else{
                    palindrome_rev[palindex_r++] = buf[len-j];
                    j--;
                }
            }
        }else if(j==0){
            palindrome_rev[palindex_r++] = buf[i];
            i--;
        }else if(i==0){
            palindrome_rev[palindex_r++] = buf[len-j];
            j--;
        }
        /*path=1 (left) path=2 (down) path=3 (diag)*/
    }

    for(i=0;i<palindex_r;i++){
        palindrome[palindex_r-1-i] = palindrome_rev[i];
    }
    palindrome_rev[palindex_r] = '\0';
    palindrome[palindex_r] = '\0';

    /*printf("imax = %u jmax = %u len=%u \n",imax,jmax,len);*/
    if(imax+jmax==len-1){
        printf("%s%s\n",palindrome,palindrome_rev);
    }else{
        printf("%s%c%s\n",palindrome,buf[imax+1],palindrome_rev);
    }
}

[TECH] Reverse Engineering and Creating Crawler BOTS.

I have my share of pleasure reverse engineering the underlying details of SCOPUS. SCOPUS as you might know is the most popular scholarly database used for citation searching. I was trying to solve this problem "Given a research paper X produce a set of research papers in the same connected component of the CITATION GRAPH", Let me define a CITATION GRAPH (CITE(V,E)) , V = {set of all research papers} and E={(i,j)} set of all directed edges from research paper 'i' to 'j' such that paper 'j' refers paper 'i' in its references. This edge information comes from SCOPUS however SCOPUS gives only one level (depth 1) in the connected component of all related papers, my goal is to get all the related papers (related in the sense fall in the same connected component of the CITE graph).

The reverse engineering the underlying comes handy when we want to automate the process of searching all these from the browser ourself.

I'm too tired to explain the details of the program which I had written using perl+LWP to create a CRAWLER BOT which gets all the related papers but if you need similar stuff sure the code can help click here

Unfortunately I don't get enough time to write blogs but in past few weeks I had some very interesting technical stuff I want to write.

[TECH] A simple algorithm to find the coefficient's of characteristic polynomial.

Its often the case that the we need coefficients of the characteristic polynomial (xA = λx) rather than just the Eigen values and Eigen vectors of the matrix A, The following simple algorithm which can determine the coefficients of the polynomial from its roots (Eigen values) would be extremely handy, its a simple dynamic programming algorithm and also illustrates how quickly we can code dynamic programming algorithms in Matlab because the matrices resize automatically.

%
% eigen_poly_coeff: input 'A' should be a square matrix
% The program finds the eigen values of A, and constructs
% the caracteristic polynomial 
%
% output is the order of coefficients in the increasing 
% degree order.
%
function retval = eigen_poly_coeff (A)
v = eig(A)';
B = size(v);
coeff_matrix = eye(1,(B(1,2)+1));
coeff_matrix(1,1) = v(1,1)*-1;
coeff_matrix(1,2) = 1;

for i=3:1:(B(1,2)+1)
   coeff_matrix(1,i) = 1;
   for j=(i-1):-1:1
    coeff_matrix(1,j) = (coeff_matrix(1,j)*
                v(1,(i-1))*-1);
    if(j-1 >=1)
      coeff_matrix(1,j) = 
             coeff_matrix(1,j)+coeff_matrix(1,j-1);
    end
   end
end
 retval = coeff_matrix;
endfunction

[TECH] Algorithmic details of UNIX Sort command.

I happened to look at the algorithmic details of UNIX Sort, a LINUX version of the classic UNIX sort is a part of GNU coreutils-6.9.90. This is classic example of the standard External R-Way merge , to sort a data of size N bytes with a main memory size of M so it creates N/M runs and merges R at a time, the number of passes through the data is log(N/M)/log(R) passes.In fact the lower bound(runtime) for external sorting is Ω((N/M)log(N/M)/log(R)). All the external memory sorting algorithms provided in the literature are optimal so the fight here is minimizing the constant before the number of passes.

UNIX sort treats keys are lines (strings), the algorithm followed by unix sort is in fact the R-Way merge. Let the input file size be IN_SIZE.
1. Choosing Run Size:
--------------------------------
The sizes of the initial runs are chosen from the total physical memory (TOTAL_PHY) and available memory (AVAIL_PHY). RUN_SIZE = (MAX(TOTAL_PHY/8,AVAIL_PHY))/2
maximum of 1/8th of TOTAL_PHY and AVAIL_PHY and divided by 2. See function "default_sort_size (void)" in the code.
2. Creating Runs:
-------------------------
Unix sort creates a temporary file for every run. So it creates IN_SIZE/RUN_SIZE (celing) temporary files. Internally it uses merge sort to sort internally it uses an optimization mentioned in Knuth volume 3 (2nd edition), problem 5.2.4-23.
3. Merging:
----------------
The number of runs merged at any time is hard coded in the program see macro NMERGE , NMERGE is defined to be 16 so it merges exactly 16 runs at any time.

[TECH] Sorting partially sorted sequences.

Partially Sorted Sequence: A sequence k₁,k₂,...k_n of n keys such that any key k_j differs from its sorted position by atmost d as an example for d=3 we have 3,5,6,1,2,4 I came across this problem recently, turns out that we can solve this problem in several ways in O(nlog(d)) time. I found an interesting and simple way to solve this problem, a simple observation reveals that the smallest element in the entire sequence of n keys exists in the first d keys.

/*Build a heap(min) H with first d elements
 *in O(d) time
 */
 for(i=d;i<n;i++){
    DeleteMin(H); /*output this key*/
    InsertHeap(H,ki);
 }
/*Note the Heap will have atmost d keys in it
at any time so the Insert and Delete can be done in 
O(log(d)) worst case.
*/

(n-d)log(d) = O(nlog(d))

[TECH] Converting an Las Vegas algorithm from an Expected Time Bound to High Probability bound.

Some times its not always possible to derive the High Probability bounds (1-n^-α) for Las Vegas algorithms, I found an interesting way to convert any Las Vegas algorithm with expected bounds on the resources to the High Probability bounds. Assume that T_n be the expected runtime(or any resource) for a Las Vegas algorithm. The plain vanilla Las Vegas algorithm have the following structure.

while(1){
  /*Select a random sample*/
  if(answer found) quit;
}

Basically any analysis of the above randomized algorithm should tell how long should we run the loop. So let T_n gives the expected time on how long this loop runs. What we can do is as follows

• Let the algorithm run for exactly 2T_n steps, if the algorithm quits before that we are fine, if the algorithm does not quit after T_n times then stop and restart.

counter = 0;
while(1){
 /*Pick a random sample*/
 if(counter++ == 2Tn){
    counter=0; /*restarting*/
 }
 if(answer found) quit; 
}

We can now show that the above algorithm will now give high probability bounds. Let X be the random variable which indicates the runtime of the algorithm. Then using Markov inequality P[X ≥ aT_n] ≤ 1/a

• P[X ≥ 2T_n] ≤ 1/2
• Lets assume that the algorithm runs for k ≥ 2T_n time steps, then we should have done a reset exactly k/(2T_n) times.
• The probability of doing a reset equals P[X ≥ 2T_n] = P[reset].
• Lets assume all the events are independent then the probability of resetting k/(2T_n) P[reset k/(2T_n) times] = P[algorithm running k time steps]
• P[reset k/(2T_n)] ≤ (1/2)*(1/2)*(1/2)...k/(2T_n) times
• P[reset k/(2T_n)] ≤ (1/2)^k/(2T_n)
• we want the above probability to be very small (n^-α), to make that (1/2)^k/(2T_n) = n^-α). So the value of k for which this happens is 2T_nαlog(n)
• So with high probability after 2T_nαlog(n) time steps if we quit the loop then we give the correct answer.
• So we just have taken an expected bound T_n and converted into ∼O(log(n)T_n) time algorithm with high probability rather than expected bounds.

[TECH] Finding max and min in exactly 3n/2-2 Element Comparisions.

We know that the lower bound on the minimum number of comparisons to find max and min in an array of n. In fact the recurrence T(n) = 2T(n/2)+2 solves exactly to 3n/2-2 the following is an interesting way to find max and min in exactly 3n/2-2 comparisons non-recursively(assume 'n' is even). Also note by comparison we mean the element comparisons as they are significant.

current_min = a[0]; current_max=a[1];
/* 1 comparison here */
if(current_min < current_max){
  current_min = a[1]; current_max = a[0];
}
/*(n-1)-2+1 times*/
for(i=2;i<n-1;i+=2){
  /*3 Element Comparisons here */
  if(a[i] < a[i+1]){
      if(a[i] < current_min) current_min = a[i];
      if(a[i+1] > current_max) current_max = a[i+1];     
  }else{
      if(a[i+1] < current_min) current_min = a[i+1];
      if(a[i] > current_max) current_max = a[i]; 
  }
}
/*return current_max current_min*/

Analysis: Total Comparisions = 1 + (((n-1)-2+1)/2)*3 = 3*n/2-2.

[TECH] Standard I/O Buffers won't get flushed when program crashes...

Today I had a interesting problem, assume that you have a program printing out some details on to the screen and suddenly the program crashes and you want to capture what ever it has printed what would you do? you would try to redirect the output to a file and look at that file and what if the contents of the redirected file is empty? how do you explain this? try the following program and try to redirect what ever it prints using '>' or a '|' ("./a.out > out" or "./a.out | more")

char *crash_me = "crash this";
int main(){ 
    int i;  

    for(i=0;i<10;i++){
        printf("Before crash line %d\n",i+1);
        if(i==9){
            crash_me[6] = 'C';
        }
    }
}
/*TRY THE FOLLOWING*/
#1$./a.out
#2$./a.out > out
#3$./a.out | more

We can see that the 'out' file and 'more' don't show any thing which was in fact printed if we just run the program normally, how can we explain this? what exactly is happened? actually this is what has happened in the first case the terminal output is line buffered when ever terminal sees '\n' it prints that but in the next two cases the output is written to a file which is not line buffered (but gets written when the buffer is full) and since the program is crashed before the buffer gets full nothing is printed in case of #2 and #3. I guess one should definitely have a signal handler for SIGSEGV and other signals which end the program and do a explicit flush as below.

/*The buffers should be flushed before
 *program crashes.
 **/
void FlushBuffers(int sig){
    fprintf(stderr,"Segmentation Fault\n");
    fflush(stdout);fflush(stderr);
    exit(1);

}
char *crash_me = "crash this";
int main(){ 
    int i;  
    assert(signal(SIGSEGV,FlushBuffers)!=SIG_ERR);
    for(i=0;i<10;i++){
        printf("Before crash line %d\n",i+1);
        if(i==9){
            crash_me[6] = 'C';
        }
    }
}

I'm thinking of making a list of this kind of problems on UNIX

[TECH] SafeRead and SafeWrite

'read' and 'write' are most frequently used system calls, its really a blunder to have something like the following in the code.

/*Read and Write blunders*/
if(read(fd,buffer,len) < 0 ){
  perror("Read ERROR:");
}

if(write(fd,buffer,len) < 0){
  perror("Write ERROR:");
}

The above code involving 'read' and 'write' syscalls may seem perfectly fine but unfortunately thats not true, NEVER IGNORE THE RETURN VALUE of a syscall, its very common to functions like 'read' and 'write' to return values less than 'len' in several situations like program interrupted by a signal or timeout or if the 'len' is very large say in 'Mb' make sure you have the following 'SafeRead' and 'SafeWrite' in your coding libraries.

ssize_t SafeWrite(int fd,void *buf,size_t wlen){
 ssize_t len; char *bbuf = (char *)buf;
 size_t writeln=0;
 while(writeln < wlen){
   len = write(fd,&(bbuf[writeln]),wlen-writeln);
   if(len<=0) return len;
   writeln += len;
 }
 return writeln;
}

ssize_t SafeRead(int fd,void *buf,size_t rlen){
 ssize_t len;char *bbuf = (char *)buf;
 size_t readln=0;
 while(readln < rlen){
   len = read(fd,&(bbuf[readln]),rlen-readln);
   if(len<=0) return len;
   readln += len;
 }
 return readln;
}

Its quite often that the while loop only executes once, but its always possible that due to some reason the 'read' and 'write' syscalls may return less than the number of bytes you read or write.

[TECH] A Contradictory gcc message.

I have been experimenting on some of my PDM (parallel disk model) sorting code and wanted to create huge files with billions of keys I wanted to create a file with 1 billion integers (1024*1024*1024*4), the program stopped after some time saying that it "File size limit exceeded" , however in my shell (csh) the 'limit' command showed unlimited.

[vamsik@abadon PDMSorting]$ ./pdm_sort 
Setting RAND_SEED to 1201763856 
Filesize limit exceeded
[vamsik@abadon PDMSorting]$ ls -al key_file.txt 
---------- 1 vamsik fuse 2147483647 Jan 31 02:18 key_file.txt
[vamsik@abadon PDMSorting]$ 

I saw that the file was created without any permissions, so I tweaked my 'umask' but nothing changed (I was doing a open with (O_WRONLY|O_CREAT)). You might be wondering what exactly I'm trying to say in this post, in fact the story just started, rather than setting my 'umask' to 'umask 22', I have set it to 'umask 755' and as usual I was doing a build with 'make' this is what happened.

[vamsik@abadon PDMSorting]$ make
gcc  -O2  -I../myutil/            -c ExternalSort.c
ExternalSort.c:1: fatal error: can't open /tmp/cct9kuSr.s for writing: Permission denied
compilation terminated.
The bug is not reproducible, so it is likely a hardware or OS problem.
make: *** [ExternalSort.o] Error 1
[vamsik@abadon PDMSorting]$ 

Looks strange right? , see the funny thing it says "The bug is not reproducible, so it is likely a hardware or OS problem." , its really a stupid error message how can it say it cannot be reproduces? , just set 'umask 755' and do a 'gcc' on any file its going to say the same thing, in fact the message is a utter contradiction because we can reproduce this by changing the 'umask'. I'm going to report this to the 'gcc' maintainers or submit a patch to the maintainers.

[TECH] Ideas for Optimizing Design pattern implementations with Stack Collapsing

One major drawback I guess with all these object oriented systems I guess is performance, since people write the code so that its extensible it always ends up creating deep stack sizes, recently I was looking into (Jmol) this structure visualization tool supports several input format descriptions for the structures (pdb,cif,molxyz....). This is how they hide format details from the display code
JmolAdapter (abstract class)
==> SmarterJmolAdapter (this contains a interface called AtomSetCollection ). So depending on the input file we have several AtomSetCollection readers like PdbAtomSetCollection etc...

Although I came to a conclusion that to implement the structural alignment algorithm into Jmol, I need to implement this AtomSetCollection which structurally aligns the protein structures, but I guess there are several draw backs of the implementation of object oriented java implementation, the cost of creating an extensible design does not come for free it comes at the cost of performance, I found that a simple command execution could end up creating a stack size of 32 this is what concerns me is there a way we can collapse the stack when we know that the intermediate functions on the stack are just delegating the call to the actual instance, I guess this STACK COLLAPSING technique can always be applied when ever the Adapter design pattern is used. For example see the below stack of size 32, its not doing any thing great its just opening a new script file, because of the way the code is written (use of design patterns) the stack size seem to increase a lot and ULTIMATELY ALL THESE PATTERNS ARE JUST DELEGATING A FUNCTION CALL TO TO FUNCTION ON TOP OF THE STACK, I'm think of ways to improve the delegation since at each level of the stack you are doing a look up and it increases linearly with the size of the stack.

  [1] org.jmol.viewer.ScriptManager.addScript (ScriptManager.java:69)
  [2] org.jmol.viewer.ScriptManager.addScript (ScriptManager.java:52)
  [3] org.jmol.viewer.Viewer.evalStringQuiet (Viewer.java:3,152)
  [4] org.jmol.viewer.Viewer.evalString (Viewer.java:3,119)
  [5] org.jmol.viewer.Viewer.openFile (Viewer.java:1,379)
  [6] org.openscience.jmol.app.Jmol$OpenAction.actionPerformed (Jmol.java:1,435)
  [7] javax.swing.AbstractButton.fireActionPerformed (AbstractButton.java:1,849)
  [8] javax.swing.AbstractButton$Handler.actionPerformed (AbstractButton.java:2,169)
  [9] javax.swing.DefaultButtonModel.fireActionPerformed (DefaultButtonModel.java:420)
  [10] javax.swing.DefaultButtonModel.setPressed (DefaultButtonModel.java:258)
  [11] javax.swing.AbstractButton.doClick (AbstractButton.java:302)
  [12] javax.swing.plaf.basic.BasicMenuItemUI.doClick (BasicMenuItemUI.java:1,051)
  [13] javax.swing.plaf.basic.BasicMenuItemUI$Handler.mouseReleased (BasicMenuItemUI.java:1,092)
  [14] java.awt.Component.processMouseEvent (Component.java:5,517)
  [15] javax.swing.JComponent.processMouseEvent (JComponent.java:3,135)
  [16] java.awt.Component.processEvent (Component.java:5,282)
  [17] java.awt.Container.processEvent (Container.java:1,966)
  [18] java.awt.Component.dispatchEventImpl (Component.java:3,984)
  [19] java.awt.Container.dispatchEventImpl (Container.java:2,024)
  [20] java.awt.Component.dispatchEvent (Component.java:3,819)
  [21] java.awt.LightweightDispatcher.retargetMouseEvent (Container.java:4,212)
  [22] java.awt.LightweightDispatcher.processMouseEvent (Container.java:3,892)
  [23] java.awt.LightweightDispatcher.dispatchEvent (Container.java:3,822)
  [24] java.awt.Container.dispatchEventImpl (Container.java:2,010)
  [25] java.awt.Window.dispatchEventImpl (Window.java:1,791)
  [26] java.awt.Component.dispatchEvent (Component.java:3,819)
  [27] java.awt.EventQueue.dispatchEvent (EventQueue.java:463)
  [28] java.awt.EventDispatchThread.pumpOneEventForHierarchy (EventDispatchThread.java:242)
  [29] java.awt.EventDispatchThread.pumpEventsForHierarchy (EventDispatchThread.java:163)
  [30] java.awt.EventDispatchThread.pumpEvents (EventDispatchThread.java:157)
  [31] java.awt.EventDispatchThread.pumpEvents (EventDispatchThread.java:149)
  [32] java.awt.EventDispatchThread.run (EventDispatchThread.java:110)

[TECH] Association rules of by Data Mining (TM Algorithm) on Cancer Data.

I have datamined the Cancer data at http://breastscreening.cancer.gov/rfdataset/ using the TM(Transaction Mapping) and FP-Growth algorithm, this is what I have done to mine the association rules.

1. Randomly partition the data into two parts, I partitioned the data into part1 of size = 148458 records, part2 of size = 153897.
2. Used the part1 (148458 records) and found association rules of support >=0.4 and confidence >=0.4 , I got 72 rules from this.
3. For each of the rule (in step 2) I found the support and confidence of each of the rules in part2, it looks like the support and confidence is close to the support and confidence in training data (part1).

The 72 rules of step1 [
http://www.engr.uconn.edu/~vkk06001/CancerDataMining/rules.txt ]

Support and Confidence of each of this rules in part2
[http://www.engr.uconn.edu/~vkk06001/CancerDataMining/training_result.txt ]

I have made the rules human readable removing all the encoding please
see the rules
[
http://www.engr.uconn.edu/~vkk06001/CancerDataMining/human_readable.txt ]

These are in the following format
==============RULE:1=================
SUP:0.402 ,CONF:0.412,TRAIN_SUP:0.404,TRAIN_CONF:0.414
{
Diagnosis of invasive breast cancer within one year of the index
screening mammogram = no,
}
IMPLIES ===>
{
Diagnosis of invasive or ductal carcinoma in situ breast cancer within
one year of the index screening mammogram = no,
menopaus = postmenopausal or age>=55,
hispanic = no,
}
==============RULE:2=================

SUP indicates support of this rule in part2 , CONF indicates confidence of this
rule in part2, TRAIN_SUP indicates the support of this rule in part1 and
TRAIN_CONF indicates the confidence of this rule in part1.

These rules may not make any sense for me but it might make sense for a cancer doctor. There are several useful perl programs for people who want to do some datamining please feel free to use them http://www.engr.uconn.edu/~vkk06001/CancerDataMining , let me know if you have any questions.

[TECH] An observation to merge upper convex hulls in O(log(n)) time rather than O(log^2(n)).

The well known divide and conquer algorithm for finding convex hull for a given set of points, needs to merge smaller hulls H_1 and H_2 for doing this merge the algorithm uses lemma 3.2 (in Book Fundamentals of Computer Algorithms). This lemma essentially finds the tangent line (u,v) in O(log^2(n)) time.

We can in fact merge the hulls in more efficient manner, the observation is based on the fact that any point with maximum y-coordinate should definitely be on the hull. Let p1 and p2 be the points in hulls H_1 and H_2 with maximum y-coordinate, then we can safely state that either p1 or p2 will be on the combined hull of H_1 and H_2, we can determine which of these two points lie on the merged hull by comparing the y-coordinates of p1,p2. Among these two the point with maximum y-coordinate will definitely be on the merged hull so one end of the tangent line (u,v) is fixed, the other end of the tangent line can be probed in O(log(n)) time, this basically saves the extra O(log(n)) time which is spent previously in lemma 3.2 for finding the other end of tangent in H_2

[TECH] Hanging simulation..

I came across a interesting problem in which the entire simulation was hanging just because of an extra non-sensitive always block , in the verilog code the statement "always dummy_reg = in;" was causing both VCS and NC-VERILOG hang. Theoretically speaking irrespective of what I do in my design the simulation should stop after 500 steps because I have a "#500 $finish" in the initial block of the module "TestHangMux", although I got around this problem by removing the "dummy_reg" totally in the multiplexer, but I still don't understand why the simulation was hanging irrespective of the "#500 $finish" statement, is it because we have multiple non-sensitive "always" statement? the LRM(Language Reference Manual) says that all the "always" blocks execute in parallel just like parallel processors in that that the statement "#500 $finish" should have executed in parallel and stop the simulation but why it hangs?

===================================
module HangMux(in,sel,out);
input [1:0]in;
input sel; output out;
reg [1:0]dummy_reg;
reg out;

always @(sel) begin
    case(sel)
        0: out = dummy_reg[0];
        1: out = dummy_reg[1];
    endcase 
end

always dummy_reg = in;


endmodule

module TestHangMux(out_net);
output out_net;
wire out_net;
reg [1:0]in_reg;
reg sel;

initial begin
 in_reg = 2'b01;
 sel = 0;
#500 $finish;
end

always begin
#10 sel = ~sel;
end

HangMux hang_me (in_reg,sel,out_net);
endmodule
==============================

[TECH] Finding frequent itemsets faster than FP-Growth algorithm

I wanted to implement my prime-number mapping intersection algorithm into the TM(Transaction Mapping) Algorithm, I got the FP-Tree implementation from PERL FP Tree and was trying to test this on a data of around 300,000 records, it works till 10,000 records with support and confidence of 0.8 and 0.9 and fails if the number of records > 20,000. I'm not sure if its a perl bug but the following code which is the cause of the problem seems difficult to understand

===================================================================
@association_rules = map $_->[0], (sort {$b->[1] <=> $a->[1]} 
      (map [$_, $_->confidence], @association_rules));      
===================================================================

I tried to bless the reference $_ but it did'nt work. The following is the error it gives.

[vamsik@abadon Tree-FP-0.04]$ !perl
perl test_vamsi.pl
Setting support
Mining rules...
Can't call method "confidence" on an undefined value at /usr/lib/perl5/site_perl/5.8.8/Tree/FP.pm line 397,  line 20001.

I need to fix this and send it to the FPTree maintainer tomorrow. I guess its really a issue to implement the FPTree in perl because of the speed and time especially when the algorithm need to work on huge data just in my case. A good idea is to re-write FPTree in C and extend TM based on that and compare the results.

[TECH] why is ((unsigned long)a_ptr+(unsigned long)b_int) not equals (a_ptr+(unsigned long)b_int)

I was looking at some code today on SGI super computer, and wanted to make sure that there are no 32-64 bit problems in the code since SGI was super computer. I found the following thing to be interesting

<---------------------->
((unsigned long)a_ptr+(unsigned long)b_int)!=
          (a_ptr+(unsigned long)b_int)
<---------------------->

That is if I cast both the operands of binary + to (unsigned long) the value I get from that addition is different from if I cast just one operand of binary + to (unsigned long), whats the compiler doing here? since if both the operands to binary + are unsigned long and the value(no.of bits) could be larger than sizeof(unsigned long) is it the reason why I get different values here?, I couldn't find this in FAQ.

[TECH] Verilog incompatabilities between 'ncverilog' and 'vcs'

Thanksgiving vacation may be fun for some but its really not fun if your IT department is taking a break, our Synopsys License server has been down for last few days all my emails are vain no one responds. I used 'vcs' to compile all my verilog code all these days, now I'm helpless.....how can we solve this problem.
I want to get some synthesis metrics for the Sequence Alignment design, although Synopsys License server is down looks like the Cadence License server is up :). Thats good news but whats equivalent to 'vcs' in Cadence....'NCVERILOG' I found 'ncverilog' and try to compile all my design modules now the in-compatibility, NC-Verilog don't like to see any thing in the module description until all the port list is filled up,but vcs scans the code of the entire declaration list before checking if the port list is filled up (I guess thats the way it should be the algorithm should be very general). I like 'vcs' and not impressed by 'NC-Verilog' but unfortunately I have to live with it for few more days, by porting my verilog code...sounds crazy I have ported code on machines different processors but the way these compilers are build is really crazy....