File Programming in C: PART - 2

Consider the Program given below. The program prints the values of member variables in the FILE structure of UNIX.

#include<stdio.h>

int main()
{
     FILE * fp;
     fp=fopen("File2.C","r");

     printf("\nThe File Structure Values are:\n");
     printf("\n_ptr = %d",fp->_ptr);
     printf("\n_cnt = %d",fp->_cnt);
     printf("\n_base = %d",fp->_base);
     printf("\n_flag = %d",fp->_flag);
     printf("\n_file = %d",fp->_file);

     fclose(fp);
}

The program prints the values of the member variables in the FILE structure.

_ptr :-   Next Character in Buffer.
_cnt :-   Number of available characters in Buffer.
_base :- The Buffer.
_flag :-  The state of the stream.
_file :-   Unix system file descriptor.
  
Click here to download the C Program to print the FILE Structure member variables.

Dijkstra's Algorithm: C/C++ Program

Dijkstra's algorithm is used to solve the Single Source Shortest Path problem in Graphs. The Algorithm's time complexity is O(n²) for a graph with n nodes. Dijkstra's algorithm works only for a graph with non-negative edge path costs. 

Click here to download the C Program implementing Dijkstra's Algorithm. 

Click here to download the C++ Program implementing Dijkstra's Algorithm.

C/C++ Program to Perform Binary Search Tree Operations

Binary Search Tree is a very useful Data Structure. In this Program the following operations are implemented.

• Insertion.
• Deletion.
• Inorder Traversal.
• Preorder Traversal.
• Postorder Traversal.
• Finding the Root Node.

Figure Below Shows a Sample Output

Click here to download the C Program performing Binary Search Tree Operations.
Click here to download the C++ Program performing Binary Search Tree Operations.

Implementing MINUS Query in MySQL

  The SQL MINUS query returns all rows in the first SQL SELECT statement that are not returned in the second SQL SELECT statement. Each SQL SELECT statement within the SQL MINUS query must have the same number of fields in the result sets with similar data types.

The syntax for the SQL MINUS query is:

select field1, field2, ... field_n 
from tables1 
MINUS 
select field1, field2, ... field_n 
from table2; 

But this query is not implemented in MySQL. So to achieve the same effect you can use the following Query statement.  

select field1, field2, ..., field_n 
from table1 
where (field_x) NOT IN (select field_x from table2); 

Where field_x is the field over which the comparison is performed. 

Implementing INTERSECT Query in MySQL

  The SQL INTERSECT query returns the results of 2 or more "select" queries. However, it only returns the rows selected by all queries. If a record exists in one query and not in the other, it will be omitted from the INTERSECT results. 

The syntax for the SQL INTERSECT query is:

select field1, field2, ..., field_n 
from table1 
INTERSECT 
select field1, field2, ..., field_n
from table2
 

But this query is not implemented in MySQL. So to achieve the same effect you can use the following Query statement.  

select field1, field2, ..., field_n 
from table1 
where (field_x) IN (select field_x from table2);

Where field_x is the field over which the comparison is performed. 

Library Call VS. System Call

  The difference between library calls and system calls has confused even expert programmers. Library calls are part of the language or application, and system calls are part of the operating system. A system call gets into the kernel by issuing a "trap" or interrupt. The other main differences between library calls and system calls are listed below.

 

• The C library is the same on every ANSI C implementation, but the Systems Calls are different in each Operating System.

• Library Call is a call to a routine in a library, Whereas System Call is a call to the kernel for a service.

• Library call is linked with the user program. System Call is an entry point to the OS.

• Library call executed in the user address space, but System Call is Executed in the kernel address space.

• Library Call execution time is Counted as part of the "user" time, whereas System Call execution time is counted as part of the "system" time.

• Library Call has the lower overhead of a procedure call, whereas System Call has a high overhead context switch to kernel and back.

• There are about 300 routines in the C library "libc". There are about 90 system calls in UNIX. WinAPI provides similar System Calls in Windows.

• Typical C library calls are system, fprintf, malloc, etc. Typical system calls are chdir, fork, write, brk, etc.

Functions setjmp( ) and longjmp( ) in C

  C language provide only limited branching facility. Most of the constructs in C provide conditional jumps only. Of course there is goto, but goto is not very powerful. Consider the program given below.

#include <stdio.h>

void fun()
{
    printf("\nYou are in the function fun\n");
    goto x;
    printf("\nyou will not see this, because of goto\n");
}
int main()
{
    printf("\nYou are in the main function\n");
    fun();
    printf("\nThis line will not be printed\n");
    x:
    printf("\nThis line will be printed\n");
    return 0;
}

The program will give you the following error "label 'x' used but not defined". The label of a goto statement is only having a function scope. Because of this limitation you can not jump out side a function using goto statement. But don't worry, we can use setjmp( ) and longjmp( ) to jump out of a function. We can also jump out of a file using these functions. These functions are defined inside the header file setjmp.h. Consider the program given below.

#include <stdio.h>
#include <setjmp.h>

jmp_buf buf;
 
void fun()
{
    printf("\nYou are in function fun\n");
    longjmp(buf,1);
    printf("\nYou will never see this, because of longjmp");
}
int main()
{
     if(setjmp(buf))
     {
        printf("\nYou are back in main\n");
     }
     else
     {
        printf("\nYou are in main\n");
        fun();
     }
     return 0;
}

Figure shows the Output of the Program

In the program setjmp(jmp_buf j) must be called first. It says use the variable j to remember where you are now and returns 0 from the call. Function longjmp(jmp_buf j, int i) can then be called. It says go back to the place where j is set, i.e., to the location of the setjmp( ). Function longjmp( ) returns the value of variable i to the function setjmp( ).

Click here to down load the C Program illustrating Functions setjmp( ) and longjmp( ). 

 

KMP Algorithm: C/C++ Program

Knuth–Morris–Pratt algorithm

  The Knuth-Morris-Pratt Algorithm (KMP Algorithm) is a string searching algorithm. The performance of KMP Algorithm is far better than the naive string searching algorithm. The time complexity of KMP algorithm is O(m+n). Here m is the length of the text and n is the length of the pattern (sub string) to be searched. KMP algorithm also requires a preprocessing time of the order of O(n).

Click here to download the C Program implemeting KMP Algorithm.
Click here to download the C++ Program implemeting KMP Algorithm.

The Naive String Searching Algorithm.

  The Naive string searching algorithm is also called the simple string searching algorithm. It employs a brute force technique to identify the presence of a pattern in the given text. Even though the working of the algorithm can be understood easily, it is not an efficient algorithm. The time complexity of the algorithm to check for a sub string is O(mn) where m is the length of the text and n is the length of the pattern (sub string) to be searched. But no preprocessing is required for this algorithm.

Click here to download the C Program implementing The Naive String Searching Algorithm. 
Click here to download the C++ Program implementing The Naive String Searching Algorithm.

Watermarking in LATEX

  Before uploading documents to the Internet, it is a very good idea to watermark them so that your work is not claimed by others. You can include a watermark to PDF documents by using LATEX. I am discussing two different methods to watermark your PDF documents.

The code given below can be used to add a watermark to your PDF file.

\usepackage{draftwatermark}

\SetWatermarkLightness{ 0.90 }    

% The above Statement sets 

% the transparency of the Watermarking Text.

\SetWatermarkScale{ 15 } 

% The above Statement sets 

% the size of the Watermarking Text.   

\SetWatermarkText{D} 

% The above Statement sets the Watermarking Text.

Click here to download the TEX file for adding watermarks to PDF documents. 
Click here to view the PDF document with Watermark.

  
If you don't have the package "draftwatermark" in your Latex installation, then use the following code.

\usepackage{graphicx,type1cm,eso-pic,color}

\makeatletter

  \AddToShipoutPicture{              

    \setlength{\@tempdimb}{.5\paperwidth} 

    \setlength{\@tempdimc}{.5\paperheight}

    \setlength{\unitlength}{1pt}

    \put(\strip@pt\@tempdimb,\strip@pt\@tempdimc){

       \makebox(0,0){

          \rotatebox{55}{  

          % The above Statement sets 

          % the Rotation of the Watermarking Text.                        

           \textcolor[gray]{0.85}{ 

           % The above Statement sets 

           % the transparency of the Watermarking Text.

               \fontsize{5cm}{5cm} 

               % The above Statement sets 

               % the size of the Watermarking Text.

               \selectfont{D}}}}}}  

               % The above Statement sets 

               % the Watermarking Text.

\makeatother

Click here to download the TEX file for adding watermarks to PDF documents. 
Click here to view the PDF document with Watermark. 

Floyd-Warshall Algorithm: C/C++ Program

  Floyd-Warshall algorithm (Also called Floyd's Algorithm) is used to solve the All-Pairs Shortest Path problem in Graphs. The Algorithm's time complexity is O(n³) for a graph with n nodes. The algorithm is given below.

for each vertex v

     dist[v][v] ← 0
for each edge (u,v)

     dist[u][v] ← w(u,v) 

for k from 1 to |V|       

     for i from 1 to |V|

         for j from 1 to |V|

                if dist[i][k] + dist[k][j] < dist[i][j] then   

                     dist[i][j] ← dist[i][k] + dist[k][j]  

  Floyd-Warshall algorithm is essentially same as Warshall's algorithm used to find the transitive closure of a relation R. Floyd-Warshall algorithm is an example for Dynamic Programming.

Click here to download the C Program implementing Floyd-Warshall Algorithm.   
Click here to download the C++ Program implementing Floyd-Warshall Algorithm. 

C/C++ Program to find the Transitive Closure of a Relation

Warshall's Algorithm

  To find the Transitive Closure of a Relation an algorithm called Warshall's Algorithm is used. The transitive closure of a Binary Relation R on a Set X is the transitive relation R⁺ on the set X such that R⁺ contains R and R⁺ is minimal. The transitive closure can answer reachability question in case of graphs. Warshall's algorithm is also the back bone of Floyd-Warshall algorithm used to solve the All-Pairs Shortest Path problem in graphs. The Time Complexity of Warshall's Algorithm is O(n³) for a Relation involving n elements.

Click here to download the C Program implementing Warshall's Algorithm. 

Click here to download the C++ Program implementing Warshall's Algorithm.     

The C11 Standard

  C11 is the latest standard for C programming language proposed in 2011. The proposals made by the C11 standard are yet to be implemented by most of the compilers. But I am writing this post to give you an idea about the changes we can expect in the near future. The changes between C99 and C11 are pointed out below.

• Improved Unicode support is proposed in C11.

• Multithreading support is mandatory with this version of C.

• Anonymous structures and unions are possible with this version.

• Stricter Bounds checking is possible with C11 standard.

• gets( ) is removed.

• The quick_exit( ) to terminate programs.

•  The _Noreturn specifier.

• An exclusive create-and-open mode for fopen( ).

Click here to download the latest Working Draft of C11 Standard.

Some Tips for Writing C/C++ Programs

  Here in this post I am discussing a few points to note while writing C/C++ programs. These points might help you reduce errors while writing programs and also makes them easy to debug.

• Be careful while using the == (Relational Operator) and = (Assignment) operators. So many errors were made because of these two operators. Consider the code given below. It will not show any error.                              

                              if(x=1)

                              {
                                   printf("\nHello");
                              }

                      The actual code intended was the one given below.
                              if(x=1)                              
                              {
                                   printf("\nHello");
                              }               
  
                      But if you change the code as follows, it will show an error if you forget an equal to sign.
                              if(1==x)
                              {
                                   printf("\nHello");
                              }
                      Here if you forget an equal to sign, you will get the following error "lvalue required".

• Always use ++ and -- operators on lines by themselves. Avoid statements like arr[++i] as you may not get the intended side effect. 

•  Try to have a default statement in every switch statement, even if it is not doing anything.

• Put parentheses around each constant expression defined by the pre-processor #define directive.

                              #define EQN(x,y)  x*y 

                       EQN(5+6) will give you 41 output instead of the intended 121.

                       The correct statement is shown below.

                              #define EQN(x,y)  (x)*(y)

• Never do nothing silently. For example consider the code given below. It was included in the program to bring some delay.

                              for(i=0;i<10000;i++) ; // Note the semi colon.                         
                        A better code is shown below.
                              for(i=0;i<10000;i++)
                               /* Do Nothing, Just for Delay */ ;
                        This will make debugging easier at a later stage.

• The upper & lower limit of data types in C/C++ is often dependent on the compiler. To verify the limits of data types in your compiler check the header file limits.h.

• Beware of Semi Colons in your program.

• If statements in your program contains operators with different precedence, then using brackets is a very good idea. 
  
  
  

Fermat Primality Test

  Fermat primality test is used to check whether the given number is prime or not. It is a probabilistic algorithm to check the primality of a number. The Fermat primality test is based on Fermat's little theorem. The theorem is stated below.

Fermat's little theorem states that if p is a prime number and 1≤ a <p then, a^p-1 ≡ 1 (mod p). 

If we want to test if p is prime, then pick random number a in the interval 1≤a<p and see if the equality holds. If the equality does not hold for a value of a, then p is composite. If the equality does hold for many values of a, then we can say that p is probably a prime number. Fermat primality test will show Carmichael Numbers as prime numbers, even though they are composite. Carmichael numbers are also called Fermat pseudo primes because they will pass the Fermat test for primality. More over it is widely believed that there are infinitely many Carmichael numbers (At least Paul Erdos believed so), there for Fermat primality test is not highly reliable.

Click here to download the C Program for Fermat Primality Test.
Click here to download the C++ Program for Fermat Primality Test.

The C99 Standard

  C99 is an informal name for ISO/IEC 9899:1999, a past version of the C programming language standard. The latest standard is called C11. Even though there are standards like C99 and C11, the most widely supported C standard is still ANSI C. Here in this post I am discussing the differences between ANSI C and C99.

• inline, restrict, _Bool, _Complex and _Imaginary are the new keywords introduced by C99.

• _Bool, long long, _Imaginary and _Complex are the new data types included by C99.

• long long has 64 bit precision.

• Declarations can be mixed with other statements.

                     int x;

                     x=10;

                     printf ("\nx is %d",x);

                     int y=20;   //Valid in C99, but error in ANSI C.

• Declarations within for loop is allowed.

                    for(int i=0;i<10;i++)  //Valid in C99, but error in ANSI C.

                    {

                          printf("\nHello");

                    } 

• Variable length arrays are supported in C99.

• Variable length macro arguments are allowed in C99.

• true and false are predefined macro constants in C99.

• Return type is no longer integer by default.

• Unicode characters are supported by C99. \u or \U followed by hexadecimal numbers will print Unicode characters.

• Single line comments ( // ) in C++ are supported by C99.

• Compound literals are supported by C99 which are used instead of temporary arrays used in function calls.

Minor Differences Between C and C++

  There are some major differences between C and C++. You can refer a good C++ programming text book to find those differences. Here in this post I am discussing about a few subtle differences between C and C++. I have tried to include as many points as possible, but still there might be some points missing.

• In C by default the return type of a function is integer. But this rule is not valid in C++. You have to mention the return type as integer explicitly. 

                               add( )  // Valid in C.
                               add( )  // Error in C++.

• In C an empty function prototype tells the compiler that the function can have any number of arguments. But in C++ it means the function does not take any argument.

                               int add( );  // in C this function can take any number of arguments.
                               int add( );  // in C++ this function does not take any arguments.  

• Structure variable declaration is different for C and C++. Consider the structure given below. 

                              struct sample
                              {
                                  int x,y;
                              };
          In C structure variable is declared as follows.
                             struct sample var1;
          In C++ structure variable is declared as follows.                               
                             sample var1;

• Built-in memory-handling operators new and delete are available in C++. In C dynamic memory allocation is done with the help of functions malloc( ) and free( ).

• Single line comment ( // ) is available in C++.

• Address of register variable can be taken in C++. But in C it is not possible.

• Size of enumeration constant is that of integere in C. But in C++ size of enumeration variable is not fixed. It depends on the size requirement of the enumeration constant.

• Anonymous unions can be declared in C++.

• Anonymous enumeration is possible in C++ if just enumeration constants are required.

• C++ preprocesser provides an additional predefined macro constant __cplusplus.

• The unary increment and decrement operators in C++ returns an lvalue. But in C they return an rvalue.

                            (++i)++;  // Error in C, but in C++ it is valid.
                            ++i=0;    // Error in C, but in C++ it is valid.      

       

Left Factoring

  An LL(K) parser can recognize a grammar unambiguously only if the grammar is left factored. To understand left factoring consider the grammar given below. The grammar is not left factored.

S→ abX | abY
X→m
Y→n  

The above grammar can not be parsed by an LL(1) parser. An LL(1) parser looks ahead only a single character (Token) to make a parsing decision. But here the the parser should read two characters in advance to make a parsing decision. Thus in general we can say that there exists a non left factored grammar which can not be parsed by an LL(K) parser for any value of K. To parse the grammar it should be left factored. The grammar given below is a left factored grammar equivalent to the grammar given above. 

S→abC
C→X | Y 
X→m
Y→n

This grammar can be parsed by an LL(1) parser. 
 

Program to Find the Square Root of a Number

  Finding the square root of a number is a very trivial operation in Mathematics. But how to find the square root of a number using some programming language like C or C++? Almost every programming language has a built in function to perform this operation. For example C and C++ has sqrt( ) defined in the header file math.h. But how to find the square root without using any standard library function? There are many different solutions available to this problem. Here I have posted programs to find the square root based on two different techniques. Babylonian Method (Heron's Method) and High/Low Method.

Babylonian Method (Heron's Method)

  
  This method is credited to the Babylonians and sometimes to Hero of Alexandria, a first-century Greek Mathematician. The technique is described below.

            To find the root of a number X, start with an initial approximation R₀.

            R₀ ≈ √X. 

          R_n+1=( R_n + ( X/R_n ) )/2.

            Repeat the process until you get a sufficiently accurate answer. 

            R_n+1 will give you the latest value of the square root.

Click Here to Download the C Program to find the Square Root of a number using Heron's Method. 
Click Here to Download the C++ Program to find the Square Root of a number using Heron's Method. 
 

High/Low Method

  

  This method is similar to the bisection method. This method involves guessing a approximate value for the square root of a number based on known squares. The guessed value is checked if it is too high or too low and adjusting accordingly until a sufficiently accurate answer is obtained.

Click Here to Download the C Program to find the Square Root of a number using Heron's Method. 

Click Here to Download the C++ Program to find the Square Root of a number using Heron's Method.

 

Self-Replicating C Programs (Quine)

  A program with no input, which prints the same program as output is called Quine. They are also called self-replicating programs, self-reproducing programs or self-copying programs. Given below is a Quine program in C. The program uses the predefined macro __FILE__ to open and print the program itself as output.

#include<stdio.h>
int main()
{
    FILE *fp;
    char c;
    fp=fopen(__FILE__,"r");
    do
    {
       c=getc(fp);
       putchar(c);
    }while(c!=EOF);
    fclose(fp);
    return 0;
}

Download.

Figure Below Shows the Output

  But the program I wrote is not a clever one, it just uses the file as input and prints it. But I have come across a brilliant program in one of the discussion forums, which replicates itself without using the file. The Program is given below for which the unknown author deserves full credit.

#include <stdio.h>
char*s="#include <stdio.h>%cchar*s=%c%s%c;%cint main(void){printf(s,10,34,s,34,10,10);}%c";
int main(void){printf(s,10,34,s,34,10,10);}

Download.

Figure Below Shows the Output

 

Standard Predefined Macros in C/C++

  C and C++ have the additional benefit of a Preprocessor which can make changes to your program even before compilation. There are some constants predefined by the C/C++ Preprocessor. There are mainly five of them about which I am discussing today. 

• __FILE__ : This predefined constant contains the name of the C Program being used currently. 

• __LINE__ : This constant contains the line number of the code being processed currently.

• __TIME__ : This constant holds the current system time.

• __DATE__ : This constant holds the current system date.

• __STDC__ : If this constant is defined as 1 yours is an ANSI standard C Compiler.

Program given below illustrates the uses of these predefined constants.

#include<stdio.h>
#ifdef __STDC__
#define MESSAGE printf("\nYour Compiler is an ANSI Standard C Compiler\n");
#else
#define MESSAGE printf("\nSorry!!! Your Compiler is not an ANSI Standard C Compiler\n");
#endif
int main()
{
    int a,b,c;
    printf("\nCompiled the Program %s and this is line no %d",__FILE__,__LINE__);
    printf("\nThis is line no %d\n",__LINE__);
    #line 100 "MyProg.c"
    printf("\nThe Program is now called %s and this is line no %d",__FILE__,__LINE__);
    printf("\nThis is line no %d\n",__LINE__);
    printf("\nTime is %s",__TIME__);
    printf("\nDate is %s\n",__DATE__);
    MESSAGE
    return 0;
}

Download the C Program. 

Download the C++ Program. 

The Figure Given Below Shows the Output

C/C++ Puzzles: PART - 18

White Spaces Can Correct Your Program

    

  I still remember the days when I first learned C Programming. One of the first rules I learned was about white spaces in C. "C is a free form language and white spaces will not affect the meaning of the program" was the rule I learned. Up until recently I found this rule perfectly valid. But the following statements shattered my belief. 

   z=x++y;             // This Statement will Give You an Error.
  z=x+  +y;           // This Statement is Correct.
  

   z=x--y;               // This Statement will give you an Error.
  z=x-  -y;             // This Statement is Correct.

  
  z=x++++y;        // This Statement will give you an Error.
  z=x++  +  +y;    // This Statement is Correct.

  
  z=x+++++y;      // This Statement will give you an Error.
  z=x++  +  ++y;  // This Statement is Correct.

Download. 

There might be other examples similar to this. If you know any please post them here.

C/C++ Puzzles: PART - 17

Rule of 'Maximal Munch'

  This rule is also called the 'Greedy Technique', which is used by the lexical analyzer of a C/C++ Compiler. This rule tells us how to evaluate tokens in C/C++. For example consider the following statement.

int x=20, y=10, z;

z=x--y;

 Download.

What is the Output? One possible Output is obtained by considering the statement as z = x-  -y; In that case the Output is 30. But if you compile the code, you will get a syntax error. The rule of 'Maximal Munch' has played a role here. C/C++ lexical analyzer always identifies the largest possible token from a given statement. So the above statement is read by the lexical analyzer as z=x--  y; So instead of recognizing the Minus operator (-) followed by the Unary Minus operator (-), a Unary Decrement operator (--) is recognized by the C/C++ lexical analyzer. Thus the statement shows a syntax error because of the missing semicolon after the Unary Decrement operator.

Now Consider the following Statements.

//1

x=20;

y=10;

z=x++y;

printf("\n%d", z);

//2
x=20;

y=10;

z=x+++y;

printf("\n%d", z); 

//3
x=20;

y=10;

z=x++++y;

printf("\n%d", z);

//4
x=20;

y=10;

z=x+++++y;

printf("\n%d", z);  

 

Which of them works and which of them shows an error ?

If you didn't get the answer, please select the red text area given below using your mouse to view the answer.

1. z=x++y; Shows a Syntax Error because it is taken as 

z=x++  y; by the Compiler.

2. z=x+++y; Shows the Output as 30 because it is taken as 

z=x++  +y; by the Compiler.

3. z=x++++y; Shows a Syntax Error because it is taken as 

z=x++   ++y; by the Compiler.

4. z=x+++++y; Shows a Syntax Error because it is taken as 

z=x++  ++  +y; by the Compiler.        

 

Petersen Graph: Find the Odd One Out.

  There are four Graphs given below. Find the odd one out from those four Graphs. I will give you a clue. You have to look for Petersen Graph.

A

 

B

C

 

D

Three of the four Graphs given above are isomorphic to each other. Isomorphic Graphs are equivalent to each other. The Graph is called Petersen Graph which is very important in Graph Theory such that entire text books are dedicated for discussing them.

If you didn't get the answer, then please select the Red Text Field given below using your mouse to view the answer.

The Odd one is C. The Graphs A, B, and D are isomorphic and called Petersen Graph.

 

Number of Possible Arrangements of N Objects

  Recently I read a book on Probability and I have come across a few useful formulas to find out the number of possible arrangements of N objects with different restrictions. This type of questions are frequently asked in many competitive examinations held for persons with a Computer Science back ground. So I am posting them here.

• N distinct objects are arranged taking R (0<=R<=N) of them at a time with the following restrictions. Repetition is not allowed such that the same object X can't be used more than once. The order of the arrangement is relevant such that AB and BA are distinct. The total number of arrangements is given by the Permutation  P(N,R).

                                         P(N,R) = (N!)/((N-R)!).
                                 Where N! is the Factorial of N. 

• N distinct objects are arranged taking R (0<=R<=N) of them at a time with the following restrictions. Repetition is allowed such that the same object X can be used any number of times. The order of arrangement is relevant such that AB and BA are distinct. The total number of arrangements is given by the following formula.
  

                                         Number of Arrangements = N^R.
                                         Where N, R >= 0. 

• N distinct objects are arranged taking R of them at a time with the following restrictions. Repetition is not allowed such that the same object X can't be used more than once. The order of arrangement is immaterial such that AB and BA are the same. The total number of arrangements is given by Combination  C(N,R).
  

                                         C(N,R) = (N!)/((N-R)!(R!)).
                                         Where N! is the Factorial of N and N, R >= 0.

• N distinct objects are arranged taking R of them at a time with the following restrictions. Repetition is allowed such that the same object X can be used any number of times. The order of arrangement is immaterial such that AB and BA are the same. The total number of arrangements is given by Combination with repetition.
  

                      Number of Arrangements =  ((N+R-1)!)/((N-1)!(R)!).
                      Where N! is the Factorial of N and N, R >= 0.  

• Now consider the Circular Permutation of N distinct objects. The total number of arrangements is given by the following formula.
  

                                         Number of Arrangements = (N-1)!.
                                         Where (N-1)! is the Factorial of (N-1). 

C/C++ Puzzles: PART - 16

Identifier Names can be Confusing

  

Names given to identifiers are often confusing to beginners in C/C++ programming. But sometimes even expert programmers will have their share of trouble with some of the valid identifier usage in C/C++. For example consider the code given below. It is a perfectly valid C code.

#include<stdio.h>
struct ok
{
   int ok;
}ok;
int main()
{
   // int ok; // This Statement will give you an Error.
   ok.ok=111;
   printf("Value of ok.ok is %d\n",ok.ok);
   ok:printf("Hello!!!\n");
   if(ok.ok==111)
   {
      ok.ok=222;
      goto ok;
   }
 }

Download the C Program. 
Download the C++ Program. 

The same identifier name ok is used as the structure name, a structure member, structure variable and a label for goto statement. Such a repeated use of same identifier is allowed in C/C++ until conflicts occur. If you add the statement int ok; to the program there arises a conflict and thus you will get an error. Otherwise there is no error. 

The Output is Shown Below

C/C++ Puzzles: PART - 15

Pointers and Constants

Consider the two declarations given below.

const char *str1;

char const *str2;

Both the declarations are same and tells the compiler that the pointers point to a constant string. But the pointers themselves are not constant.

Now consider the declaration given below.

char *const str3;

Here the pointer is a constant but the string pointed by the pointer is not a constant.

Now consider the declaration given below.

const char *const str4;
Here both the pointer and the string the pointed by the pointer are constants.

The program given below shows the difference between the above mentioned pointers.

#include<stdio.h>
int main()
{
     char const *str1="Hello";
     const char *str2="Hello";
     char *const str3="Battle";
     const char *const str4="Battle";
     printf("\nstr1 is %s",str1);
     //*str1='h'; //This Statement will give you an Error.
     str1="Hai";  // This Statement works fine.
     printf("\nNow str1 is %s",str1);
     printf("\nstr2 is %s",str2);
     //*str2='h'; //This Statement will give you an Error.
     str2="Hai";  // This Statement works fine.
     printf("\nNow str2 is %s",str2);
     printf("\nstr3 is %s",str3);
     //str3="Cattle"; //This Statement will give you an Error.
     *str3='C';  // This Statement works fine.
     printf("\nNow str2 is %s",str3);
     printf("\nstr4 is %s\n\n",str4);
     //*str4='C'; //This Statement will give you an Error.
     //str4="Cattle"; //This Statement will also give you an Error.
     return 0;
}


Download.

Figure Below Shows the Output

Graph Homeomorphism

  Two graphs G and H are said to be homeomorphic if there is an Isomorphism from some subdivision of G to some subdivision of H. A subdivision of a Graph is obtained by adding vertices in the middle of existing edges. Homomorphism and Homeomorphism are different. Homomorphism is discussed in the previous post. If you have any doubt refer that post.

Figure Given Below Shows Graphs N, O and P which are Subdivisions of Graph M

  Two graphs are homeomorphic if and only if they have at least one common subdivision. 

The Two Graphs Shown Below are Homeomorphic to each other

 

The Common Subdivision of the Two Graphs is Shown Below

Homomorphism Vs. Isomorphism

  Homomorphism and Isomorphism are two confusing topics in Graph Theory. I have learned many definitions for both of them. But frankly none of them were very helpful. So I thought it might be a good idea to differentiate between Graph Homomorphism and Isomorphism.

I just want to mention a few points regarding Isomorphisms and Homomorphisms.

• If a Graph M is Isomorphic to N then they are equivalent. They have equal number of edges and vertices with same structure. The two graphs given below are Isomorphic to each other.

 

• The two graphs given above are also Homomorphic to each other. So we can conclude that all Isomorphisms are also Homomorphisms. But the converse is not true. All Homomorphisms are not Isomorphisms.
• If M is Homomorphic to N and N is Homomorphic to M, Then they are also Isomorphic to each other. Thus they are equivalent.
• Homomorphism is a structure preserving transformation. A Homomorphism simply maps adjacent vertices of the first graph to adjacent vertices of the second graph. The figure given below shows a graph G which is Homomorphic to a graph H.

• In Graph H the vertex X represents the two vertices 1 and 2 of Graph G. The two vertices has combined but the edge relationship is preserved. But the two graphs are not Isomorphic since Graph H is not Homomorphic to Graph G.   

C/C++ Puzzles: PART - 14

Beware of the Return Type of Functions

  In C and C++ there is a rich set of library functions available. But we must be very careful about the return type of functions. For example consider the program given below. 

#include<stdio.h>
int main()
{
   int i=-1;
   if(i<sizeof(int))
   {
       printf("\nThis is the expected Output, since sizeof(int) is 4\n");
   }
   else
   {
       printf("\nThis is the actual Output\n");
   }
}

Download. 

The expected Output is the message "This is the expected Output, since sizeof(int) is 4", but the actual Output is the message "This is the actual Output".

The Figure Below Shows the Output

 What is the reason? The return type of sizeof is unsigned int. Therefor the value of integer i is also considered as an unsigned integer. Thus the value of i becomes a large positive integer (4294967295) which is greater than 4.