Course Name: DATA STRUCTURE

MODULE-II

ARRAY

Dr. Gufran Ahmad Ansari

(Professor)

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

1
MIT WORLD PEACE UNIVERSITY PUNE
CONTENTS MODULE- II
 Array
1. Storage representation, Operation and
applications(Polynomial addition and subtraction)
2. Stack: Operation and applications(infix, postfix and prefix
expression handling)
3. Queue: Operation and applications, concept of Double
ended queue and Priority Queue, Linked representation
of stack and Queue.
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
2
MIT WORLD PEACE UNIVERSITY PUNE
Arrays
 An array is a collection of items of same data type stored at
contiguous memory locations.

 The idea is to store multiple items of the same type together.

 Arrays have a fixed size where the size of the array is defined
when the array is initialized.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

3
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
4
MIT WORLD PEACE UNIVERSITY PUNE
Representation of Arrays:
 Array can be represented in several ways, depending on the
different languages. To make you understand, we can take one
example of the C language. The picture below shows the
representation of the array

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

5
MIT WORLD PEACE UNIVERSITY PUNE
Arrays always store the same type of values.

 int is a type of data value.

 Data items stored in an array are known as elements.

 The location or placing of each element has an index value.

Important: Array can store only the same type of data items.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

6
MIT WORLD PEACE UNIVERSITY PUNE
 In the array a, we have stored all integral values (same type)
 In the array b, we have stored all char values (same type)
 In the array c, there is integral, float, char all types of values and
this is not something an array can store so, option 3 is wrong
because an array cannot store different types of values.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

7
MIT WORLD PEACE UNIVERSITY PUNE
Declaration Syntax of Array:
Variable Type Variable Name[Sequence of Elements];
Example 1: For integral value
int A[10];
Here 10 means, this array A can have 10 integer elements.

Example 2: For character value

char B[10];
This array B can have 10 character elements.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

8
MIT WORLD PEACE UNIVERSITY PUNE
Initialization of an Array:
 If an array is described inside a function, the elements will have
garbage value. And in case an array is static or global, its
elements will be initialized automatically to 0.
 We can say that we can simply initialize elements of an array at
the time of declaration and for that, we have to use the proper
syntax:
Syntax: datatype Array_Name[size] = { value1, value2, value3, …..
valueN };
Types of Arrays:
There are two types of arrays:

(1) One-Dimensional Arrays (2) Multi-Dimensional Arrays

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
9
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
10
MIT WORLD PEACE UNIVERSITY PUNE
Applications of Array
 Arrays are used to implement data structures like a stack, queue, etc.
 Arrays are used for matrices and other mathematical
implementations.
 Arrays are used in lookup tables in computers.
 Arrays can be used for CPU scheduling.

Real-Time Applications of Array:

 Contact lists on mobile phones.

 Arrays are used in online ticket booking portals.
 Pages of book.
 Matrices use arrays which are used in different fields like image
processing, computer graphics, and many more.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

11
MIT WORLD PEACE UNIVERSITY PUNE
Operations Performed in Array
We can perform the different operations on Arrays like;
 Traversal operation
 Search operation
 Insert operation
 Delete operation
 Merge operation
 Sort operation

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

12
MIT WORLD PEACE UNIVERSITY PUNE
TRAVERSAL OPERATION
 We may need to access each element stored in data structure for certain
purpose. This activity is referred to as traversal operation.

 Traversal indicates iterating over each element starting from beginning to the
end or vice-versa.

 For example, we have data structure containing elements in given sequence:

3, 77, 42, 19, 90

 We can traverse this set starting from 3 till 90 via 77, 42 and 19 or in reverse
direction as well.

 All popular data structures like array, linked list, stack and queue supports
these traversal operations.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

13
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
14
MIT WORLD PEACE UNIVERSITY PUNE
Output:

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

15
MIT WORLD PEACE UNIVERSITY PUNE
SEARCH OPERATION
 We may need to find a particular element from the data structure
which satisfy the required search criteria. This activity is referred to
as search operation.

 During search operation, we traverse through all elements and

check the element at various index to find the matching element.

 For example, we have data structure containing elements in given
sequence: 4, 6, 2, 1,3

 We should be able to search element, say 2, easily in the data

structure at index 2 (considering 3 is at index 0)
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
16
MIT WORLD PEACE UNIVERSITY PUNE
Search Elements in Array
 An array is a collection or sequential arrangement of elements
in any given order. Arrays form the basics of the C
programming language.
Enter the size of Array : 5
Enter elements in Array : 4
6
2
1
3
Enter they key: 2
Element found

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

17
MIT WORLD PEACE UNIVERSITY PUNE
 As we see in previous slide, the elements are first entered in no
particular order.
 The elements entered here are 4, 6, 2, 1 and 3.
 The target element is mentioned here as well. The target
element here is 2.
 Once the element is present in the array, it will say “element
found”.

 Thus, the several methods to find an element in an array are as

follows:
1- Using Standard Method
2- Using Function
3- Using Recursion

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

18
MIT WORLD PEACE UNIVERSITY PUNE
Using Standard Method
 Read the array size and store that value into the variable n.

 Read the entered elements and store those elements into an

array a[] using scanf statement and the for loop.
scanf(“%d”,&a[i]) indicates scanf statement reads the entered
element and assigned that element to a[i].

 Read the key which we want to search in an array.

 Compare the key with each element of the array as a[i]==key

and print element found, if the key matches with any element of
the array otherwise print element not found.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

19
MIT WORLD PEACE UNIVERSITY PUNE
#include <stdio.h>
#include <conio.h> for(i=0; i<n; i++)
int main() {
{ if(a[i]==key)
int a[10000],i,n,key; {
printf("Enter size of printf("element found ");
the array : "); return 0;
scanf("%d", &n); }
printf("Enter elements in }
array : "); printf("element not fou
for(i=0; i<n; i++) nd");
{ }
scanf("%d",&a[i]);
}
printf("Enter the key : ");
scanf("%d", &key);

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

20
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
21
MIT WORLD PEACE UNIVERSITY PUNE
Using Function – Search An Element In An Array
 The search() function compares each element of an array with
the key which we want to search using if condition and the for
loop.If any element matches with that key then this function
returns 1, otherwise, it returns 0 to main() function at ‘if”
condition.

 The search() function will be called by passing an array,

array size, key as arguments.

 If the function search() returns 1 to if condition, then if(1) is

true and prints “element found”. If it returns 0 then if(0) is false
and prints “element not found”.
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
22
MIT WORLD PEACE UNIVERSITY PUNE
#include <stdio.h>
#include <conio.h> printf("Enter size of the array
int search(int *a,int n,int key) : ");
{ scanf("%d", &n);
int i; printf("Enter elements in
for(i=0; i<n; i++) array : ");
{ for(i=0; i<n; i++)
if(a[i]==key) {
{ scanf("%d",&a[i]);
return 1; }
} printf("Enter the key : ");
} scanf("%d", &key);
return 0; if(search(a,n,key))
} printf("element found ");
int main() else
{ printf("element not found ");
int a[10000], i, n, key; }

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

23
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
24
MIT WORLD PEACE UNIVERSITY PUNE
INSERT OPERATION
 We may need to insert new element in the data structure. This
activity is referred to as insert operation.

 When we create a data structure, say array, we do so to store

some data in it. This is possible using insertion operation.

 For example, we have data structure containing elements in given
sequence: 3, 77, 42, 19, 90

 We should be able to insert new element (say 100) at any location,

say at index 1, within data structure easily. Once inserted new set
would look like 3, 100, 77, 42, 19, 90
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
25
MIT WORLD PEACE UNIVERSITY PUNE
DELETE OPERATION

 We may need to delete certain elements from the data

structure if it is no longer required. This activity is referred to
as delete operation.

 For example, we have data structure containing elements in
given sequence: 3, 77, 42, 19, 90

 We should be able to delete existing element (say 77) at any

location, say at index 1, within data structure easily. Once
deleted new set would look like 3, 42, 19, 90

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

26
MIT WORLD PEACE UNIVERSITY PUNE
 MERGE OPERATION
 We may need to combine data of different files into a single file. This activity is
referred to as merging.
SORT OPERATION
 We may need to sort data in certain order, say in increasing order or
alphabetically. This is referred to as sorting.

 For example, we have data structure containing elements in given sequence: 3,

77, 42, 19, 90
 We should be able to sort above elements within data structure easily either in
ascending or descending order.

 A good data structure would be well equipped to provide facility for all the
above operations

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

27
MIT WORLD PEACE UNIVERSITY PUNE
POLYNOMIALS
 Polynomials are algebraic expressions that consist of variables
and coefficients. Variables are also sometimes called
indeterminates.

 We can perform arithmetic operations such as addition,

subtraction, multiplication and also positive integer exponents
for polynomial expressions but not division by variable.

 An example of a polynomial with one variable is x2+x-12.

 In this example, there are three terms: x2, x and -12.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

28
MIT WORLD PEACE UNIVERSITY PUNE
 Polynomial is made up of two terms, namely Poly (meaning
“many”) and Nominal (meaning “terms.”).

 A polynomial is defined as an expression which is composed of

variables, constants and exponents, that are combined using
the mathematical operations such as addition, subtraction,
multiplication and division (No division operation by a variable).

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

29
MIT WORLD PEACE UNIVERSITY PUNE
 Based on the numbers of terms present in the expression, it is
classified as monomial, binomial, and trinomial. Examples of
constants, variables and exponents are as follows:

 Constants: Example: 1, 2, 3, etc.

 Variables: Example: g, h, x, y, etc.
 Exponents: Example: 5 in x5 etc.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

30
MIT WORLD PEACE UNIVERSITY PUNE
DEGREE OF A POLYNOMIAL
 The degree of a polynomial is defined as the highest degree of a
monomial within a polynomial. Thus, a polynomial equation
having one variable which has the largest exponent is called a
degree of the polynomial.
Polynomial Degree Example
Constant or Zero Polynomial 0 6
Linear Polynomial 1 3x+1
Quadratic Polynomial 2 4x2+1x+1
Cubic Polynomial 3 6x3+4x3+3x+1
Quartic Polynomial 4 6x4+3x3+3x2+2x+1

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

31
MIT WORLD PEACE UNIVERSITY PUNE
TERMS OF POLYNOMIAL
 The terms of polynomials are the parts of the equation which
are generally separated by “+” or “-” signs. So, each part of a
polynomial in an equation is a term.

 For example, in a polynomial, say, 2x2 + 5 +4, the number of

terms will be 3. The classification of a polynomial is done
based on the number of terms in it.

Polynomial Terms Degree

P(x) = x3-2x2+3x+4 x3, -2x2, 3x and 4 3

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

32
MIT WORLD PEACE UNIVERSITY PUNE
TYPES OF POLYNOMIALS
 Polynomials are of 3 different types and are classified based on
the number of terms in it. The three types of polynomials are:
 Monomial
 Binomial
 Trinomial

 These polynomials can be combined using addition, subtraction,

multiplication, and division but is never division by a variable. A
examples of Non Polynomials are: 1/x+2, x-3

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

33
MIT WORLD PEACE UNIVERSITY PUNE
MONOMIAL
 A monomial is an expression which contains only one term. For
an expression to be a monomial, the single term should be a
non-zero term. A few examples of monomials are:
 5x
3
 6a4
 -3xy

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

34
MIT WORLD PEACE UNIVERSITY PUNE
BINOMIAL
 A binomial is a polynomial expression which contains exactly
two terms. A binomial can be considered as a sum or
difference between two or more monomials. A few examples
of binomials are:

1. – 5x+3,
2. 6a4 + 17x
3. xy2+xy

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

35
MIT WORLD PEACE UNIVERSITY PUNE
TRINOMIAL
 A trinomial is an expression which is composed of exactly
three terms. A few examples of trinomial expressions are:
1. – 8a4+2x+7
2. 4x2 + 9x + 7

Monomial Binomial Trinomial

One Term Two terms Three terms
Example: x, 3y, 29, x/2 Example: x2+x, x3-2x, y+2 Example: x2+2x+20

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

36
MIT WORLD PEACE UNIVERSITY PUNE
SOLVING POLYNOMIALS
 Any polynomial can be easily solved using basic algebra and
factorization concepts.

 While solving the polynomial equation, the first step is to set the
right-hand side as 0.

 The explanation of a polynomial solution is explained in two

different ways:
 Solving Linear Polynomials
 Solving Quadratic Polynomials

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

37
MIT WORLD PEACE UNIVERSITY PUNE
SOLVING LINEAR POLYNOMIALS

 Getting the solution of linear polynomials is easy and simple.

First, isolate the variable term and make the equation as
equal to zero. Then solve as basic algebra operation.

 An example of finding the solution of a linear equation is

given below:

Example: Solve 3x – 9

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

38
MIT WORLD PEACE UNIVERSITY PUNE
SOLUTION:

First, make the equation as 0. So,

3x – 9 = 0
⇒ 3x = 9
⇒ x = 9/3
Or, x = 3.
Thus, the solution of 3x-9 is x = 3.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

39
MIT WORLD PEACE UNIVERSITY PUNE
SOLVING QUADRATIC POLYNOMIALS
 To solve a quadratic polynomial, first, rewrite the expression
in the descending order of degree.

 Then, equate the equation and perform polynomial

factorization to get the solution of the equation. An example
to find the solution of a quadratic polynomial is given below
for better understanding.

Example: Solve 3x2 – 6x + x3 – 18

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

40
MIT WORLD PEACE UNIVERSITY PUNE
SOLUTION:
 First, arrange the polynomial in the descending order of degree
and equate to zero.

⇒ x3 + 3x2 -6x – 18 = 0
Now, take the common terms.
x2(x+3) – 6(x+3) =0
⇒ (x2-6)(x+3)=0
So, the solutions will be x =-3 and
x2 = 6
Or, x = √6

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

41
MIT WORLD PEACE UNIVERSITY PUNE
POLYNOMIAL OPERATIONS
There are four main polynomial operations which are:

 Addition of Polynomials
 Subtraction of Polynomials
 Multiplication of Polynomials
 Division of Polynomials

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

42
MIT WORLD PEACE UNIVERSITY PUNE
ADDITION OF POLYNOMIALS

 To add polynomials, always add the like terms, i.e. the terms
having the same variable and power. The addition of
polynomials always results in a polynomial of the same degree

Example: Find the sum of two polynomials:

5x3+3x2y+4xy−6y2, 3x2+7x2y−2xy+4xy2−5

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

43
MIT WORLD PEACE UNIVERSITY PUNE
SOLUTION:

 First, combine the like terms while leaving the unlike terms as
they are. Hence,

(5x3+3x2y+4xy−6y2)+(3x2+7x2y−2xy+4xy2−5)
= 5x3+3x2+(3+7)x2y+(4−2)xy+4xy2−6y2−5
= 5x3+3x2+10x2y+2xy+4xy2−6y2−5

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

44
MIT WORLD PEACE UNIVERSITY PUNE
SUBTRACTION OF POLYNOMIALS
 Subtracting polynomials is similar to addition, the only difference
being the type of operation. So, subtract the like terms to obtain
the solution.

 It should be noted that subtraction of polynomials also results in

a polynomial of the same degree.

Example: Find the difference of two polynomials:

5x3+3x2y+4xy−6y2, 3x2+7x2y−2xy+4xy2−5

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

45
MIT WORLD PEACE UNIVERSITY PUNE
SOLUTION:

 First, combine the like terms while leaving the unlike terms as
they are. Hence,
(5x3+3x2y+4xy−6y2)-(3x2+7x2y−2xy+4xy2−5)
= 5x3-3x2+(3-7)x2y+(4+2)xy-4xy2−6y2+5
= 5x3-3x2-4x2y+6xy-4xy2−6y2+5

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

46
MIT WORLD PEACE UNIVERSITY PUNE
Exercise-1:
Addition:

(2x2 + 6x + 5) and (3x2 - 2x – 1)

(2x2 + 6y + 3xy) , (3x2 - 5xy - x) and (6xy + 5)

Subtraction:

(4x3 + 2x2 -4x +6)- (2x3 + 4x2 -6x-7)

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

47
MIT WORLD PEACE UNIVERSITY PUNE
Solutions:
1: 5x2 + 4x + 4

2: 5x2 + 6y + 4xy - x + 5

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

48
MIT WORLD PEACE UNIVERSITY PUNE
Subtraction:

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

49
MIT WORLD PEACE UNIVERSITY PUNE
Subtraction:

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

50
MIT WORLD PEACE UNIVERSITY PUNE
Polynomial addition, multiplication (8th degree polynomials) using
arrays
#include<math.h> do
#include<stdio.h> {
#include<conio.h> printf(“nn1 : create 1’st polynomial”);
#define MAX 17 printf(“n2 : create 2’nd polynomial”);
printf(“n3 : Add polynomials”);
void init(int p[]); printf(“n4 : Multiply polynomials”);
void read(int p[]); printf(“n5 : Quit”);
void print(int p[]); printf(“nEnter your choice :”);
void add(int p1[],int p2[],int p3[]); scanf(“%d”,&option);
void multiply(int p1[],int p2[],int p3[]);
void main()
{
int p1[MAX],p2[MAX],p3[MAX];
int option;

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

51
MIT WORLD PEACE UNIVERSITY PUNE
switch(option) case 4:multiply(p1,p2,p3);
{ printf(“n1’st polynomial -> “);
case 1:read(p1);break; print(p1);
case 2:read(p2);break; printf(“n2’nd polynomial -> “);
case 3:add(p1,p2,p3); print(p2);
printf(“n1’st polynomial -> “); printf(“n Product = “);
print(p1); print(p3);
printf(“n2’nd polynomial -> “); break;
print(p2); }
printf(“n Sum = “); }while(option!=5);
print(p3); }
break;

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

52
MIT WORLD PEACE UNIVERSITY PUNE
void read(int p[]) void print(int p[])
{ {
int n, i, power,coeff; int i;
init(p); for(i=0;i<MAX;i++)
printf(“n Enter number of terms :”); if(p[i]!=0)
scanf(“%d”,&n); printf(“%dX^%d “,p[i],i);
/* read n terms */ }
for (i=0;i<n;i++) void add(int p1[], int p2[], int p3[])
{ printf(“nenter a term(power {
coeff.)”); int i;
scanf(“%d%d”,&power,&coeff); for(i=0;i<MAX;i++)
p[power]=coeff; p3[i]=p1[i]+p2[i];
} }
}

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

53
MIT WORLD PEACE UNIVERSITY PUNE
void multiply(int p1[], int p2[], int p3[])
{
int i,j;
init(p3);
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
p3[i+j]=p3[i+j]+p1[i]*p2[j];
}
void init(int p[])
{
int i;
for(i=0;i<MAX;i++)
p[i]=0;

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

54
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
55
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
56
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
57
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
58
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
59
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
60
MIT WORLD PEACE UNIVERSITY PUNE
Output:

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

61
MIT WORLD PEACE UNIVERSITY PUNE
Stack
 A stack is a data structure in which items can be inserted only
from one end and get items back from the same end. There ,
the last item inserted into stack, is the first item to be taken
out from the stack. In short its also called Last in First out
[LIFO].

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

62
MIT WORLD PEACE UNIVERSITY PUNE
Example of STACK (LIFO)
 A Stack of book on table

 Stack of Plates.

 Stack of Tires.

 Coin stack
.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

63
MIT WORLD PEACE UNIVERSITY PUNE
Basic Features of STACK
 Stack is an ordered list of similar data type.
 Stack is a LIFO(Last in First out) structure or we can say FILO(First in
Last out).
 push() function is used to insert new elements into the Stack
and pop() function is used to remove an element from the stack. Both
insertion and removal are allowed at only one end of Stack called Top.
 Stack is said to be in Overflow state when it is completely full and is
said to be in Underflow state if it is completely empty.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

64
MIT WORLD PEACE UNIVERSITY PUNE
Application of STACK

1- Reverse a word

2-Expression Conversion(Infix to Postfix, Postfix to Prefix etc)

3- Wearing/Removing Bangles

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

65
MIT WORLD PEACE UNIVERSITY PUNE
STACK OPERATIONS
TOP: Open end of the stack is called TOP, From this end item can be inserted
or deleted.

PUSH: To insert an item from Top of stack is called push operation. The push
operation change the position of Top in stack.

POP: To put-off, get or remove some item from top of the stack is the pop
operation, We can POP only from top of the stack.

Is Empty: Stack considered empty when there is no item on Top. Is Empty

operation return true when no item in stack else false.

Is Full: Stack considered full if no other element can be inserted on top of the
stack. This condition normally occur when stack implemented through array.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

66
MIT WORLD PEACE UNIVERSITY PUNE
STACK EXAMPLE

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

67
MIT WORLD PEACE UNIVERSITY PUNE
STACK EXAMPLE CONTINUE …

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

68
MIT WORLD PEACE UNIVERSITY PUNE
STACK EXAMPLE CONTINUE…

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

69
MIT WORLD PEACE UNIVERSITY PUNE
Example-1: Assume 5 elements A,B,C,D,E to be added into the stack
one-by-one

C Top = 2
B Top = 1 B
Top = 0 A A A
Top = - 1 Insert A Insert B Insert C
E Top = 4
D Top = 3 D
C C
B B
A A
Insert E

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

70
MIT WORLD PEACE UNIVERSITY PUNE
 DELETE OPERATION
Top -> E
D D Top
C C C Top
B B B B Top
A A A A
Delete E Delete D Delete C

A Top
Top -1
Delete B Delete A

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

71
MIT WORLD PEACE UNIVERSITY PUNE
Operation in STACK

 Operation on stack is generally implemented with two basic

operators such as PUSH and POP

PUSH: Allow adding an element at the top of the stack

POP: Allow to remove and element from the top of the stack

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

72
MIT WORLD PEACE UNIVERSITY PUNE
PUSH Operation:

 The process of adding a new element at the top of the stack is called
push operation. Pushing an element is the stack invoke adding of
element at the top.

 Suppose after inserting an element max size reached is stack is full and
if we want insert one more or new element, it is not possible to insert
any new element.

 This situation is called stack Overflow condition. At this point stack is

present highest location of the stack.

If TOP= MAX SIZE-1 Then stack is full

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

73
MIT WORLD PEACE UNIVERSITY PUNE
Algorithm for PUSH Operation
1-Push(stack, top, item, max)
2-If top = max then
print“ Stack is Over flow”
exit else
3- Read data
4-top=top+1
4-stack[top] = item
5-Stop

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

74
MIT WORLD PEACE UNIVERSITY PUNE
POP Operation
 The process of deleting an element from the top of the stack is called
POP operation.

 After every POP operation the stack is decrement top by 1. Finally

when all the elements are deleted, top points to bottom of the stack.

 When stack is empty it is not possible to delete any element and this
situation is called underflow

If TOP = - 1 then stack is underflow

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

75
MIT WORLD PEACE UNIVERSITY PUNE
Algorithm for POP

1-If top = null then

print“ Stack is Underflow”
exit else
2- stack[top] = null
3-top=top-1
4-stop

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

76
MIT WORLD PEACE UNIVERSITY PUNE
IMPLEMENTATION OF STACK
 A stack can be implanted in anyone of the following ways:

1- Using Array
2- Using Linked List

Array implementation Stack:

 The easiest way to represent a stack is by using one dimensional array

. A particular variable TOP represent the index of last insert variable.

 A stack is an ordered collection of items and C language already

contains a data type is an ordered collection of items such as array.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

77
MIT WORLD PEACE UNIVERSITY PUNE
 A Stack and Array are two entirely different things. The number of
elements in an array is fixed and is assigned by the declaration for
the array.

 A stack on the other hand is fundamentally a dynamic object whose

size is constantly chasing as items are Popped and Pushed.

A Stack in C may declared as a structure containing two objects:

1- An array to hold the elements of the stack

2-A variable TOP is hold the top most elements of the stack is of fixed
size.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

78
MIT WORLD PEACE UNIVERSITY PUNE
 Advantage of array implementation is that implementation of the
stack using an array is easy.

 The array implementation has the following disadvantages:

1- Memory space is wasted if we store less no of items in the array than

the maximum size of the array.

2- Limitation in storing the items into the stack.

3- Insertion and deletion operations in a stack using an array involves

more data movements.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

79
MIT WORLD PEACE UNIVERSITY PUNE
Linked list implementation of stack
 The stack can be represented as a linked list in which top of
the stack is represented by the first item in the list.

 The first item inserted into the stack is pointed out by the
second element by the third and so on.

 In general the (n-1)th element is pointed out by the nth element

Data Link Data Link Data Link

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

80
MIT WORLD PEACE UNIVERSITY PUNE
 In liked list implementation the stack does not need to be of fixed
size there can be any number of elements of nodes in the stack.

 The second advantage of linked list method is that insertion and

deletion operation do not involve more data movement.

 The other advantage of this method is memory space is not wasted

because memory space is allocated only when the user wants to
push an element into the stack

 To implement PUSH we create a new node in the list and attaché it

as the new first element.

 To implement a POP we advance the top of the stack to the second

item in the list
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
81
MIT WORLD PEACE UNIVERSITY PUNE
Infix, Postfix and Prefix
 An expression is any programming language is a meaningful
combination of operands and operations. The operands may
be type of int, float or double

 The operators may be arithmetic, logical, relational or bitwise

 There are three ways of writing arithmetic expressions. They are

Infix, Postfix and Prefix expression.

Let us describe these three from of expressions with example:

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

82
MIT WORLD PEACE UNIVERSITY PUNE
Infix
 It is a form of arithmetic expression in which fix(place) the
arithmetic operator in between two operands.

 This is the usual notation of writing mathematical expression.

 Example 1: Let A and B two operands then the infix from of

expression for arithmetic operators +,-,* and / are given below;

(i) A+B
(ii) A-B
(iii) A*B
(iv) A/B

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

83
MIT WORLD PEACE UNIVERSITY PUNE
 Example 2: If A, B and C three operands then we can write the
following infix form of expression;

(i) (A+B)-C
(ii) A+(B*C)
(iii) (A/B)+C

In infix form of expression parenthesis impose a precedence of

operation. The term precedence refer to the order of evaluation.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

84
MIT WORLD PEACE UNIVERSITY PUNE
Postfix
 It is a form of arithmetic expression in which fix(place) the arithmetic
operator after (Post) its two operands.

 The postfix notation is also called Suffix notation and is also referred
to as reverse polish notation.

 Example 1: Let A and B two operands. We can write postfix (Placing

operator after) expression as given below;
Infix Postfix
A+B AB+
A-B AB-
A*B AB*
A/B AB/

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

85
MIT WORLD PEACE UNIVERSITY PUNE
Example 2: Let A, B and C are operands. We can write postfix from
expression using +, -, * or / as given below;

Infix Postfix

A+B*C ABC*+

A+B-C AB+C-

(A+B)*C AB+C*

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

86
MIT WORLD PEACE UNIVERSITY PUNE
 Let us how postfix expression is obtained. To do this recall the
rules that govern the evaluation of arithmetic expression.
 The given table below shows the precedence of arithmetic
operations
Operation Operators Precedence
Exponential ^ Highest
Multiplication/Division *, / Next
Addition/Subtraction +,- Last

Also Note:
1- Arithmetic is evaluated from Left to Right
2- Exponent Operation is evaluated from Right to Left
3- Parenthesized expression is evaluate first
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
87
MIT WORLD PEACE UNIVERSITY PUNE
Prefix
 It is the form of arithmetic expression in which we fixed (Place)
the arithmetic operator before(Pre) its two operands.
 The prefix form of expression is also called Polish Notation as it
is developed by the Polish Mathematician Jan Lukasiewiez
 Example 1: Let A and B two operands. The we can write prefix
expression using arithmetic operator as given below;
Infix Postfix
A+B +AB
A-B -AB
A*B *AB
A/B /AB
A^B ^AB

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

88
MIT WORLD PEACE UNIVERSITY PUNE
 Example 2: Let A, B and C are operands. The we can write
prefix expression using some of the arithmetic operator as given
below;
Infix Prefix
A+B*C +A*BC

A+B-C -+ABC

(3+4)*(8-9) *+34-89

X/Y^Z+A +/X^YZA

The given expression is converted to its equivalent prefix by doing the

following two steps-

1- Apply the rule that govern the evaluation of arithmetic expression

2- Go on placing the corresponding operator before its two operand.
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
89
MIT WORLD PEACE UNIVERSITY PUNE
 Let us take a example infix expression
A*B+C/D
In the LEFT to Right evaluation * is encountered first. It is same precedence as
that of / . But / comes after * in order to evaluation and + have leave
precedence than * and /
Step-1 Convert A*B to prefix and store in it X
i.e. X=*AB
Step-2 Then the next expression become
X+C/D
Convert C/D to prefix and store it in Y
Y=/CD
Step-3 Then expression X+Y
Step-4 Now convert this expression is prefix form and store in it Z
i.e. Z= +XY

So Z will contains the result Z= +*AB/CD

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

90
MIT WORLD PEACE UNIVERSITY PUNE
Infix to Prefix

(1) (A+B) * (C+D)

+AB * +CD
X Y
*XY
*+AB+CD

(2) (3+4) * (8-9)

+34 * -89
A B
*AB
*+34-89

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

91
MIT WORLD PEACE UNIVERSITY PUNE
Infix to Postfix
3. [ (A+B)*C-D]
1. (A+B) * C [ (AB+)*C-D]
AB+ * C [ (K*C)-D]
X *C [ (KC*)-D],
XC* [(AB+C*)-D],
AB+C* [M-D],
MD-,
2. A+B*C AB+C*D-
A+BC*
A+ X
AX+
ABC*+

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

92
MIT WORLD PEACE UNIVERSITY PUNE
 Infix to Postfix By-Hand Algorithm
1. Given a expression in the infix form.
2. Find the highest precedence operator
3. If there are more then one operators with the same precedence
check associativity, i.e. pick the left most first.
4. Convert the operator and its operands from infix to postfix A + B
--> A B+
5. Repeat steps 2 to 4, until all the operators in the given expression
are in the postfix form.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

93
MIT WORLD PEACE UNIVERSITY PUNE
Infix to Prefix By-Hand Algorithm
1. Given a expression in the infix form.
2. Find the highest precedence operator
3. If there are more then one operators with the same precedence
check associativity, i.e. pick the left most first.
4. Convert the operator and its operands from infix to prefix A + B
--> +A B
5. Repeat steps 2 to 4, until all the operators in the given expression
are in the postfix form.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

94
MIT WORLD PEACE UNIVERSITY PUNE
C language operators Precedence and Associativity

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

95
MIT WORLD PEACE UNIVERSITY PUNE
Infix to Prefix Step by Step Conversion
A*B+C/D (Infix) A*(B+C/D)
*AB+C/D A*(B+/CD)
*AB+/CD A*(+B/CD)
+*AB/CD (Prefix) *A+B/CD

Exercise:
1.Infix ( (A * B) + (C / D) ) to Prefix
2.Infix ((A * (B + C) ) / D) to Prefix
3.Infix (A * (B + (C / D) ) ) to Prefix

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

96
MIT WORLD PEACE UNIVERSITY PUNE
Infix to Postfix using stack
Example: A*B+C become AB*C+

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

97
MIT WORLD PEACE UNIVERSITY PUNE
Example A * (B + C * D) + E becomes A B C D * + * E +

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

98
MIT WORLD PEACE UNIVERSITY PUNE
Example: Infix to Post Fix Conversion (A/(B – C)* D) + E)

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

99
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
100
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
101
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
102
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
103
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
104
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
105
MIT WORLD PEACE UNIVERSITY PUNE
QUEUE
 Queue is a linear data structure type which is used to organize
the data.
 Queue are also an order collection of items. But unlike stacks that
have only one end for insertion and deletion.
 Queue have two ends one end for insertion and other for
deletion. The end which we insert an element is called Rear
end(Back) and where we remove an item is called Front End
 The item removed from the queue in the same order as they
were inserted in the Queue i.e. the first inserted item into queue
will be serviced first and so it has removed first from the Queue.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

106
MIT WORLD PEACE UNIVERSITY PUNE
i.e. the Queue operation performed on FIFO basis. Whenever an
item is removed or deleted from the Queue then the value of front
is incremented by 1

Example:

DELETION 1 2 3 4 5 INSERTION

FRONT REAR

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

107
MIT WORLD PEACE UNIVERSITY PUNE
Operation in Queue
The basic operation that can be performed on a Queue are listed below;

Operation Description Restriction

1- Create Queue It creates new empty Queue

This operation must be carried ---------
out in order to make the Queue
logically accessible

2- Queue insert It insert new data items at Queue Must not full
rear of the Queue

3- Queue delete It deletes and return the data Queue must not
items at the Front of the Queue be empty

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

108
MIT WORLD PEACE UNIVERSITY PUNE
Operation Description
Restriction

4- Create Full It returns true if the Queue

is full otherwise it returns falls ---------

5- Queue empty It returns true if the queue

is empty. Otherwise it returns ---------
false

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

109
MIT WORLD PEACE UNIVERSITY PUNE
Algorithm of Queue Operation
The algorithm for Queue insert and Queue delete operation are given below;

Qinsert:- The operation insert a new data items at the REAR end of the queue.

Qinsert(int Q[ ], int MAXSIZE, int FRONT, int item)

{
if(REAR>=MAXSIZE-1) /*Overflow Condition*/
printf(“ Queue is Full”)
}
REAR=REAR+1; /*Increment rear pointer*/
Q[REAR]=ITEM; /*Insert data items*/
If(FRONT==-1) /*Check proper setting of front pointer*/
FRONT=0;
}
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
110
MIT WORLD PEACE UNIVERSITY PUNE
Qdelete:- The operation deletes and returns the data items at the front of
the queue.

Qdelete(int Q[ ], int FRONT, int REAR, int item)

{
if(FRONT==-1) /*Underflow Condition*/
printf(“ Queue is empty”)
return;
item=Q[FRONT]; /*Delete element*/
if(FRONT==REAR)
FRONT=REAR=-1;
Else
FRONT=FRONT+1;
return(item);
}

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

111
MIT WORLD PEACE UNIVERSITY PUNE
Example :
 Let us consider an example where the queue can hold maximum four
elements. Initially queue is empty.

Empty Queue

FRONT=REAR=-1
F R

Now insert 10 to the queue. Then the Queue status will be

10
R=R+1
F R F=0

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

112
MIT WORLD PEACE UNIVERSITY PUNE
Next, insert 20 to the queue. Now Queue status is

10 20

R=R+1
F R F=0

Again insert an other element 30 to the queue. The status of Queue is

10 20 30

R=R+1
F R

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

113
MIT WORLD PEACE UNIVERSITY PUNE
 Let us delete an element. Remember that the element of the Front is
candidate for removal. So the status of Queue would be

20 30
F=F+1
F R

 Again delete an element. Remember that the element to be deleted

always pointed by the FRONT pointer. So 20 is deleted. Therefore Queue
take the following status
30

F=F+1
F R

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

114
MIT WORLD PEACE UNIVERSITY PUNE
 Now insert a new element 40 in the Queue. The Queue status will be
30 40

R=R+1
F R
 Next insert an other element say 100 to the queue. You can not add 100
to the queue as the REAR crossed maximum size of the queue (i.e. 4).
There will be Queue full signal the status is shown below

30 40

R=R+1
F R

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

115
MIT WORLD PEACE UNIVERSITY PUNE
Types of Queue Operation

There are three main category in a simple Queue

1- Circular Queue

2- Doubled ended Queue (dqueue)

3- Priority Queue

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

116
MIT WORLD PEACE UNIVERSITY PUNE
Simple Queue
 Simple queue defines the simple operation of queue in which
insertion occurs at the rear of the list and deletion occurs at
the front of the list.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

117
MIT WORLD PEACE UNIVERSITY PUNE
Circular Queue
 In circular queue the elements Q[0],Q[1]-------Q[n-1] is represented in
circular fashion.

 In circular Queue in which the insertion of new element is done at the

very first location of the Queue. If the last location of the queue is full.

 Suppose Q is a Queue array of six elements. PUSH and POP operation

can be performed on Circular Queue as:

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

118
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
119
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
120
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
121
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
122
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
123
MIT WORLD PEACE UNIVERSITY PUNE
SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE
124
MIT WORLD PEACE UNIVERSITY PUNE
Double Ended Queue
Double ended queue is a more generalized form of queue data structure
which allows insertion and removal of elements from both the ends, i.e ,
front and back.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

125
MIT WORLD PEACE UNIVERSITY PUNE
Input restricted Double Ended Queue
Double Ended Queue can be represented in TWO ways, those are
as follows...

1. Input Restricted Double Ended Queue

2. Output Restricted Double Ended Queue

Input Restricted Double Ended Queue

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

126
MIT WORLD PEACE UNIVERSITY PUNE
Output restricted Double Ended Queue
 In output restricted double ended queue, the deletion operation is
performed at only one end and insertion operation is performed at
both the ends.

Output Restricted Double Ended Queue

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

127
MIT WORLD PEACE UNIVERSITY PUNE
Priority Queue

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

128
MIT WORLD PEACE UNIVERSITY PUNE
Types of priority Queue
There are two types of Priority Queues:
1). Ascending Priority Queue
2). Descending priority Queue
Ascending Priority Queue

The element can be inserted arbitrarily or randomly but only the smallest
element can be removed.

For example, suppose there is an array having elements 4, 2, 8 in the

same order. So, while inserting the elements, the insertion will be in the
same sequence but while deleting, the order will be 2, 4, 8.

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

129
MIT WORLD PEACE UNIVERSITY PUNE
Descending priority Queue:

The element can be inserted arbitrarily but only the largest element can
be removed first from the given Queue.

For example, suppose there is an array having elements 4, 2, 8 in the

same order. So, while inserting the elements, the insertion will be in the
same sequence but while deleting, the order will be 8, 4, 2.

Application of priority queue

1. Stack implementation
2. In CPU scheduling algorithms
3. For load balancing and interrupt handling in an operating system

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

130
MIT WORLD PEACE UNIVERSITY PUNE
 THANK YOU

SCHOOL OF COMPUTER SCIENCE, FACULTY OF SCIENCE

131
MIT WORLD PEACE UNIVERSITY PUNE