. .

END TERM EXAMINATION [MAY-JUNE 2017]

_SECOND· SEMESTER [MCA]
DATA AND- FILE STRUCTURE [MCA-102]
'fiJ1le: 3 hrs,
M.M.:75
ote:Attempt any five questions including Q. No. l zphich is compulsory.
Q.l. (a) Explain various asymptotic. notations for representing time
0 mplexity. (2.5)
Ans, Asymptotic Notations
Asymptotic analysis of an algorithm refers to defining the mathematical
undation/framing of its run-time performance ..Using asymptotic analysis-, we can
ery well conclude the best case, average case, and worst case scenario of an algorithm.
' Following are the commonly used asymptotic notations to calculate the running
e complexity of,an algoritltm:
_(1) Big Oh Notation, 0

The notation O(n) is the formal way to express the upper bound of an algorithm's
·ng time. It measures the worst case time complexity or the longest amount of time
algorithm can possibly take to complete.
For example, for a function f(.n)
0 (fin))= {g(n) : there exists c > 0 and n 0 such that f(n) :S c.g(n) for all n > n .}
(2) Omega Notation, Cl 0

The notation Cl(n) is the formal war to ~xpress the lower bound of an algorithm's
'ngtime. It measures the best case time complexity or the best amount of time an
orithm can possibly take to complete. ' ·
For example, for a function f(.n)
0(/tn)) {g(n) : there e2(ists c >.0 and n 0 such tha~ g(n) c.f(n) for i=tll n > n • }
(3) Theta Notation, 8 0

' \

Th~ notation 0(n) is the formal way to express both the lower bound and the upper
bound of an algorithm's running time. It is represented as follows- ·
0(./tn)) = {g(n) if and only ifg(n) = O(f(n)) and g(~) = !l(f(n)) for all 11 > n • .}
0
Q.l.(b) Differentiate between e+ 'Free and B* Tree.
(2.5)
· Ans. B+trees are very common. Tpe major difference between B+.and B* trees is
t~t B+ trees are split into-to different c~ld nodes ~hen they are full which means that
:lllnber of data points in each node in B+ tree _is 1/2 ofit's _m~mum capacity. In B* tree
h~ number of data point~ in each node is at least 2 / 3. Thus the B* trees are m~e
~lllPact compared to B+ trees. This is typically achieved by sharing data points between
1

·sibling or n~ighbouring nodes. When a single node is full it shares data points at_1d only
When both the neighbour nodes are full it splits. · . ·.
llowever thi"s . comes. at a cost. ·Deleting a 'data point i~ B* tree is much more
:lllPlicated than other trees. This is a 'valid tradeoff because in many use ca~s the
equen f ' · 1- -
cy o delete operation is much less. . · .

I
 ....
I.P. University-(MCAJ-AB Pu .
2-2017 Second Semester, Data and File Structure . . bheher _
•5 algonthm works quite efflciently fo 2017 3
Q.1.(c) Explain preorder traversal of a binary tree. (2 'fhi time complexity is near to O(n). r ema11 and medium size array its
11"8rai8 · k i 88
Ans. Pre-order Traversal •6) S ere are some ey po nts of shell sort alg 'th
. . on. 111-
In this traversal method, the root node is visited first, then the left subtree • Shell Sort 1s a companson based Sorting.
finally the right subtree. ¾4 The best case in shell sort is when the arr .
• . ns is. less.
colllPanso . ay 18 already sorted. The number of
Root
• It is an m-place sorting algorithm as it requires no add1't•o I tch
• Shell Sort 1s · unstabl e sort as relative order of I .na ecra apace.
change, e1ements with equal values may
,·,>-·-<
• It is been observed that shell sort is 5 times faster than b bbl rt d t .
· than
faster ' · rt·10n sort 1·ts cIosest competitor.
mse u e so an wice
Q.l.(f) Write any two disadvantages of sequential file allocation method.
,<;)_
-<\ ( \~ Ans. Disadvantages of sequential file (2.5)
Sequential file is time consuming process.
2~ 3'~ 2\__J 3(v It has high data redundancy.
Random searching is not p,ossible.
Left Subtree Right Subtree Q.l.(g) What is dequeue? (2.5) ·
Am. DEQUEUE
We start from A, and fo~owing pre-order traversal, we first visit A itself and t: Double Ended Queue (Dequeue) .
move to its left subtree B. B 1s also traversed pre-order. The process goes on until all 1 Double Ended Queue is also a Queue data structure in which the insertion and
nodes.are visited. The output of pre-order traversal of this tree will be - · deletion operations are performed at both the ends (front and rear). That means, we
. can insert at both front and rear positions and can delete from both front and rear
Q.l.(d) What do you mean by AVL tree? How the balance factor of a node positions.
anAVL tree i1 comp~tecL (J
•1· I
front rear ,
I I I I I•
Am. AVL Tree
AVL tree is a self balanced binary search tree. That means, an AVL tree is a insert 4
·binary search tree but it is a balanced tree. A binary tree is said to be balanced, if'\. insert
difference between the hieghts of left and right subtrees of every node in the tr!! '
either -1, Oor +1. In other words, a binary tree is said to .be balanced if for eveey '
delete(""
. . J delete
height of its children differ by at most one. In an AVL tree, every node maintains a et, Double Ended Queue can be represented in TWO ways, those are as follows ...
Input Restricted Double Ended Queue ·
information known as balance factor.
Balance factor of a node is the difference between the heights of left and ri Output Restricted Double Ended Queue
subtrees of that node. The balance factor of a node is calculated either height ti, Input Restricted Double Ended Queue .
subtree -height of right subtree (OR) height of right subtree - height ofleft sub In input restricted double ended queue, the insertioii operation is performed .at
the following explanation, we are calculating as follows ... only one end and deletion operation is performed at both the ends.
Balance factor -= height Of Left Subtree - height Of Right Subtree · Output Restricted Double Ended Queue
Q.1. (e) E¥plsin shell 1hort uin, 1uitable example.
In output restricted double ended queue,' the deletion operation is performeq at
only one end and insertion operation is performed at both the ends.
~- Shell Sort is a generalized version of inaertion sort. It is an in-~
Q.l.(h) What do you mean by a heap? How is it different from a binary
comp~son sort. Shell Sort is also luaown a, cUmlni1hln~ increment ,ort
algontlun use · · search tree? (2.5)
. 8 ~rtion sort on the large interval of elements• to sort. Then thB JJI· ii
Ans. A heap is a specialized tree-based data structure that satisfies the heap
kno keeps on deaeasmg
0 f sorting
are · · the interval reaches 1. The98 JJI· vi
10 a sequence until
Property: if Pis a parent node ofC, then the key (the value)of Pis either greater than or
wn 86 gap sequence.
k..._ t1
 4-2017 Second Semester, Data and File Structure

r
I.P. University-[MCAJ-AB Publisher

-
l
2017-5
•<the-,.,••"'" ..., (Mth no,=•"' I• ulled th• =•
eqi;al to (in a ,naz Jieap) or Jess than or equal to (in '1 min heap) the key ofC. Th
node. • nod,
next data next
data next
Difference between DST & Heap : 10
( 1) Heap just guarantee,s that elements on higher levels _are greater (for max- 2
M ,m•lltt (fM Dlln·heaP) d,~ e)emento on low~ I,wla, whereas BST gua,ant, heapJ
, _ s,ft" tn "right"). If ,-u - • ...... element>, go Mth BST. """'"
(2) Heap is better at findMin!findMSX (O(H), while BST is good at all finds (O
Insert is O(logN) for both structures, lfyou only care about findMin/findMax ( (l?gN)},
related), go with heap. If you want everything sorted, go with BST. e,g. Pnonty.
HEAD Last Element Points back to First
Q.I.(i) Explain adjacency list representation of a graph. Circular lists are usually preferable to non-circular ones, for two reasons:
Ao& Graph Representation in memory (2,15)
They provide easy access to both ends of a list: notice that we do not need
There are several possibilities t.o represent a graph G = (V.E) in memo
the first pointer in the header, because we can easily reach the first.node with L->last-
of nodes be V = (1, 2, ... n) with edges E !:;; V x V, and let m., IE I , ry, Le~ the set >next
, The code for processing a circular list is often simpler than the code for processing
a non-circular list- mainly because you don't have to constantly check if the next node is
defined • it is always defined.
Q.2.(a) Write algori~ for insertion and deletion of~ element in a linear
queue. (6.5)
Adjacency List
80rted Am. INSERT-ITEM(QUEUE,FRONT~~)
An adjacency list is similar to an edge list: for each node a .
.
nodes (also t.ermed neighbors) is stored. Llkewise • this is an e ffi c1ent
. waybetto of aclja""ftt
_, This algorithm is used to add or insert item to QUEUE,
graph bu.t the access tunes are slower compared to a matrix (0( represent.
One way to solve this issue is to use a hash table for ea h
neighbors.
1:;) compared to 0<1)1
c n e , containing all it,
1. If (REAR • MAX) then
a. Display •Queue overflow";
b. Return; ,
The adjacency list for the example graph is:
2. Otherwise
Node Neighbou,.
a. REAR :.. REAR+ 1;
1 {2, 6)
b. QUEUE(REAR) :• ITEM; ·
2 (1 , 3, 4, 5}
3. Return;
3 (2, 4)
4 (2, 3, 5} REMOVE-ITEM(QUEUE,FRONT,REAR,ITEM)
5 (2, 4, 6) Thia algorithm is used to delete an item from QUEUE.
6 (1 , 5) 1. If(FRONT. REAR+ 1) then
a. Display "Queue underflow";
list. Q.L(j) What ii a circular
. linked U.t?Write lu --over a UDearlinked
' advan••--
b . Return;
Ans. Circular Llst (2JJ 2. Otherwise
. Circular Linked List is littl a. ITEM :• QUEUE(FRONT);
liot';."""'~'.m'"" anywt,,,. in the mked data ,wctu,.. In the"""'
linked list we , e more oomplicat.ed 1·
'"''" '""''"~;::"'"'
•~wa, llnled the liot be<auoe it ia liot whereu m the arrayw•""'
b. FRONT :a FRONT+ 1;
Jut elem,01 ,...., th:'"""'
other in a circul
,1..,,., '"""'
addreas of the starti
the :" the oontiruoue memotY•
ddree1 of the next element and thl
IP 3. Return·
•
Q.2.(b) Convert
i
the followinar infix expression into postfix express on.
(6)
w.,, °' •
1
'''""''"" wlri-::. •hfoh......,. a cirnul •"'."nl The elemento poinP ., ...
means the memory can be':i~n. The circular linked list h•'' a/b-c+d•e-a•c.
. : a lb - c+d•e-a•c
·
ocated when it is required• Ans. Infix to postfix expression
t
 r -~ __,, .,
-
Second Semester, Data and File Structure
LP. University-[MCAJ-.AB Publisher
S-No. Symbol Scanned Stack Postfix Expression
a a . ~3[k].exp = pl[i_J.exp; 2017-7
1.
I a p3[k],coef = pl[i).coef + p2[j).coef;
2. I
b I a,b
3. i++;
- - - a, b,/
4. j++;
5. C - a, b,/, c
k++;
6. + + a, b,/, c, -
d + a, b, /, c,. -, d
7.
s: • .
+•
+,.
a, b, I, c, -, d
a , b, I, c, -, d, e
I
while( i <maxl )
9. e
I
10. - - a, b,/, c, -, d, e, •, +
. ~3[kl = pl[i];
11.
12.
a
• .
-
-,
.
a, b, /, c, -, d,.e, • , +, a
a , b, /, c, -, d, e, •, +, a
k++;
-
i++;
13. C -• a, b, /, c, -, d, e, •, +, a, c
. 14 a, b,/, c, -, d, e, •,+,a, c, • , ..
while(j _<max2)
Q.S.(a) Write ac function that adds two polynomials whic P&s&edaetta I
aquments. (6) p3[kl = p2[j);
Ans. //function to add polynomials 'k++;
intadd__addpolynomial(pl,p2,p3,maxl,~) j++;'
struct addpolynomial pl[), p20, p30;
int maxl , max2; return(k);
intij,k;
i =j = k = O; Q.3.(b) Prove thot the maximum no. of nodes on level l of binary treo ls 21-
while ( i <maxl &&j <max2) for i :1:1 and maximum no. of nodes in a binary tree of depth kin 2k-l fork~ l 1.
(' Ans.Proof: (6.5)
if( pl[i].exp > p2fj].exp)
(1) The maximum number of nodes on level i of a binary tree is 21-1, i 1.
l
(2) The maximum number of nodes in a binary tree of depth k is 2• - 1, k 1.
p3[k] = pl[iJ; Proot: • .
k++; (1) The proof is by induction on i.
i++;
Induction Base: The root is the on!~ node on level i = 1 . Hence, the maximum
number of nodes on.level i • 1 is 2i-l 2° • 1.
else
th Induction HyPotheais: Let i be an arbitrary positive integer greater than 1 Asswn~
ilt pl[i].exp < p2[jJ.exp) at the maximum number of nodes on level i - 1 is 2i--2•
I . Induction Step: The maximum nµmber of nodes on level i-1 is 21-2 by the hypothesis.
p3[k] .. p2[jJ; Since each node in a binary tree has a maximum degree of 2, the maximum number of
k++; nodes on level i is two tim~s the maximum number of nodes on level i -1, or 2i--1•
2
( ) The maximum number of nodes in a binary tt:ee of depth k is
i++;
else
'
t.. (maximum number of nodes on level 1)"' , L•t·I = 2• -1
JI..
·-
.,-- ' l
._ i ~ ~
r ·1
I.P. University-fMCAJ-AB Publi!!her
8-201 7 Second ,Semester, Data and File Structure • h ad - par ->ieft;
st·,. It re - 2017-9
Q.4. (a) Explain the concept of threaded binary tree. Write algorith p left = temp;
inserting a node in a ~aded binary tree• It!.(6.
fcit pst' _,. When. new node is~inserted as the right child
cases:
Ans. Threaded Binary Tree . . f . . ••)
A binary tree rs threaded by making all right child pointers that would n · nt oftmp is its inorder predecessor. The node which was inorder successor
null point to the inorder successor of the node (if it exists), and all left chi)~l1ll~IJy~
that would normally be null point to the in order predecessor of the node. Po111teri of thefhe
pa: :node
i s now be- inorder successor of this node tmp. So the left and right threads
will the
tJie new
We have the pointers reference the next node in an inorder traversal; called of left = par;
trnp ·> .
We need to know if a pointer is an actual link or a thread, so we keep a bo three.de,
) 'ght =par-> nght;
each pointer. olean for trnp ·> n . .
Types of threaded binary trees: · Beforem . sertion, the nght pointer of parent was a thread, but after insertion it will
Single Threaded : each node is threaded towards either th 1. , 1•n
1 ·kpom
. ti'ng to the new node.
bea
predecessor or successor (left orright) means all right null point-ers will . e n-ord per·> rthread = false;
succes-sor OR all left null pointers will point'to inorder predecessor. point to inor~
, ar -> right = tmp;
Double threaded: each node is threaded towa~ds b I1
predecessor and successor (left andright) means all right null point-V::.l~ t _h e i norder Q.4.
P (b) Write algorithm for deletion of a ·node in a binary search tree. (6)
successor AND ell left null pointers will point to inorder predecessor. point to ino...i.
•""1
Ans. Bj D ary Search . Tree (Deletion)
(1) N o d e to be deleted is leaf: Simply remove from the tree.
50 . _50
I \ delete(20) I \
30 70 ---> 30 70
I \ I \ \ I\ I\
20 40 60 80 40 60 80
Sing le Thre a ded Bin a ry T,-e., Doub!• Thre-a de>d Binary Tre .,
(2) Node to be deleted has only one child: Copy the child to the node and delete
the child
50 50
Single and Double threaded binary tree (I) I \ delete(30) I \
Insertion in Threaded Binary Tree : 30 70 - - - > 4 0 70
Case I: Insertion in empty tree
\ I \ I \
Both left and right point.ere oftmp will be set to NULL and new node becomes the mi
root= tmp; 40 60 80 6080
tmp -> left = NULL; (S) Node to be deleted has
two children: Find inorder successor <if the node.
tmp -> right = NULL; / Copy contents of the inorder successor to the node and delete the inorder successor. Note
that inorder predecessor can also be used. ·
Case 2: When new node inserted aa the left child
50 60
After inserting the node at its proper place we havo to make its left and ri~I
threads points to inorder predecessor a nd succe~sor respectively. The node whicl I \ delete(50) / \
was inorder successor. Sb the left and right threads of the new node will be- 40 70
tmp •> left= pa r ->lelt; · - - - > 40 70
I \ \
tmp ·> right = par; , . ,,JI
L"'"'""'
60 80 80
Before insertion, the left pointer of Parent was a thread, but
be a link point iug to the new node.
aner insertion it
not The important thing to note is, inorder successor is needed only when right child is
nu ~mpty. In this particulat case, inorder successor can be obtained by finding the
Valuejn right ehild of the nod,. . .
illi w=-
 10-2017 Second Semester, Data and File Structure I.P. University--fMCAJ-.AB Publisher

~ 9-~_' '
11
Q.o.(a) What do you mean by strongly connected graph is the direct d th breadth first traYersaI of the above graph d . ,
shown below strongly connected? Last all the simple paths in it. c ln°a1>h 2017-11
(8.S) 1
;!1
we do_ ~ print the following output. "AB c DE riinnt the ~~ited node as
r
1
'.,, ,, ·, will ,tart with'""''" •hkh ,, lb,""''" d • BF$··~ . . -
i/l' obu_.Jevel,~Ohl are B, C and D, then the last leVeJs Whicoh e, andE then it moves to the
, r1,bJDfc
ptt! Jeve Is wh1c Steps , are and F.
~I"
SteP 1·. Puah the root node in the Queue. ,
l,SteP 2.· Loop until the queue is empty.
,. _ S· Remove the node from the Queue.
Ans, Strongly connected GJ"llph: A Directed graph G is said to b st s.S&eP 4 . d d h . 'ted hil
connected, if for each pair u,vofnodes in G there is -a path from u to v and the ~ong]y
19
a path from v to u, A directed graph is strongly connected if there is a path be:re also rt4.Step ·. If
the unVIS the remove
. ited nothe
children in as unvis1
e queue. c d nodes, mark them as visited and
two pair of vertices. Ween any
1¢e (a) Prove that a complete lrl'aph with 11 l'ertices, has n~ sPllnning trees.
Q.6. Proof: Let us consider a complete graph with 3 vertices
).rd. dge 8 in complete graph with 3 Vertices
Noofe
n(n - 1) 3 " (3 - 1) 3" 2
• = =2 >= 3
Now we have the graph
A
In the Figure, this directed graph ,is strongly oonn,eoted, because there ia 8 Path
from one node to another node. '
~· Li1t of all paths in the above en,ph :
(0, 1), (0, 1, 2), (0, 3), (1, 2), (1, 2, 0), (2, 0), (2, 0, 3), (3, 2), (3, 2, 0).
Q.S.(b) Write an algorithm for breath search or a 11"aph. (6)
A1panni~ trcee with 3 vertices has o,nly 2 edges.
Ans. Breadth Search (BFS)
So, total no of spanning trees with 2 edges out of 3 edges.
This is a very different approach for travening the graph The aim ofBFS
algorithm is to traverse the graph as close u possible to the root node. Queue i1 used in 3
the implementation oftbe breadth fir&t eeuch. Let's see how BFS traversal wilh woru • C2 - no of cycles with two edges
respect to the following graph :
- 3! 0
2! 1! -
l-ol\
3 Spanning trees
......
j,,
 LP. University-[MCAJ-AB Publisher
--....
2017-13
Second Semester, Data and File Structure
12-2017
= 3-0
= 3
= 31=33-2
If we have a complete graph with 4 vertices then .
4(4-.1) 4x3
No. of edges = - -- = - 2- = 6
2
A spanning tree with 4 vertices has 3 edges
Total No. of spanqmg trees with 3 edges out of 6 edges
= 6 c3 - no of cycles oflength 3
6!
= ! x ! - no of cycles oflength 3
3 3
M
In a complete graph with 4 vertices, we have 4 cycles oflength 3.
All 16 spanning trees of K4•
Q.6.(b) Write Prim's algorithm for finding the minimum cost spanning tree.
So,Total no spanning trees with 3 edges out of6 edges (6.5)
6! Ans. Steps of Prim's Algorithm:
4
= 3!x3!- The following are the main 3 steps of the Prim's Algorithm:
1. Begin with any vertex which you think would be suitable and add it to the tree.
,6x5x4x~ _
4
N
tre 2 Fi nd an edge that co~nects any vertex in the tree to any vertex that is not in the
= ,ix,ix1x_i? e. ote that, we don't have to form cycles.
3· Stop when n - 1 edges have been added to the tree.
= 20-4
Solved Example
l '
= 16
Question:·Solve the following by applying Prim's Algorit~m.
=42
=4,-2 (Here n =4) Solution: .
In general we can say that a complete gr h "th . h 2 atr)
·... By_ applying Prim's Algorithm we will find the following iterations:
•P .,. n vertio,a "n•- •p-•
II I C ti
. __
,
14-2017
Second Semester, Data and File Structure

LP. UniyersitY-lMCA]-AB Publisher

Iteration 8: 2017-15

-~
Iterationo
A \
Iteration 2: Iteration 3:
t( \\•
h last iterati_on number 8 represents the optimal solution of the problem,
.flere,tht Id dark black lines, which gives us the mi~mum length of the path. And,
¢ven by e ~d be ~alculated by addii:tg the numbers written on optimal path. That is,
,,~•l the length w 9o 2 + 4 + 2 + 1 = 37 is the minimum length.
4 8+7 + +
' · Short following
,+,Q,7,(a) . integers using heap sort:
..!., z (6)
I
. 8,25, 16, 214519,17,67,52,69,70.
• '
.Ans, Heap Sort
Iteration 4: Ii, 25, _16, 21, 45, 19, 17, 67, 52, 69, 70. Fist we make a more heap
1
First we make a max heap
!25
'·
@
i<fo
@) 8 @
Iteration 6: Iteration 7: ~--
 II
1.P. University-[MCA]-AB Publisher I
16-2017 Second Semest.er, Data and File Structure . 2017-17
.17
17
TJus1s e d store the root element at last position.
it
. . th final heap. Now we delete the root elem~~t and Replace with th"!! last
eletoentofHeap an .
' 1narray
A[I0] "'70
The new Heap is
17
Again a.fum max heapify the new heap is-
storeNow
the again
R we delete the Root element and replace it with last element, ofHeap and
a[ ] == oot Elem en t at second last position
. . of array.
9 69
The {lew Heap is
'
_JI,._
 al pa

J.P.
ritycbeck
univ 0::,,,,..r-L1m..,nJ-ftD
hi h .

. t'Ublisher
,
2017-'"., 9
i
I
h · _,,-
Second Semester, Data and File Structure . osfoll culated for eac row, w c ie equivalent to a simple Parity
18- ~017 ,.Jiffl~ . are cal lso calculated for all columns, then both are sent along
11 bits lt eceiv1ng
ec1' ctiec bits ~re aen d these are compared with the parity bits calculated
• ·tf c '·tjr
fl~~psfl p..t the r
i ' dstB·
r. er,e '\'ed
dat8·
II
17 '- ~1 . • inal oaca - - - . - -·--,-~~:-7
l -~ 11100010\ 00100100\100001oo]
, Row parities
.Now we again do the max Heapify the new Heap. 10011001 0
This process is Repeat until all the nodes are not deleted. 11100010 0
So the final elements after sorting are- 00100100 0 •
I I I I
8 16 17 19 1 21 I I 1 I I l, I
2s 45 s2 67 69 70 10000100 0
Q. 7.(b) Explain various parity & error contro~ techniques in (Iles. (6,5) column 11011011 0
Ans, Error Detecting Codes:
_, parities • ·
Whenever a message is transmitted, it may get scrambled by noise or data may get
corrupted. Tu avoid this, we use ~rror-detecting codes which are additional data added §IT001ol 1110001001001001000 I100001000 I110110110 1
to a given digital message to help us detect if any error has occurred during transmission Data to be sent
of the message.
Some popular techniques for error detection are : I
s. ChecksUJll ·
1. Simple Parity check , In checksum error detection scheme, the data is divided into k ~egments each of
Blocks of data from tlic source are subjected to a check bit or parity bit generat.ar
DI bits,
form, where.a parity of: '
./
• 1 is added to the block ifit contains odd number ofl's, and Original Data
• Ois added if it contairul even number of l's \ 10011001L11100010100100100!10000100 1
This scheme makes the total number of l's even, that is why it is called even parity 1 2 3 "
checking. · k=4,m=8 IRecievea
RECEIVER ISender I 1 10011001
SENDER 2 11100010
1 10011001
(»-0 11110 11
IReject oataj+~+f Aa:ep1 oao j
.
2 11100010
..:;. 1
g>o11110111
•
\10~0111
__,_. 01111100
Compute
parity b4t
•
Compute 3
01111100
00100100
3
00109100
1010000.0
10000100
- ...
10100000 <:!)00100100
•
paril)I bit 10000100 1
}J)oo100100 00100 101
·~ 1 11011010
\100011\1\•
Transmission
Media
. _ __ _..J
• 1100011\1] Sum: 00100101
CheckSum: 11 0 110 10
, sum: l 1111111
eomplement0 ooooooo
Conclusion: Acce11_t Data
IIL,., ;it~Ci•
 J.P. University-[MCA}-AB Publisher 2017-2l
,._.j
20- 2017 &!oond Semetter, Data and Filo Structure
• ln the aend&'I end th.e eegmonts are added using l'a complement arithtnetit
, ,1,~ ... s1
tr
...,.rte
~ ere1Jl8·p theh 8dataf
. _,.,.,..
d
we use a concept called Raab table to •tore data. All the
ucture:10t 0 Ute hash table based on the hash key value. Haeh key
sh un
· . · ha h bl An
th index m the • ta e. d the hath by" -
. •
. eve,y.,,uy in the hath table i, buol
"'etion. That mean, 'I
''
get the eum. The eum i1 complemented lo get the checksum. lo .,•tr-
. ,..._
Al. tous1>• -.. g a te d us 1·ng a hash function.
• The checbum eegment i11 sent along with tho data segments. ,'.,' f bashing and hash table isahown in the lollcw;n, fi1on, ...
~ue gel\""
,i/1 doll
f~ t,,1 cePt o
Hoh'tW .., 4
• At t he end, all received segments are added using l's completn
arithmetic to get the ,um. The 11um is oomplementea.
• Uthe roeult i1 zero, the received data is accepted; otherwise diecarded.
I,;,"• . . .
\
4. Oycllc redundancy check (CRC)
1-: I ....J ktua1 DIJ IIDtd
• Unlike checksum scheme, which is ba_sed on addition, CRC is based on bllla!) •
d.iviaio.n .
• In CRC, a sequence of redundant bits, called ~clic redundancy check bite, llJl
iq,J)C!Dded to the end of data unit BO that the resulting data unit becomes exactly divisible
by a second, predetermined binary number.
• At the destination, the incoming data unit is divided by the 1fame number. If at
th.is step there is no remainder, the data unit is assumed to be correct and is therefore
accepted.

t' . ' : Value

'
~l)aGtO~~ore ·
• A remainder indicates that the data unit has been damaged in transit and n
therefore must be rejected.
.. . .. . .-.1-.: ,.
Sender Rec.e+ver Q.S.(b) BHree : .
Ans, A)3.:~~i;l"ee maintains the follo~ng invariants:
'
m n n , Every node has one tnore references than it has keys.
Data joo ....oj CRC , · Ail leat~s are at the same distance from the root.
, -
, _F or every non-leaf node N with k being the number of keys in N: all keys in the
{n•1)brui (n+i )b;!s first child's subtree are less than Ns first key;_and all keys in the ith child'a subtree
Divisor I Divisor ~~i~ k)are ·b e~tween _the (i - l)th key of n and the ithkeyofn.
•·· The root has at least two children.,
• .~ non-leaf, non-root node has at least fioor<d / 2) children.
Reminder ,- · .. , -'~;•
-~-Each leaf contains at least floor(d I 2) keys.
•., E~ery key from the table app~ars in a leaf, in left-to-right sorted order.
Reject
\
Data I CRC
Q.8. Write short notes on following: (4+4+4.5 =12,6) ' '} ·
(a) lJaabing (b) B• tree (c) Coloring of graphs ·
. Ans. (a) Ba.bing: Hashing is the process of indexing and retrieving element (data/
8
m datast.nictlll'I! to provide faster way of finding the element using the hash key. .
. Here, hash key 1l! . a value which .provides the index value where tha actuaJ data 11
.1:U)
likely to store in the datastructure. I I ~.1 re·! TI'·
, • , l
>et =-
 r Data and File Structure
Second Semes te , . ·
22-2017
Q,8,(c) Coloring of graphs, ·
Ans, Graph Coloring : . ,
G h coloring is nothing but a sim'ple way oflabelling graph compon~nts such
. rap d nd reaions under some constraints. In a graph, no two adjacent Vert· as
vertices, e ges, a b lees
adjacent edges, or adjacent regions fire colored with m1mmu~ num er of c9lors. 'Int,
1:1· • • •

number is called the chromatic number and' the graph is called a properly colore:
graph .
• While graph coloring, the constraints that are set on the graph are colors, order
coloring, the way.of assigning color, etc. A coloring is given to a vertex or a particui of
region. Thus, the v~rtices or regions having same colors form independent sets. ar
Vertex Coloring
Vertex coloring is an assignment oicolors to the vertices of a graph 'G;such th ' t
two
_ ad· - color. Si~ply put, no two vertices of an edge sha ,.1no
~acent ve rti ces h ave th e,same
he of the same color. Ou.id

Chromatic Number
--
th Thhe mi~mum number of colors required for vertex coforing of graph 'G' is call d
e c romatic number ofG, denoted by X(G). . . . - e as
.X fJ )= 1 if and on ]y if
.
G..is
.
a null , . h , .. . . - -
grap . If G JSnotanu~grp.ph .-then~ J; )~ 2