C/C++ teaser

This is not very difficult. But just have a look.

1. Predict the outcome
#include < stdio.h >
main()
{
int a=0;
printf("%s",a);
}

2. Predict the outcome
#include < stdio.h >
main()
{
int arr[]={2,3,4,5,6};
int *iptr=arr;
iptr++;
printf("%d",*(iptr+i));
arr++;
printf("%d",*(arr+i));
}


3. Predict the outcome
#include < stdio.h >
main()
{
int arr[]={2,3,4,5,6};
int *iptr=arr;
int i=0;
printf("%d,%d%d,%d",*(iptr+i),i[arr],arr[i],*(arr+i));
}


Please answer the questions as comments. The answers will be posted soon.

Thanks
Layman

Art of computer programming -Sorting #3

Shell sort
For any sorting algorithm that moves only one position at a time , then the running time will always be proportional to n^2. Hence the idea was struck to make larger leaps rather than small ones. The small leaps is one of the prime reasons for insertion sort's low efficiency. And Donald Shell proposed shell sort.
Now you will be wondering how to choose he leap/step size. In shell sort we can start with an arbitrary step size in the first pass, after every pass the step size decreases. Hence shell sort is also known as decreasing increment sort. We'll take an example. In the first pass, let the step size be 8.
So during first pass element 0 is compared with element 8, element 16 , element 24.....element n.....element( n+8) etc. During second pass the increment is reduced to 4, so element 0 is compared with element 4, element 8........element n, element(n+4) etc. In the third pass increment size be 2, comparison will be between element 0, element 2, element 4....element n,element( n+2) etc. And finally increment becomes 1 in the last pass. In the last pass element 0, element 1, element 2 ....element n, element (n+1) etc is compared.

This is how the shell sort operates. During each pass the elements being compared are re-arranged in sorted order,ie, if element i and j are compared the position of i and j are rearranged so that the series i,j is in sorted order.

Points of interest
Like the insertion sort it has best case of O(n) hence its suitable to check whether an array is sorted or not.
Choosing the increment sequence is a tricky question. If you are concerned about the efficiency I have few recommendations for you:
The Sedgewick increment sequence..
, or ......
The best known sequence according to research by Marcin Ciura is 1, 4, 10, 23, 57, 132, 301, 701, 1750


Algorithm:

input: an array a of length n with array elements numbered 0 to n − 1

inc ← round(n/2)
while inc > 0 do:
  for i = inc .. n − 1 do:
      temp ← a[i]
      j ← i
      while j ≥ inc and a[j − inc] > temp do:
          a[j] ← a[j − inc]
          j ← j − inc
      a[j] ← temp
  inc ← round(inc / 2.2)

Worst case performance : Depends on the leap/step size sequence
Best case performance : O(n)
Average case performance : Depends on the leap/step size sequence
Worst case space complexity: O(n)

Thanking you, Layman

Art of computer programming -Sorting #2

Insertion sort
Insertion sort is one of those very traditional sorting methods. In this method, we scan through the list element by element and we assume that all elements preceding the present element is sorted. We start with the assumption that first element is sorted and we need to place the 2nd element to the left or the right of the first element based on whether its greater than or less than the 1st element. So we can generalize that for the i'th element we assume that the list from 0...i-1 is sorted and we can insert the ith element at the the correct position in this sorted sublist. So the problem reduces to inserting an element in a sorted list. But its not as simple as it sounds. Inserting in a sorted list may need shifting the elements of the sublist. Its a reasonably expensive operation. Hence using arrays will be quite expensive for insertion sort. Whereas if you are using linked lists, then shifting operations become much more easier(as it involves only 2-3 pointer operations).
On an average we will need a total of 0.5(1+2+...+n) shiftings ~ 0.25n^2

A method to improve this will be to use binary search to find the position of the element in the sorted list. This will reduce the position search time to log n. Hence the algorithm improves.


Points of interest
To check whether a list is already sorted insertion sort is highly recommended.
It can receive data as it is working. This is particularly useful when you have only an incomplete piece of data.
While insertion sort typically makes fewer comparisons than selection sort, it requires more writes because the inner loop can require shifting large sections of the sorted portion of the array.

Algorithm

insertionSort(array A)
begin
   for i := 1 to length[A]-1 do
   begin
       value := A[i];
       j := i - 1;
       while j >= 0 and A[j] > value do
       begin
           A[j + 1] := A[j];
           j := j - 1;
       end;
       A[j + 1] := value;
   end;
end;

Worst case performance О(n^2)
Best case performance O(n)
Average case performance О(n^2)
Worst case space complexity O(1)

Rectangle intersection problem with tree datastructure

The problem here is to write a program that will find all the rectangles that intersects with a given rectangle once the left bottom and top right of the rectangles are given.

#include < stdio.h>
#include < stdlib.h>
#include < sys/stat.h>


struct rect {
int x,y;
struct rect *left,*right,*rtpoint;
};

int xmin,ymin,xmax,ymax;

typedef struct rect rec;
rec *root=NULL,*newptr=NULL;

void find(int x1,int cnd) {
rec *parent=NULL,*tptr=NULL;
rec *ptr=root;
while(ptr!=NULL) {
parent=ptr;
if(cnd==0) {
//if( ((ptr->x > x1) && (ptr->rtpoint)->x < x1) || ((ptr->x < x1) && ((ptr->rtpoint)->x>x1) ) )
if(ptr->rtpoint!=NULL) {
if(check(ptr)) {
printf("\nIntersects (%d,%d) - (%d, %d)\n",ptr->x,ptr->y,(ptr->rtpoint)->x,(ptr->rtpoint)->y);
(ptr->rtpoint)->rtpoint=NULL;
ptr->rtpoint=NULL;
}
}
}
if(ptr->x > x1)
ptr=ptr->left;
else
ptr=ptr->right;
}
if(cnd==1) {
if(parent->x > x1 )
parent->left=newptr;
else
parent->right=newptr;
}
}

int check(rec *temp) {
rec *temp2=temp->rtpoint;
int ys=temp->y,xs=temp->x;
int yr=temp2->y,xr=temp2->x,t;
if(ys>yr) {
t=ys;
ys=yr;
yr=t;
}
if(xs>xr) {
t=xs;
xs=xr;
xr=t;
}
return !( (yr <= ymin) || (ys >= ymax) || (xr <= xmin) || (xs >= xmax) );
}

void preorder(rec *ptr) {
if(ptr!=NULL) {
preorder(ptr->left);
printf("x=%d y=%d\n",ptr->x,ptr->y);
preorder(ptr->right);
}
}
void bt_free() {
if(root==NULL)
return;
bt_free(root->left);
bt_free(root->right);
free(root);
}

int main() {

FILE * fp;
int temp;
rec *temp_ptr=NULL;
struct stat stFileInfo;
char filename[50];
do {
printf ("Enter the filename to get data : ");
gets(filename);
temp=stat(filename,&stFileInfo);
if(temp!=0) {
printf("File doesnt exist!!! \n");
}
}while(temp != 0);
fp = fopen(filename,"r");
while(fscanf(fp,"%d %d %d %d",&xmin,&ymin,&xmax,&ymax) > 0) {
if(root==NULL) {
root=(rec *)malloc(sizeof(rec));
root->x=xmin;
root->y=ymin;
root->left=NULL;
root->right=NULL;
temp_ptr=root;
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->rtpoint=temp_ptr;
newptr->x=xmax;
newptr->y=ymax;
find(xmax,1);
temp_ptr->rtpoint=newptr;
}
else {
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->x=xmin;
newptr->y=ymin;
temp_ptr=newptr;
find(xmin,1);
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->rtpoint=temp_ptr;
newptr->x=xmax;
newptr->y=ymax;
find(xmax,1);
temp_ptr->rtpoint=newptr;
}
}
fclose(fp);
printf("Tree created successfully\nPreorder traversal follows\n");
preorder(root);
printf("\nEnter the test rectangle co-ordinates seperated by comas\n");
scanf("%d,%d,%d,%d",&xmin,&ymin,&xmax,&ymax);
if(xmin>xmax) {
temp=xmin;
xmin=xmax;
xmax=temp;
temp=ymin;
ymin=ymax;
ymax=temp;
}
find(xmin,0);
find(xmax,0);
bt_free();
return 0;
}


Sample input file
6 6 11 11
0 0 2 2
9 9 12 12
60 0 70 100
7 2 8 12

COM/Serial communication in C

This program will help you to understand how to do serial communication in C.
The C program will illustrate the basics of serial communication.


/////////////////////////////////////////////////
// Serial port interface program //
/////////////////////////////////////////////////

#include < stdio.h > // standard input / output functions
#include < string.h > // string function definitions
#include < unistd.h > // UNIX standard function definitions
#include < fcntl.h > // File control definitions
#include < errno.h > // Error number definitions
#include < termios.h > // POSIX terminal control definitionss
#include < time.h > // time calls
#include < stdlib.h >
#include < sys/types.h >
#include < netinet/in.h >
int fd;
int open_port(void)
{
int fd; // file description for the serial port

fd = open("COM2", O_RDWR);

if(fd == -1) // if open is unsucessful
{
perror("open_port: Unable to open /dev/ttyS0 - ");
}
else
{
printf("Opened %d\n",fd);
}

return(fd);
}

int configure_port(int fd) // configure the port
{
struct termios oldtio,port_settings; // structure to store the port settings in
tcgetattr(fd,&oldtio);
//cfsetispeed(&port_settings, B115200); // set baud rates
//cfsetospeed(&port_settings, B115200);

bzero (&port_settings, sizeof (port_settings));
port_settings.c_cflag = B115200 | CLOCAL | CREAD;
port_settings.c_cflag &= ~PARENB; // set no parity, stop bits, data bits 8N1
port_settings.c_cflag &= ~CSTOPB;
port_settings.c_cflag &= ~CSIZE;
port_settings.c_cflag |= CS8;
port_settings.c_iflag = IGNPAR | ICRNL;
port_settings.c_oflag = 0;
port_settings.c_lflag &= ~ICANON;
tcflush(fd, TCIFLUSH);
tcsetattr(fd,TCSANOW,&port_settings);
return(fd);
}

int query_modem(int fd) // query modem with an AT command
{

int k=0;
char str[5];
str[0]=2;
str[1]=str[2]='f';
str[3]=str[4]=3;
k=write(fd,str,strlen(str)); // send an AT command followed by a CR
printf("command %d\n",k);

}
int dsadas()
{
printf("In fm");
int bytesRead;
char *str;
char *buff;
//str=(char *)malloc(100*sizeof(char));
//buff=(char *)malloc(1024*sizeof(char));
while(1)
{

//printf("In while");
if(read(fd,str,10)>0)
{
printf("in if");
buff="";
printf("yesyeysyes %s\n",str);
//strcpy(buff,str);
do
{
//sleep(100);
//append
printf("Buffer = %s",buff);
strcat(buff,str);
bytesRead=read(fd,str,10);
}while(bytesRead>0);
//send bytes to ip
printf("Buffer = %s",buff);
}
}
}

int main(void)
{
pthread_t thread1,thread2;
fd = open_port();
configure_port(fd);
query_modem(fd);
int iret1, iret2;
//iret1 = pthread_create( &thread1, NULL, dsadas);
//pthread_join(thread1, NULL);
return(0);
}

Create tree from preorder traversal

#include < stdio.h >
#include < stdlib.h >

int current=0;

struct bstree {
int val;
struct bstree *left,*right;
};

typedef struct bstree node;

node* tree_build(int* inarr,int* prearr,int left,int right);
void sort(int inarray[], int begin, int end);
void swap(int *a,int *b);
void inorder_traverse(node *ptr);
void bt_free(node *ptr);

main() {
int i;
int prearr[]={10,4,3,2,5,6,11,13,12};
int inarr[10];
for(i=0;i<9;i++)
inarr[i]=prearr[i];
sort(inarr,0,9);
node* root = tree_build(inarr,prearr,0,9);
printf("\n\nTREE CREATED. NOW DOING AN INORDER TRAVERSAL ON THE TREE...\n\n");
inorder_traverse(root);
printf("\n\n");
bt_free(root);
}

void bt_free(node *ptr) {
if(ptr==NULL)
return;
bt_free(ptr->left);
bt_free(ptr->right);
free(ptr);
}

void swap(int *a,int *b) {
int temp=*a;
*a=*b;
*b=temp;
}

void sort(int inarray[],int begin,int end) {
if (end > begin + 1) {
int pivot=inarray[begin],l=begin+1,r=end;
while(l if (inarray[l] <= pivot)
l++;
else
swap(&inarray[l],&inarray[--r]);
}
swap(&inarray[--l],&inarray[begin]);
sort(inarray,begin,l);
sort(inarray,r,end);
}
}

node* tree_build(int inarr[],int prearr[],int left,int right) {
int i,position;
if(left==right)
return NULL;
node *temp=(node *)malloc(sizeof(node));
temp->val=prearr[current];
if(left+1==right)
return temp;
i=left;
while(i if(inarr[i]==prearr[current])
break;
i++;
}
for(position=0;inarr[position]!=inarr[i];position++);
if(position>left) {
current++;
temp->left=tree_build(inarr,prearr,left,position);
}
if(position+1 current++;
temp->right=tree_build(inarr,prearr,position+1,right);
}
return temp;
}

void inorder_traverse(node *ptr) {
if(ptr==NULL)
return;
inorder_traverse(ptr->left);
printf(" %d - ",ptr->val);
inorder_traverse(ptr->right);
}

TCPIP communication in C

Server.c
/* A simple server in the internet domain using TCP
The port number is passed as an argument */
#include < stdio.h >
#include < sys/types.h >
#include < sys/socket.h >
#include < netinet/in.h >

void error(char *msg)
{
perror(msg);
exit(1);
}

int main(int argc, char *argv[])
{
int sockfd, newsockfd, portno, clilen;
char buffer[256];
struct sockaddr_in serv_addr, cli_addr;
int n;
if (argc < 2) {
fprintf(stderr,"ERROR, no port provided\n");
exit(1);
}
sockfd = socket(AF_INET, SOCK_STREAM, 0);
if (sockfd < 0)
error("ERROR opening socket");
bzero((char *) &serv_addr, sizeof(serv_addr));
portno = atoi(argv[1]);
serv_addr.sin_family = AF_INET;
serv_addr.sin_addr.s_addr = INADDR_ANY;
serv_addr.sin_port = htons(portno);
if (bind(sockfd, (struct sockaddr *) &serv_addr,
sizeof(serv_addr)) < 0)
error("ERROR on binding");
listen(sockfd,5);
clilen = sizeof(cli_addr);
newsockfd = accept(sockfd,
(struct sockaddr *) &cli_addr,
&clilen);
if (newsockfd < 0)
error("ERROR on accept");
bzero(buffer,256);
n = read(newsockfd,buffer,255);
if (n < 0) error("ERROR reading from socket");
printf("Here is the message: %s\n",buffer);
n = write(newsockfd,"I got your message",18);
if (n < 0) error("ERROR writing to socket");
return 0;
}




Client.c
#include /* for printf() and fprintf() */
#include /* for socket(), connect(), send(), and recv() */
#include /* for sockaddr_in and inet_addr() */
#include /* for atoi() and exit() */
#include /* for memset() */
#include /* for close() */
#include
#define RCVBUFSIZE 200024 /* Size of receive buffer */

void DieWithError(char *errorMessage); /* Error handling function */

int main(int argc, char *argv[])
{
int sock; /* Socket descriptor */
struct sockaddr_in echoServAddr; /* Echo server address */
unsigned short echoServPort; /* Echo server port */
char *servIP; /* Server IP address (dotted quad) */
char *echoString; /* String to send to echo server */
char echoBuffer[RCVBUFSIZE]; /* Buffer for echo string */
unsigned int echoStringLen; /* Length of string to echo */
int bytesRcvd, totalBytesRcvd; /* Bytes read in single recv()
and total bytes read */

servIP = "10.64.122.26"; /* First arg: server IP address (dotted quad) */
echoServPort = atoi("9000"); /* Use given port, if any */

/* Create a reliable, stream socket using TCP */
if ((sock = socket(PF_INET, SOCK_STREAM, IPPROTO_TCP)) < 0)
DieWithError("socket() failed");

/* Construct the server address structure */
memset(&echoServAddr, 0, sizeof(echoServAddr)); /* Zero out structure */
echoServAddr.sin_family = AF_INET; /* Internet address family */


echoServAddr.sin_addr.s_addr = inet_addr(servIP);



echoServAddr.sin_addr.s_addr = inet_addr(servIP); /* Server IP address */
echoServAddr.sin_port = htons(echoServPort); /* Server port */

/* Establish the connection to the echo server */
if (connect(sock, (struct sockaddr *) &echoServAddr, sizeof(echoServAddr)) < 0)
DieWithError("connect() failed");




/* Receive the same string back from the server */
totalBytesRcvd = 0;
printf("Received: "); /* Setup to print the echoed string */
while (1)
{
/* Receive up to the buffer size (minus 1 to leave space for
a null terminator) bytes from the sender */
if ((bytesRcvd = recv(sock, echoBuffer, RCVBUFSIZE - 1, 0)) > 0)
{
echoBuffer[bytesRcvd] = '\0'; /* Terminate the string! */
printf("%s\n", echoBuffer); /* Print the echo buffer */
}

}

printf("\n"); /* Print a final linefeed */

close(sock);

exit(0);
}//-- end main --//



void DieWithError(char *errorMessage)
{
perror(errorMessage);
exit(1);
}

Thanking you
Layman