NRI INSTITUTE OF INFORMATION SCIENCE

& TECHNOLOGY BHOPAL

DEPARTMENT OF COMPUTER SCIENCE &

ENGINEERING

LAB MANUAL

Data Structure
(CS – 303)

BACHELOR OF TECHNOLOGY
Course Objectives:

This course's objectives are to develop students' abilities to construct

and analyze basic linear and nonlinear data structures. It improves
students' capacity to recognize and use the best data structure for
the given real-world issue. It helps them to learn about actual data
structure applications.

Course Outcomes:
After successful completion of course, students will be able to:

CO1: Compute asymptotic notations of an algorithm to analyze the

Consumption of resources (time/space).

CO2: Implement stack, queue and list to manage the memory using

static and dynamic allocations

CO3: Identify appropriate data structure and algorithm for a given

contextual problem.

CO4: Implement binary search trees

CO5: develop code for real life problems like shortest path and MST

using graph theory.

 NRI INSTITUTE OF INFORMATION
SCIENCE & TECHNOLOGY
FORM
NIIST/A/10
NO
DEPT NAME: Computer Science &
Engineering
NIIST BHOPAL
REV.
BRANCH CSE LIST OF EXPERIMENT NO
0
REV.
SEMESTER III 30/06/2011
DT
SUBJECT/CODE :- DATA STRUCTURES / CS 303

[Link]. LIST OF EXPERIMENT

1 Program to input marks of 5 subjects and print the total and percentage using arrays

2 Program to read two 3x3 matrices and add them

3 Program to find whether a matrix is upper triangular or not

4 Program to find the factorial of a number using recursion

Program to perform the following string operations:

a) Find length of entered string b) Concatenate two strings
5
c) Copy one string to another d) Compare two strings
e) Reverse the entered string f) Check whether the entered string is a palindrome

6 Program to create a stack and implement push and pop operations on it

7 Program to create a queue and implement insertion and deletion operations on it

8 Program to create a circular queue & implement insertion & deletion operations on it

9 Program to create a linked list and implement insertion and deletion operations on it

10 Program to traverse a binary tree in pre-order, in-order and post-order

Program to implement sorting of data using: a)Bubble sort b) Selection sort c) Insertion
11
sort
12 Program to implement a graph and traverse it using Breadth First Search

1
 EXPERIMENT NO.1

AIM:

Program to input marks of 5 subjects and print the total and percentage using arrays

INTRODUCTION:

An array is a linear data structure that stores homogeneous data in contiguous memory locations.
In this experiment the user will input marks in 5 subjects which will be stored in an array of size
5. The data in the array will then be added to find the total marks and percentage will be
calculated out of 500.

SOURCE CODE:

#include<iostream.h>
#include<conio.h>
void main()
{
float marks[5],total=0,per;
clrscr();
//Asking for marks from user and adding it to total
for(int i=0;i<=4;i++)
{
cout<<"Enter marks in subject "<<i+1<<":";
cin>>marks[i];
total=total+marks[i];
}
//Calculation of percentage and printing
per=total/5;
cout<<"\nTotal="<<total<<" out of 500\nPercentage="<<per<<"%";
getch();
}
SAMPLE OUTPUT:

Enter marks in Subject 1:90

Enter marks in Subject 2:90

Enter marks in Subject 3:90

Enter marks in Subject 4:90

Enter marks in Subject 5:90

Total=450 out of 500

2
Percentage=90%

VIVA QUESTIONS:

Q.1. What is an array?

Ans. An array data structure or simply an array is a data structure consisting of a collection
of elements (values or variables), each identified by at least one array index or key. An array is
stored so that the position of each element can be computed from its index tuple by a
mathematical formula.

Q.2. What is the syntax of for loop?

Ans. for(variable initialization; test condition; increment/decrement variable)

Body of the loop

Q.3. What is the use of #include<iostream.h>?

Ans. iostream.h is a header file that contains the definition of basic_iostream class template,
which implements formatted input and output.

Q.4. What is the use of #include<conio.h>?

Ans. conio.h is a C header file used mostly by MS-DOS compilers to provide

console input/output.

Q.5. What is the difference between getch() and getche()?

Ans.

 getch - Reads a character directly from the console without buffer, and without echo.
 getche - Reads a character directly from the console without buffer, but with echo.

3
 EXPERIMENT NO.2

AIM:

Program to read two 3x3 matrices and add them

INTRODUCTION:

The user will be required to input the elements in the 3x3 matrices A and B. The elements of the
matrices would be added and stored in matrix C. Nested for loops would be used for entering
elements into the matrices and to calculate the sum matrix.

SOURCE CODE:

#include<iostream.h>
#include<conio.h>
void main()
{
int a[3][3],b[3][3],c[3][3],i,j;
clrscr();
cout<<"MATRIX A\n";
//Matrix values to be entered by user
for(i=0;i<=2;i++)
{ for(j=0;j<=2;j++)
{
cout<<"\nEnter element:";
cin>>a[i][j];
}
}
cout<<"\nMATRIX B\n";
for(i=0;i<=2;i++)
{ for(j=0;j<=2;j++)
{
cout<<"\nEnter element:";
cin>>b[i][j];
}
}
//Addition of two matrices
cout<<"\nMATRIX C=MATRIX A+MATRIX B\n";
for(i=0;i<=2;i++)
{ cout<<"\n\n";
for(int j=0;j<=2;j++)
{ c[i][j]=a[i][j]+b[i][j];
cout<<c[i][j]<<"\t";
}
}

4
 getch();
}

SAMPLE OUTPUT:

MATRIX A:

Enter element:2

Enter element:2

Enter element:2

Enter element:2

Enter element:2

Enter element:2

Enter element:2

Enter element:2

Enter element:2

MATRIX B:

Enter element:2

Enter element:2

Enter element:2

Enter element:2

Enter element:2

Enter element:2

Enter element:2

Enter element:2

Enter element:2

5
MATRIX C=MATRIX A+MATRIX B

4 4 4

4 4 4

4 4 4

VIVA QUESTIONS:

Q.1. What is a matrix?

Ans.

A matrix (plural matrices) is a rectangular array of numbers, symbols, or expressions, arranged

in rows and columns. The individual items in a matrix are called its elements or entries. An
example of a matrix with 2 rows and 3 columns is

Q.2. What are nested for loops?

Ans. A for loop within a for loop is known as nested for loop.

For example: for(i=0;i<=2;i++)

{ for(j=0;j<=2;j++)
{
// Body of the loop
}
}

Q.3. What will be index of the first element off a 2x2 matrix in C++?
Ans. 0,0
Q.4. What are the major programming tasks performed in this experiment?
Ans.
A) Variable declarations
B) Entering values in Matrix A
C) Entering values in Matrix B

6
D) Addition and display of resultant matrix
Q.5. Why do you use \n and \t?
Ans.
\n is used for new line and \t is used for tab

7
 EXPERIMENT NO.3
AIM:

Program to find whether a matrix is upper triangular or not

INTRODUCTION:

In an nxn matrix, if all elements below the diagonal are 0, then it is called an upper triangular
matrix. Similarly, in an nxn matrix, if all elements above the diagonal are 0, then it is called a
lower triangular matrix.

Example:

2 2 2 3 0 0

0 3 3 5 3 0

0 0 5 2 4 5

Upper Triangular Matrix Lower Triangular Matrix

SOURCE CODE:

#include<iostream.h>
#include<conio.h>
void main()
{
int a[10][10],i,j,n,flag;
clrscr();
cout<<"Enter order of the matrix:";
cin>>n;
//Matrix values to be entered by the user
cout<<"\nEnter matrix elements:\n";
for(i=0;i<=n-1;i++)
{
for(j=0;j<=n-1;j++)
{
cout<<"a["<<i<<"]["<<j<<"]=";
cin>>a[i][j];
}
}
//Check for upper triangular matrix
flag=1;
for(i=0;i<=n-2;i++)
{
for(j=i+1;j<n;j++)

8
 {
if(a[j][i]!=0)
{
flag=0;
break;
}
}
}
if(flag)
cout<<"Upper Triangular Matrix";
else
cout<<"Not an Upper Triangular Matrix";
getch();
}

SAMPLE OUTPUT 1:

Enter order of the matrix:3

Enter matrix elements:

a[0][0]=2

a[0][1]=2

a[0][2]=2

a[1][0]=2

a[1][1]=2

a[1][2]=2

a[2][0]=2

a[2][1]=2

a[2][2]=2

Not an Upper Triangular Matrix

SAMPLE OUTPUT 2:

Enter order of the matrix:3

9
Enter matrix elements:

a[0][0]=2

a[0][1]=2

a[0][2]=2

a[1][0]=0

a[1][1]=2

a[1][2]=2

a[2][0]=0

a[2][1]=0

a[2][2]=2

Upper Triangular Matrix

10
VIVA QUESTIONS:

Q.1. What is an upper triangular matrix?

Ans. In an nxn matrix, if all elements below the diagonal are 0, then it is called an upper
triangular matrix.

Q.2. What is a lower triangular matrix?

Ans. In an nxn matrix, if all elements above the diagonal are 0, then it is called a lower
triangular matrix.

Q.3. What are the major programming tasks performed in this experiment?
Ans.
A) Variable declarations
B) Entering values in Matrix A
C) Checking for upper triangular matrix
D) Display result
Q.4. What is the use of break statement?
Ans. break statement is used to terminate the current loop immediately and transfer control to
the statement immediately following that loop.
Q.5. What is the use of flag?
Ans. flag is used for checking the status of initialized variable.

11
 EXPERIMENT NO.4

AIM:

Program to find the factorial of a number using recursion

INTRODUCTION:

A factorial of a number n is the continued product n x (n-1) x (n-2)… .........1

Recursively it could be written as

n!=n x (n-1)!

=n x (n-1) x (n-2)! ……….

= n x (n-1) x (n-2) x… ........... x 1!

Functions which call themselves repeatedly until a certain condition is met, are called recursive
functions.

SOURCE CODE:

#include<iostream.h>
#include<conio.h>
int fact(int);
void main()
{ int n,ans;
clrscr();
cout<<"Enter any number:";
cin>>n;
ans=fact(n); //Calling recursive function fact(int)
cout<<"\nFactorial of "<<n<<"="<<ans;
getch();
}

int fact(int x) //Recursive function body

{ int y;
if(x==0)
return(1);
y=fact(x-1);
return(x*y);
}
SAMPLE OUTPUT:
Enter any number: 5
Factorial of 5=120

12
VIVA QUESTIONS:

Q.1. What is factorial?

Ans. A factorial of a number n is the continued product n x (n-1) x (n-2)… ........ 1

Q.2. What is single recursion and multiple recursion?

Ans. Recursion that only contains a single self-reference is known as single recursion, while
recursion that contains multiple self-references is known as multiple recursion.

Q.3. What are the essential components of a function?

Ans. A) Function prototype

B) Function call

C) Function Body

Q.4. What is a function prototype?

Ans. A function prototype is a declaration of a function that omits the function body but does
specify the function's return type, name and argument types.

Q.5. Which data structure is applied when dealing with a recursive function?

Ans. Recursion, which is basically a function that calls itself based on a terminating condition,
makes use of the stack. Using LIFO, a call to a recursive function saves the return address so that
it knows how to return to the calling function after the call terminates.

13
 EXPERIMENT NO.5

AIM:

Program to perform the following string operations:

a) Find length of entered string

b) Concatenate two strings

c) Copy one string to another

d) Compare two strings

e) Reverse the entered string

f) Check whether the entered string is a palindrome

INTRODUCTION:

A string constant is a one dimensional array of characters terminated by a null (\0) character. A
string can be initialized as follows:

char name[ ]=”ABC”;

A null character will be appended to the string while storing it in memory locations as shown
below:

A B C \0

Hence, null character will be used in string operations to check the end of the string.

SOURCE CODE:

Experiment 5 (a): Program to find the length of the string

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
void main()
{
char a[20];
int c=0,i=0;
clrscr();
cout<<"Enter any string: ";
gets(a);
while(a[i]!=NULL)

14
 {
c++;
i++;
}
cout<<"\nLength of string is "<<c;
getch();
}

SAMPLE OUTPUT:

Enter any string: ABC

Length of string is 3

Experiment 5 (b): Program to concatenate two strings

#include<iostream.h>
#include<conio.h>
void main()
{
char a[15],b[15],c[30]={'\0'};
int i,j,k;
clrscr();
cout<<"Enter the first string:";
cin>>a;
cout<<"Enter the second string:";
cin>>b;
for(i=0;a[i]!=NULL;i++)
c[i]=a[i];
for(j=i,k=0;b[k]!=NULL;j++,k++)
c[j]=b[k];
cout<<"The concatenated string is "<<c;
getch();
}
SAMPLE OUTPUT:

Enter the first string:ABC

Enter the second string:DEF

The concatenated string is ABCDEF

15
Experiment 5 (c): Program to copy one string to another

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
void main()
{
char a[20],b[20]={'\0'};
int i=0;
clrscr();
cout<<"Enter the string: ";
gets(a);
while(a[i]!=NULL)
{
b[i]=a[i];
i++;
}
cout<<"The entered string is "<<a;
cout<<"\nThe copied string is "<<b;
getch();
}
SAMPLE OUTPUT:

Enter the string: ABC

The entered string is ABC

The copied string is ABC

Experiment 5 (d): Program to compare two strings

#include<iostream.h>
#include<conio.h>
void main()
{
char a[15],b[15];
int i,c=0;
clrscr();
cout<<"Enter the first string:";
cin>>a;
cout<<"Enter the second string:";
cin>>b;
for(i=0;a[i]!=NULL||b[i]!=NULL;i++)
{

16
 if(a[i]!=b[i])
{
c=1;
break;
}
}
if(c==0)
cout<<"The entered strings are same";
else
cout<<"The entered strings are not same";
getch();
}

SAMPLE OUTPUT:

Enter the first string: ABC

Enter the second string: ABC

The entered strings are same

Experiment 5 (e): Program to reverse the entered string

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
void main()
{
char a[20],b[20]={'\0'};
int i,len,c=0;
clrscr();
cout<<"Enter any string:";
gets(a);
for(i=0;a[i]!='\0';i++)
c++;
len=c;
for(i=0;i<=len-1;i++)
{
b[i]=a[c-1];
c--;
}
cout<<"Reversed String:";
for(i=0;b[i]!='\0';i++)

17
 cout<<b[i];

getch();
}

SAMPLE OUTPUT:

Enter any string:ABCDE

Reversed String:EDCBA

Experiment 5 (f): Program to check whether the entered string is a palindrome

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
void main()
{
char a[20];
int i,len=0,flag=0;
clrscr();
cout<<"Enter any string:";
gets(a);

for(i=0;a[i]!='\0';i++)
len++;

for(i=0;a[i]!='\0';i++)
{
if(a[i]!=a[len-1])
flag=1;
len--;
}
if(flag)
cout<<"Entered string is not a palindrome";
else
cout<<"Entered string is a palindrome";

getch();
}

SAMPLE OUTPUT 1:

Enter any string: abcddcba

18
Entered string is a palindrome

SAMPLE OUTPUT 2:

Enter any string: abc

Entered string is not a palindrome

19
VIVA QUESTIONS:

Q.1. What is a string?

Ans. A string is traditionally a sequence of characters, either as a literal constant or as some kind
of variable.

Q.2. What is concatenation?

Ans. For any two strings s and t in Σ*, their concatenation is defined as the sequence of symbols
in s followed by the sequence of characters in t, and is denoted st.

Q.3. What is a palindrome?

Ans. A palindrome is a word, phrase, number, or other sequence of symbols or elements that
reads the same forward or reversed.

Q.4. List some string manipulation functions in C++.

strcpy copies one string to another

strncpy writes exactly n bytes/wchar_t, copying from source or adding nulls

strcat appends one string to another

strncat appends no more than n bytes/wchar_t from one string to another

Q.5. List some string examination functions in C++.

strlen returns the length of the string

strcmp compares two strings

strncmp compares a specific number of bytes/wchar_t in two strings

20
 EXPERIMENT NO.6

AIM:

Program to create a stack and implement push and pop operations on it

INTRODUCTION:

A stack is a list of elements in which an element may be inserted or deleted only at one end,
called the top of the stack. It works on the principle of Last In First Out. The insertion
operation is termed as push and the deletion operation is termed as pop. In C/C++, array
indexing begins at 0. So, initially Top pointer is kept at -1.

Algorithm for push operation:

1. If Top=Maxsize-1

then print overflow and exit.

2. Set Top=Top+1

3. Set stack[Top]=Item

4. Exit

Algorithm for pop operation:

1. If Top<0

then print underflow and exit.

2. Item=stack[Top]

3. Set Top=Top-1

4. Return Item

5. Exit

SOURCE CODE:

#include<iostream.h>
#include<conio.h>
#include<process.h>
#define MAX 10
void push(void);
int pop(void);

21
void traverse(void);
int stack[10];
int tos=-1;
void main()
{
clrscr();
char ch1='y';
int ch;
while(ch1=='y')
{
cout<<"\t\t\t\tSTACK";
cout<<"\n [Link]";
cout<<"\n [Link]";
cout<<"\n [Link]";
cout<<"\n Enter your choice:";
cin>>ch;
switch(ch)
{
case 1: push();
break;
case 2: int p;
p=pop();
cout<<"\n The popped element is "<<p;
break;
case 3: traverse();
break;
default: cout<<"\n Wrong choice!!!!!!!!!! ";
}
cout<<"\n Do you want to continue???? ";
cin>>ch1;
}
}
void push() //Function to push element
{
int item;
if(tos==MAX)
{
cout<<"\n Stack full";
getch();
exit(0);
}
else
{
cout<<"\n Enter element to push: ";
cin>>item;

22
 tos=tos+1;
stack[tos]=item;
}
}
int pop() //Function to pop element
{
int item;
if(tos==-1)
{
cout<<"\n Stack empty";
getch();
exit(0);
}
else
{
item=stack[tos];
tos=tos-1;
}
return(item);
}
void traverse() //Function to display stack elements
{
if(tos==-1)
{
cout<<"\n Stack empty";
getch();
exit(0);
}
else
{
for(int i=tos; i>=0; i--)
cout<<stack[i]<<"\t";
}
}
SAMPLE OUTPUT:

STACK

1. PUSH

2. POP

3. TRAVERSE

Enter your choice:1

23
Enter element to push: 12

Do you want to continue???? y

STACK

1. PUSH

2. POP

3. TRAVERSE

Enter your choice:1

Enter element to push: 34

Do you want to continue???? y

STACK

1. PUSH

2. POP

3. TRAVERSE

Enter your choice:3

34 12

Do you want to continue???? y

STACK

1. PUSH

2. POP

3. TRAVERSE

Enter your choice:2

The popped element is 34

Do you want to continue???? y

24
 STACK

1. PUSH

2. POP

3. TRAVERSE

Enter your choice:2

The popped element is 12

Do you want to continue???? y

STACK

1. PUSH

2. POP

3. TRAVERSE

Enter your choice:2

Stack empty

25
VIVA QUESTIONS:

Q.1. What is a stack?

Ans. A stack is a data structure in which only the top element can be accessed. As data is stored
in the stack, each data is pushed downward, leaving the most recently added data on top.

Q.2. Differentiate STACK from ARRAY.

Ans. Data that is stored in a stack follows a LIFO pattern. This means that data access follows a
sequence wherein the last data to be stored will the first one to be extracted. Arrays, on the other
hand, does not follow a particular order and instead can be accessed by referring to the indexed
element within the array.

Q.3. What is the difference between a PUSH and a POP?

Ans. Pushing and popping applies to the way data is stored and retrieved in a stack. A push
denotes data being added to it, meaning data is being “pushed” into the stack. On the other hand,
a pop denotes data retrieval, and in particular refers to the topmost data being accessed.

Q.4. What is LIFO?

Ans. LIFO is short for Last In First Out, and refers to how data is accessed, stored and retrieved.
Using this scheme, data that was stored last , should be the one to be extracted first. This also
means that in order to gain access to the first data, all the other data that was stored before this
first data must first be retrieved and extracted.

Q.5. What is the data structure used to perform recursion?

Ans. Stack. Because of its LIFO (Last In First Out) property it remembers its 'caller' so knows
whom to return when the function has to return. Recursion makes use of system stack for storing
the return addresses of the function calls.

Every recursive function has its equivalent iterative (non-recursive) function. Even when such
equivalent iterative procedures are written, explicit stack is to be used.

26
 EXPERIMENT NO.7
AIM:

Program to create a queue and implement insertion and deletion operations on it

INTRODUCTION:

A queue is a linear data structure that works on the principle of First In First Out. The element
inserted first in the queue will be deleted first. Two variables front and rear would be
implemented to keep a track of the inserted and deleted items. Initially both front and rear will be
at -1. With every insertion rear will be incremented and with every deletion front will be
incremented. Hence all insertions would take place at the rear end and all deletions will take
place at the front end.

For n=10

Condition for empty queue:

front=rear=-1

Queue after 2 insertions:

2 3

front=0 rear=1

Condition for queue full:

2 3 4 5 6 7 8 9 10 11

front=0 rear=9

Insertion Algorithm:

1. If rear=max-1 then print “Queue full” and exit.

2. Set rear=rear+1
3. Set queue[rear]=item
4. Exit

Deletion Algorithm:

1. If front=rear then print ”Queue empty” and exit

27
 2. Set front=front+1
3. Return item=queue[front]
4. Exit

SOURCE CODE:

#include<stdio.h>
#include<conio.h>
#include<process.h>
int queue[5];
long front,rear;
void initqueue();
void display();
void main()
{
int choice,info;
clrscr();
//Initialising queue
initqueue();
while(1)
{
//Displaying menu
printf("\n MENU \n");
printf("[Link] an element in queue\n");
printf("[Link] an element from queue\n");
printf("[Link] the queue\n");
printf("[Link]!\n");
printf("Your choice: ");
scanf("%i",&choice);
switch(choice)
{
case 1: if(rear<4)
{
printf("enter the number");
scanf("%d",&info);

if (front==-1)
{
front=0;
rear=0;
}

else
rear=rear+1;

28
 queue[rear]=info;
}
else
{
printf("queue is full");
getch();
}
break;

case 2: int info;

if(front!=-1)
{
info=queue[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
front=front+1;

printf("no deleted is = %d",info);

}
else
printf("queue is empty");
getch();
break;
case 3: display();
getch();
break;

case 4: exit(0);
break;

default:printf("You entered wrong choice!");

getch();
break;
}
}
}
void initqueue()
{
//Initialising front & rear to -1
front=rear=-1;

29
}
/*displays the current position of the queue*/
void display()
{
int i; //For loop driver
//Displaying elements in queue
for(i=front;i<=rear;i++)
printf("%i\n",queue[i]);
}
SAMPLE OUTPUT:

MENU

[Link] an element in queue

[Link] an element from queue

[Link] the queue

[Link]!

Your choice: 1

enter the number12

MENU

[Link] an element in queue

[Link] an element from queue

[Link] the queue

[Link]!

Your choice: 1

enter the number45

MENU

[Link] an element in queue

[Link] an element from queue

[Link] the queue

[Link]!

30
Your choice: 2

no deleted is = 12

MENU

[Link] an element in queue

[Link] an element from queue

[Link] the queue

[Link]!

Your choice: 3

45

MENU

[Link] an element in queue

[Link] an element from queue

[Link] the queue

[Link]!

Your choice: 4

31
VIVA QUESTIONS:

Q.1. What is a queue?

Ans. A queue is a data structure that can simulates a list or stream of data. In this structure, new
elements are inserted at one end and existing elements are removed from the other end.

Q.2. What is FIFO?

Ans. FIFO is short for First-in, First-out, and is used to represent how data is accessed in a
queue. Data has been inserted into the queue list the longest is the one that is removed first.

Q.3. What is the minimum number of queues needed when implementing a priority queue?

Ans. The minimum number of queues needed in this case is two. One queue is intended for
sorting priorities while the other queue is intended for actual storage of data.

Q.4. What is a dequeue?

A dequeue is a double-ended queue. This is a structure wherein elements can be inserted or

removed from either end.

Q.5. What is the algorithm for insertion and deletion in a queue?

Insertion Algorithm:

1. If rear=max-1 then print “Queue full” and exit.

2. Set rear=rear+1
3. Set queue[rear]=item
4. Exit

Deletion Algorithm:

1. If front=rear then print ”Queue empty” and exit

2. Set front=front+1
3. Return item=queue[front]
4. Exit

32
 EXPERIMENT NO.8

AIM:

Program to create a circular queue and implement insertion and deletion operations on it

INTRODUCTION:

A circular queue is a queue in which the link of the last element points back to the first element.

1 2 3 4 5

SOURCE CODE:

#include<stdio.h>
#include<conio.h>
#define MAXSIZE 5
int cq[10];
int front=-1,rear=0;
void cqinsert();
int cqdelete();
void cqdisplay();
int choice;
char ch;
void main()
{
clrscr();
do
{ printf("--------1. Insert--------- \n");
printf("------- 2. Delete --------- \n");
printf("------- 3. Display ------- \n");
printf("------- 4. Exit ------------ \n");
printf("Enter your choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1 :cqinsert();
break;
case 2 : cqdelete();
break;
case 3 : cqdisplay();
break;

33
 case 4: return;
}
fflush(stdin);
}
while(choice!=4);
}
void cqinsert() //Function to insert element
{
int num;
if(front==(rear+1)%MAXSIZE)
{
printf("Queue is full\n");
return;
}
else
{
printf("Enter the element to be inserted\n");
scanf("%d",&num);
if(front==-1)
front=rear=0;
else
rear=(rear+1) % MAXSIZE;
cq[rear]= num;
}
return;
}
int cqdelete() //Function to delete element
{
int num;
if(front==-1)
{
printf("Queue is Empty\n");
return 0;
}
else
{
num=cq[front];
printf("Deleted element is =%d\n",cq[front]);
if(front==rear)
front=rear=-1;
else
front=(front+1)%MAXSIZE;
}
return(num);
}

34
void cqdisplay() //Function to display queue elements
{
int i;
if(front==-1)
{
printf("Queue is empty\n");
return;
}
else
{
printf("\nThe status of the queue\n");
for(i=front;i<=rear;i++)
{
printf("%d\n",cq[i]);
}
}
if(front>rear)
{
for(i=front;i<MAXSIZE;i++)
{
printf("%d\n",cq[i]);
}
for(i=0;i<=rear;i++)
{
printf("%d\n",cq[i]);
}
}
printf("\n");
}
SAMPLE OUTPUT:

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice

Enter the element to be inserted

12

35
 1. Insert

2. Delete

3. Display

4. Exit

Enter your choice

Enter the element to be inserted

34

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice

Deleted element is =12

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice

Enter the element to be inserted

34

1. Insert

36
 2. Delete

3. Display

4. Exit

Enter your choice

The status of the queue

34

34

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice

37
VIVA QUESTIONS:

Q.1. What is a circular queue?

Ans. A circular queue is a queue in which the link of the last element points back to the first
element.

Q.2. How is a circular queue implemented?

Ans. A circular queue can be implemented using an array or a linked list.

Q.3. What is the use of a switch statement?

Ans. A switch statement is a type of selection control mechanism used to allow the value of
a variable or expression to change the control flow of program execution via a multiway branch.

Q.4. What is a menu driven program?

Ans. In a menu driven program the user gives his choice of input as indicated on the console
menu and depending upon this choice the program fragment is executed.

Q.5. What is the use of #define?

Ans. #define is used to assign value to a variable

38
 EXPERIMENT NO.9

AIM:

Program to create a linked list and implement insertion and deletion operations on it

INTRODUCTION:

Linked lists are list of data elements linked to one another. The logical ordering is represented by
having each element pointing to the next element. Each element is called a node, which has two
parts:

i) info part which stores the information

ii) next part which points to the next element

start Info1 Info2 NULL

SOURCE CODE:

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int info;
struct node *next;
};
typedef struct node NODE;
NODE *start;
void traversinorder(NODE *start)
{
while(start != (NODE *) NULL)
{
printf("%d\n",start->info);
start=start->next;
}
}
void insertatbegin(int item)
{
NODE *ptr;
ptr=(NODE *)malloc(sizeof(NODE));
ptr->info=item;
if(start==(NODE *)NULL)
ptr->next=(NODE *)NULL;

39
 else
ptr->next=start;
start=ptr;
}
void insert_at_end(int item)
{
NODE *ptr,*loc;
ptr=(NODE *)malloc(sizeof(NODE));
ptr->info=item;
ptr->next=(NODE *)NULL;
if(start==(NODE*)NULL)
start=ptr;
else
{
loc=start;
while(loc->next!=(NODE *)NULL)
loc=loc->next;
loc->next=ptr;
}
}

void dele_beg(void)
{
NODE *ptr;
if(start==(NODE *)NULL)
return;
else
{
ptr=start;
start=(start)->next;
free(ptr);
}
}
void dele_end(NODE *start)
{
NODE *ptr,*loc;
if(start==(NODE *)NULL)
return;
else if((start)->next==(NODE *)NULL)
{
ptr=start;
start=(NODE *)NULL;
free(ptr);
}
else

40
 {
loc=start;
ptr=(start)->next;
while(ptr->next!=(NODE *)NULL)
{
loc=ptr;
ptr=ptr->next;
}
loc->next=(NODE *)NULL;
free(ptr);
}
}
void main()
{
int choice,item,after;
char ch;
clrscr();
start=NULL;
do
{ printf("\t\t\t\tLINKED LIST\n");
printf("[Link] element at begining \n");
printf("[Link] element at end \n");
printf("[Link] the linked list\n");
printf("[Link] from the begining\n");
printf("[Link] from the last\n");
printf("[Link]\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the item:");
scanf("%d",&item);
insertatbegin(item);
break;
case 2: printf("Enter the item:");
scanf("%d",&item);
insert_at_end(item);
break;
case 3: printf("\nTraversing the linked list:\n");
traversinorder(start);
break;
case 4: printf("Deleted the item\n");
dele_beg();
break;
case 5: printf("Deleted the item\n");

41
 dele_end(start);
break;
case 6: return;
}
fflush(stdin);
printf("Do your want to continue(y/n)?\n");
scanf("%c",&ch);
}while((ch=='y')||(ch=='y'));

}
SAMPLE OUTPUT:

LINKED LIST

[Link] element at begining

[Link] element at end

[Link] the linked list

[Link] from the begining

[Link] from the last

[Link]

Enter your choice:1

Enter the item:34

Do your want to continue(y/n)?

LINKED LIST

[Link] element at begining

[Link] element at end

[Link] the linked list

[Link] from the begining

[Link] from the last

[Link]

42
Enter your choice:2

Enter the item:56

Do your want to continue(y/n)?

LINKED LIST

[Link] element at begining

[Link] element at end

[Link] the linked list

[Link] from the begining

[Link] from the last

[Link]

Enter your choice:3

Traversing the linked list:

34

56

Do your want to continue(y/n)?

LINKED LIST

[Link] element at begining

[Link] element at end

[Link] the linked list

[Link] from the begining

[Link] from the last

43
[Link]

Enter your choice:4

Deleted the item

Do your want to continue(y/n)?

VIVA QUESTIONS:

Q.1. What is a linked list?

Ans. A linked list is a sequence of nodes in which each node is connected to the node following
it. This forms a chain-like link of data storage.

Q.2. How do you search for a target key in a linked list?

Ans. To find the target key in a linked list, you have to apply sequential search. Each node is
traversed and compared with the target key, and if it is different, then it follows the link to the
next node. This traversal continues until either the target key is found or if the last node is
reached.

Q.3. What are the parts of a linked list?

Ans. A linked list typically has two parts: the head and the tail. Between the head and tail lie the
actual nodes, with each node being linked in a sequential manner.

Q.4. What is a structure?

Ans. Structure is the collection of variables of different types under a single name for better
handling. For example: You want to store the information about person about his/her name,
citizenship number and salary. You can create these information separately but, better approach
will be collection of these information under single name because all these information are
related to person.

Q.5. What is the use of a switch statement?

Ans. A switch statement is a type of selection control mechanism used to allow the value of
a variable or expression to change the control flow of program execution via a multiway branch.

44
 EXPERIMENT NO.10

AIM:

Program to traverse a binary tree in pre-order, in-order and post-order

INTRODUCTION:

Inorder traversal (Symmetric order)

1) Traverse (inorder) the left sub tree

2) Visit the root node
3) Traverse (inorder) the right sub tree

Preorder traversal

1) Visit the root node

2) Traverse(preorder) the left sub tree
3) Traverse (preorder) the right sub tree

Postorder traversal

1) Traverse(postorder) the left sub tree

2) Traverse (postorder) the right sub tree
3) Visit the root node

Example:

B C

D F
E

Inorder: GDBEACF

Preorder: ABDGECF

Postorder: GDEBFCA

45
SOURCE CODE :

#include<iostream.h>
#include<stdio.h>
#include<process.h>
#include<conio.h>
#include<alloc.h>
struct rec
{
long num;
struct rec *left;
struct rec *right;
};
struct rec *tree=NULL;
struct rec *insert(struct rec *tree,long num);
int select();
void preorder(struct rec *tree);
void inorder(struct rec *tree);
void postorder(struct rec *tree);
int count=1;
void main()
{
clrscr();
int choice;
long digit;
do
{
choice=select();
switch(choice)
{
case 1: puts("Enter integer: To quit enter 0");
cin>>digit;
while(digit!=0)
{
tree=insert(tree,digit);
cin>>digit;
}continue;
case 2: puts("\npreorder traversing TREE");
preorder(tree);continue;
case 3: puts("\ninorder traversing TREEE");
inorder(tree);continue;
case 4: puts("\npostorder traversing TREE");
postorder(tree);continue;
case 5: puts("END");

46
 exit(0);
}
}while(choice!=5);
}
int select()
{
int selection;
do
{
puts("\nEnter 1: Insert a node in the BT");
puts("Enter 2: Display(preorder)the BT");
puts("Enter 3: Display(inorder)the BT");
puts("Enter 4: Display(postorder)the BT");
puts("Enter 5: END");
puts("Enter your choice");
cin>>selection;
if((selection<1)||(selection>5))
{
puts("wrong choice:Try again");
getch(); }
}while((selection<1)||(selection>5));
return (selection);
}
struct rec *insert(struct rec *tree,long digit)
{
if(tree==NULL)
{
tree=(struct rec *)malloc(sizeof(struct rec));
tree->left=tree->right=NULL;
tree->num=digit;count++;
}
else
if(count%2==0)
tree->left=insert(tree->left,digit);
else
tree->right=insert(tree->right,digit);
return(tree);
}
void preorder(struct rec *tree)
{
if(tree!=NULL)
{
cout<<"\n"<<tree->num;
preorder(tree->left);
preorder(tree->right);

47
 }
}
void inorder(struct rec *tree)
{
if(tree!=NULL)
{
inorder(tree->left);
cout<<"\n"<<tree->num;
inorder(tree->right);
}
}
void postorder(struct rec *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
cout<<"\n"<<tree->num;
}

SAMPLE OUTPUT:

Enter 1: Insert a node in the BT

Enter 2: Display(preorder)the BT

Enter 3: Display(inorder)the BT

Enter 4: Display(postorder)the BT

Enter 5: END

Enter your choice

Enter integer: To quit enter 0

23

45

67

48
Enter 1: Insert a node in the BT

Enter 2: Display(preorder)the BT

Enter 3: Display(inorder)the BT

Enter 4: Display(postorder)the BT

Enter 5: END

Enter your choice

preorder traversing TREE

23

45

67

Enter 1: Insert a node in the BT

Enter 2: Display(preorder)the BT

Enter 3: Display(inorder)the BT

Enter 4: Display(postorder)the BT

Enter 5: END

Enter your choice

inorder traversing TREEE

45

23

67

49
Enter 1: Insert a node in the BT
Enter 2: Display(preorder)the BT
Enter 3: Display(inorder)the BT
Enter 4: Display(postorder)the BT
Enter 5: END
Enter your choice

END

50
VIVA QUESTIONS:

Q.1. List out few of the Application of tree data-structure?

Ans.

1. The manipulation of Arithmetic expression,

2. Symbol Table construction,
3. Syntax analysis.

Q.2 What are binary trees?

Ans. A binary tree is one type of data structure that has two nodes, a left node and a right node.
In programming, binary trees are actually an extension of the linked list structures.

Q.3. Explain Binary Search Tree

Ans. A binary search tree stores data in such a way that they can be retrieved very efficiently.
The left subtree contains nodes whose keys are less than the node’s key value, while the right
subtree contains nodes whose keys are greater than or equal to the node’s key value. Moreover,
both subtrees are also binary search trees.

Q.4. What is the minimum number of nodes that a binary tree can have?

Ans. A binary tree can have a minimum of zero nodes, which occurs when the nodes have
NULL values. Furthermore, a binary tree can also have 1 or 2 nodes.

Q.5. List the operations that can be performed on a Binary Tree.

Ans. 1) Insert a node in the BT

2) Display(preorder)the BT

3) Display(inorder)the BT

4) Display(postorder)the BT

5) Delete a node from BT

51
 EXPERIMENT NO.11
AIM:

Program to implement sorting of data using:

a) Bubble sort

b) Selection sort

c) Insertion sort

INTRODUCTION:

Bubble Sort

Multiple swapping take place in one pass. Smaller elements move or bubble up to the top of the
list. Adjacent members of the list to be sorted are compared. For obtaining ascending order, if the
item on left is greater than the item immediately right to it, they are swapped. This process is
carried on till the list is sorted.

Example:

List: 85 66 53 33 27

Pass I 66 53 33 27 85

Pass II 53 33 27 66 85

Pass III 33 27 53 66 85

Pass IV 27 33 53 66 85

Selection Sort

Perform a search through the table starting from the first record to locate the element with the
smallest key. Interchange it with the first record. Thus, the smallest key is placed in the first
position. In the second iteration, locate the second smallest key, examining the keys of the
records starting from the second record onwards. Interchange it with the second record. Continue
the process until all records are sorted.

Example:

List: 45 25 75 15 65 55 95 35

Pass I 15 25 75 45 65 55 95 35

52
Pass II 15 25 75 45 65 55 95 35

Pass III 15 25 35 45 65 55 95 75

Pass IV 15 25 35 45 65 55 95 75

Pass V 15 25 35 45 55 65 95 75

Pass VI 15 25 35 45 55 65 95 75

Pass VII 15 25 35 45 55 65 75 95

Insertion Sort:

Suppose an array A with n elements A[1], A[2]…..A[n] is in memory. The insertion sort
algorithm scans A from A[1] to A[n], inserting each element A[k] into its proper position in the
previously sorted sub array A[1], A[2]…. A[k-1].

Example:

List: 77 33 44 11 88 22 55

Pass I 77 33 44 11 88 22 55

Pass II 33 77 44 11 88 22 55

Pass III 33 44 77 11 88 22 55

Pass IV 11 33 44 77 88 22 55

Pass V 11 33 44 77 88 22 55

Pass VI 11 22 33 44 77 88 55

Pass V 11 22 33 44 55 77 88

SOURCE CODE:

Experiment 11 (a): Program to implement Bubble Sort

#include<stdio.h>
#include<conio.h>
void main()
{

53
int a[100],n,i,j,temp;
clrscr();
printf("How many elements:");
scanf("%d",&n);
printf("Enter the element of array:\n");
for(i=0;i<=n-1;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<=n-1;i++)
{
for(j=0;j<=n-1-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("Elements of array after bubble sorting are:\n");
for(i=0;i<=n-1;i++)
{
printf("%d\n",a[i]);
}
getch();
}
SAMPLE OUTPUT:

How many elements:5

Enter the element of array:

12

34

23

56

45

Elements of array after bubble sorting are:

54
12

23

34

45

56

Experiment 11 (b): Program to implement Selection Sort

#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],n,i,j,temp,loc,min;
clrscr();
printf("\nEnter number of elements:\n");
scanf("%d",&n);
printf("Enter the elements of array:\n");
for(i=0;i<=n-1;i++)
{
scanf("%d",&a[i]);
}
min=a[0];
for(i=0;i<=n-1;i++)
{
min=a[i];
loc=i;
for(j=i+1;j<=n-1;j++)
{
if(a[j]<min)
{
min=a[j];
loc=j;
}
}
if(loc!=1)
{
temp=a[i];
a[i]=a[loc];
a[loc]=temp;
}

55
}
printf("The array after selection sort is:\n");
for(i=0;i<=n-1;i++)
{
printf("%d\n",a[i]);
}
getch();
}

SAMPLE OUTPUT:

Enter number of elements:

Enter the elements of array:

12

34

The array after selection sort is:

12

34

56
Experiment 11 (c): Program to implement Insertion Sort

#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],n,k,i,j,temp;
clrscr();
printf("How many elements:\n");
scanf("%d",&n);
printf("Enter the elements of array:");
for(i=0;i<=n-1;i++)
{
scanf("%d",&a[i]);
}
for(k=1;k<=n-1;k++)
{
temp=a[k];
j=k-1;
while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=temp;
}
printf("Elements of array after insertion sort:\n");
for(i=0;i<=n-1;i++)
{
printf("%d\n",a[i]);
}
getch();
}

SAMPLE OUTPUT:

How many elements:

Enter the elements of array:78

45
34
12
67
57
Elements of array after insertion sort:
12
34
45

67

78

58
VIVA QUESTIONS:

Q.1. What is Bubble Sort?

Ans. Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list
to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong
order. The pass through the list is repeated until no swaps are needed, which indicates that the
list is sorted.

Q.2. What is Selection Sort?

Ans. The algorithm divides the input list into two parts: the sublist of items already sorted, which
is built up from left to right at the front (left) of the list, and the sublist of items remaining to be
sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist
is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on
sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element
(putting it in sorted order), and moving the sublist boundaries one element to the right.
Q.3. What is Insertion Sort?
Ans. Insertion sort iterates, consuming one input element each repetition, and growing a sorted
output list. Each iteration, insertion sort removes one element from the input data, finds the
location it belongs within the sorted list, and inserts it there. It repeats until no input elements
remain.

Q.4. Analyse the various sorting algorithms based on their complexities.

Time Time Time Space

Sorting
Complexity: Complexity: Complexity: Complexity:
Algorithms
Best Average Worst Worst

Quick Sort O(n log(n)) O(n log(n)) O(n^2) O(log(n))

Merge sort O(n log(n)) O(n log(n)) O(n log(n)) O(n)

Bubble sort O(n) O(n^2) O(n^2) O(1)

Insertion sort O(n) O(n^2) O(n^2) O(1)

Selection sort O(n^2) O(n^2) O(n^2) O(1)

59
 EXPERIMENT NO.12

AIM:

Program to implement a graph and traverse it using Breadth First Search

INTRODUCTION:

A graph is a structure G={V,E} in which V is a finite set of nodes and E is a finite set of edges.
It is represented by an adjacency matrix. An adjacency matrix for a graph with n nodes is an
nxn matrix. Any element of the adjacency matrix is either 0 or 1. Aij =1 if there is an edge from
Vi to Vj and Aij=0 if there is no such edge.

Breadth First Search:

Step 1: Start with any vertex and mark it as visited.

Step 2: Using the adjacency matrix of the graph, find a vertex adjacent to the vertex in step 1.
Mark it as visited.

Step 3: Return to vertex in step 1 and move along an edge towards an unvisited vertex, and mark
the new vertex as visited.

Step 4: Repeat step 3 until all vertices adjacent to the vertex, as selected in step 2, have been
marked as visited.

Step 5: Repeat step 1 through step 4 starting from the vertex visited in step 2, then starting from
the nodes visited in step 3 in the order visited. If all vertices have been visited, then continue to
next step.

Step 6: Stop

SOURCE CODE:

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void insert(int);
int q[20],r=-1,g[7][7],row;
void insert(int x)
{
r++;
q[r]=x;
}
remove()
{
60
 int item,k;
item=q[0];
for(k=0;k<r;k++)
q[k]=q[k+1];
r--;
return(item);
}
void main()
{
int i,j, num,w,visited[10],v,j1;
int l,vertices[10],count=0,final[10];
clrscr();
randomize();
printf("Enter no. of vertices:");
scanf("%d", &row);
printf("\nAdjacency Matrix:\n\n");
printf(" ");
for(j=0;j<row;j++)
printf(" Vertex %d ",j);
for(i=0;i<row;i++)
{
for(j=count;j<row;j++)
{
if(i!=j)
{
g[i][j]=random(2);
g[j][i]=g[i][j];
}
else
g[i][j]=0;
}
count++;
}
for(i=0;i<row;i++)
{
printf("\nVertex%d",i);
for(j=0;j<row;j++)
printf("%8d",g[i][j]);
printf("\n\n");
}
for(i=0;i<row;i++)
visited[i]=0;
printf("\n Enter start vertex:");
scanf("%d",&v);
visited[v]=1;insert(v);

61
getch();
clrscr();
printf("\nStart vertex=V%d\n\n",v);
count=1;
j1=0;
while(r>=0)
{
v=remove();
final[j1]=v;
j1++;
l=0;
for(i=0;i<row;i++)
if(g[v][i]==1)
{
vertices[l]=i;
l++;
}
for(i=0;i<l;i++)
{
w=vertices[i];
printf("Step %d:Vertex visited: Vertex %d\n",count,w);
if(visited[w]!=1)
{
insert(w);
visited[w]=1;
}
}
printf("Elements in the queue:");
if(r>=0)
for(j=1;j<=r;j++)
printf("%d",q[j]);
else
printf("Traversal complete");
count++;
printf("\n\n");
getch();
clrscr();
}
printf("BFS Traversal:\n");
if(count==2)
printf("\nIsolated vertex");
else
for(i=0;i<j1;i++)
printf("Vertex %d ",final[i]);
getch();

62
}

SAMPLE OUTPUT:

Enter no. of vertices:4

Adjacency Matrix:

Vertex 0 Vertex 1 Vertex 2 Vertex 3

Vertex0 0 1 1 1

Vertex1 1 0 0 1

Vertex2 1 0 0 0

Vertex3 1 1 0 0

Enter start vertex:2

Start vertex=V2

Step 1:Vertex visited: Vertex 0

Elements in the queue:

Step 2:Vertex visited: Vertex 1

Step 2:Vertex visited: Vertex 2

Step 2:Vertex visited: Vertex 3

Elements in the queue:3

Step 3:Vertex visited: Vertex 0

Step 3:Vertex visited: Vertex 3
Elements in the queue:
Step 4:Vertex visited: Vertex 0
Step 4:Vertex visited: Vertex 1
Elements in the queue: Traversal complete

BFS Traversal:
Vertex 2 Vertex 0 Vertex 1 Vertex 3

63
VIVA QUESTIONS:

Q.1. What is a graph?

Ans. A graph is one type of data structure that contains a set of ordered pairs. These ordered
pairs are also referred to as edges or arcs, and are used to connect nodes where data can be stored
and retrieved.

Q.2. What is a spanning Tree?

Ans. A spanning tree is a tree associated with a network. All the nodes of the graph appear on
the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight
between nodes is minimized.

Q.3. What is a Directed Graph?

Ans. A directed graph or digraph is an ordered pair D = (V, A) with

 V a set whose elements are called vertices or nodes, and

 A a set of ordered pairs of vertices, called arcs, directed edges, or arrows.

Q.4. What is a Weighted Graph?

Ans. A graph is a weighted graph if a number (weight) is assigned to each edge. Such weights
might represent, for example, costs, lengths or capacities, etc. depending on the problem at hand.
Such a graph is also called a network.

Q.5. What is an Undirected graph?

Ans. An undirected graph is one in which edges have no orientation. The edge (a, b) is identical
to the edge (b, a), i.e., they are not ordered pairs, but sets {u, v} (or 2-multisets) of vertices. The
maximum number of edges in an undirected graph without a self-loop is n(n - 1)/2.

64