Monday 28 September 2015

To be a programming language poet

Learning a programming language is same as learning any natural language. Except programming language have negligible amount of  special words and no ambiguity. Grammar and language specification/standard are major ingredients here.
You can be a poet on the other side of the language, but to reach there I strongly believe that you have to go through them: language specification/standard and grammar. Because all your questions/doubts can be answered with them. It is a bit difficult to understand them because they are intended(mainly) for language implementors, who are assumed to have sound knowledge. But being a poet counts. :)

Monday 24 August 2015

Heapsort program in C

Before talking about heapsort I would prefer to talk about my terrible three-day-debugging story.
I thought of implementing heapsort function as qsort of C's standard library. 
I referred CLRS book for the algorithm. As it should work with any type of data, I needed to use void pointers to implement. Unfortunately, even when I followed algorithm clearly I got bad results during testing. I cross checked it again and again for three days but found no clue what was wrong with that. I figured out that I was doing something wrong while manipulating void pointers. I focused on void pointers usage; and while doing this I got a doubt : why qsort function takes size of each object when it is sufficient to have length of array to sort?
         Actually void specifies no type. So, like int it has no size specified. Then how can we expect incrementing void pointer with 1 will make it point to next object when we don't know the type of object it points to. During the debugging I found that incrementing a void pointer will make it to point next byte but not whatever the next object you are expecting it to point. So I did try sizeof(void) and got result 1. We need to understand that incrementing a type pointer where type is other than void doesn't equal to incrementing a void pointer. Size of each object must be used to calculate the offset from base of the array pointed by void pointer.
        Coming to heapsort, it is better explained in CLRS book. I implemented it as it is. No heuristics added. It is available here. I documented the source code clearly. Be careful. Don't get stuck like me.

Thursday 4 June 2015

Significance of extern and static keywords in C

Consider a module in a C program. When I say a module ,it can be a piece of large project. Let us call it as a translation unit. Because modular programming helps the programmers working on a large project. To understand keywords static and extern , we need to understand linkage and storage classes in C. Most of the times description of the above keywords confuse. Actually there are only two types of storage classes (describes the life time of the variable) in C. Those are
  1. automatic storage class
  2. static storage class
A variable with automatic storage class will have its lifetime equal to the execution time of the block it is defined in.

A variable with static storage will have its lifetime equal the execution time of the program (The variable can retain its value between function calls) .

We can divide any translation unit into two parts.
  1. internal to a function
  2. external to all functions
You can find global definitions/declarations (not every external declaration/definition is global because of scope ) and preprocessor directives (most often) external to all function. Of course you can have preprocessor directives anywhere in the translation unit.


According to the standard all the variables defined external to all functions will have static storage class (It has nothing to do with static keyword).

If you want to define a variable internal to any function with static storage class then you need to use static keyword.


Linkage determines whether the same name in another scope refers to the same object or function. You can have two types of linkages. Those are
  1. internal linkage
  2. external linkage
  3. no linkage
We use internal linkage only for translation unit. You may want to hide some of global variables or function definitions (global means external to all functions ) from other translation units, in that case you can specify internal linkage using static keyword. Hence, internally linked variables/functions can't be accessed from other translation units.

We generally use external linkage for communication among translation units. We can allow all translation units to use the same definition of a function/variable. Unless you use static keyword with functions/variables defined they will have external linkage hence can be called/accessed from any translation unit, provided that the translation unit knows the declarations of the functions/variables (may be using header file). What if you want to use the same definition of a variable in all translation units. We know that we can have any number of declarations of a function/variable but only one definition. How can you actually declare a variable. Functions have prototypes to declare (no definition). Here is the way (only way) of declaring a variable in C, i.e, by using extern keyword. This tells the compiler that the identifier has been defined somewhere (and resolve its location during linking) but I will access here.

A block-scope variable defined without extern will have no linkage.

If the definition of the external variable occurs in the translation unit before its use in a particular function, then there is no need for an extern declaration in the function. Because of this reason we are able to access global variables in functions.

Some keywords are used for syntactic convenience in C. That confuses a lot.

We use storage-class specifiers (some keywords) to specify the storage properties of a variable, those are auto , register , static , extern , typedef .

Don't think all these keywords will specify storage class (either automatic or static).

auto - announces variable has automatic storage-class.
register - announces variable has automatic storage-class (if possible store it in CPU registers)
static - It has two roles.
  1.   To specify internally defined variable has static-storage class.
  2.   To announce internal linkage for an identifier (function/variable) defined external to all functions.
extern  - It specifies that this identifier has been defined somewhere(external) hence no need to allocate memory
  1. If you want to use function defined in somewhere we need to use      : extern ret-type func(type arg,...);  . But it is same as   ret-type   func(type    arg,...); . Hence it is optional to use extern with declaration of identifier for a function
  2. For variable identifiers : If you want to use variables defined in someother scope (like other translation units) you need to specify: extern type var-name.
typedef - does not reserve storage and is called a storage-class specifier only for
syntactic convenience (we will talk about it later).

Wednesday 4 March 2015

A Case Study

Problem :
Scientist recently found a new element X, which can have different isotopes up to an atomic value of 199.
Specialty of element X is that when two atoms fuse they produce energy multiple of their atomic value and forms an atom with atomic value of their multiple modulus 199.
For Example :
If atom1 with value 56 and atom2 with value 61 fuse.
They produce energy of 3416 KJ (56 * 61)
Resulting atom will have atomic value (56*61) mod 199 = 33
Scientists created a nuclear reactor to create energy by this method.
Every day they get several atoms of  X from supplier in a particular sequence. Since this element highly radioactive they can’t risk by changing
its sequence. So each atom can fuse only with another atom nearby.
Nevertheless scientists can choose order of fusion thereby maximizing total energy produced.
Now, for given sequence of atomic values, output maximum energy that can be produced.
For Example :
If sequence of atoms are 56,61 & 2
Then they can produce 3416KJ by fusing 56&61 which results in an atom of value 33.
Then they can fuse 33 and 2 to get energy of 66KJ. So total energy generated is 3482.
But if they cleverly choose to fuse atoms 61 & 2 first then they generate 122 KJ with a resulting atom of value 122.
Then if they fuse 122 and 56, they can generate 6832 KJ. So the total energy is 6954.
Hence Maximum energy that can be generated from this sequence is 6954.

INPUT FORMAT :
Input starts with a number specifying number of inputs(n) followed by n space separated integers
specifying atomic values of n atoms.
Line 1  N,where N is the number of atoms in the  sequence to be fused.
Line 2  a1 a2 a3 .... an . where ai -> Atomic value of i th atom. and two atoms are space delimited.

Constraints:
   0 < ai < 199
   1 < n < 1000

OUTPUT FORMAT:
In Line 1  For Valid Input,print E,where E is Integer stating maximum energy that can be produced
For Invalid Input,print INVALID INPUT .


SAMPLE INPUTS AND OUTPUTS :

Sr.no            Input                Output
1                  3
                    15 75 60           8925

2                  J                        INVALID INPUT

3                  3
                    15 0 6               INVALID INPUT

4                  3
                    5 5 199             INVALID INPUT

5                  4
                    15 75 60 45      18515



                                                   :ANALYSIS:
Here, we will be given a sequence of integers (check with constraints provided, if input doesn't satisfy the constraints , exit by prompting INVALID INPUT ) . We should not change the  sequence .
We have to find a pair of elements (adjacent elements only) which maximizes the produced atom's atomic value ((first element's atomic value* second element's atomic value )%199) from the given sequence . Fuse them ( update total energy(multiplication of atomic values of two atoms) and replace those two atoms with new atom produced from them (its atomic value will be (first element's atomic value* second element's atomic value )%199 ) . Do this until we have only one atom in the sequence (In this case we don't have another atom to fuse with and this condition violates one of the constraints provided ) .
                If you observe, our data-structure is shrinking  during execution. Hence, using linked list will be a good idea .

Here is the   PROGRAM IN C .
      Let me know if you have any different approach .

Sunday 8 February 2015

Lexical Analyzer in C

After FAILING to write a Lexical Analyzer in C by just reading the source file character by character, I decided to follow a different approach to make my task simpler:

1.Trim the lines and store the result in a temporary file.
2.Take the above temporary file as input, open another temporary file to write output, look for signs
of string/character constants and comments  as they can enclose any character sequence,
if found, store that in a global data-structure write some key in place of that in new temporary file,
else write the same to the new temporary file.
After step 2 we will have a temporary file which doesn't contain string/character constants (in their place we will have keys)
and comments.
3. Use this temporary file as input and extract pre-processor directories (store them in data-structure and replace with the key)
write o/p to another temporary file.
4. Now the file contains only identifiers/­keywords/numbers/­operators/delimeters and keys we replaced with .
(If a pre-processor statement contain any string constants they will be extracted and replaced with key .
So, while printing, you need some more lines of code to replace the key with the string-constant)
5. Now read character by character and split into tokens (if you find the key print the details in key) I followed the above steps to avoid confusion.

The program I wrote can respond with some errors.
  
This program takes file names as arguments.

If you follow those steps you can write program easily even the program is large.

Let me know if you have any other approach. 

Friday 23 January 2015

General Purpose Merge-Sort

Here is a C program for sorting different types of data in Merge-Sort paradigm . You have to include this program in your application program to use it. And important thing is that you have to specify the type of data you are going to use( Don't worry there is an example). You can sort int,char,char*,float,double,unsigned int,unsigned long types.

Merge-Sort.c contains two useful functions ,those are MergeSort(array,startindex,endindex) and a utility function to print sorted data . Below example uses these .

Here is a C program that uses this program to sort strings ( array of character pointers)

#define type string
#include "MergeSort.c"
int main(void)
    {
    char* array[]={"C programming","Python Programming","Operating System","Unix","Programs for you","How are you"};
    MergeSort(array,0,5);// starting index to last index
    PrintArray(array,0,5);
    return 0;
    }

Here is MergeSort.c .
Let me know if you have any different methods to do this or any questions .

Wednesday 7 January 2015

A Difficult Thing For Beginner

           I feel that a programmer finds it difficult to adopt to certain language constructs that are low-level when compared to a high-level language he/she has worked with.
  Consider a person who learnt Python as one's first computer language and practiced most of the language constructs,  begins to learn C programming. One may feel difficult at the beginning because one's first language has very flexible built-in data-structures and functions than when compared to C.
             The fact that I am one of the examples for the above supports my statement . After I learnt Python, I started experimented with  C. It took me a considerable amount of time to realize how  valuable C is. I kept on wishing that C should've had simple constructs as Python, till I got to know that in fact, Python is a C program.
 Thanks to Mr. Guido Van Rossum for that flexible, general purpose, object oriented, scripting language . If we consider complexities of the programs written in Python and C , compared to C programs, a Python program has a high time and space complexity. We need to know that there is a trad-off between efficiency and flexibility and internal complexity is proportional to flexibility .

Tuesday 6 January 2015

Program To Search A Word In Given Files : C language

Hi,
Here is a C program to search for a string-of-characters in given files line-by-line. That is, it searches for the required search key in each line of the file and prints the no. of occurrences in that line.
It takes a string-of-characters and any number of files separated with space as input via arguments. It uses ANSI C  standard library functions.

NOTE: During execution, if the string-of-characters or file-names has white-spaces in its name, QUOTE that.
 Ex: file-name.exe "I am" "file1.txt" "file2.txt" 
Download file from here

An Inspirational Article

 I found an inspirational article by Erica Heidi. Its wonderful and  inspires those of us who are the creative geniuses (as I'd like to name them, the creators).
 Felt like sharing this because it inspired me a lot.

About This Blog

Dear reader,
I being a Computer Science student, love programming and am keen to know programming methods based on different efficient algorithms. This blog is just my share of the vast ocean of knowledge, mine being only a droplet.