A Quine Program in C

A quine is a non-empty computer program which takes no input and produces a copy of its own source code as its only output. 

The program given below is a quine program in C.

char*s="char*s=%c%s%c;main(){printf(s,34,s,34);}";main(){printf(s,34,s,34);}

Figure below shows the output of the program

Click here to download the C program.

Backtracking Algorithms : Explaining Cindy's Puzzle with a C++ Program

Classic text books in Algorithm Analysis like Cormen, Leiserson and Rivest, Sedgewick and Flajolet, etc. often neglect or give least preference to the algorithm development technique called backtracking. Even those textbooks discussing backtracking only discuss few selected problems. A classic problem discussed along with backtracking is the eight queens puzzle. Often this problem is unappreciated by persons not well versed in the game of Chess. Here I am trying to explain backtracking using a very simple game often called ‘Cindy’s puzzle’.

The game Cindy’s puzzle involves n Red marbles, n Green marbles and a playing board which consists simply of a line of 2n+1 spaces to put the marbles in. Start with the Red marbles all at one end (say, the left), the Green marbles all at the other end, and a free space in between. For n=2, the initial arrangement on the board is shown below.

To denote this position we use the notation |R|R| _ |G|G| is used.

The aim of the puzzle is to reverse the positions of the marbles as shown below.

So the solution for the puzzle can be denoted as |G|G| _ |R|R|.

The movements of the marbles are restricted by the following rules.

The Red marbles can only move to the right, and the Green marbles can only move to the left (no backing up). At each move, a marble can either

• Move one space ahead, if that space is clear, or
• Jump ahead over exactly one marble of the opposite color, if the space just beyond that marble is clear.

I am trying to develop a backtracking algorithm to solve this puzzle. The algorithm will be able to produce one particular solution to this puzzle. For example for n=2, the solution steps are given below.

           |R|R| _ |G|G|

        |R|R|G| _ |G|

        |R| _ |G|R|G|

        | _ |R|G|R|G|

        |G|R| _ |R|G|

        |G|R|G|R| _ |

        |G|R|G| _ |R|

        |G| _ |G|R|R|

        |G|G| _ |R|R|

Of course this is an ideal solution where no backtracking is used but in the proposed backtracking algorithm, if non winnable situation arises backtracking is applied to go back to a previous state and continue the search for a solution. 

 Click here to download the C++ Program.

C Program to Find the Endianness of a Machine

Endianness is the ordering or sequencing of bytes of a word of digital data in computer memory storage or during transmission. Words may be represented in big-endian orlittle-endian manner. Big-endian systems store the most-significant byte of a word at the smallest memory address and the least significant byte at the largest. Little-endian system, in contrast, stores the least-significant byte at the smallest address.

In this post I have given a C program to find out the Endianness of your system. The program is given below.

int main()

{

    int x = 1;

    if(*(char *)&x == 1)

    {

        printf("little-endian\n");

    }

    else

    {

        printf("big-endian\n");

    }

    return 0;

}

The program finds the Endianness by using the size of integer variables and a character variables. The integer variable holds the value 1. Then this integer variable is cast into a character and if the value of this character  is 1 you have a little-endian machine. If the character    is 0 then you have a big-endian machine. What is the working principle of this program? When you cast an integer to char the lowest addressed byte of the integer is used a char variable. If this lowest addressed byte contains the value 1 then the machine is little-endian, otherwise it is a big-endian machine. Why so? The integer 1 is represented as 00000000 00000000 00000000 00000001 in a 4 byte int. When you cast this int variable as a char the lowest address contains 00000001 in little-endian and 00000000 in big-endian. Hence if the value of the character variable is 1 you have a little-endian system and if the value of the character variable is 0 you have a big-endian system.

Click here to download the C program.

Operator Overloading in C++ : PART 2 ([ ] Operator)

  Array subscript operator [ ] used for array indexing can also be overloaded in C++. In this post I have added a program in which the array subscript operator [ ] is overloaded. The program illustrates an overloaded array subscript operator.

The program also offers a solution to the C++ puzzle question given below.

Floating Point Number in Array Subscript

Write a C++ program in which the following statement compiles without an error.

cout << a[0.123];

The difficulty in solving this puzzle arises from the fact that array subscript should be an integer.  

If you pass a float value to a normal array subscript you will get the following error "Invalid type for array subscript". 

One possible solution is to overload the array subscript operator.

Click here to download the C++ program solving the puzzle.

There might be some other solutions to this puzzle. If you know any other solution please share them here. 

   

Operator Overloading in C++ : PART 1 (++ Operator)

 I am now teaching under graduate students C++ programming. I thought I will share the programs I have prepared so that it benefits everyone.

Overloading ++ Operator

In this post I have added sample programs overloading the ++ Operator. In C++ we have preincrement and postincrement operators. For example ++a is preincrement whereas a++ is postincrement. So in order to handle these two situations there should be two versions of the operator++( ) function. The two versions are shown below. 

    void operator++(int y);  // for postincrement

   // The call a++; will invoke this version

   // The call a++; is same as the call a.operator++();
   

   void operator++( );        // for preincrement

   // The call ++a; will invoke this version

   // The call ++a; is same as the call a.operator++(0);

Click here to download the C++ program. 

Overloading ++ Operator with Friend Function

In C++ we can overload the ++ operator by using friend function.  Here also we need two versions to manage the preincrement and postincrement versions of the ++ operator. The two versions are given below.

   void operator++(A, int);  // for postincrement

   // The name of the Class is A

   // The call a++; will invoke this version

   // The call a++; is same as the call operator++(a);
   

   void operator++(A);        // for preincrement
   //The name of the class is A 

   // The call ++a; will invoke this version

   // The call ++a; is same as the call operator++(a,0);

Click here to download the C++ program. 

The \nocite Command in BibTeX

  The normal behavior of BibTeX is set in such a way that unreferenced entries in the .bib file will not be displayed in the bibliography section. But what if we need to print even the unreferenced entries in the .bib file also made part of the bibliographic section? For that we have a command called \nocite{*}. This command will override the default behavior of BibTeX such that even an referenced entries in the .bib file will be added in the bibliographic section in the DVI or PDF file produced. The script below shows the working of \nocite{*} command. The TeX file uses a .bib file called bib1.bib. 

\documentclass{article}

\usepackage{natbib}

\title{Sample Article}

\author{D}

\begin{document}

\maketitle

\nocite{*}

Here the entries in the Bibfile are not referenced. 

But they are shown in the reference section because we 

use \textbackslash cite\{*\} command.

\bibliographystyle{plain}

\bibliography{bib1.bib}

\end{document}

Client Server Program in C to Simulate TCP Multicast Server

  This program simulates a multicast server in C. The following line of code sets the number of clients accepted by the server program. 

#define NC 4

Here the number of clients is set as 4. First run the server process, then run the client processes.

Click here to download the Client program.

Clcik here to download the Server Program.

Client Server Program in C to Simulate Go-Back-N-ARQ

  This program was also written some 5 years before. This again is a simulation program trying to imitate Go-Back-N ARQ. It is a client server program. Click here to view the Wikipedia article on Go-Back-N_ARQ. Here also the server side acts as the receiver and hence you should run this program first. Afterwards you should also run the client program which acts as the sender side. 

Figure Below Shows the Receiver

Figure Below Shows the Sender

The line given below sets the window size for the sender and the receiver.

#define W 5 
If you want you can change the window size to some other value. Currently the window size is 5.

The following lines in the receiver side decides the probability with which a frame fails to reach the destination.

#define P1 50
#define P2 10

You can increase the probability of a frame being corrupted by increasing the value of P2 and decrease the probability by decreasing the value of P2. Currently there is a 20% probability for frame corruption.

Click here to download the Receiver Side program.

Click here to download the Sender Side program.


Click here to view the article on Selective Repeat ARQ.

Client Server Program in C to Simulate Selective Repeat ARQ

  I wrote these programs 5 years ago. It is a simulation program trying to imitate the working of Selective Repeat ARQ. Click here to view the Wikipedia article on Selective Repeat ARQ. A client server C program is used to simulate the working of Selective Repeat ARQ. The server acts as the receiver. The client acts as the sender. Because of this reason first run the receiver program and afterwards run the sender program. 

Figure Below Shows theReceiver

Figure Below Shows the Sender

  

The line given below sets the window size for the sender and the receiver.

#define W 5 
If you want you can change the window size to some other value. Currently the window size is 5.

The following lines in the receiver side decides the probability with which a frame fails to reach the destination.

#define P1 50
#define P2 10

You can increase the probability of a frame being corrupted by increasing the value of P2 and decrease the probability by decreasing the value of P2. Currently there is a 20% probability for frame corruption.

Click here to download the Receiver Side program. 

Click here to download the Sender Side program. 


Click here to view the article on Go-Back-N ARQ.

In C and C++ typedef is a Storage Class Specifier

  Consider the program given below.

#include<stdio.h>
int main()
{
   typedef static int i;
   i a = 0;
   printf("%d", a);
   return 0;
}

The program when compiled as C or C++ will give you the following error "multiple storage classes in declaration specifiers". The error tells us that typedef in C and C++ is treated as a storage class specifier and this leads to the error since it is not allowed to use two storage class specifiers with a variable.

The C Reference Manual says "The typedef specifier does not reserve storage and is called a storage class specifier only for syntactic convenience".

Yet Another Difference Between C and C++: Initializing Constant Variables

  Constant variable initialization is yet another minute difference between C and C++. Consider the program given below.

#include<stdio.h>
int main()
{
  int x = 111;
  static int y = x;
  if(x == y)
     printf("Equal");
  else
     printf("Not Equal");
  return 0;
}

If you save the program as a C++ program, it compiles fine and shows the output as "Equal". But the same program when compiled as C will give you the following error "initializer element is not constant|". What is the reason? This is another minor difference between C and C++. In C a constant variable can only be initialized with a constant value and not by using another variable. But C++ do not have this restriction. You can initialize a constant variable with any other variable.

Click here to download the C++ program.

Yet Another Difference Between C and C++: Case Labels

 There are many major differences between C and C++. Such differences are matters for Text Books and Manuals. Here I am pointing out yet another minor difference between C and C++. This time the difference arises from the way case labels are treated in C and C++. 

 C++ will allow const int variables as case labels, whereas C will give you an error. Consider the program given below.

#include<stdio.h>

int main()
{
    int i=1;
    const int j=1;
    switch(i)
    {
        case j:
            printf("\nHello\n\n");
            break;
        case 2:
            printf("\nHi\n\n");
            break;
        default:
            printf("\nWelcome\n\n");
    }
    return 0;
}

The program will give the error 'case label does not reduce to an integer constant' when compiled as a C program. But when compiled as a C++ program the program executes without any errors and gives 'Hello' as output. 

C/C++ Puzzles: PART - 36

  The following program will give you syntax error.


#include<stdio.h>

int main()
{
    int a=10,b=5,c;
    c=a>b?a:;
    printf("\n%d\n\n",c);
    return 0;
}

Whereas the program given below will work without any syntax errors. Predict the output of the program.


#include<stdio.h>

int main()
{
    int a=10,b=5,c;
    c=a>b?:b;
    printf("\n%d\n\n",c);
    return 0;
}

C/C++ Puzzles: PART - 35

   C Program Tricked to Believe X equals X+2

  The puzzle has been discussed previously, but only one solution was provided. But now I have added a few more solutions to this puzzle. The challenge is to get a true value for the following conditional statement. 

x==x+2  

You are free to use any feature of the C preprocessor or Compiler. If you can't get a solution then check the programs shown below.

Solution 1

#define x 2|0
#include<stdio.h>

int main()
{
    if(x == x+2)
    {
        printf("\n Hello");
    }
    else
    {
        printf("\n Hi");
    }
}

Solution 2

#include<stdio.h>

int main()

{

    float x=1.0/0;

    if(x==x+2)

    {

        printf("\nHello");

    }

    else

    {

        printf("\nHi");

    }

}

Solution 3

#include<stdio.h>

int main()

{

    float x = 1e100;

    if(x==x+2)

    {

        printf("\nHello");

    }

    else

    {

        printf("\nHi");

    }

}

Solution 4

#include<stdio.h>

struct {}*x=0;

int main()

{

    if(x==x+2)

    {

        printf("\nHello");

    }

    else

    {

        printf("\nHi");

    }

}

Solution 5

#include<stdio.h>

int (*x)[0x20000000];

int main()

{

    if(x==x+2)

    {

        printf("\nHello");

    }

    else

    {

        printf("\nHi");

    }

}

Solution 6

#include<stdio.h>

int main()

{

/////////////////////////////////////

// we initialize tr = 1            //

int tr = 1;

int x = 111;

////////////////////////////////////

// Can You change the value of tr??/

tr = (x == x + 2);

/////////////////////////////////////

// The value of tr is not changed  //

    if(tr==1)

    {

        printf("\nHello");

    }

    else

    {

        printf("\nHi");

    }

}

Click here to download the C program solutions. 

Click here to download the C++ program solutions.

Power Method to Find the Largest Eigenvalue

   Power method is used to find the numerically largest eigenvalue. The method sometimes converge very slowly. In this post I am providing the C and C++ programs to implement power method.

Figure Below Shows a Sample Output

Click here to download the C program.

Click here to download the C++ program. 

Crout's Reduction Method for Solving System of Linear Equations.

   Crout's reduction method is used to solve system of linear equations. In this post I have included the C and C++ program implementing Crout's reduction method.

Figure Below Shows a Sample Output

Click here to download the C Program.

Click here to download the C++ Program

Fitting a Parabola Using Method of Moments : C/C++ Program

   In this post I have shared the C and C++ programs to fit a Parabola using the method of moments.

Figure Below Shows a Sample Output

Click here to download the C Program.

Click here to download the C++ Program.

A Simple Client-Server Chat Utility in Java

   In this post I have added the Client and Server Programs in Java to implement a very simple chat utility.

Figure Below Shows the GUI of a Chat Client

Click here to down load the Java Client Program.

Click here to download the Java Server Program.

Straight Line Fitting By Using the Method of Least Squares : C/C++ Program

   In this post I have shared the C and C++ Programs to perform straight line fitting by using the method of least squares. 

Figure Below Shows a Sample Output

Click here to download the C Program.

Click here to download the C++ Program.

Straight Line Fitting Using the Method of Group Averages : C/C++ Program

   In this post I have shared the C and C++ programs to perform straight line fitting by using the method of Group Averages.

Figure Below Shows a Sample Output

Click here to download the C Program.

Click here to download the C++ Program.