[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....

[TECH] Iso-spectral and Non-Isomorphic Graphs (PINGS)

Having the same spectrum for the adjacency matrix is a Necessary but not sufficient condition for Graph Isomorphism, our recent algorithmic result states a conjecture that every graph is characterized by its Family of Spectra, rather than Spectrum itself.

I have been doing some work on efficient algorithms for generating PINGS (Pair of Isospectral and Non-Isomorphic Graphs), I wrote a program which can search for PINGS in a very efficient manner, I found some interesting results there are no PINGS for n=2,3,4 for n=5 we have one PING (see the picture) it happens that its the only PING for n=5 it has a symmetric spectrum of {-2,0,0,2}. Also I found a very interesting result that there cannot be more than two INGS(Iso-Spectral and non-isomorphic graphs) which share the same spectrum so if INGS exists they exist as PINGS, I was curious if they exist something like XINGS X=P or T or ... but it happens its just P (only a pair). There are 5 PINGS for n=6 for n=7 there are 55 PINGS see the list at http://trinity.engr.uconn.edu/~vamsik/n.7.

[TECH] Design of my first chip (A sequence Aligner O(n) space implementation)

Designing hardware is totally different from writing software, writing verilog code is totally different from writing software 'C' programs, often a software engineer tries to solve the problems using loops,arrays etc.. unfortunately implementing the same algorithm in hardware is totally different. I had my experience in designing a chip (verilog code) for finding edit distance between two strings this has a well known O(n^2) dynamic programming based algorithm. Now the trick is how do you create a hardware which realizes the two for loops in the O(n^2) algorithm, after quite a bit of thinking I came up with a solution which involves just SHIFTERS,MULTIPLEXERS and ADDERS. I'm not aware of any such hardware implementation of edit distance algorithm till now...I'm tempted to share my design diagram on the blog but I cannot do it until it gets published some where....

My design flow is as follows (verilog)->vcs; (libs+verilog)->Design Compiler; and I will use cadence virtuso (ICFB) for my placement and routing and also extraction; Will use HSPICE/Nanosim and spectre for postlayout simulation.

[TECH] A simple O(n^2) time algorithm to construct the Ultra-metric trees.

Given a matrix 'D' which is symmetric an Ultra-metric tree 'T' is a binary tree with internal nodes corresponding to D(i,j) and leaves corresponding to rows in the matrix 'D', and a path from the root to the leaf must be strictly decreasing (Ultra-metric tree). Also D(i,j) is the lowest common ancestor for 'i' and 'j'.
The problem is given 'D' we need to figure out corresponding 'T'.

The well know fact about the Ultra-metric trees is that if we take any 3 leaves i,j,k the maximum is not unique (e.x D(i,j)=5, D(j,k)=6,D(i,k)=5) we have D(i,j) and D(i,k) having same value.
How do we test if D is Ultra-metric?

• A trivial solution is O(n^3).
• The Errata shows construction of Ultra-metric trees in O(n^2) and asks a question if we can check for the Ultra-metric property in O(n^2) ? which my next item answers affirmatively.
• My observation is we can partition the leaves of the ultra-metric tree with out any need of building a complete weighted graph as in Gusfields solution, one fact is that every row in D is going to have a maximum (global) we don't need to spend O(n^2) (comparing all the elements in the matrix D) to find one. The algorithm below we perform such a check if an ultra-metric tree exists and also builds one.

  
  L = {1,2,....n};
  UltraMetricPartition(L){
   i = select_a_random_element_in(L) ;
   max = find_max(D(i,*)); /*Takes linear time*/
   /*max = D(i,q) && q should be in L*/
   Part_q = {};
   Part_i = {};
   foreach(j in L){
      if(j!=i){
          if(D(j,i)<=max && D(j,q)==max){
               Part_i += {j};
          }else if(D(j,q)<=max && D(j,i)==max){
               Part_q += {j};
          }else{
             printf("D is not ultra-metric");
             return 0;
          }
      }
   }
   UltraMetricPartition(Part_i);
   UltraMetricPartition(Part_q);
  
  }
  
  

Running time would be T(n) = T(n-k) + T(k) + O(n), clearly its quadratic O(n^2).

[TECH] Implementing Reliability(FEARLESS) on top of FUSE

FUSE is a user space file system implementation framework, the file system implementation can run as a user process and interact with the VFS of the kernel through a named pipe /dev/fuse, FUSE comes by default with all kernels > 2.6.8

"Any data which persists on just one disk is very unreliable" , I was talking with Rohit couple of days back and he compared disk as an "Electric Bulb", and u know about the filament in the bulb it can go off any time. So what do you think of your laptop how many disk's does it have? JUST ONE.....thats extremely unreliable until and unless your system is not backed up every day. So how can we get the reliability achieved by RAID (Redundant Array of Inexpensive Disks) ? the answer is persist what is called an "ACTIVE DATA" on some thing like FLASH memory and we can integrate this with a backup mechanism to get good reliability for personal storage devices like laptops. FEARLESS is idea which came up with this reliability for personal storage devices, you can read paper by Dr.Chandy.

Our IDEA is now to realize FEARLESS using FUSE and rsync (for backup), so FEARLESS would be just another file system similar to SSHFS but very reliable

Cheers!
Vamsi.

[BDAY] unsigned char age = age++;

Today happened to be my birthday, we just need an unsigned char to represent age, can you tell whats wrong with the code in the title (or below?).

static unsigned char age;

void Birthday(){
  age = age++;
}

Looks like the Standard 'C' says the value in the age is undefined ? because the assignment (=) is not a sequence point where the side effects (++,--) are settled. That can make the age of the person remain the same or increase it by one its ambiguous.

Cheers!
Vamsi. google index this

[TECH] O(n^2/(log(n)^2)) time algorithm for finding edit distance. [How does it feel when you know have reinvented the wheel :(]

Yesterday night during the workout suddenly I thought about what will happen if we encode the t-vector {-1,0,1}in the Four Russian algorithm as an integer.....the idea was a BOOM! I really felt like EUREKA! just like Archimedes thought when he discovered the law of flotation, I felt that suddenly I speedup the edit-distance dynamic programming algorithm which is O(n^2) by a factor of O(log^2(n)), it was really great I spend working on the details all special cases and written up every thing was great till then. I discussed the solution with Dr.Wu and found that it was actually solution to some exercise problem in Gusfield's book which says that in a RAM based computation model the copy of vector 't' can be done in O(log(t)) time.

How do you feel when you know some thing which you are exited just slips from you ? its very painful and its like killing you, but thats the way the world is its full of SMART people and any path which you are taking might have been taken before........

[TECH] Generic Randomized Quicksort algorithm.

Adding to my own collection of generic data structures, today I added a generic Randomized Quicksort algorithm, I need a good sorting routine in the SAPE algorithm for sorting distances. I want to makesure that it can sort any kind array (array of char's,int's,float's,double's and also structures).

/*A generic Randomized Quicksort:
 *The key idea of being generic comes
 *from the fact that you take a memory 
 *block and size of each element and 
 *sort this memory chunk, so we always
 *deal with address's.
 *
 *
 *Sep 20,2007 vamsik@engr.uconn.edu
 **/
#include
#include
#include
#include
#include
#include "RandQsort.h"

/*INPUT: swap_routine,compare_routine
 * swap_routine: The algorithm gives the 
 * (void *)'s swap_routine of two things
 * which need to be swapped.
 *
 * compare_routine: The algorithm gives the
 * (void *)'s to the compare_routine its 
 */
static char QSORT_RAND_SEED=0;
static void (*swap_routine)(void *,void *) = NULL;
static unsigned char (*compare_routine_l)(void *,void *) = NULL;
static unsigned char (*compare_routine_g)(void *,void *) = NULL;
static time_t t_rqsort;
unsigned int GetPivot(void){
 if(!QSORT_RAND_SEED){
  assert(((time_t)-1)!=time(&t_rqsort));
  srand(t_rqsort);
  fprintf(stdout,"Setting RAND_SEED to %d \n",t_rqsort);
  QSORT_RAND_SEED=1;
 }
 return ((unsigned int)rand());
}
/*Avoid loosing the pivot during swaps*/
void UpdatePivot(void **pivot,void **i,void **j){
 if(*i==*pivot){
  *pivot = *j;
 }else if(*j == *pivot){
  *pivot = *i;
 }
}
/*Take a memory address location and size 
of the data items[Inplace partition]*/
static void PartitionWithPivot(void* start,void* end,
unsigned int dsize){
 void *pivot=NULL;
 void* i=start;
 void* j=end;
 unsigned int p_index = GetPivot();
 if(start==end){
  return;
 }
 p_index %= (((unsigned int)(end-start))/dsize);
 pivot=(void *)((unsigned long)start+
  (unsigned long)((p_index)*dsize));
 while(i=start)){
   j-=dsize;
  }
  /*Swap i,j*/
  if(istart){
  swap_routine(pivot,(void *)(i-dsize));
  PartitionWithPivot(start,(void *)(i-(2*dsize)),
  dsize);
 }
 if((i+dsize)<=end){
  PartitionWithPivot(i,end,dsize);
 }
}
/*Call PartitionWithPivot recursively*/
void RandQsort(void *start,void *end,unsigned int dsize,
void_void_fptr sroutine,bool_void_fptr croutine_l){
 swap_routine = sroutine;
 compare_routine_l = croutine_l;
 assert(swap_routine && compare_routine_l);
 PartitionWithPivot(start,end,dsize);
}
#ifdef UNIT_TEST_RQSORT
/*TEST1:Testing for chars*/
unsigned char CharCompare_L(void *a,void *b){
 return ((*((char *)a))<=(*((char *)b)))?1:0;
}
unsigned char CharCompare_G(void *a,void *b){
 return ((*((char *)a))>=(*((char *)b)))?1:0;
}
void CharSwap(void *a,void *b){
 char temp=*((char *)a);
 *((char *)a) = *((char *)b);
 *((char *)b) = temp;
}
void TestCharSort(){
 char *data = malloc(sizeof(char)*10);
 char test_buffer[64];
 unsigned int i,j,k;
 time_t test_time;
 for(i=0;i<10;i++){
  data[9-i] = '0'+i;
 }
 /*Randomize the input data*/
 time(&test_time);
 srand(test_time);
 for(i=0;i<100;i++){
  j=(rand())%10;
  k=(rand())%10;
  test_buffer[63]=data[j];
  data[j]=data[k];
  data[k]=test_buffer[63];
 }
 /*Print the buffer*/
 if(strncpy(test_buffer,data,10)!=test_buffer){
  fprintf(stderr,"SYSTEM_ISSUE:Copy into buffer failed\n");
 }else{
  test_buffer[10]='\0';
  fprintf(stdout,"%s\n",test_buffer);
 }
 RandQsort((void *)data,(void *)(data+9),1,
 CharSwap,CharCompare_L);
 for(i=0;i<10;i++){
  if(data[i]-('0'+i)){
   printf("Test Failed for Chars\n");
   printf("Expecting %d but found %d\n",i,
    ((unsigned int)data[i]-'0'));
   exit(1);
  }
 }
 test_buffer[0]='\0';
 if(strncpy(test_buffer,data,10)!=test_buffer){
  fprintf(stderr,"FAILED_TEST: UNABLE TO COPY BUFFER\n");
  fprintf(stderr,"MAY_BE_SOME_MEMORY_CORRUPTION_DURING_SORT\n");
  exit(1);
 }else{
  fprintf(stdout,"%s\n",data);
 }
 printf("Test Passed For Chars....\n");
}

unsigned char FloatCompare(void *a,void *b){
 int a_int = (int)((*(float *)a)*10000);
 int b_int = (int)((*(float *)b)*10000);
 return (a_int<=b_int)?1:0;
}
void FloatSwap(void *a,void *b){
 float temp;
 temp = *((float *)a);
 *((float *)a) = *((float *)b);
 *((float *)b) = temp;
}

#include
void TestFloatSort(){
 float *data = malloc(sizeof(float)*10);
 float temp;
 unsigned int i,j,k;
 time_t test_time;
 for(i=0;i<10;i++){
  data[9-i] = (float)sin(i);
 }
 /*Randomize the input data*/
 time(&test_time);
 srand(test_time);
 for(i=0;i<100;i++){
  j=(rand())%10;
  k=(rand())%10;
  temp=data[j];
  data[j]=data[k];
  data[k]=temp;
 }
 /*Print the buffer*/
 for(i=0;i<10;i++){
  printf("%f ",data[i]);
 }
 printf("\n");
 printf("The # of elements %d\n",(&data[9]-&data[0])/4);
 RandQsort((void *)&data[0],(void *)&(data[9]),4,
 FloatSwap,FloatCompare);
 for(i=1;i<10;i++){
  if(!FloatCompare((void *)&data[i-1],(void *)&data[i])){
   printf("Test FAILED comparing %f , %f\n",
   data[i-1],data[i]);
   exit(1);
  }
 }
 for(i=0;i<10;i++){
  printf("%f ",data[i]);
 }
 printf("\n");
 printf("Test Passed For Floats....\n");
}

/*Test for floats*/
int main(){
 TestCharSort();
 TestFloatSort();
 exit(0);
}
#endif

[TECH] Perl template toolkit and Bugzilla

I have now done with the customization of Bugzilla for our internal needs, to keep track of things. The core of the idea of templates was simple

• Seperate the presentation from the code

The good thing about using Perl + TTK is that the split (presentation code and actual code) is very wide compared to any other framework which I'm aware at least from my past experience. I have used the following frameworks previously. Its a very useful add on as a skill learn more about http://www.template-toolkit.org

Have few things to fix today, Add code to SAPE_1 with the new Center of Gravity algorithm.

Cheers!
Vamsi

[TECH] Bugzilla Internals

Got back to work today !

Was looking at the Bugzilla's perl code to extend it for some of my internal work, I found that it was a expert level perl code (Object oriented) they are using several things which I never used, It was a good learning experience.

I want extract few concepts from this code

• How do all these websystem's avoid hard coding of HTML inside the code which generate's HTML dynamically (I know its kind of servlet and JSP/ASP situation), I found that these guys have some mechanism based on templates which avoids hard coding of the HTML inside the dynamic HTML generation code

I guess this is the key idea/concept behind all the code which generates HTML dynamically.

I was reading Sriram's "Advanced Perl Programming" I think its a great book the way he build's up the concepts, I was really impressed by a quote by him in the book
"It is indicative of inflexible procedural design if you find yourself using conditional statements to distinguish between object types"

I want to go out to get some lunch today :)
Cheers!
Vamsi

[NON-TECH] The old and cold feeling comes back........

I visited India from Aug10-Aug30 all those 20 days were great most of the time I was in Hyderabad, life was great in India except that there was a lot of pollution especially in Hyderabad and also overcrowded places especially because of the booming IT industry.

Some of the things I noticed have changed in India from the time I left

• The money spending power of people have increased a lot, I heard that the average salary for a undergrad is now around 5.0 lack/annum ($12.5k ), this was a huge increase compared to average of 2.4 lack/annum ($6k) which is more than double.
• The cost of living has gone up from the last year, I remember that I used to eat in a hotel called Kakatiya in Ameerpet a full meal for Rs 26.00/- the same costs Rs 32.00/- now. A bottle of mineral water went up to 13.00/- from 10.00/-
• There have been a lot of malls/multiplexes mushrooming every where in Hyderabad. I saw several existing houses being demolished and new multiplexes and malls are taking their place.
• Looks to me that almost every thing is available in India now. I was shocked to see PSP in Music World, I guess people are now getting into games market and if its true India will be a great market for selling computer games.
• In India cell phone has become a revolution I find that almost every one in the country has a mobile phone, thanks to Reliance which had a vision of making cell phones affordable to every one.

All these things are fine but my old feeling comes back again, I remember all those dilemma which I was having when I just landed in U.S went to riverside and came to UCONN, all those feeling are fresh in my mind. Well that COLD FEELING of missing India comes back again I don't know why but its back.....I feel sorry for myself I don't know what I'm up to in my life.....But I'm transforming my self to be better than what I used to be, and I believe that what ever is happening is just transformation for something better........as usual Connecticut is very lonely very quiet place, I used to go for jogging in India every day around 7-8 a.m in the morning.....

Well its life and lets face it without fear!
Cheer! Vamsi.

[NON-TECH] From Dennis Ritchie's Bio....

Some times there are far too many things for people to decide on what to do? how to excel? what exactly is our strength ? . The problem here is that people tend to be *good* in several things, but being *good* is not enough if a person who is *good* compares to some of the smartest people in the same field. All this thoughts haunt every one I found the following from Dennis Ritchie's biography here
"My undergraduate experience convinced me that I was not smart enough to be a physicist, and that computers were quite neat. My graduate school experience convinced me that I was not smart enough to be an expert in the theory of algorithms and also that I liked procedural languages better than functional ones."
see that line "I was not smart enough to be an expert in the theory of algorithms....." I guess any person at his position would never say that (even though he is not smart), I really felt this guy is TRULY a GREAT GUY, he had to be really modest and humble to say such things......
Cheers!
Vamsi.

[TECH] My Quick VIM tip of the day

To add something to every line in a file with vim
:s/^/something/gc

[TECH] FORTRAN awful stories

Well first time in my life had a chance to look at a messy FORTRAN code. I used some of the CRAY style POINTER(ptr,pointee) stuff and it looked to me its really weird.
There are several crazy things which got me irritated while writing the code

• Can you beleive that when you write FORTRAN code you must make sure that every line is no more than 80 chars, some one told me that FORTRAN had this because of the punch cards whose size limit come from there.
• Really strange that FORTRAN has no concept of global variables, and its a real pain especially when you have SUBROUTINES you will have to make a COMMON block and copy all the definitions into the SUBROUTINE, real big pain, thanks to INCLUDE which saves us.
• I found they there seems to be a huge variations in the standards of FORTRAN, there are several things 'g77' did'nt support, I used 'ifort' intel fortran compiler.
• Really had tough time figuring out the format specifiers equivalent to 'printf' for 'WRITE(6,*)'
• Last but not least FORTRAN dont have a ';' at the end of statement and its really pain when you are a 'C' programmers.
• Last++ IF conditions seems to require THEN , I figured out after writing several lines of code :(, really an Experience of writing programs in legacy languages and a real test for a real programmer.

I forgot I wanted to keep track of this piece of code, to close all the files in a program with calling close(fd) in each of fd's

fp = tmpfile();
fp->_chain = stderr;
fpclose(fp);
fp = NULL;

Take care guys!
Cheers!
Vamsi

[TECH] Memory corruption and format specifiers "%s%c" is different from "%s%1s"

I have been fixing several issues last few weeks, and the following issue in someone's code is a clear test for understanding differences between strings and char's.

On the first look "%s%c" and "%s%1s" seem very similar, but unfortunately NO! and they can create some nasty runtime bugs corrupting your variables, suppose the code existing in someone's code like this.

void BuggyScanner(){
    char buf[MAX_SIZE];
    int a;
    char b;
    scanf("%d",&a);
    scanf("%3s%1s",buf,&b);
    printf("a=%d buf=%s b=%c\n",a,buf,b);
}

The format specifier is really a blunder as scanf "%1s" is going to write beyond one byte (the extra '\0' which gets padded for strings)at the address of 'b' , since 'buf','a','b' are on the stack writing one byte beyond the address of 'b' can do really nasty stuff.

• Just as in this corrupted the variables.
• Potentially corrupt the return address of the function, creating a great security bug.

Be Careful guys! Vamsi.

[BOOKS] List of books I want to buy when I'm in india

1. The Practice of Programming (Paperback) by Brian W. Kernighan (Author), Rob Pike (Author) 2. Programming Pearls (2nd Edition) (Paperback) by Jon Bentley (Author). 3. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology (Hardcover)

I'll keep adding to this list...
Life has been through a lot of code in Matlab/Octave, Perl and C. Cheers! Vamsi.

[Perl] Don't nest your regular expressions when you use /g switch

I have been busy all these days with quite a few things, well the motive of this blog is to document some of the issues I face in my day to day work.

while($line =~ /input .*? name="(.*?)" .*? value="(.*?)"/g){
  $param_name = $1;
  $param_value = $2;
  if($param_name =~ /blah/){
    # Do some stuff
  }else{
    #Do some stuff
  }
}

The above code can go miserably wrong and hard to debug especially when the outer while loop has hundreds of lines of code in it, as you can see when we use '/g' switch in the matching all the matches within a string, make sure that THERE ARE NO NESTED REGULAR EXPRESSIONS WHEN USING /g switch

I want to become expert in one area

Some times I think what I'm I worth of? what can sell myself?
In fact I did sell myself when I created perl2exe based on my systems knowledge.
few things I think I should concentrate on
1. Parallel Algorithms (they make me to say ahaa!)
2. Systems (Drepper called me Moron! :()
3. EDA (Feels good for me).

[NON-TECH] Puppy

Pic of puppy after a fashion show in hyderabad!
IMG_0495
Originally uploaded by vamsi.

[Tech] Bitonic Sequences and Bitonic Merge

Given a Bitonic Sequence of length 2n (a motonically decreasing (inceasing) and montonically increasing (decreasing).
If we do a Bitonic merge we still of 2 bitonic sequences of length 'n' each.

void BitonicMerge(int *array,size_t size){
 int i;
 assert(!(size%2));
 for(i=0;i lessthan size/2;i++){
   if(a[i+(size/2)] < a[i]){
     swap(a[i+(size/2)],a[i]);
   }
}

What we have is now two Bitonic sequences. Doing a Bitonic sort on a parallel machines with 'p' processors and 'n' elements n >> p. Next post I'll post my code to do the Bitonic merge of the sequences.

[FUN] Top 21 things an Indian does after returning from U.S

(---  Good One!.... Just for fun---)


21. Tries to use credit cards in a road side hotel.


20. Drinks and carries mineral water and always speaks of being health conscious.


19. Sprays deo so that he doesn't need to take bath.


18. Sneezes and says 'Excuse me'.


17. Says "Hey" instead of "Hi".
says "Yogurt" instead of "Curds".
Says "Cab" instead of "Taxi".
Says "Candy" instead of "Chocolate".
Says "Cookie" instead of "Biscuit".
Says "Free Way" instead of "Highway".
Says "got to go" instead of "Have to go".
Says "Oh" instead of "Zero", (for 704, he will say Seven Oh Four Instead of Seven Zero Four)

 

 


16. Doesn't forget to crib about the air pollution. Keeps cribbing every time he steps out.

15. Says all the distances in Miles (Not in Kilo Meters), and counts in Millions. (Not in Lakhs)

14. Tries to figure all the prices in Dollars as far as possible (but deep inside multiplies by 43).


13. Tries to see the % of fat on the cover of a milk pocket.

12. When he needs to say Z (zed), he never says Z (Zed), instead repeats "Zee" several times, and if the other person is unable to get it, then says X, Y Zee(but never says Zed)

11. Writes the date in MM/DD/YYYY. On watching traditional DD/MM/YYYY, says "Oh! British Style!!!!"

10. Makes fun of Indian Standard Time and the Indian Road Conditions.

9. Even after 2 months, complaints about "Jet Lag".

8. Avoids eating spicy food.

7. Tries to drink "Diet Coke", instead of Normal Coke. Eats Pizza instead of Dosa.

6. Tries to complain about any thing in India as if he is experiencing it for the first time. Asks questions etc. about India as though its his first visit to India.

5. Pronounces "schedule" as "skejule", and "module" as "mojule".

4. Looks suspiciously towards any Hotel/Dhaba food.Few more important ones:

3. From the luggage bag, does not remove the stickers of the Airways by which he traveled back to India, even after 4 months of arrival.

2. Takes the cabin luggage bag to short visits in India and tries to roll the bag on Indian Roads.The Ultimate one


1. Tries to begin any conversation with "In US ...." or "When I was in US..."

[Tech] How to determine the bus bandwidth.

Hi recently I had a need to find out the bus bandwidth. 
The bus had 64 lines and assume that the speed of the bus is xMHz.
This implies the bandwidth = (no.of lines) * (speed of each line).
Bus Bandwidth = ((64/8)*x*10^6)/(2^20) MBytes/sec.

A simple use of this metric is suppose you have 
SMP(Shared memory processors) with a common bus
and the bandwidth of the bus is 1 GBytes/sec
and you have several processors which have an 
(memory) Instruction bandwidth of 250 MBytes/sec
you cannot connect more than 4 processors to 
saturate the bus.  

[Tech] Pathetic non unix standard matlab editor

Well I'm really pissed of this damn editor (matlab editor) , some how I cannot execute my program .m file from the command line so I had to use this matlab's editor to run my program, after using vi for long this is really pathetic, its more worse than windows I just did ctrl+c and ctrl+v it pased some junk instead of the code which I intended to paste.

[SPICE2LAYOUT] 40% Complete

Got back to the SPICE2LAYOUT project updated some Makefiles and added all the skeletal code today. By the mid of the week I should get this up and running, It also needs to have the channel router in that.
Need to get back home and study some stuff for a upcoming Friday jury.

Algorithm for Permuting in place

Problem: Given a set of numbers S = 1...n and a permutation PI(S), how can you rearrange elements in S in O(n) time with no extra space.

I don't like explaining things just code it., here's code below

#include
#include
#include
int a[10];
int b[10];

void ResetArray(){
    unsigned int i;
    for(i=0;i<10;i++){
        a[i] = i; 
    }
}
void swap_elements(unsigned int i,unsigned int j){
    int temp;
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
/*b is the swap list*/
void InplacePermute(int *perm){
    unsigned int i;
    for(i=0;i<10;i++){
        if(perm[i] < i){
            perm[i] = perm[perm[i]];
        }
        if(a[i] < i){
            perm[a[i]] = perm[i];
        }
        swap_elements(i,perm[i]);
    }
}

void PrintPermutation(void){
    unsigned int i;
    for(i=0;i<10;i++){
        printf("%d ",a[i]);
    }
}

int main(){
    int runs=10;
    unsigned int i;
    do{
        ResetArray();
        printf("Please enter the permutation of size 10, 10 unique digits from 0-9\n");
        for(i=0;i<10;i++){
         if(scanf("%d",&b[i])<=0){
            break;
         }
         assert(b[i] >=0 && b[i] <=10);
        }
        if(i<10){
            break;
        }
        InplacePermute(b);
        printf("The permutation is::");
        PrintPermutation();
    }while(1);
}

The following are testcases

7 3 2 1 4 8 9 0 5 6
8 9 1 2 5 6 7 3 4 0
1 2 3 4 5 6 7 8 0 9
1 3 4 8 9 0 7 6 5 2

Well this week has been a little productive, got the space for http://phaedrus.sourceforge.net a library of randomized algorithms
Have Fun.... Vamsi.

Passing multidimensional arrays to functions

Got enlightened by this today. And realized the following.

int a[10][20];

int main(){
 print_array(a); /*results in a crash.*/

}

void print_array(int **a,int i,int j){
 printf("%d",a[i][j]); /*How stupid this can be?*/
}

I love PHP

Have been using PHP with apache to build some stuff really like programming in this I'am in love with PHP.

[Tech] One more reason why MACRO's are Not Preferred over inlines.

...macro.h....
/***Dangerouse Macro1***/
#define print_int_value_twice(c) do{\
 printf("first time %c second time %c\n",c,c);\
}while(0);

/***Stupid Preprocessor***/
#define my_error(c) do{\
 fprintf(stderr,"Error::");
 fprintf(stderr,c);
 fprintf(stderr,"\n");
 exit(1);
}while(0);

.....macro user ....
j=0;
print_int_value_twice(j++);
/*j incremented twice by the preprocessor*/


/*In this case the preprocessor is stupid 
 not treat the string spanned across several lines
 as a incomplete macro argument and fails compilation.*/
my_error(" My error spans three lines
            line1
            line2");

Avoid MACROS start using inlines , if you define macros the users should use them with caution

[Personal] I was not good and never have been.....

Yes! today I realize my potential, I was never good in fact never have been....I accept my failure. I'm a looser, I cannot win and never have won and in fact I'm obliged to life for letting me live and eat what ever I want and wear what ever I could....in the midst of bitter shame....I gave up...I don't want to live as a looser...I will soon end my life and this blog may be the last. I was never honest to myself I have things which I don't deserve. And I get emotional for small things...what else a looser can say except bending down head in shame.

[TECH-NON-TECH] SPICE2LAYOUT should I use BGL?

A Warm Welcome to a great new year 2007! This is my first blog after 24 days in the new year. Last time I had written my blog was on Dec 31, 2006, well this was the coldest new year eve I had. I just went to bed on Dec 31 night 2006. Its because I was with puppy taking care of puppy...we were really afraid on whats going to happen next....but it was great what happened next day was really a new begining in a new year things went excatly how I wanted (In fact I did'nt know what would be the best solution and just prayed "God! Please do something so that I will be comfortable after that")...a great going new year 2007 from there on, really had great time in Hyd from Jan-1 to Jan-6.....after that I took pathetic AeroSvit flight (Never Ever Take this shoddy airline) back to JFK, travelled all the way from NewYork to Hartford and took a cab to my place....its quite a tiresome journey to travel from India to U.S, next time I will travel by either BA ,Lufthansa or Emirates..... Now I need startoff my coding for the SPICE2LAYOUT project its been a while I took a break and its really a long one....Tomorrow Is a SRM from TopCoder....I was having a dilemma to use Boost Graph library or not...but I guess it will be fine if I write it on my own. Take care...keep Warm :) Cheers! Vamsi

[PERSONAL] Lets solve the problem.....

"Lets solve the problem" , thats what I have been saying to myself for all these days. Well I have decided never to budge and just take the things the way they come..just bought my copies to the Art of Computer Programming. For me right now there are no shortcuts, no quickies I have to take the things the hardway or the toughway more specifically.
I guess I have become a little bit more matured now, because I have to do things more responsibly now. I have a big responsibility now, I don't worry about it but I welcome it into my life, I'am ready to solve it and all the consequences...I will never run-away from the problem. But I need to be a little bit more practical also, well for any problem now there is no way out except to solve it.
So...LETS SOLVE THE PROBLEM RATHER RUNNING AWAY FROM IT....
And when you are solving problem's you need to be very methodological...I know its all spelling mistakes my blog...I may not be a great genius but I'll try my part to solve the problem. And when I solve the problem there will be no shortcuts.
Frankly I have been not getting great results for my Dynamic Programming based Border Length Minimization Problem. What to do I don't know I cannot really fake up any results. It's bad really bad. I leave it
Today puppy came out, she has been not liking the place where she is living but she has to for sometime, she should feel free and I'am a very lucky guy interms of that. I will always care for puppy and will solve the problem and not run away from it.
Happy new year 2007.....LETS SOLVE IT....that's the quote of this year.
Take care guys and keep having fun.....mean while I will lay back and keep thinking....

[NON-TECH] Travelling to india....

I should be indeed thankful to sudha for a ride from Storrs to Stamford. When I reached Stamford it was a little difficult to find out where ravi is and finally found ravi, went to circuit city to buy some stuff, later toured manhattan,brooklyn went to a great Italian restaurant, I really liked the hot bread and that olive oil to eat the bread, I never tried any Italian food apart from the normal pizza. Its really windy today in New York with -7 Centigrade, really had a hard time pulling all my luggage into the airport.....well found a wireless connection at the food court here, IT WORKS...well I'am writing this from that connection only, I need to wait till 4:00 PM to take my flight. Its a long wait.

Good that I got some charge on my laptop so that I can do some work today, I have many things pending, mac,tim,ion and raj. I need to get all the work done in this break good if I could make a proper schedule to fix up all the things.

Lets see how things work......luv....Vamsi

I have not started any packing

Its just 12 hours for my flight I have not packed any thing .....dont know how I will pack....I think in have insomnia I cannot sleep its killing me every day its 4:00 AM in the morning I have been trying to sleep for last 4 hours but failed miserably. God please gimme some sleep please....it would have been great if we could buy sleep :((

[TECH] Algorithm to find euler circuit in a graph in O(|E|)

Important observation I found is that, if we delete a cycle (delete all the edges which form a cycle) from the graph which has a Euler circuit, the property of the graph still remains, i.e the necessary and sufficient condition for the graph to have a Euler cycle is that every vertex should have even degree. And also there has to be a cycle at every vertex.

INPUT: G =(E,V)
v = v
euler_cycle = NULL;
while(|E| > 0){
 /*Find a cycle in G, start
   the search at v, returns c0 around 
  which cycle is formed*/
 c0 = FIND_CYCLE(G,v);
 v = GET_NON_ZERO_DEGREE_VERTEX(c0); 
/*Above can be done in constant time,
 using some space while finding the cycle
 */
 MERGE(c0,euler_cyle);
/*constant time operation,
 put c0 after an edge e1 in
 euler cycle which ends at 
 vertex 'v', we can just remember 
 the position of v n euler_cycle
 every time we merge*/

}

[TECH] Building tags on the complete source code...

I see that sometimes

  $ctags -R *  

don't work. I just typed
$ctags -R *
in my cygwin it crashed

 ctags.exe.stackdum 

. Well now the question is how do I build the tags on the complete source recursively if

  -R 

don't work, we can use the the following to build the tags

$find . -name "*.c" -exec ctags -a \{\} \; -print; sort tags > tags1; mv tags1 tags;

The -a option appends to the existing tags file build

I initially thought that ctags keeps some seek information of the file in tags file,but just was amazed its a 3 column multientry text file, the first column is the tag which you are searching, second column is the file where is tag is and the most interesting part the 3 column is the search string for vim....hmmm see every one takes advantage of the plethora of things vim can do :)

Make_bp_profile ./RNAlib/ProfileDist.c  /^PUBLIC float *Make_bp_profile(int length)$/
Make_swString   ./RNAlib/stringdist.c   /^PUBLIC swString *Make_swString(char *string)$/

.........luv.......Vamsi

[TECH] Never use a file stream for lookahead reading while using lex.....

Just got the parser working....I did a lot of modification to mac's code, especially the grammar rules which have the lookahead information while parsing. The code tries to read from the

yyin

file stream of lex, but that is really pathetic because lex code is now optimize and it position in the lex buffer may not correspond to the position in the filestream...well this is what is the bug in code, well it took a while to fix. But its a good one.

I added lookahead rules

(st,bt)\n[\+]{linenum++;}
(st,bt)\n[\*].*${linenum++;}

for lookahead extensions and comments in the spice syntax.

Tomorrow I'll get the layout printed ,,,,,,

Apart from this folks from india called and were telling me about the issues regarding priya pickles, well I think its really a slander against Ramoji Rao, any way I support this guy...yes may be after that great 3 day party at ramoji film city makes me baised, I guess you too will be baised once you receive that wonderful hospitality at hotel sitara in ramoji film city...when our team (verification group) went out there I saw mithun chakraborthy

..........luv..........Vamsi

[TECH] SPICE layout generator.......

I have been a bit of slackish this week, but sure I want to start running soon.

Last night I read about the BPlane (Binned Plane datastructure used in micromagic, I need to implement that in magic soon).

Tonight, I thought about backing up my CVS repository regularly into my external hardrive, so that I can keep all my projects safe.

SPICE Layout generator

My new project, which generates cell layout from by reading from the SPICE files (transistor netlist) directly. I need to rewrite some of the code for the algorithm which tries to find the EULER trace in the transistors graph (and also its p-stack dual graph). Its exiting for me start it today....

I'am in love with my life for the first time.......writing code is what I loved apart from all other tensions in life I love it

Tomorrow morning I'll be running for the sale in circuit city and best buy

[TECH] SRM327

http://www.topcoder.com/stat?c=problem_statement&pm=6871&rd=10007

/*
 * topcoder_class1.java
 *
 * Created on November 22, 2006, 1:41 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package topcoder_srm1;

/**
 *
 * @author vamsi
 */
import java.lang.Math;

public class NiceOrUgly{


   
    private boolean checkNice(char[] s_arr,int len){

 int vcount=0;
 int ccount=0;
 int i;
 for(i=0;i


I challenged some guy in this SRM  got 50 bonus points.

..........luv......vamsi

[TECH] DAG's and Dynamic Programming......

Directed Acyclic Graph (DAG), directly embeds into dynamic programming....as from Vazirani's notes, the useful property of the DAG is that its nodes can be linearized (topologically). So if we process these nodes in the topological order we have sub-problems solved and the solution can be used for the next level. In the simple example of shortest path, we need (u1,v) , (u2,v) are the edges adjacent on the node v. To solve the shortest path problem we need the shortest path to u1, u2 to get the shortest path to v. The wonderful property of the DAG's is that if we start with the topological SOURCE (may be hypothetical by adding 0 weight edges), we are sure that we solved u1,u2 before solving v (if we process the nodes in topological order)

Longest monotonic subsequence in a given sequence, suppose the given sequence is '5,2,8,6,3,6,9,7' (The longest monotonically increasing sequence) in this is 2,3,6,9. On the first look, it appears that it doesn't have sub-optimality inside it. In the sense take a subsequence '5,2,8' the longest monotonically increasing subsequence in this is is (5,8) or (2,8) but neither (5,8) and (2,8) is not in the overall longest monotonic subsequence, so the question is how dynamic programming works here??.....well people don't talk about the sub-optimality here......but still this can be solved by dynamic programming...
Let me restate the principle of optimality here...."If a optimization problem involves of sequences of decisions d1,d2,d3,d4...dn . The principle of suboptimality states that what ever decision you make initially the rest of the decisions should still optimize whats remaining after making decision d1...i.e would form a sequence of decisions to save a smaller optimization problem
Any way I wrote the following code segment , S[i] = length of the longest monotonic subseqence ending at index i, input is a array of integers A[i].

global_max_length=-INFINITY;
PATH[N];
for(i=0;i0;j--){
      if(A[j] < A[i]){
         if(S[j]+1 > S[i]){
             S[i] = S[j]+1;
             if(S[i] > global_max_length){
                 global_max_length = S[i];
                 PATH[N] = j;
             }
             PATH[i] = j;
         }
      }
   }
}

void printSeqence(){

 int j=N;
 do{
  print("%ld ",A[PATH[j]]);
  j = PATH[j];
 }while(j!=PATH[j])

}

global_max_length , returns the length of the longest monotonic increasing sequence, and also prints the sequence

Apart from this life has been very cold, man today was REALLY_ __FREEZING__ here, I have cold the damn cold, I cannot drink cool drinks, eat any cold stuff it sucks......Well , I'll be going to India soon meet swapna,chamu...just talked to chamu on the phone, hope to see her and swappy soon...............THE LIFE GOES ON ON ON...by the way the GYM is closed till 26th and its cold outside I cannot even jog its really HELL out here

With love ...............Vamsi...............

[TECH] Channel Router for cell synthesis......

Its quite an effort to get this thing working.....started on saturday night , worked on sunday, and monday night its done

perl had lot of kookups especially my $a,$b and my ($a,$b) are not the same, I pulled it from the manual. sometimes its really hard to fix this kind of errors, thanks for that wonderful debugger 'perl -d' , its really great to work with.

But I did'nt see if perl debugger has a backtrace kind of facility? just a gdb?

Life apart for my passion of the CGEN2MAGIC project, is quite slow need to study a lot about that Border Minimization Problem, also got the home work done on parallel algorithms and network flows.

I guess I'have started loving algorithms/problem solving...its really kewl

Take care....HAPPY CHILDRENS DAY.

[TECH] Setting up VNC on LAN

Today I got my laptop dell-inspiron-640m, I have linux desktop running fedora connected to a wireless router which my friend uses, so totally we have 3 computers connected to the wireless router. Actually we have cloned the MAC address of my desktop onto the wireless router. Now I want to use my laptop and start working with vnc on my desktop. By default the port 5901 was firewalled, I had to setup the firewall to accept the tcp:5901. After which I had the probelems with the window manager, by default kde starts the twm& . So I edited the xstartup file to get the kde.

kwin & kdesktop & kicker &

You need all the three things to get the kde desktop up and running

Well thats all the infrastructure work, now I'am back to write the CHANNEL ROUTER for CGEN which I have not worked on for the last three days, due that motif-algorithm which I have been working on, last week I also had the polynomial algorithm for FINDING OUT ALL THE CUTS in the network flow graph.

Take care guys, I also had a long chat with swapna and that was really wonderful.

[TECH]Crippled mmap

I was trying to use a anonymous memory mapping to use in the first version of the Tile database memory manager which I was writing,

mmap(void *start_address,size_t length,int prot,int flags,int fd,off_t offset)

. I had prot = MAP_ANONYMOUS , (I thought its equivalent to MAP_ANON | MAP_PRIVATE , the man page says MAP_ANON , is depreciated). Well any way I got it fixed by MAP_ANONYMOUS | MAP_PRIVATE.

Last time I had problem with this syscall is when I need to mmap to actual address's , i.e the start_address argument is not NULL, once again WHEN YOU DO A MMAP FOR A STATIC ADDRESS YOU NEED TO HAVE OFFSET OF THE FILE ALIGNED TO THE PAGE BOUNDARY.

Fridays seems to coming very quickly.

I dont know why Fridays seems to be coming so quickly for me? I'am doing less work?.

A melancholic 24th birthday....but I think I have started to think

Just added a year of life's experience, its really the coldest birthday I had ever had, it really feels lonely here. Nothing to smile about except the fall colors to cheer up missing all my loved ones back home, sometimes I feel I don't like it here(infact any where away from home)....
The other day I was returning back from the bus I broke within my heart, I knew I was a little more capable of getting into a better school, all my friends I have studied are now in better schools and me at UCONN making that hasty desicion to move from UCR....
I could certainly feel that I have a really hard luck, I don't know I think I have a nac for the SELF PITY for myself...first time in my life I feel I need to compromise, really I feel very low every day dont know why. May be I'am missing people very much, more than I could ever think of...mom told me to come back to india if I dont feel good here....you know at the same time I feel that by doing that I'am running away from the problem, ok now I'am in the problem a big complex problem the only way I can overcome this just by solving it....I say to myself I'AM TRANSFORMING TO MYSELF TO ATTAIN STRENGTH AND ENERGY TO SOLVE PROBLEMS....God please give me STRENGTH to face this problem. I know that I'am not a genius to come up with some idea to create a revolution but I'am trying sincerely...I don't do things to impress any one...
I don't feel any selfish any more the other day I was thinking about the change in me, I don't know I started feeling happiness in others happiness, sometimes I just did things that people are happy, although I don't expect anything from them.....
What ever it might be its really a rocky ride ahead of me....

[TECH] Buffer insertion and signal integrity.

10-09-2006...if we add up all these its a perfect modulo of nine. Well today I started my research. Studied the classic "Buffer Insertion Algorithm" paper, its really great I the moment I read it I see the application of dynamic programming in it.
Well its a well studied problem after all this should have been done, but I'am loving it application of algorithms. The basic principles I need to stick to is honesty. I want to carry on like this feel good about it every day I sleep.....Well Its becoming a habit for me.
Delay modeling is a totally different research area, but the classic paper assumes a simple Elmore delay modeling...I guess I need to design a good algorithm which strikes a right balance on delay estimation and timing minimization.
Apart from that I wanted to see how much I can think backward. I tried to recall what I have done in my last few new years.
2006--> Partied in escape pub, hyderabad [I got a wildest dancer prize :)]
2005--> Freaked out on the roads boozing, my friend veeru with me he was annoyed a little that day :(
2004--> Well I was interning at Oracle this time, drank bacardi and made a mess, I guess I was frustrated that I was not having a grilfriend :))
2003--> Well I was with my parents in railclub. 2002--> I think I did nothing, but tasted beer for the first time...

Cheers! Vamsi

Yes I cannot cheat myself......I never had...I'am proud that I was myself

Well I always had that guilty feeling in me every time I told everyone that I'am going to california and study. Every one thought that its some how great to belong to california, well pheadrus in me was I guess taking a break...started to enjoy the material pleasures and forgot about his journey which is the quest of quality. Yes indeed I wanted to cash on the name of UC .
Although I couldnt blame the professor for bringing me this far I need to blame myself. I know I want to do more fundamental things rather then jumping in something which I claimed to know, I told people that I had been working in a mixed signal simulation tool development. The word DEVELOPMENT here meant a different thing, I never really wrote anything core, what I was doing was just doing all system realted work to make the tool work. Well I guess I was somewhat doing well in what ever I had done. When I got admission at UCR with this background I started feeling guilty, I want to make up for it by looking into books on how fastspice was implemented, although I had a very high level of understanding on how fastspice worked I thought I could make it and decided to come to riverside. But when I talked to the professor I felt bad that he want to make use only programming skills which I had, he never expected me to design new algorithms, create new paradigms to revolutionize the research. Just at this moment I decided to leave this place RIVERSIDE. I CANNOT JUST DO SOMETHING JUST TO BELONG TO A UC AND BELONG TO CALIFORNIA AND TELL THAT PROUDLY FOR ALL THE PEOPLE OVER THAT WORLD...........I THOUGHT I'AM CHEATING MYSELF I CANNOT TAKE IT I DECIDED TO MOVE TO UCONN.
I know Dr.Raj was a great prof but people dont want me to go there when I said I got admit in a UC, well now I really dont give a damn shit on which university I belong I want to really learn the ART OF ALGORITHM DESIGN and apply in much more elegant manner with more CS pedagogy.....I FELT IF I COULD MASTER THE ART OF SOLVING PROBLEMS WITH A COMPUTER.....IT DOESNT KEEP MYSELF JUST TO CAD I CAN APPLY MY ALGORITHM DESIGN SKILLS TO ANY PROBLEM....I'AM EXCITED TO WORK UNDER DR.RAJ....
Well this is excatly what happens in pheadrus's book.......BUT I ADMIRE MY GUTS TO NOT TO CHEAT MYSELF EVEN TILL THE LAST MINUTE....ITS NEVER TO LATE TO GET IT BACK....,,,,,,NOW I NEED TO LIE SAYING SOMETHING TO THE OLD PROF AND MAKE SURE THE BRIDGES ARE NOT BURNT......

Problems for which "Principle of Optimality" does not hold??

For many optimization problems we take for granted that DP (Dynamic Programming works). But the first thing we need to check before we use the DP technique is the "Principle of Optimality".
o If the aim of a descision sequence(d1,d2,d3,d4........dn) is to minimize/maximize some objective function, then for any di , 1<=i<=n , the subsequence (di,di+1,....dn) should also minimize/maximize the objective function respectively.
o One problem for which the "Principle of Optimality" is when we have a KNAPSACK problem which both negative and postive profits, we might well ask ourself if a Item has negative profit then why we select that Item? well you might have forgotten the other factor which is the size of item...
I dont know of any other problems.

[NON-TECH] Marriage is buying conditional LOVE its for loosers, unconditional LOVE is what winners get.

Well, have seen several guys getting married these days in india. I don't know some how people in india always think thats the ultimate thing. I have heard many people definition of SETTLING in life is something like "I neeed to get a high paying job, have a house a car and a beautiful wife and have children".....
I just think its bullshit if you marry you get to loose the fire in you, I just don't beleive in SETTLING in life. I just believe that "ITS JUST A JOURNEY which goes on and on and on......." , I don't think there is a destination where you think you have reached the NIRVANA and just bullshit marry and have SEX.....
I live a life for myself, I just beleive I just want to be happy without causing others any trouble (ofcourse envy and jealous are some thing I cannot help).
Any way reiterating things my aim is just to create technology for real good, not for building research papers or making a huge sum of money. Feel technology as an art and contribute without any motive. Some time I see that people tend to use my high energy levels, thats what I tell myself "Don't take it damn seriously, when can people expolit something ? if something is in abundance (high energy here) people exploit it. If I crib about people who expolit I'll loose my abundance of energy, I want more people to exploit me so that indirectly they are helping me to create a lot of abundance of energy to create things...."
Well if I keep all things aside (all but technology), people's egoes, money, holidays etc... life just ROCKS for me I love it.

Yet another memory corruption on linuxipf, new FAT POINTERS on IA-64

Well its really gruesome last two days, was haunted by this problem in which my program on IA64 gets stuck just before the exit, I drilled down to _IO_flush_all @@ glibc which is not returning. After a elegant investigation found that a memcpy into a invalid address cooked up all this it basically created a cycle in FILE *ptr->_chain which is the reason why _IO_flush_all was not returning..
Well IA-64 had been a real good thing to work with, it has a real helpful kernel maintainers especially at ia64-linux@kernel.org, Well these guys gave me a lot of insight into several things RES backing store [60000fff80000000-60000fff80004000 rw-p 0000000000000000 00:00 0] this segment maps for every process on IA64 kernel.
Well other intresting thing is about the FAT POINTERS, the IA64 ABI mandates that the call to functions should be done via FAT POINTERS. do a google search if you want more details about this....
All in all a good productive week also fixed a couple of HSIM issues..
I really love it.

IA64 different virual memory layout

Hey just found that the IA64 is having a totally different mmap space and start of the text generally text start at 0x08048000 but here it starts at some 0x400000000000000. and also the mmap space is above &_etext in contrast to below &_end.

How SIGINFO structure makes our life easy...

Well have been fixing code failing due to SIGFPE, The code was written to handle all signals like (SIGBUS,SIGFPE,SIGSEGV....). Well the culprit is SIGFPE which generally happen due to compiler optimization, the tricky thing is that I dont recevie SIGFPE when I run this through a debugger, it happens only when I run it normally.
Writing siginfo handlers will help you get the culprit virtual address which causes the problem. See the following handy code.

=======================================
struct sigaction action;
action.sa_sigaction = my_handler;
action.sa_flags = SA_RESTART | SA_SIGINFO | SA_RESETHAND;
if(sigaction(SIGBUS,&action,NULL)<0) {
printf("Cannot register handler\n");
}

HANDLER:
void my_handler(int sig,siginfo_t *siginfo,void *ucontext){
if(sig == SIGBUS){
printf("SIGBUS Caught\n");
switch(siginfo->si_code){
case BUS_ADRALN:
printf("SIGBUS due to address alignment at %x\n",siginfo->si_addr);
break;
case BUS_ADRERR:
printf("SIGBUS due to BUS_ADRERR%08lx\n",siginfo->si_addr);
break;
case BUS_OBJERR:
printf("SIGBUS due to hardware\n");
} q

Cheers! V.

Gives some solace.....

I have been thinking that I have reinvented the wheel, I had that guilty feeling when I did'nt use _etext , _edata , _end to figure out the begining and end of .data and .bss sections, which I rather got from the ELF sections. I had a feeling that I reinvented the wheel until I tested the code with _etext , _edata and _end they seem just SCREW....My method was and elite one I love it...I'am really happy. I love it. Now I realize how its a different feeling when you do things really right from your heart, other day after my workout (obviously with a lot of sweat, I generally jog for 33minutes cover 3 miles and burn 500 CAL) I was talking to arindam. I really liked what this guy said. He said "Workout spirit is something you need to get right from your heart just like a 100m sprinter......Theres just no showoff" WOW I liked what he said thats what I'am after in my life be it technology or art or just life.... KEWL V.

ELF CORE file optimizations in Linux, problems with non standardization of core files.

Well, all these days life is revolving on BINARY RECONSTRUCTION from the corefiles(although this is only one of the ideas I have currently for BINARY RECONSTRUCTION).

o After my deep observation of the fact why core files have some program headers which have phdr.p_filesiz==0, found that David Miller, had added some changes to the core file which the linux kernel dumps, the optimizations are ofcourse to reduce the core file size, so I guess these guys are taking off the text part of the executable and the text part of the dyanmic shared libraries.

o My Question is WHY?? WHY?? do these people just dont try to stick to standards (if some standard dont exist they should create one, and once they enhance some stuff then update the standard rather than just flushing the changes into the code), in this opensource community this is really bad that the current standard of the core file depends on few induviduals.

I checked the PHDRS (readelf --segments) the following are the PHDRS of the core.exe

=================================
Elf file type is EXEC (Executable file)
Entry point 0x8048364
There are 11 program headers, starting at offset 52

Program Headers:
 Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
 NOTE           0x000194 0x00000000 0x00000000 0x00a48 0x00000     0
 **LOAD           0x001000 0x08048000 0x00000000 0x00000 0x01000 R E 0x1000

 LOAD           0x001000 0x08049000 0x00000000 0x01000 0x01000 RWE 0x1000
 LOAD           0x002000 0xf649b000 0x00000000 0x01000 0x01000 RWE 0x1000
 **LOAD           0x003000 0xf649c000 0x00000000 0x00000 0x132000 R E 0x1000
 LOAD           0x003000 0xf65ce000 0x00000000 0x03000 0x03000 RWE 0x1000
 LOAD           0x006000 0xf65d1000 0x00000000 0x03000 0x03000 RWE 0x1000
 LOAD           0x009000 0xf65e8000 0x00000000 0x01000 0x01000 RWE 0x1000
 **LOAD           0x00a000 0xf65e9000 0x00000000 0x00000 0x15000 R E 0x1000
 LOAD           0x00a000 0xf65fe000 0x00000000 0x01000 0x01000 RWE 0x1000
 LOAD           0x00b000 0xfeffe000 0x00000000 0x02000 0x02000 RWE 0x1000
===================================

o As I said earlier I see some of the PHDRS are having FileSiz as zero, the
first (1st **ed ) PHDR which is having virtual address 0x08048000
(this is obviously) the start of the text of the program, and its not
having any memory in the core file.

o The other PHDRS for which FileSiz is zero correspond to the
dynamic shared objects (.so) text , example in the above we see (2
**ed ) PHDR with VirtAddr as 0xf649c000 , so this means the text of
some shared .so has been mapped here.

o I had a question about the memory mapping with permissions r--s or
r--p (gconv used by glibc gets mapped like this some time) , so does
the core file contains this information of the memory mappings? IMO this content
is also mapped as PROGBITS I guess not sure.

o Is there a way I can findout the standard which the OS follows to
write the core file? No absolutely no, solaris dumps the entire core.

o Rather than depending on the OS core file, hows your opinion on
writing out all the mappings form /proc//maps as PT_LOAD into a
elf formatted file of type ET_EXEC, do you think this works? rather
than converting core file to exe?

Should I start working to write the standard.

=======================================================
#include
#include
#include
#include
#include

#ifndef __64_BIT__
#define __32_BIT__
#endif

#ifdef __32_BIT__
#define ELF_EHDR Elf32_Ehdr
#else
#define ELF_EHDR Elf64_Ehdr
#endif

ELF_EHDR place_holder;

/*Chages the elf_header in the file with ptr */
int ChangeElfHeader(int CoreFd, int WriteFd, unsigned long vaddr){

     unsigned long got_len=0;

     if((got_len = read(CoreFd,&place_holder,sizeof(ELF_EHDR)))
             != sizeof(ELF_EHDR)){
             perror("Unable to read the ELF Header::");
             exit(1);
     }
     /*Change the ET_CORE tto ET_EXEC*/
     if(place_holder.e_type == ET_CORE) {
             place_holder.e_type = ET_EXEC;
     } else {
             fprintf(stderr,"The file is not of ELF core file");
             exit(1);
     }

     /*Change the entry */

     place_holder.e_entry = vaddr;

     /*Write back the header*/
     got_len = 0;
     if (( got_len = write(WriteFd,&place_holder,sizeof(ELF_EHDR)))
             != sizeof(ELF_EHDR)) {
             perror("Unable to write the header::");
             exit(1);
     }
     return 1;
}

static void finishWriting(int coreFd, int writeFd) {

     unsigned char write_buffer[4*1024];
     int got_len = -1;

     while( (got_len = read(coreFd,write_buffer,4096)) != 0) {
             if(write(writeFd,write_buffer,got_len) != got_len ){
                     perror("Unable to to write the length which was read:");
                     exit(1);
             }
     }
     close(writeFd);
     close(coreFd);

}

int main(int argc,char* argv[]){

     int coreFd;
     int writeFd;
     unsigned long vaddr;

     if( argc < 3 ) {
             fprintf(stderr,"Usage core2elf core.file exe.file.name");
             exit(1);
     }
     if( (coreFd = open(argv[1],O_RDONLY)) < 0) {
             perror("Unable to open the core file:");
             exit(1);
     }
     if ((writeFd = open(argv[2],O_WRONLY| O_CREAT)) < 0) {
             perror("Unable to open the write file::");
             exit(1);
     }
     sscanf(argv[3],"%lx",&vaddr);
     ChangeElfHeader(coreFd,writeFd,vaddr);
     finishWriting(coreFd,writeFd);


}
====================================================

My F1 student visa.....

Wow its been couple of weeks of unavoidable personal work I was busy with, although I got a full support I had to do all the formalities to get enough documentation that I'am not a potential immigrant. Well it costed me my valuable time and also money (Thats OK) but not time. The Visa officer was a nice lady she just saw my I-20 and my Transcripts and approved my visa... Well now I'am alleviated of this pain which is unavoidable for any student who is going to U.S. The only thing I have learned from all this excercise is JUST FINISH IT OFF, THERE IS NO WAY OUT. VAMSI.

Life through ELF loaders.....

Hey its a long time I have been blogging...... yes its really a tough last two weeks. From last two weeks I have been trying to get a work around to the 'exec-shield' problem we were facing. I have got a lot of new ideas on implementing this. The following are some of the them pretty generic though
o My current problem boils down to create a executable from the running program itsself. To get this working I have been studying the kernels code in 'fs/binfmt_elf.c' especially code around 'load_elf_binary', The following are my finding might find it useful (for myself to look after some time).
-----1.)The kernels loader does not do any great , it basically gets all the metadata from the elf headers and just does the dirty work of just mapping and transferring the control. The summary of what excatly the kernel does is
a.) set the entry point from the (Elf32_Ehdr *).e_entry as the start jump to the program
b.) Load all the segments (PHDRS) the loader just deals with the program headers, it does not use any section headers. It loads all the segments with type (Elf32_Phdr *).type == PT_LOAD. If you do a 'readelf --segments a.out' you can see the segments

(gdb) shell readelf --segments a.out

Elf file type is EXEC (Executable file)
Entry point 0x80482a0
There are 7 program headers, starting at offset 52

Program Headers:
Type           Offset   VirtAddr   PhysAddr   FileSiz MemSiz  Flg Align
PHDR           0x000034 0x08048034 0x08048034 0x000e0 0x000e0 R E 0x4
INTERP         0x000114 0x08048114 0x08048114 0x00013 0x00013 R   0x1
    [Requesting program interpreter: /lib/ld-linux.so.2]
LOAD           0x000000 0x08048000 0x08048000 0x004cc 0x004cc R E 0x1000
LOAD           0x0004cc 0x080494cc 0x080494cc 0x00104 0x00198 RW  0x1000

DYNAMIC        0x0004dc 0x080494dc 0x080494dc 0x000c8 0x000c8 RW  0x4
NOTE           0x000128 0x08048128 0x08048128 0x00020 0x00020 R   0x4
STACK          0x000000 0x00000000 0x00000000 0x00000 0x00000 RWE 0x4

Section to Segment mapping:
Segment Sections...
 00  
 01     .interp
02 .interp .note.ABI-tag .hash .dynsym .dynstr .gnu.version .gnu.version_r .rel.dyn .rel.plt .init .plt .text .fini .rodata .eh_frame
 03     .data .dynamic .ctors .dtors .jcr .got .bss
 04     .dynamic
 05     .note.ABI-tag
 06
(gdb) 

c.) One more important thing about how excatly it sets the 'brk' base I guess to set up the 'brk' base the kernel only (also see the copy of the email posted on linux-kernel mailing list

Hello All,

I have been working on an idea of creating an executable from a
running process image.

MOTIVATION:
Process migration among the nodes in distributed computing,
checkpointing process state.

BASIS:

The basis of my idea would be update the existing executable with
extra PHDRS (Program Headers) with type PT_LOAD and each of these
headers corresponding the vaddr mapping from /proc//maps.

I have done some basic study of kernels loders code in
'fs/binfmt_elf.c' especially code in 'load_elf_binary' function, the
following is my understanding.
-----------------------------

bss=0;
brk=0;
foreach (phdr in elf_header){

if(phdr->type == PT_LOAD){
if( phdr->filesize <>memsize){
/* Segment with .bss, so update brk and bss*/
}
else {
/* Just map it*/
}
}
/*Update brk bss*/
}
------------------------------------

from the above the kernel is updating brk, thus creating the start of
sbrk(0) only when it sees a PT_LOAD segment with filesize less than memsize. 
The kernel will set brk base i.e sbrk(0) to the value phdr.vaddr+phdr.memsize 
of the last PT_LOAD
segment its mapping? so do I need to reoder my PT_LOAD segments so
that the heap goes as the last PT_LOAD segment?

Is there any way we can tell the elf loader to force the vaddr for
sbrk(0) i.e brk base ?

Let me know your suggestion on this idea?

Really appreciate your valuable comments.

Sincerely,
Vamsi

[PS: I dont know if some one has already implemented this idea??]

-----2.) Also found out that the virtual address's for the sections in the segments are the excat virtual address if they are within the range of corresponding phdr. that is I found that if .bss section has a vaddr of 0x00001000 and .data has 0x00000010 and there is a corresponding mapping (rw-p) in /proc//maps as 0x00000004-0x00010000 which includes segment to section mapping in the order '.data ...... .bss' note that .data will not start at 0x00000004 it infact still starts at 0x00000010 same with .bss. This is very logical since if the kernel's loader changes the mapping of the .data section the all the code referencing the virtual address's has to be changes. So the segments in /proc//maps file are not the segments excatly corresponding to 'readelf --segments a.out' infact they are bigger carousels with wrap around the the excat segment address's for page alignment.
More ideas next time..........
Cheers
Vamsi