COMILLA UNIVERSITY
Department of
Computer Science & Engineering
Presentation on: Data Structure
ASSALAMU ALIKUM
WELCOME TO
OUR
PRESENTATION SESSION
THE NAME OF OUR
GROUP
IS
11 Group
th
OUR GROUP MEMBERS ARE:
SL No Name Roll
01 MD: RAJIB MIA 11608024
02 MD: FORHAD HOSSAIN 11608037
03 MD: TUHIN MORSHED 11608044
04 MST: SABIKUN NAHAR 11608046
TAFHIM
05 MD: AMINUL ISLAM 11608048
OUR PRESENTATION
TOPICS ARE :
. INFIX TO POSTFIX OPERATION
. BUBBLE SORT
. PRIORITY QUEUE
Infix Notation:
When the operators exist between two operands then
the expression is called Infix notation.
Example : A+B.
2+9.
Postfix Notation :
When the operators are written after their
operands then the expression is called the postfix
Notation.
Example : A B +.
2 9 +.
EXAMPLE
Suppose Q is an arithmetic expression
written in infix notation . This algorithm finds
the equivalent postfix expression P.
Q: A+[ (B+C) + (D+E)*F]/G
P: ABC+ DE+F*+G/+
Algorithm
1. Push ( onto the stack and add to the end of Q.
2. Scan Q from left to right and repeat steps 3to 6 for each element of Q
until the stuck is empty.
3 . If an operand is encountered add it to p.
4. If a left parenthesis is encountered ,push it onto stack.
5. If an operator is encountered ,then
a. Repeatedly pop from stack and add to p each operator which has
the same precedence as or higher precedence than *
b. Add to stack.
6. If a right parenthesis is encountered ,then
a. Repeatedly pop from stack and add to P each operator until a left
parenthesis is en countered.
b. Remove the left parenthesis.
7. Exit
Infix to postfix convert:
A+[(B+C)+(D+E)*F]/G
A+[ (BC+ )+ ( DE+F*)]/G
A+[ BC+ DE+F*+]/G
A+ BC+ DE+F*+G/
BC+ DE+F*+/G+
Infix to postfix convert with Stack:
(a + b)*(c + d)
First Reverse it
(d + c)*(b + a)
Scanned Stack Expression
( (
d ( d
+ (+ d
c (+ dc
) (+) dc+
* * dc+
( *( dc+
b *( dc+b
+ *(+ dc+b
a *(+ d c +b a
) *(+) d c +b a +
Then reverse it, d c + b a+ *
BUBBLE SORT
Bubble Sort is very simple and easy to emplement sorting
technique . Bubble sort is an algorithm which is used to sort
N elements that are given in a memory for eq. : an array
with N number of elements .Bubble sort compares all the
elements one by one and sort them based on their values.
It is called Bubble sort ,because with each iteration the
largest element in the list bubbles up toward the last place ,
just like a water bubble rises up to the water surface
Work until unless explicity started sorting means ascending
order.
LOGIC AND EXAMPLE
Lets take an example , we have a list of
numbers sorted in an array
0 1 2 3
A 34 15 29 8
Logic starts with comparison of first two
elements and if the left element is great
than right element ,they swap their position .
Comparison proceeds till the end of array.
A 0 1 2 3
34 15 29 8
Round 1:
0 1 1 2 2 3
34 15 34 29 34 8
Round 2:
0 1 2 3
15 29 8 34
0 1
1 2
15 29 29 8
0 1 2 3
A 15 8 29 34
A
Round 3:
o 1
15 8
0 1 2 3
A 8 15 29 34
ALGORITHM
Bubble Sort (A,N): A is array of values and N is
the number of elements.
1.Repeat for round =1,2,3,….N-1.
2.Repeat for I = 0,1,2,……N-1-round
3.If A[i]>A[i+1] then swape A[i] and A[i+1].
4.Return.
COMPLEXITY OF BUBBLE SORT
In Bubble sort ,n-1 comparisons will be done in
round 1,n-2 in round 2,n-3 in round 3 and so
on.
(n-1)+(n-2)+(n-3)+………+3+2+1 start
Sum =n(n-1)/2
I . e 0(n*n)
Hence the Complexity of Bubble Sort is 0(n*n).
PRIORITY OF QUEUES
A priority Queue is a collection of elements
such that each element has been assigned a
priority and such that the order in which
elements are deleted and processed comes
from the following rules:
1. An element of higher priority is processed
before any element of lower priority .
2. Two elements with the same priority are
processed according to the order in which
they were added to the queue.
START
.
AAA 1 BBB 2
. .
CC
C
2
.
D
EE 4 FF 4
D
D
4
. E . F
.
G
G 5
G
Figure 1
PRN LINK
INFO
BBB 2 6
7
DDD 4 4
EEE 4 9
AAA 1 1
start 5
CCC 2 3
10
GGG 5 0
Avail 2 FFF 4 8
11
12
0
Figure. 2
Algorithm 1
1. Set Item :=Info [START]
2. Delete first node from the list.
3. Process Item
4. Exit.
Algorithm 2
This algorithm adds an ITEM with priority number N to a
priority queue which is maintained in memory as a one way
list.
1.Traverse the one –way list until finding a node X whose
priority number exceeds .Insert ITEM in front of node X.
2.If no such node is found , insert Item as the element of the list.
Example
Suppose an item XXX with priority number 2 is to be inserted
into the queue in Figure 1
We traverse the list ,comparing priority numbers . Observe that
DDD is the first element in the list whose priority number
exceeds that of xxx .Hence XXX is inserted in the list in front of
DDD, as pictured in fig 1 . Observe that XXX comes after BBB
and CCC , which have the same priority as xxx.
Suppose now that an element is to be inserted is to be
deleted from the queue .It will be AAA ,the first element in the
list. Assuming no other insertions ,the next element to be
deleted will be BBB ,then XXX ,and so on .
START . XXX 2
.
AA 1 BB 1
A . B . CC 2
C . DD 4
D .
EE 4
E . FFF 4
. GG 5
G
Figure 3
THE END
