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