All 2nd Semester Subjects

Professional English - II - HS3252 Engineering Graphics - GE3251

Statistics and Numerical Methods - Physics for Electronics Engineering -
MA3251 PH3254
Physics for Electrical Engineering - Physics for Civil Engineering - PH3201
PH3202
Materials Science - PH3251 Basic Electrical and Electronics
Engineering - BE3251
Physics for Information Science - Basic Civil and Mechanical Engineering -
PH3256 BE3255
Basic Electrical and Instrumentation Electric Circuit Analysis (Circuit
Engineering - BE3254 Theory) - EE3251
Programming in C - CS3251 Circuit Analysis - EC3251
Data Structures Design - AD3251
 [Link]

Downloaded from [Link]

[Link] 1
 [Link]

Downloaded from [Link]

[Link] 2
 [Link]

Downloaded from [Link]

[Link] 3
 [Link]

Downloaded from [Link]

[Link] 4
 [Link]

Downloaded from [Link]

[Link] 5
 [Link]

Downloaded from [Link]

[Link] 6
 [Link]

Downloaded from [Link]

[Link] 7
 [Link]

Downloaded from [Link]

[Link] 8
 [Link]

Downloaded from [Link]

[Link] 9
 [Link]

Downloaded from [Link]

[Link] 10
 [Link]

Downloaded from [Link]

[Link] 11
 [Link]

Downloaded from [Link]

[Link] 12
 [Link]

Downloaded from [Link]

[Link] 13
 [Link]

Downloaded from [Link]

[Link] 14
 [Link]

Downloaded from [Link]

[Link] 15
 [Link]

Downloaded from [Link]

[Link] 16
 [Link]

Downloaded from [Link]

[Link] 17
 [Link]

Downloaded from [Link]

[Link] 18
 [Link]

Downloaded from [Link]

[Link] 19
 [Link]

Downloaded from [Link]

[Link] 20
 [Link]

Downloaded from [Link]

[Link] 21
 [Link]

Downloaded from [Link]

[Link] 22
 [Link]

Downloaded from [Link]

[Link] 23
 [Link]

Downloaded from [Link]

[Link] 24
 [Link]

Downloaded from [Link]

[Link] 25
 [Link]

Downloaded from [Link]

[Link] 26
 [Link]

Downloaded from [Link]

[Link] 27
 [Link]

Downloaded from [Link]

[Link] 28
 [Link]

Downloaded from [Link]

[Link] 29
 [Link]

Downloaded from [Link]

[Link] 30
 [Link]

Downloaded from [Link]

[Link] 31
 [Link]

Downloaded from [Link]

[Link] 32
 [Link]

Downloaded from [Link]

[Link] 33
 [Link]

Downloaded from [Link]

[Link] 34
 [Link]

Downloaded from [Link]

[Link] 35
 [Link]

Downloaded from [Link]

[Link] 36
 [Link]

Downloaded from [Link]

[Link] 37
 [Link]

Downloaded from [Link]

[Link] 38
 [Link]

Downloaded from [Link]

[Link] 39
 [Link]

Downloaded from [Link]

[Link] 40
 [Link]

Downloaded from [Link]

[Link] 41
 [Link]

Downloaded from [Link]

[Link] 42
 [Link]

AD3251 DATA STRUCTURES DESIGN L T P C 3 0 0 3

COURSE OBJECTIVES:
● To understand the concepts of ADTs
● To design linear data structures – lists, stacks, and queues
● To understand sorting, searching and hashing algorithms
● To apply Tree and Graph structures
UNIT I ABSTRACT DATA TYPES 9
Abstract Data Types (ADTs) – ADTs and classes – introduction to OOP – classes in Python –
inheritance – namespaces – shallow and deep copying Introduction to analysis of algorithms –
asymptotic notations – recursion – analyzing recursive algorithms
UNIT II LINEAR STRUCTURES 9
List ADT – array-based implementations – linked list implementations – singly linked lists –
circularly linked lists – doubly linked lists – applications of lists – Stack ADT – Queue ADT – double
ended queues
UNIT III SORTING AND SEARCHING 9
Bubble sort – selection sort – insertion sort – merge sort – quick sort – linear search – binary search –
hashing – hash functions – collision handling – load factors, rehashing, and efficiency
UNIT IV TREE STRUCTURES 9
Tree ADT – Binary Tree ADT – tree traversals – binary search trees – AVL trees – heaps – multiway
search trees
UNIT V GRAPH STRUCTURES 9
Graph ADT – representations of graph – graph traversals – DAG – topological ordering – shortest
paths – minimum spanning trees
TOTAL: 45 HOURS
COURSE OUTCOMES:
At the end of the course, the student should be able to:
∙ explain abstract data types
∙ design, implement, and analyse linear data structures, such as lists, queues, and stacks, according to
the needs of different applications
∙ design, implement, and analyse efficient tree structures to meet requirements such as searching,
indexing, and sorting
∙ model problems as graph problems and implement efficient graph algorithms to solve them
TEXT BOOKS:
1. Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser, “Data Structures and
Algorithms in Python” (An Indian Adaptation), Wiley, 2021.
2. Lee, Kent D., Hubbard, Steve, “Data Structures and Algorithms with Python” Springer Edition
2015.
3. Narasimha Karumanchi, “Data Structures and Algorithmic Thinking with Python” Careermonk,
2015.
REFERENCES:
1. Rance D. Necaise, “Data Structures and Algorithms Using Python”, John Wiley & Sons, 2011.
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, “Introduction to
Algorithms", Third Edition, PHI Learning, 2010.
3. Mark Allen Weiss, “Data Structures and Algorithm Analysis in C++”, Fourth Edition, Pearson
Education, 2014
4. Aho, Hopcroft, and Ullman, “Data Structures and Algorithms”, Pearson Education India, 2002.

Downloaded from [Link]

[Link] 43
 [Link]

Downloaded from [Link]

[Link] 44
 [Link]

Downloaded from [Link]

[Link] 45
 [Link]

Downloaded from [Link]

[Link] 46
 [Link]

Downloaded from [Link]

[Link] 47
 [Link]

Downloaded from [Link]

[Link] 48
 [Link]

Downloaded from [Link]

[Link] 49
 [Link]

Downloaded from [Link]

[Link] 50
 [Link]

Downloaded from [Link]

[Link] 51
 [Link]

Downloaded from [Link]

[Link] 52
 [Link]

Downloaded from [Link]

[Link] 53
 [Link]

Downloaded from [Link]

[Link] 54
 [Link]

Downloaded from [Link]

[Link] 55
 [Link]

Downloaded from [Link]

[Link] 56
 [Link]

Downloaded from [Link]

[Link] 57
 [Link]

Downloaded from [Link]

[Link] 58
 [Link]

Downloaded from [Link]

[Link] 59
 [Link]

Downloaded from [Link]

[Link] 60
 [Link]

Downloaded from [Link]

[Link] 61
 [Link]

Downloaded from [Link]

[Link] 62
 [Link]

Downloaded from [Link]

[Link] 63
 [Link]

Downloaded from [Link]

[Link] 64
 [Link]

Downloaded from [Link]

[Link] 65
 [Link]

Downloaded from [Link]

[Link] 66
 [Link]

Downloaded from [Link]

[Link] 67
 [Link]

Downloaded from [Link]

[Link] 68
 [Link]

Downloaded from [Link]

[Link] 69
 [Link]

Downloaded from [Link]

[Link] 70
 [Link]

Downloaded from [Link]

[Link] 71
 [Link]

Downloaded from [Link]

[Link] 72
 [Link]

Downloaded from [Link]

[Link] 73
 [Link]

Downloaded from [Link]

[Link] 74
 [Link]

Downloaded from [Link]

[Link] 75
 [Link]

Downloaded from [Link]

[Link] 76
 [Link]

Downloaded from [Link]

[Link] 77
 [Link]

Downloaded from [Link]

[Link] 78
 [Link]

Downloaded from [Link]

[Link] 79
 [Link]

Downloaded from [Link]

[Link] 80
 [Link]

Downloaded from [Link]

[Link] 81
 [Link]

Downloaded from [Link]

[Link] 82
 [Link]

Downloaded from [Link]

[Link] 83
 [Link]

Downloaded from [Link]

[Link] 84
 [Link]

Downloaded from [Link]

[Link] 85
 [Link]

Downloaded from [Link]

[Link] 86
 [Link]

Downloaded from [Link]

[Link] 87
 [Link]

Downloaded from [Link]

[Link] 88
 [Link]

Downloaded from [Link]

[Link] 89
 [Link]

Downloaded from [Link]

[Link] 90
 [Link]

Downloaded from [Link]

[Link] 91
 [Link]

Downloaded from [Link]

[Link] 92
 [Link]

Downloaded from [Link]

[Link] 93
 [Link]

Downloaded from [Link]

[Link] 94
 [Link]

Downloaded from [Link]

[Link] 95
 [Link]

Downloaded from [Link]

[Link] 96
 [Link]

Downloaded from [Link]

[Link] 97
 [Link]

Downloaded from [Link]

[Link] 98
 [Link]

Downloaded from [Link]

[Link] 99
 [Link]

Downloaded from [Link]

[Link] 100
 [Link]

Downloaded from [Link]

[Link] 101
 [Link]

Downloaded from [Link]

[Link] 102
 [Link]

Downloaded from [Link]

[Link] 103
 [Link]

Downloaded from [Link]

[Link] 104
 [Link]

Downloaded from [Link]

[Link] 105
 [Link]

Downloaded from [Link]

[Link] 106
 [Link]

Downloaded from [Link]

[Link] 107
 [Link]

Downloaded from [Link]

[Link] 108
 [Link]

Downloaded from [Link]

[Link] 109
 [Link]

Downloaded from [Link]

[Link] 110
 [Link]

Downloaded from [Link]

[Link] 111
 [Link]

Downloaded from [Link]

[Link] 112
 [Link]

Downloaded from [Link]

[Link] 113
 [Link]

Downloaded from [Link]

[Link] 114
 [Link]

Downloaded from [Link]

[Link] 115
 [Link]

Downloaded from [Link]

[Link] 116
 [Link]

Downloaded from [Link]

[Link] 117
 [Link]

Downloaded from [Link]

[Link] 118
 [Link]

Downloaded from [Link]

[Link] 119
 [Link]

Downloaded from [Link]

[Link] 120
 [Link]

Downloaded from [Link]

[Link] 121
 [Link]

Downloaded from [Link]

[Link] 122
 [Link]

Downloaded from [Link]

[Link] 123
 [Link]

Downloaded from [Link]

[Link] 124
 [Link]

Downloaded from [Link]

[Link] 125
 [Link]

Downloaded from [Link]

[Link] 126
 [Link]

Downloaded from [Link]

[Link] 127
 [Link]

Downloaded from [Link]

[Link] 128
 [Link]

Downloaded from [Link]

[Link] 129
 [Link]

Downloaded from [Link]

[Link] 130
 [Link]

Downloaded from [Link]

[Link] 131
 [Link]

Downloaded from [Link]

[Link] 132
 [Link]

Downloaded from [Link]

[Link] 133
 [Link]

Downloaded from [Link]

[Link] 134
 [Link]

Downloaded from [Link]

[Link] 135
 [Link]

Downloaded from [Link]

[Link] 136
 [Link]

Downloaded from [Link]

[Link] 137
 [Link]

Downloaded from [Link]

[Link] 138
 [Link]

Downloaded from [Link]

[Link] 139
 [Link]

Downloaded from [Link]

[Link] 140
 [Link]

Downloaded from [Link]

[Link] 141
 [Link]

Downloaded from [Link]

[Link] 142
 S
Dect Code/Title: AD 3251-Data Structures Design Unit:
[Link]

LUnut
DA 4 -

Gcaphtnavesak-
Rapaesentation oç qnaph. Taea
GtVaph ADT- -8hoAtstVpabbs-minimum
spanning
lopological ondbang

Gpaph ADT
w e meke
collectton of
Vertices and edges
A
A qnaph is a
a Combinatton of
thzno o l a t a t y p o s
Eigtka
as
tho ab&tilac kon Vntexrs a set of nados,
and Gaaph
VeRtex,Elge
of
Ventices es mathods .

colecHon of
pata
includes
the followtng
fotlouwtnq
ADT
The
The 9naph

Sotve atex
g e t ve atox

ddd Edg2
g0tEdols

Applieattons Of Gaphs . betuween Componena

in
Aalattonship8
Repaas entth9
Tlight N{w
electaonie Caals

Taanspontation
hetwonk -hughuay No,
LAN, Intex ne
Compuiter nlw
-

Rpasentin ER diagnam
Databases
Gaaph Rapaas entalton
Adjacncy Matix
Adtacence ist
tAdyacend set

Adiacencu Mataiz2 Numbea af

,oe need the
T epresent gnaphs also thein inteconi
and alsothol intexcornecians
and
nlumboa ofV edlges
eaticos, the

Downloaded from [Link]

[Link] 143
 Unit:
Subject Code/Title: AD 3251-Data Structures Design
[Link]
Adljacency Matair Rapansermabia
class Graph(object):
# Initialize the matrix one imple uoay
def_init_(self, size):
[Link] = []
Aapaesernt a n ph
for i in range(size): C L s a a0haioy
range(size)])
[Link]([O for i in known as
[Link] = size This s
Aoljaceney mataLK

# Add edges Apaientaton

Foa eachedge (t,V)
def add_edge(self, vl, v2):
ifv==v2:
and %d" % (vl, v2)
print("Sanme vertex %d
[Link](vl][v2] =I
[Link]{v2][v1] = 1 Othwis2 the 2nt u
tho arra
f a l a d

#Remove edges vl, v2):

defremove_edge(self, 0:
[Link]{v 1][v2]
between %d and %d" % (v1, v2))
print("No edge
return
[Link][v|][v2] =0
[Link][v2][v1] =0

def_len_(self):
return [Link] A B
7.
#Print the matrix
def print_matrix(self):
for row in [Link]:
B
for val in row:
print({:4).format(val),end=")
c o
print("n") Do O0.
def main():
g=Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(4,1)
[Link] matrix()

if_name main
main()

Downloaded from [Link]

[Link] 144
 Unit:
[Link]
Subject Code/Title: AD 3251-Data Structures Design

Adjaceney list epaasentaton an aray of inka

T eprekens a qnaph as aeatee and eac
apnesentz
the qra other VRAfeas Tha|
etement
elemont n
An t
ta nk
inkedt, i st
List representation in Python
Renasanttha
Dorm an edge cwm tha a a r
# Adjascency
class AdjNode:
def init_(self, value):
[Link] = value

[Link]= None

class Graph:
def_init_(self, num):
self.V= num
[Link]
=
[None]* self.V

# Add edges
def add_edge(self, s, d):
node AdjNode(d)
[Link]= [Link][s]
[Link][s] = node

node AdjNode(s)
[Link]= [Link][d)
[Link][d]=node
#Print the graph
def print_agraph(self):
for i in range(self. V):
print("Vertex + str(i) +":", end="")
"

temp [Link][i)
while temp:
print(">{}".format([Link]), end="") C)
temp= [Link]
print(" In")
if name main_ A
V = 5
#Create graph and edges
graph Graph(V)
graph.add_edge(0, 1)
B
e
graph.add_edge(0, 2)
D
graph.add_edge(0, 3) D
graph.add_edge(1, 2)
graph.print_agraph()

PPYenax0:3 >| ( (3
Vaafar > 9 0
Vate 3 : >o
eateA

Downloaded from [Link]

[Link] 145
 Unit:
3251-Data Structures Design
Code/Title: AD
Subject [Link]

Adjacancy set.
o adjacancy uad. kist,but
T ts Yey much stmla
list, Asjont
kek ade
nstaao of u s inkad
naph Taarersals
amachantsm
9naphs,w0 noocd
classftud by atypes
on
To solvo pAoblems chn be
the graphs.T
foa txavoxing Deph fiast
saanch CDFS)
saaach (BES)
Bheaclth {iast
s2aach (DFS)
useo taavnaR oalocalz a
p i h tnst an
algoaihm
Ctaa. It ptkuti
DFS en taee
datasfau

en a qkaph as it g9until
noole one
bäanch as fa
tanget
&eaches Valong backtsacks to he
hae it
Bepii ad that bnarch
Once
baarch Q
baareh
d2archa
and&earhea
af
ho endpoksibla
he fRom that
divegnce aom
that
epeaitng
the pocos
fiast endl of thdt
baahch,
ntil tha

Aigoittm
d a o f a (eliadgtophheda)

node. not:n ysikd

T Daintcnada
Viskad.ädd hola
in 1aph[nool
fon naighbotun
dfsvisilid,aphnaghboua)
thäollotoing 9naph.
,considea
As an example

tnea is
Callod t h e DEs taaa.
geneialid u
The'inal VAtcas ara pADcOLad
twhith tha
ôadla"in
and the numbaas of tha Vantca
DFS
caltaod

Downloaded from [Link]

[Link] 146
 [Link]

Downloaded from [Link]

[Link] 147
 [Link]

Downloaded from [Link]

[Link] 148
 [Link]
ubject Code/Title: AD 3251-Data Structures Design Unit:

Braadhiast 6eaach CBFS)

of noale
of taavonsi'rg
s each
BFS the paoco Visi lid, Npt nisitad .the
paak
the qraph into'quwo
the qxaph alqotihtm to vist all the Veatex
Ipunpdso of th .BFS ug28 a quotue
tb 7oprasn
eyeleg Y
Lshilo avotoling
the nsilzol heops [Link] BFS
Stam a
eel
by
is a t Jevol o nthe iagt
BRS aRks
oate x ohich and s0 o n
a given all yHfcos a t lavol 1
the
&tade it Visil thie poceIs Until all the levols of
Conttnuog
BFS0
ph ana complalzd

RlgoaiYhm
de bfs cVisilad,naph,nsda)
[Link])
La appand Choala)
whila qaua caaahng koopt5 risit each od4
m9uotia. pop)
PrinCm,end
foR neighbota raph in

Keighbou 'not in visilid:

f [Link] nelahbota)
uoua aphand Cneidhboua)D
TI

Downloaded from [Link]

[Link] 149
 [Link]

Downloaded from [Link]

[Link] 150
 [Link]
Topological Sbat
is an Dadertng of
kenHces in
s0at
A Hopolcqcal that ifV thone s a patn
gnaph,u ch
deaee tt ol acylic Yi t n tha DAddoaing
a
td Vj tNbn Vappeana
aftex
faom i ,VAV3,V1, Vb adol
in iguae , Viva V5
the qnaph
Th aae both topoogtcal oadeaings.
VVoVs,V+ 7, Vsr V6

q1 tnal a fopoloqical
topoloqical
algoei hm
0 lo ftnal a intomirg
Vbatix with no
AA Stmple V 4 i n d any s e m o v e it,alon

OAdonung
RBE thi
Venkex,and
then paint staaBeqy
[Link] the qnaph The same 0
edgus aom Othe 9iaph,
giaph
with i Aest af (he a ve tor
the ndeg7rco.0f
applied lo the
T o honmali20
this tod doftné
Cu
W ) u e c o m p t a tHe
Indegae
humo2ot eoges dequeuav
a s the the n9aaph. )
yenices
O at

deqiuatu is
Indaut meve daqusuas H
Yrt 2 3 5
2
3

Raqemuayh_h VsV4Vg Va daqueu:V

danjuane:V

Downloaded from [Link]

[Link] 151
 [Link]

da topolegccalsont (@)
topaloqicallist : [1
:

topolcgiCal 9ueue [ : J
Aemaintngindeg: f3
()
hool es [Link] EreAtces
=

fon Vin G0;

9getT»rep/n0a C)
Tndegnco =.
if Lendagate= 0¥
append cv
o
lseoKe* aalaunuL
A e m a i n i n g indogree[vJ=tndog aee

lohilo [Link] qotua)

holo = topologlcalqcLOue .Pop(o)
topoloqéadlltst. apperd tn ole)
cohde Rehctopologitallrst):
hoale = tó[Link])
Pant node qtvealix ld')
s DCvtE
Hopologital 60at
Total unning time oA

deqeue:V7 dcgqueus:Vs

VL

Downloaded from [Link]

[Link] 152
 Design Unit
Subject Code/Title: AD 3251-Data
Struetures
[Link]

Shonte6t -Path Algonuthms nod to

e a t e x S, o e
a dtsttgeuishacd G,s
(VrE) anod în G
ea tax im
othea veatax s
gaaph G 5Uevey othea
A path 1 n poblem.
Shoate6t snoAtest path
ftnd thb sngte I 6oUace unweiqhtad a p h
by Shoatest path i n
Rofined
Shoatost path in wecghuibl gadph
in tunuOeLg h lto) q aaph
Shoatest path

( n
an
untoeighliol
unweighlãot 99napi
nap
woudd
w old
diagnam &hotwa
above pa
p aaaaarrttie
etta
a,,he
he

The b a n inrt
inRf
vexl x SLwhich
nom' o a l othea VeaHeeg. ve2Hces.
ustng
Lstng
som2
the
Shoatest pacth ot o l g Containe
riumba2n
Uo i n
nakonostad i n the on h tHoo ed ea. wbo
edh es. we
ikU
Liko k
i n t e n e s l i d

ho werah
o ueians
Only h
thene are
aae
Cwe 1pat,o aa weight "of
oeia hE "of 1
1 .
On the
on all edges wo can tell hat
ra,
CDuld QssrgnChoos2 % 0 w e hoole Slo be angh 0.
w is then a path 0f
path n o m S lo
Vs
&hontest
the 1
Th shcos the fig
(V Knnun dN
(t

Nou aoe aan s tant lookinq foanal(

1 auny
ao a
d i s t a n ce
that
VeaHceg
l a n bA found by
aom S .Those
tha Vezntices that dh
V Rooking
adjacodt l
at
[Link] and Y6 ane
00e

e anS 6hown tn
dlga.
fiq3 uwhos2 Bhoatost path faom S is
Nowind
Now ydaticos
xactly &,By findtng aalL tha oatices adjalent ls Ynand V6
whose Shoest pat e not alneady enoLon.

Downloaded from [Link]

[Link] CHENNAI DEPARTMENT OF
sCIENCE AND HUMANITIES
153
 Structures Design Unit
AD 3251-Data
Subject Code Title: [Link]
+e l s tus that tho,Shntcst
pah o ag
1
seanch that has becn mal
This 493Shetos the pargaess
Veaices adjacent
5
V4 & . e nd by exkamining
Vthak 5 andd hae
inall evaltialuol
v a and va
the Ae Cen ti& t h a e e edgex.
the Ce palth ot thae ag
h af the alqohm
ot the
a s u l t of
Sesult
s alq
Shoatest shaus the inal
H

193
Tritial shat VaDegtas MDacuud_2nuaLacd
y ondv pv Wrun dv Kiosn di ey kon dy

YS

Kvon di P KmndyA Ktaa dv P Kmandv e

Algoasthm.
He bis¢):
Sefstaatvisilis =Taue
[Link] (Seif-start)
whila aheue :
Cumdntnode [Link])
[Link]:
o nodle în
[Link] l i
i not
[Link]-Mue
9ucue. appendCnade)
[Link] -cTent nede
inede =2el f end
QuQuo .clcaaO.
Self traceAo Downloaded
s from [Link] DEPASTAMENT OF
SE UMAniTIES
[Link] 154
 AD 3251-Data Design
[Link]
Structures Unit:
Subject Code/Title:

qsapb Djkstaa'sAlkourhm
Shoatest path in oeahlidtn'wetqhthd qnapH' paodu
path phpaden

The shoatest dijkstaa D

kstadi
deve Loped by alg8aithm.
UDas thev BFS
3 e n e n a l i 2 a t t o n af
use the dis istanca [Link] shoatest disame
the
we use
itself olistance table fon
is [Link]
to
othe
6otuce
cala h
e t to , to inolical, hab
at
btu othea ane
not
n alneadiH
ot a lnead pAocesedd.
Ventices

thoe oua examplo . The ffq1 aapusen

exampla. .Tho
The 9naph is
i n i t t a l l c b n i q u n a t t o n

the
Y Knoon dv R
JU
2
Ys

Initta confiqutahbn

8taat
nodla S is Vi, The frast
t h a t the yealx k
Asuminq
n,with path lengh [Link]
k 8ome entaies
Veatee etec to that Vi ts knosn,
Viafda
knoton Noo lo
maakool VeAtieos adjacent
The adjuulid.
be adjustaol. enttatos
neeal to Veaticos get thatn
Q n d maaked knoton
knotan.

and [Link] thbse 8e Lele

lelEo
a n d maaked
8e Vy it tuang ,and
Next
'n i9 à,Ve,V5,Vo and V7
ana aolacont
adljugtfngshouwn
in g 3
Veaticos
that all eatuno qdjacent but alaaady
out Vs jan
put
Nect Va is8eleclco,
peafoamedl
oh ft. Vs k ad
&
8 0 ho uwoRkb e c a u s e t h a l o s t of
going9 fkough
knoon.
not a d jusliol, 3 k dladhdeyknovn.
but
a t lo 1 ahd a pah of leng h veatices alo
Va the t b l e aft2a those
q u n 4 Shoo&8
selecr ot.

Downloaded from [Link]

[Link] 155
 Design Unit:
Subject Code/Title:
AD 3251-1Datu Struetures
[Link]

The next Ventex Seleclea VB at Cost3. V s me

tt not adjuslid, b ecauss.
becausO
adiuslid, b
hot
ahol Mo dtstance toa V6
verlex,but

aoliacenl cleol,and
Seleetecol, table
only V3 KS ele
Aosultinq tabt
3t
65Then, loS3T 5 8
tD *..Tho A0sulting
adjtus
lial d a n 5.
in e tupedalid down t
8houds
V is &e lecud V6ge tn gaab
Next tabto Vghouos
a0&ultinq is 3hoton tn
The inaltalta
5+[Link]
V6 is seloclack
Hinaly
on houo tho.
tiquneT tma depenols Consida
aunning have yet lo
The whikh too
maniplal+ol ,
are ie oCIEI+/V12) -%Ive
oCEl+lvi2) -oIvP)
eaitces
entic es timne
of
total
aunnin
Ainaar è
inaaa en tha
n fha
number
n umbe o
he 2un8 n Himo
mo
Since it
edass
newn dv Vknen dy [Link]
2

Y4 3
co Y4
V Y4
F Y4
Vavdael and
sdeclaud H V4 H 3
knouon
4- Knouwn dedlaredknouon

V kncun dv knouwn dv R V knoun dy

V
2
3 Ya
VA s T
Vb 5
V 5 Y4
4 5 V 6 Vb ik oleelan
t 4 V5V5ae noun
doelaned
deitaral known

Downloaded from [Link]

[Link] 156
 Subject Code/Title: AD 3251-Data Structures IDesign
[Link]

Algorithm
1-Stages of Dnkstaa's
#ImplementingDijkstra's Algorithm
def dijkstra(graph. initial):
visited initial : 0}
path defaultdict(list)
nodes set([Link])
while nodes:
minNode = None

for node in nodes:

if node in visited:
if minNode is None:
minNode = node

elif visited[node] < visited[ minNode]:

minNode =node
if minNode is None:
break
[Link](minNode)
currentWeight = visited[ minNode]

for edge in [Link][minNode]:

weight current Weight - [Link]{(minNode. edge)]

i fedge not in visited or weight < visited[edge

visitedjedge] = weight

pathedge].append( minNode)
return visited, path

Downloaded from [Link]

[Link] 157
 Subject Code/Title: AD 3251-Data Structures Design
[Link] Unit

Minimal Apanning la0o

spanning tnee af a qnaph i a subnaph that
The
Cbntain8 allthaventices an ials0 atnoe IA aph
panning taees.
may have mony
Fon thissimple
9naph we cán

Hara multtpla
Z
pannng tiues

he minimum <panning taea in an

linestnd
To 4tnd we asëteme fhat ha Vgivon qophs and
undineclid anaph,
weiqhid ndph tA2e of an,undiznecteol
hinimum spanning
A A 4lom raph ealges t h a t
taee fozamad m i n i l u m t o taltost.
Gnaph G L8
a
the Veatices of
twith p h is
Conriect all S p a n n e n g tae'e o
Oxis
isls
i3l& onty tf
k only f the a9aph

A
A
miimum
Tuso Ualqoeithms
ane CLs Sl thisploblamn
Conneclol. Thsde
P i m s hlgoith
4Kauskalsalgoaithm.

as dejkstnals
Paums Agorithm the same
is almost finds'the
inds"the.
Algoeithm a s input and
Paems qraph
aq gnaph
t h d t q a p h which
T t (Hakes E h d t qaaph
hlgoithm
the edges
of 0. Qvmy Vertex
Sutset of that inetudes
all tha
thue among
foam
a
Cweih
woihla
minimum 8um of qaapN.
tho
has the be
fOAm0clAom

taeos that
an

Downloaded from [Link]

[Link] 158
 one [Link]
way lo Compuli a minimum panninq t a c 2
o
to uqrow tK nee en [Link] 2ackstage
Acot,and w ad an eda
i s pickcool at
the
one ann KSOuaeod Veal x, tothe ta00. ag
nd thus
At any potnt in the algoaithm, we can &ea hat
sht of veaHces that hao alanady been
ve have a have nt
ineluled tn the trea, the aest of the Voatichs neuw vealx lo
alqoaithm then 4inolk at eachstaqe,a
The
to Utho taoe by ehoosing
tho eokagu o)sich that the
hdd all edges ushara u
Cost ot (u u) ts tNa Smgaltst amond
s in the tiee and y not

(
7
Vs

Vs
(V6
Spaningfa0a
9Aaph G ano ii
mnimum
A

node i is seleeud ano

The tnittal Contiqurakon
.The Aesul+ing &hown n
Va,Va and V are upolabol
the i 4 The hxt veatex sekelid is V4.'Eveay Veatex
adiaceht to V4 ex cept Vi s examinad, becau i is
knbuon

Downloaded from [Link]

[Link] 159
 AD 3251-Data Structures Design Unit:
Subject Code/Title:
[Link]
cunchangeo,becauLse
(E has dv=& and the
Ve is updalcd
e updaled
the 7est a
o ane 3 a
ool ae Co8t aon va v3
eot the Asulinqfable The next Chosen kikx
shotos
Fig hot a f e c c a n y dtstana
.Then Ya s
This does tn
afoes astance i n V6,shown
[Link]
4aom the se lection oL V1,whch
Aesua,
Atqune 3. Rqur 4tobe [Link] and then bmLseluelid
oHeos V, anlt Vs
Complettng t h e algozütmm

shoLch in [Link] edqes th

in
TH tinal table iB
Can ba Acad Aom thetable cVa, ) vsVA)
taee
Spannnq total cost is tb
tV6,V), (V1,VA) The
v,V), %N1),

- -

- . G-

Paims algotthm aften 0ach Stag

v knoun dv Av
VmDun dv f Y krioion dv Ry T
V T 2 Y

Y
Vs A
F F V4
F

Table aftea Table afta VMy

Tnitial Table. is declded
knon known

Downloaded from [Link]

[Link] 160
 3251-Data Struclu
AD
[Link]
Code/Title:

Subject

V knoun Gy P V khon d R
VMnaun y
2
2

V4 Tabta Qfta V^u& Tabte aft ea V6kVs

VaVg a l &eclardknouwn ae 3placoi
d eaftea
Tabte c l a a e d known
CPma algoaitnmn
def primsAlgo(selt):
visited [0]*[Link] Num Texinates),

edgeNum=0
visited[0]=True
while edgeNum<[Link]-l:

min [Link]

for i in range([Link] Num):

if visited[i]
vertex Num):
forj in range(self.
if ((not visited[i]) and [Link][i|l):
if min > [Link][i]G]:
min [Link][i]0]

d-j
[Link]([[Link][s], [Link][d), [Link][s][d]])
visited[d] = True

edgeNum+=||

Downloaded from [Link]

[Link] 161
 Structures vesigu
AD 3251-Dala Unit:
[Link]
Code/Title:
Subject

Kauskal's Alpadhm.
alqoaithm
8taa totn r disteaent [Link]
The
Constauchir te
minuMtem
menumcem taee spanhin ,2veay tmo
the
Jlavaithm Selec k
an eolae that has nlinimumn
Kauskal s adds that
on adals that eolge,
it docsnot canat a eolor
Kauskals thon
and Ivl3
veight
inittallythee ane Sinqte Noolo taees in na
tha
Cye.s0 tudtaees int one.
an odge meages en
[Link] Vthee will be only Ono
oloorithnY is Compeud,
he al (thatt h e minimum spanninqtaod
and

Ganph
Ege Waight Action
Axaptid
Aeceptod
2
Accaptod
Accepted
, Recpd
Raectod
Actaptod
16) Reted
Aecoptod
Action e kzuskals
algottinmon&

Downloaded from [Link]

[Link] 162
 J251-Dila
S t r u c t u r e s

veagn
Code/Tite:
AD Unit:
Subjcet
[Link]

- 2

.
kauska" algoeihm afterRach &tag
class Giraph
def init_(self. vertex):
self V vertex

selfgraph-[1
v. w):
def add odgc(self, u,
[Link]((u, v, w])
def scarch(self. parent, i):
ifparentfil==i:
return i
returm [Link](parent, parent[i])
rank. x, y):
def apply_union(self. parent,
xroot [Link](parent. x)
yroot [Link](parent.y)
if rank xroot< rankly root:
parent[xroot] = yroot

elif rank[xroot] > rank[yroot:

parent[yroot] = xroot

else
parent(yroot aroot

rank aroot] += |
def kruskal(self):
result= []
i ,e 0,0
[Link] =
sorted([Link], key=lambda item: item[2))
parent [
rank []
for node in range(self.V):
[Link](node)
[Link](0)
while e< self.V - 1:
u. v, w = [Link]|i

i=i+l
a self search(parent, u)
y [Link](parent. v)
ifx=y
eetl
resultappend([u, v, w])
selapplniontparent,rank, x, y)
for u, v, weight in result:
print("Edge:",u, v,end=" ") print("-",weight)

Downloaded from [Link]

[Link] 163
 All 2nd Semester Subjects
Professional English - II - HS3252 Engineering Graphics - GE3251
Statistics and Numerical Methods - Physics for Electronics Engineering -
MA3251 PH3254
Physics for Electrical Engineering - Physics for Civil Engineering - PH3201
PH3202
Materials Science - PH3251 Basic Electrical and Electronics
Engineering - BE3251
Physics for Information Science - Basic Civil and Mechanical Engineering -
PH3256 BE3255
Basic Electrical and Instrumentation Electric Circuit Analysis (Circuit
Engineering - BE3254 Theory) - EE3251
Programming in C - CS3251 Circuit Analysis - EC3251
Data Structures Design - AD3251