Learn BTech Information Science Engineering with Free Lessons & Tips

Algorithm

1. Scan the infix expression from left to right.

2. If the scanned character is an operand, output it.

3. Else,

a. If the precedence of the scanned operator is greater than the precedence of the operator in the stack (or the stack is empty), push it.

b. Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence of the operator residing on the top of the stack. Push the scanned operator to the stack.

4. If the scanned character is an ‘(‘, push it to the stack.

5. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘is encountered.

6. Repeat steps 2-6 until infix expression is scanned.

7. Pop and output from the stack until it is not empty.

Heat transfer mechanism in which no medium is required is called radiation. It refers to the movement of heat in waves, as it does not need molecules to travel through. The object need not be in direct contact with one another to transmit heat. Whenever you feel heat without actually touching the object, it is because of radiation. Moreover, colour, surface orientation, etc. are some of the surface properties on which radiation depends greatly.

In this process, the energy is transmitted through electromagnetic waves called as radiant energy. H0t objects generally emit thermal energy to cooler surroundings. Radiant energy is capable of travelling in the vacuum from its source to the cooler surroundings. The best example of radiation is solar energy that we get from the sun, even though, it is miles aways from us.

Registers are faster than memories to access. Hence when we declare a variable with a registerkey word, the compiler gets to know that the variable can be put to registers. Now whether the variables will be put into the register indeed or not, that depends on the compiler and the number and size of the registers for the corresponding hardware.

In general, the variables which are to be used with high frequencies (like loop variables) are the perfect choice for declaring as register, because the gain in speed would be considerable in those cases.

It is not allowed to access the address of the register variables as accessing the address of the register is illegal.

It is perfectly all right to declare a pointer as register because a register can always store the address of other variables if the size of the register permits that to do.

Scope of a variable is defined as the block of code from where we can refer or access it. On the other hand the life time of a variable is defined as the time in between allocating memory for it and relinquishing the memory from it. Let us have an example

void func1(void){

int x = 5;

// do other stuffs

}

void func2(void){

int y = 10;

func1();

//do other stuffs

}

In the above example scope of x is func1 and scope of y is func2. Now when we call func1from func2, then inside func, scope of y is ended but the life time of y still persists, because the memory for y is still not relinquished.

What is Complexity Analysis of Algorithm?

Complexity Analysis, simply put, is a technique through which you can judge about how good one particular algorithm is.  Now the term “good” can mean many things at different times.

Suppose you have to go from your home to the Esplanade! There are many ways from your home that may lead to Esplanade. Take any one, and ask whether this route is good or bad. It may so happen that this route is good if the time of travel is concerned (that is the route is short enough), but at the same time, it may be considered bad taking the comfort into considerations (This route may have many speed breakers leading to discomforts). So, the goodness (or badness as well) of any solution depends on the situations and whatever is good to you right now, may seem as bad if the situation changes. In a nutshell, the goodness/badness or the efficiency of a particular solution depends on some criteria of measurements.

So what are the criteria while analyzing complexities of algorithms?

Focusing only on algorithms, the criteria are Time and Space. The criteria Time, judges how fast or slow the algorithms run when executed; and the criteria Space judges how big or small amount of memory (on primary/hard disks) is required to execute the algorithm. Depending on these two measuring criteria, two type of Algorithm Analysis are done; one is called Time Complexity Analysis and the second one is Space Complexity Analysis.

Which one is more important over the other?

I am sorry! I do not know the answer; rather there is no straight forward answer to this question. Think of yourself. Thinking of the previous example of many solutions that you have for travelling from your home to Esplanade, which criteria is most important? Is it Time of Travel, or is it Comfort? Or is it Financial Cost? It depends actually. While you are in hurry for shopping at New Market, the Time Taken would probably be your choice. If you have enough time in your hand, if you are in jolly mood and if you are going for a delicious dinner with your friends, probably you would choose Comfort; and at the end of the month, when you are running short with your pocket money, the Financial Cost would be most important to you.  So the most important criterion is a dynamic notion that evolves with time.

Twenty or thirty years back, when the pace of advancement of Electronics and Computer Hardware was timid, computer programs were forced to run with lesser amount of memory.  Today you may have gigantic memory even as RAM, but that time, thinking of a very large hard disk was a day dreaming! So at that time, Space Complexity was much more important than the Time Complexity, because we had lesser memory but ample times.

Now the time has changed! Now a day, we generally enjoy large memories but sorry, we don’t have enough time with us. We need every program to run as quick as possible! So currently, Time Complexity wins over Space Complexity.  Honestly, both of these options are equally important from theoretical perspective but the changing time has an effect to these.         

There are two variants of #include. The one is #include and the other one is #include”file”. In general the first form that is #include is used to include system defined header files which are searched in the standard list of system directories. The second form i,e #include”file” is generally used to include user defined header files. These files are searched first in the current directory, if failed, then secondly in the standard list of system directories.

Both the forms of #include share a common property that is no escape sequence or commenting  styles are recognized within or “file”. What I mean to say is that if I write #include <x/*y>, that means I want to include a file named x/*y.  Similarly writing #include<x\y\\z> is also perfect if the file x\y\\z is needed to be included.

The difference is indeed very thin and it depends on the context. In general Function is a piece of code with a name, inputs (arguments) and an output (return types). That is function should always return. Some programming languages are there which uniquely maps inputs to the corresponding outputs. But surely C is not such.  There is also a convention (but not a very strict one) that a function should not change any global variable. In C language, a function is always a realistic part of the code.

Subroutine is just a piece of any sorts of code with a definite entry and exit point. It should not return anything and a subroutine can always change global variables. These are generally used for conceptual purposes like in psudocodes.

Are reference and pointers same?

No.

I have seen this confusion crumbling up among the student from the first day. So better clear out this confusion at thevery beginning.

Pointers and reference both hold the address of other variables. Up to this they look similar, but their syntax and further consequences are totally different. Just consider the following pieces of code

Code 1                                         Code 2

int i;                                             int i;

int *p = &i;                                 int &r = i ;

Here in code 1 we have declared and defined one integer pointer p which points to variable i, that is now , p holds the address of i.

In code 2, we have declared and defined one integer reference r which points to variable i, that is now, r holds the address of i. This is completely same as that of p.

So where is the difference?

The first difference can be found just by looking at the code. Their syntaxes!

 Secondly the difference will come up when they would be used differently to assign a value (suppose 10) to i.

 If you are using a pointer, you can do it like *p = 10; but if you are using a reference, you can do it like r = 10.  Just be careful to understand that when you are using pointers, the address must be dereferenced using the *, whereas, when you are using references, the address is dereferenced without using any operators at all.

 This notion leaves a huge effect as consequences. As the address of the variable is dereferenced by * operator, while using a pointer, you are free to do any arithmetic operations on it. That is you can increment the pointer p to point to the next address just by doing p++. But, this is not possible using references.  So a pointer can point to many different elements during its lifetime; where as a reference can refer to only one element during its life time.

Does C language support references?

No. The concept of reference has been added to C++, not in C. So if you run the following code, C compiler will object then and there.

 #include

#include

int main(void)

{

    int i;

    int &r = i;

    r = 10;

    printf("\n Value of i assigned with reference r = %d",i);

    getch();

    return 0;

}

 But if you are using any C++ compiler, this code will work fine as expected.

 If there is no concept of reference in C language, then how come there exists C function call by reference?

Strictly speaking, there is no concept of function call by reference in C language. C only supports function call by value. Though in some books ( I will not name any one) it is written that C supports function call by reference or the simulation of  function call by reference can be achieved through pointers, I will strongly say that C language neither directly supports function call by reference, nor provides any other mechanism to simulate the same effect.

I know you are at your toes to argue that what about calling a C function with address of a variable and receiving it with a pointer? The change made to that variable within the function has a global effect. How this cannot be treated as an example of function call by reference?

You probably argue with a code like following

 #include

#include

void foo(int* p)

{

     *p = 5;

      printf("\n Inside foo() the value of the variable: %d",*p);

}

int main(void)

{

    int i = 10;

    printf("\n before calling  foo() the value of the variable: %d",i);

    foo(&i);

    printf("\n after calling  foo() the value of the variable: %d",i);

    getch();

    return 0;

}      

  Your code will show the result as 

Your points are well taken. But the thing is what you are showing is not at all calling a function by reference. It just the function call by value! Here you are essentially copying the value of address of your variable i and calling the function foo with that copy. Now eventually in this case, the value that is being passed contains the address of another variable. Within the function, you are accepting this value with a pointer and changing the value of the content addressed by that pointer. So it is nothing but a function call by value only.

 Please note that to change the value of the content addressed by a pointer, you are to use *, no way could it be thought of as a reference.

 Now let me give you one example of true function call by reference

 #include

#include

void foo (int& r1)

{

     r1 = 5;

     printf("\n Inside foo() the value of the variable: %d", r1);

}

int main(void)

{

    int i = 10;

    int &r = i;

    printf("\n before calling  foo() the value of the variable: %d",i);

    foo(r);

    printf("\n after calling  foo() the value of the variable: %d",i);

    getch();

    return 0;

}

 Will this run with your C compiler? No.

 Note:: I have used DevC++ as the coding platform

What is a void pointer?

Void pointer is a special type of pointer which can reference or point to any data type.  This is why it is also called as Generic Pointer.

As a void pointer can point to any data type, neither it is possible to dereference a void pointer, nor is it possible to do any arithmetic operations on void pointer. Hence an explicit type casting is absolutely must for using a void pointer.

What is a null pointer?

A null pointer is also a special type of pointer which points definitively to nothing.

As per official C language description, every valid type of pointer has a special value called “Null Pointer” and this value is always distinguishable from all other pointer values and it is guaranteed to compare unequal to a pointer of any object or function.  

Hold it for a second! So what you are saying is there are different versions of null pointers for every pointer type. Is it so?

No. We cannot call it as a “different versions” rather their internal values are different. But as a programmer, we need not to worry about it because compilers take care of and track the internal values (may be differently depending on the compiler types)

So why don’t you say that a null pointer is a pointer which is not initialized yet?

I cannot go with this idea because an uninitialized pointer may point to any thing. There might be an uninitialized char pointer, an uninitialized int pointer and so on. But a null pointer is definitely something which is there not to point anything.

Ok. Now tell me what is a dangling pointer?

Dangling pointers are the pointers which point to already de allocated or de referenced memory locations. Suppose I write a piece of code like this

int*p;

p = (int*)malloc(n*sizeof(int);

----

----

free(p);

In this piece of code, after allocating some memory to p, we are de allocating the memory which was initially pointed by p. Hence now onwards, p acts as dangling pointer.

How to rectify this?

In this case, after de allocation that is after using free() we should set the pointer p to null as p = NULL   

Could you please exhibit any other source of dangling pointer problems?

Well, there might be other sources also, like

Suppose I have declared int*p, and within a specific scope, I have defined another integer x as 10; and then within that specific scope I am making the pointer p to hold the base address of x. Now outside this specific scope the p will act as a dangling pointer. I can write the code as

void foo (void)

{

   int *p;

   {

          {

int x = 10;

                 p = &x;

          }

          // here p will act as dangling pointer

   }

}

Another case might occur when from a function, we return an address of any variable and a corresponding pointer in the receiver section receives it, then the receiving pointer might get into dangling pointer problem, as just after the returning, as the variable has passed it scope, the memory stack (where the variable is stored currently) might be refreshed. But this phenomenon is not obvious, this might happen.

Fine, so how to deal with this second case?

To deal with this, to be in safer side, we must have the scope of the variable intact out of the function call; declaring it as static might be an option.