Monday, December 31, 2007

[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

Tuesday, December 25, 2007

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


Friday, December 21, 2007

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

Wednesday, November 28, 2007

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

Friday, November 23, 2007

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

Wednesday, November 21, 2007

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

Saturday, November 10, 2007

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

Saturday, October 27, 2007

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

Tuesday, October 16, 2007

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

Monday, October 08, 2007

[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

Friday, October 05, 2007

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

Thursday, September 20, 2007

[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


Saturday, September 08, 2007

[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

Monday, September 03, 2007

[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

Sunday, September 02, 2007

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

Thursday, August 02, 2007

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

Tuesday, July 03, 2007

[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

Thursday, June 28, 2007

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

Tuesday, June 19, 2007

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

Saturday, June 09, 2007

[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

Wednesday, April 04, 2007

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

Wednesday, March 21, 2007

[NON-TECH] Puppy


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

Thursday, March 08, 2007

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

Monday, March 05, 2007

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

Tuesday, February 27, 2007

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

Thursday, February 22, 2007

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

Monday, February 19, 2007

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

Sunday, February 18, 2007

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.

Thursday, February 15, 2007

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?*/
}

Monday, February 12, 2007

I love PHP

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

Tuesday, January 30, 2007

[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

Monday, January 29, 2007

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

Wednesday, January 24, 2007

[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