## Breadth First Search in Graphs

Breadth First Search is a technique to visit all the nodes of graph in a well-defined way.This technique can be applied  to  directed,undirected,weighted or unweighted  graph.Queues are used as a data structure to store elements.

• BFS traverses all the nodes and edges of graph.
• BFS in graph with m vertices and n edges takes O(n+m) time.

Example

Say we have a graph as shown in  Fig 1

Fig 1 : A Graph

• Start from any vertex say A.(Fig 2)
• Visit and mark A.
• Look for neighbors of A.
• Result list –> A
• Find all the vertices connected to A.E,B,D are connected to A .
• Pick any random neighbor of A.Say B.

Fig 2 : Mark A

Fig 2 : Mark B

• Visit B and mark it.(Fig 2)
• Add B to the queue.
• Result –> AB
• Look for next vertex which is connected to A.
• Say  D is chosen.
• Result –>ABD
• Visit D and mark it.(Fig 3)
• Add D to the queue.

Fig 3 : Mark D

• Look for any another vertex connected  to A.
• E is connected to A.(Fig 4)
• Visit E and mark it.
• Result –>ABDE
• Add E to the queue.
• Fig 4 : Mark E

• Look for any other vertex connected to A.
• No other vertex is connected to A.
• Now,dequeue B.
•  Find neighbor vertices  connected to B.
• Visit C and mark it.(Fig 5)
• Result –> ABDEC
• Add C to the queue.

Fig 5 : Mark C

• Look for next unvisited element connected to B.
• No other unvisited element is connected to B.
• Dequeue D.
• Look for another unvisited vertices connected to D.
• No other unvisited vertex is connected to D.
• Dequeue E.
• Look for unvisited neighbors of E.
• Visit F and mark it.(Fig 6)
• Result –> ABDECF
• Add F to the queue.

Fig 6 : Mark F

• Look for another vertex connected to E.
• G is connected to E.
• Visit G and mark it.(Fig 7)
• Result –> ABDECFG
• Add G to the queue.

Fig 8 : Mark G

• There are no unvisited neighbors of C,F, and G.
• Dequeue C,F and G one by one.

Short URL: http://tinyit.cc/c27b00
July 16, 2014 | Computer Science
Tags:

## Strings

String is a collection of characters that forms a word.It is stored in one dimensional array and terminated by null(\0) character.The size of array is one more than the length of string as it required to store null character.The compiler itself places a null character at the end of array during its initialization

Syntax

char array_name[array_size] = {‘character 1′,’character 2′,…….,’\0′};

or

char array_name[] = ‘string_name';

Example

```#include <stdio.h>
int main()
{
char website[12]= {'L','e','t','s','l','e','a','r','n','C','S','\0'};//or char website[]="LetslearnCS";
printf("Name of the website is:\t");
printf("%s",website);
return 0;
}
```

Memory Representation of String

The memory representation of a string is given in Fig 1.The addresses of character is assumed for

Fig 1 : Representation of a String in memory

String Functions

There are various predefined  functions in C that are used to perform various operations on strings.In order to use these function a header file string.h must be included in the program.The function definitions are placed in this file.We just call these functions through function call statements.

• strlen()
• strcpy()
• strcat()
• strcmp()
• strchr()

strlen()

This function finds the length of string and gives answer in numeric form.

Syntax

strlen(string_name);

Example

```#include <stdio.h>
#include<string.h>//header file for string functions

int main()
{
char website_name[] ="LetsLearnCS";//string initialization
int len;//len is of int type to store length of string
len = strlen(website_name);//function call
printf("The length of string is %d",len);
return 0;
}
```

If a space is given in between the string,then that is also counted in length by strlen function.

strcpy()

strcpy function copies the content of one string into another string.

Syntax

strcpy(string_1,string_2);

It copies the content of string 2 into string 1.

Example

```#include <stdio.h>
#include<string.h>

int main()
{
char string1[] = "Two-Dimensional";
char string2[] = "Arrays";
printf("String 1 before strcpy() function :%s\n",string1);
printf("String 2 before strcpy() function: %s\n\n",string2);
strcpy(string1,string2);
printf("String 1 after strcpy() function: %s\n",string1);
printf("String 2 after strcpy()function: %s\n",string2);
return 0;
}
```

strcat()

This function concatenates/combines two strings.

Syntax

strcat(string1,string2);

string2 is combined to end of string1.The second string remains as it is.

Example

```#include <stdio.h>
#include<string.h>

int main()
{
char string1[] = "Two-Dimensional";
char string2[] = "Arrays";
printf("String 1 before strcat() function :%s\n",string1);
printf("String 2 before strcat() function: %s\n\n",string2);
strcat(string1,string2);
printf("String 1 after strcat() function: %s\n",string1);
printf("String 2 after strcat()function: %s\n",string2);
return 0;
}
```

strcmp()

This function returns 0 if string 1 and string 2 are same and 1 if they are not same.If the first or few initial characters of both the strings are same then it returns -1.

Syntax

strcmp(string1,string2)

Example

```#include <stdio.h>
#include<string.h>

int main()
{
char string1[] = "Arrays";
char string2[] = "Arrays";
int val;
val= strcmp(string1,string2);
printf("%d",val);
return 0;
}
```

Short URL: http://tinyit.cc/8f4440
July 11, 2014 | Computer Science
Tags:

## Loop Control Statements

Loop Control Statements alter  execution of a program from the normal execution sequence.The statements are as follows

• break
• continue
• goto

### break statement

break statement terminates the execution of loop immediately ineffective of the condition status.The control is transferred to the first statement after the loop block.If break statement is used in nested loops      (Refer : Nesting of Loops) then innermost loop is terminated and control is transferred to outer loop.

Syntax

break;

Program 1

```#include <stdio.h>

int main()
{
int i;
for(i=1;i<20;i=i+2)
{
if(i>15)
{
break;
}
printf("%d\n",i);
}
return 0;
}
```

Program 2

```#include <stdio.h>

int main()
{
int i;
while(i<=15)
{
if(i%2 == 0)
{
printf("%d\n",i);
}
i++;
if(i>10)
{
break;
}

}
return 0;
}
```

### continue statement

continue statement forces to execute( instead of termination)the next iteration and skips some statements.

Syntax

continue;

Program 3

```#include <stdio.h>

int main()
{
int i;

for(i=0;i<10;i++)
{
if(i >5)
{
continue;
i=i+5;
printf("%d\n",i);
}
printf("%d\n",i);
}
return 0;
}```

### goto statement

goto statement jumps the control to a desired labelled statement of a program.The use of goto is generally avoided as it leads to difficult understanding of the control flow.

Syntax

goto label;

…..

….

label:statement;

Program 4

```#include <stdio.h>

int main ()
{
int i,j;
int num;
//printf("Enter the no");
scanf("%d",&num);
for(i=0;i<10;i++)
{
if(num>5)
{
num = num +2;
printf("%d\n",num);
}
else
{
goto LOOP;
}
}
LOOP:for(i=0;i<10;i++)//LOOP is a label
{
num=num+3;
printf("%d\n",num);
}
return 0;
}
```

Short URL: http://tinyit.cc/d42290
July 10, 2014 | Computer Science
Tags:

## Nesting of loops

Loops can be nested if required.Nesting means to have one or more loops inside the main loop.

### Syntax of nested for loops

for(initialization;condition;iteration)

{

for(……)

{

for(…)

{…

}

…….

}

}

while(condition)

{

…..

while(condition)

{

……..

}

….

}

### Syntax of nested do-while loop

do

{

statements;

do

{

statements;

}

while(condition);

}

while(condition);

Example 1

Say we want to print a pattern like

#
# #
# # #
# # # #
# # # # #

Program 1

```#include <stdio.h>

int main()
{
int i,j;
for(i=0;i<5;i++)
{
for(j=0;j<=i;j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
```

Illustration

The working of Program 1 is explained in Fig 1.

Fig 1 : Working of Program 1

Example 2

Say we want to print table of numbers from 5 t0 10.If we need to print a table of single number then single loop can be used.In order to print table of different numbers in a single go,we need nested loop.

Program 2

```#include <stdio.h>

int main()
{

int i,j;
int res;

for(i=5;i<=10;i++)
{
printf("\n");
for(j=1;j<=10;j++)
{
res = i*j;
printf("%d * %d = %d",i,j,res);
printf("\n");

}

}
return 0;
}
```

Short URL: http://tinyit.cc/00849b
July 9, 2014 | Computer Science
Tags:

## do-while loop

The functionality of do-while is slightly different from while and for loop.The condition of do-while is at the bottom of loop and it executes at least once even if the condition is false.The initialization of a variable loop is done before the loop block.

Syntax

do

{

set_of_statements;

}

while(condition);

Example 1

Say we need to print  numbers from 0 to 100.

Program 1

```#include <stdio.h>

int main()
{
int i = 0;
do
{
printf("%d\t",i);
i++;
}
while(i<=100);
return 0;
}
```

Example 2

Say we want to print a table of a user entered number.

Program 2

```#include <stdio.h>

int main()
{
int num,i=1;
int tab;
//printf("Enter the number");
scanf("%d",&num);
do
{

tab = num * i;
printf("%d * %d = %d\n",num,i,tab);
i++;

}
while(i<=10);

return 0;
}
```

Example 3

Say we want to print even numbers and odd numbers from 0-100  separately .

Program 3

```#include <stdio.h>

int main()
{
int i=0;
int j=1;
printf("The even mumbers are :\n");
do
{
printf("%d\t",i);
i=i+2;
}
while(i<=100);
printf("\nThe odd numbers are :\n");
do
{
printf("%d\t",j);
j=j+2;
}
while(j<100);
return 0;
}
```

Example 4

Say we want to print series like 30,27,24,21,18,15,12,9,3.

Program 4

```#include <stdio.h>

int main()
{
int i=30;
do
{
printf("%d\t",i);
i=i-3;

}
while(i>=3);
return 0;
}
```

Short URL: http://tinyit.cc/ec0f9d
July 8, 2014 | Computer Science
Tags:

## while loop

While loop keeps on executing the given statements as long as the condition is true.When the condition  turns out to be false then set of statements in the block never gets executed and the control goes to first line after the while block.

Syntax

while(condition)

{

set_of_statements;

iteration statement;

}

If the condition is true,then set of statements are executed.The value of i is iterated and then control again returns to while condition.If condition is true again then same process is followed otherwise control exits the loop.

Example 1

Say we need to print  numbers from 0 to 100.while loop can also be used instead of for loop to fulfill this task.

Program 1

```#include <stdio.h>

int main()
{
int i=0;
while(i<=100)
{
printf("%d \t",i);
i++;
}
return 0;
}
```

Example 2

Say we want to print a table of a user entered number.

Program 2

```#include <stdio.h>

int main()
{
int n,i=1;
int res;
//printf("Enter the number");
scanf("%d",&n);
while(i<=10)
{
res = n * i;
printf("%d * %d = %d\n",n,i,res);
i++;
}
return 0;
}
```

Example 3

Say we want to print even numbers and odd numbers from 0-100  separately .

Program 3

```#include <stdio.h>

int main()
{
int i=0;
int j=1;
printf("The even numbers are:\n");
while(i<=100)
{
printf("%d\t",i);
i=i+2;
}
printf("\nThe odd numbers are :\n");
while(j<100)
{
printf("%d\t",j);
j=j+2;
}
return 0;
}
```

Example 4

Say we want to print series like  15625,3125,625,125,25,5.

Program 4

```#include <stdio.h>

int main()
{
int i=15625;
while(i>=5)
{
printf("%d\t",i);
i=i/5;
}
return 0;
}
```

Illustration

The working of program 4 is explained in Fig 1.

Fig 1 : Working of Program 4

Short URL: http://tinyit.cc/8489e9

## for loop

Loops are control structures that are used to execute a code several times.There may be situation when we need to print series from 1-100 or we need to print our name 1000 times on screen.It will be inappropriate to use 100 or thousand  times printf for this scenario.Loops can be used to efficiently perform the task as many times as required.There are 3 types of loops used in C language.They are:

• for loop
• while
• do-while

### for loop

for loop is a control structure which has  initialization statement,condition  and iteration statement.

Syntax

for(initialization,condition,iteration)

{

body_of_loop

}

• In initialization,variable is initialized i.e variable is assigned some value.Declaration can also be done in this step.
• If the condition is true,body of the loop is executed otherwise flow of control jumps to next lines of code after the ending of loop.After this,control jumps back to increment statement.
• The incrementation/ decrementation  is done and condition is checked again.If it is true then control goes to body of loop and executes it.
• The same process happens again and again until the condition becomes false.
• When the condition becomes false control exits the for loop.

Example 1

Say we need to print  numbers from 0 to 100.For loop can be used to fulfill this task.

Program 1

```#include <stdio.h>

int main()
{
int i;
printf("Numbers are ");
for(i=0;i<=100;i++)
{
printf("%d\t",i);
}
return 0;
}
```

Illustration

The working of program 1 is explained in Fig 1.

Fig 1 : Working of Program 1

Example 2

Say we want to print a table of a user entered number.

Program 2

```#include <stdio.h>

int main()
{
int n;
int i;
int t;
//printf("Enter the number");
scanf("%d",&n);
printf("The table of %d is:\n ",n);
for(i=1;i<=10;i++)
{
t=n*i;
printf("%d * %d = %d\n",n,i,t);
}

return 0;
}
```

Example 3

Say we want to print even numbers and odd numbers from 0-100  separately .

Program 3

```#include <stdio.h>

int main()
{
int i,j;
printf("The even numbers are:\n");
for(i=0;i<=100;i=i+2)
{
printf("%d\t",i);
}
printf("\nThe odd numbers are:\n");
for(j=1;j<100;j=j+2)
{
printf("%d\t",j);
}
return 0;
}
```

Example  4

Say we want to print series like  64,32,16,8,4,2,1

Program 4

```#include <stdio.h>

int main()
{
int i;
for(i=64;i>0;i=i/2)
{
printf("%d\t",i);
}

return 0;
}
```

Short URL: http://tinyit.cc/24ddd
July 3, 2014 | Computer Science
Tags:

## Decision Making Statements

Decision Making Statements are the statements that imposes one or more conditions on the expression and if the conditions evaluates to be true then specific actions are followed,if not true then some other actions are followed.They are called as decision making as it leads to a particular conclusion/decision.In C,true values are treated as non-zero i.e.1 and false values are treated as 0.The various types of decision making statements are :

• if statement
• if-else statement
• nested if statement
• switch

### if statement

The if statement consists of boolean expression followed by group of statements.If the expression evaluates to be true then block of code inside if is executed otherwise nothing happens.

Syntax

if(boolean_expression)

{

//lines_of_code ;

}

Example

Say we need to find whether a child is eligible for admission in school on basis of age.If his age is greater than/equal to 5 but less than 6 then he is eligible for admission otherwise not.To specify this in C programming language we can use if statement.

Program

```#include <stdio.h>

int main()
{
int age;
//printf("Enter the age of child");
scanf("%d",&age);
if((age>=5) && (age < 6))
{
printf("Chid is eligible for admission");
}
return 0;
}```

### if-else statement

In if-else statement if the condition in if part evaluates to be true then code of lines in if block is executed otherwise code of lines in else part gets executed.

Syntax

if(boolean_expression)

{

code 1;

}

else

{

code 2;

}

Example

Say we need to find larger of two numbers and print the same.The bigger no. can be found out by using if-else statement.

Program

```#include <stdio.h>

int main()
{
int a;
int b;
//printf("Enter two numbers :");
scanf("%d",&a);
scanf("%d",&b);
if(a > b)
{
printf("%d is bigger",a);
}
else
{
printf("%d is bigger",b);
}
return 0;
}
```

### Nested if statement

In nested if statement,one or more if statements are inside another if statement.

Syntax

if(boolean_expression_1)

{

if(expression 2)

{

lines_of_code

}

if(expression 3)

{..}

}

Program

```#include <stdio.h>

int main()
{
int marks;
//printf("Enter the marks of child");
scanf("%d",&marks);
if((marks >=50) && (marks <=100))
{
if((marks >=50) && (marks <=60))
{
printf("Child needs improvement");
}
if((marks >60) && (marks <=70))
{
printf("Child can do better");
}
if((marks >70) && (marks <=80))
{
printf("Good Attempt");
}
if((marks >80) && (marks <=100))
{
printf("Excellent");
}

}
else
{
printf("Failed");
}
return 0;
}
```

### switch statement

The functionality of switch statement is same as of if-else statement.It uses cases for different conditions and code of lines are executed according to the case (whichever is true).Each case has a break statement so that control gets transferred (if case is valid)to out of switch block and other false cases are not executed.It has a default case where code of lines are executed if none of the cases satisfy the mentioned conditions.The expression of switch is the variable on which conditions are based.Constant expressions of cases must match the data type of expression mentioned in switch.

Syntax

switch(expression)

{

case constant-expression 1:

set of statements;

break;

case constant-expression 2:

set of statements;

break;

..

default:

statements;

….

}

Example

```#include <stdio.h>

int main()
{
char alphabet;
//printf("Enter the alphabet:");
scanf("%c",&alphabet);
switch(alphabet)
{
case 'a':
case 'A':
printf("%c is a vowel",alphabet);
break;

case 'e':
case 'E':
printf("%c is a vowel",alphabet);
break;

case 'i':
case 'I':
printf("%c is a vowel",alphabet);
break;

case 'o':
case 'O':
printf("%c is a vowel",alphabet);
break;

case 'u':
case 'U':
printf("%c is a vowel",alphabet);
break;
default:
printf("%c is not a vowel",alphabet);

}

return 0;
}
```

Short URL: http://tinyit.cc/298821
July 1, 2014 | Computer Science

## Functions

A function is a group of statements that performs some specific task.They can be used in other programs depending on their accessibility and are ended by brackets.In order to define a function inside  a program we need to specify three things:

• Function Declaration
• Function Definition
• Function Calling

Some functions are pre-defined like main(),printf(),scanf().We just need to call these type of functions in our program as their definition and declaration are  already stored in other files.The purpose of main() is to start the execution of program.

### Function Declaration

Functions are declared at the top of program in which function call has been placed.It is required to be declared when we define a function in one program and call it another program.It  includes return type,function name and parameters.It tells the compiler how to call the function.

Syntax

return_type function_name(parameter 1, parameter 2,parameter 3,….parameter n);

return_type function_name();

• return_type is the data type of function.It can be void,int,float or char.
• function_name is the name of function.
• parameters are the arguments passed to the function.Parameter has return type and parameter name.Return type is compulsory to mention whereas parameter name is optional in this function declaration.

Example

`float area_circle(int r)`

or

`float area_circle(int)`

### Function Definition

Function definition defines the task/purpose of the function.The purpose is defined in the body of function.

Syntax

return_type function_name(parameters)

{

body_of_function

}

•  return_type is the data type of function
•  function_name is the name of function.
• parameters are the arguments passed to the function.They are optional   in definition.
• body_of_function defines the purpose/task of function.

Example

```float area_circle(int r)
{
float area;
area =3.14 *r*r;
return area;
}```

### Function Calling

To use a function and return results function calling is used.When the control in program reaches the function calling,it gets transferred to function definition and the required task is performed.When return statement or function ending close brace is encountered control gets transferred back to the main program.To call a function simply function name along with arguments is required.The arguments are passed in function calling according to the declaration/definition.There is no need to mention return_type in function calling.

Syntax

function_name(arguments);

Example

`area_circle(5);`

Program 1

```#include <stdio.h>

float area_circle(int r);//Function Declaration
int main() //main function
{
float result;
result = area_circle(5);//Function calling
printf("Area of circle is %f",result);
return 0;
}
float area_circle(int r)//Function Definition
{
float area;
area = 3.14 *r *r;
return area;
}```

Program 2

```#include <stdio.h>
int largest(int,int,int);
int main()
{
int big;// int p=2,q=1,r=7;
big = largest(2,1,7);//largest = (p,q,r);
printf("The largest no is %d",big);
return 0;
}
int largest(int a,int b,int c)
{
if((a>b) && (a>c))
{
return a;
}
else if((b>a && b>c))
{
return b;
}
else
{
return c;
}

}

```

Program 3

```#include <stdio.h>

float area_rectangle(float,float);
float area_triangle(float,float);
float area_square(float);
int main()
{
float res1,res2,res3;
res1 = area_rectangle(3.5,6);
res2 = area_triangle(4.5,7);
res3 = area_square(3);
printf("The area of rectangle is %f\n",res1);
printf("The area of triangle is %f\n",res2);
printf("The area of square is %f\n",res3);
return 0;
}
float area_rectangle(float length,float breadth)//Function definition
{
float area;
area = length * breadth;
return area;
}
float area_triangle(float base,float height)
{
float area; area = 0.5 * base * height;
return area;
}

float area_square(float side)
{
float area;
area = side * side;
return area;
}```

Short URL: http://tinyit.cc/8e898

## Merge Sort

Merge sort is the divide and conquer method to arrange elements in the order.The steps followed in merge sort are :

• Divide the sequence of n elements into two sub-sequences of n/2 elements each.
• Sort the sub-sequences using merge sort.If the size of sequence is 1,nothing more can be done.
• Merge the sub-sequences to form a sorted sequence of elements.

The complexity of merge sort is O(n log n).It runs faster than insertion and bubble sort but requires large amount of memory.

Program

```#include<stdio.h>
void merge(int [],int ,int ,int );
void partition(int [],int ,int );
int main()
{
int a[20];
int i,size;
printf("Unsorted List:\t");
//printf("Enter total no. of elements : ");
scanf("%d",&size);
for(i=0; i<size; i++)
{
scanf("%d",&a[i]);
printf("%d\t",a[i]);
}
printf("\n");
partition(a,0,size-1);
printf("Sorted List  :\t");
for(i=0; i<size; i++)
printf("%d \t",a[i]);
return 0;
}
void partition(int a[],int min,int max)
{
int mid;
if(min<max)
{
mid=(min+max)/2;
partition(a,min,mid);
partition(a,mid+1,max);
merge(a,min,mid,max);
}
}
void merge(int a[],int min,int mid,int max)
{
int temp[20];
int i,j,k,m;
j=min;
m=mid+1;
for(i=min; j<=mid && m<=max ; i++)
{
if(a[j]<=a[m])
{
temp[i]=a[j];
j++;
}
else
{
temp[i]=a[m];
m++;
}
}
if(j>mid)
{
for(k=m; k<=max; k++)
{
temp[i]=a[k];
i++;
}
}
else
{
for(k=j; k<=mid; k++)
{
temp[i]=a[k];
i++;
}
}
for(k=min; k<=max; k++)
a[k]=temp[k];
}
```

Example

Consider a sequence 7,44,2,10,1,35,74,88,5,3,15.We need to sort this  using merge sort.The list contains 11 elements(Fig 1).Divide the list such that first sub-list has 6 elements and second sub-list has 5 elements(vice-versa is also possible).Keep on dividing till we get single elements in the last.After dividing merge all the elements step by step as shown in Fig 2.

Fig 1 : Dividing

Fig 2 : Merging

Short URL: http://tinyit.cc/d2ed
June 26, 2014 | Computer Science
Tags:

Algorithms
Computer Science
Data Structures