DAARECORD

I
DNO :N1 8051
8
NAME ;U. SOUJANYA
BRANCH :CSE
BATCH : 1
SECTI
ON :CSE-02
 LAB-
1
Pr
obl
em:
I
mpl
eme
nta
tio
nan
dAn
aly
siso
fSo
rti
ngAl
gor
ithmI
nse
rti
onSo
rt.

I
npu
t:

a
rra
y[]
={5,7
,9,1
,3,6,2,6,8,5}
;

Co
de:

#i
ncl
ude<s
tdi
o .
h>
i
ntmain(
)
{
i
nti,a
rray[]={
5,7 ,9,1,3,6,2,6,8,5}
;
fo
r(i
=1;i
<10;i
++)
{
i
nttemp=array
[i]
;
i
ntj=i
-1;
whi
le(j
>=0&&a rray
[j]>
temp
)
 {
a
rra
y[j
+1]
=ar
ray
[j]
;
j
--;
}
a
rra
y[j
+1]
=te
mp;
}
fo
r(i
=0;i
<1
0;i
++)
p
rint
f("
%d"
,ar
ray
[i]
);
}

Ou
tpu
t:

1235566789
LAB-
2
Pr
obl
em:
I
mpl
eme
nta
tio
nan
dAn
aly
siso
fSo
rti
ngAl
gor
ithmMe
rgeSo
rt.

I
npu
t:

a
rra
y[]
={5,7
,9,1
,3,6,2,6,8,5}
;

Co
de:

#i
nclude<s t
dio
.h>
i
nta[ ]={ 5,7,9,1 ,3,6,2,6,8,5};
i
ntb[ 1
0];
vo
idme rging(i
ntlow,in
tmid,i
nthi
gh){
intl1,l2,i;
for (
l1=l o
w,l 2=mid+1,i=low;l1<
=mi
d&&l
2<=hi
gh;i
++){
if(a[
l1]<=a[l2])
b[i
]=a [
l1
++] ;
else
 b
[i]=a
[l2++]
;
}
whi
le
(l
1<=mi
d)
b[
i++]=a[
l1
++]
;

whi
le
(l
2<=hi
gh)
b[
i++]=a
[l2++]
;

f o
r(i=low;i< =hi gh;i++)
a[i
]=b [i];
}
v
oidsort(
intlow,inthi gh){
intmid;
if(l
ow<hi gh){
mid=( l
o w+hi gh)/2;
sort
(lo
w,mi d);
sort
(mid+1,high) ;
merging(lo
w,mi d ,high)
;
}e l
se{
retu
r n
;
}
}
i
ntma i
n(){
inti;
sort(
0,9) ;
f o
r(i=0;i<1 0;i ++)
prin
tf("%d",a[i]);
}

Ou
tpu
t:

1235566789
 LAB-
3
Pr
obl
em:
I
mpl
eme
nta
tio
nan
dAn
aly
siso
fSo
rti
ngAl
gor
ithmQu
ickSo
rt.

I
npu
t:

a
rra
y[]
={5,7
,9,1
,3,6,2,6,8,5}
;

Co
de:

#i
ncl
ude<st
dio
.h>
i
ntpart
it
ion
(i
nta[],in
tst
art,i
nte
nd)
{
i
ntpi
vot=a[end
];
i
nti=(st
art-1);
fo
r(in
tj=s ta
rt;j<=en
d-1;j++)
{
i
f(a[j
]<p i
vot
)
{
 i
++;
i
ntt=a[i
];
a
[i]=a
[j]
;
a
[j]=t
;
}
}
i
ntt=a[
i+1
];
a
[i+1
]=a[e
nd];
a
[end
]=t;
r
etur
n(i
+1 )
;
}

v
oidqu
ick(i
nta
[],i
ntsta
rt,in
tend)
{
i
f(st
a r
t<end)
{
i
ntp=p a
rti
ti
on(
a,sta
rt,en
d);
q
uick(
a,st
art
,p-1 )
;
q
uick(
a,p+1,end)
;
}
}

v
oidprint
Ar r
(i
nta[],i
ntn)
{
i
nti;
fo
r( i=0;i<n ;i++)
prin
tf("
%d",a[i]
);
}
i
ntmain()
{
i
nta[]={5,7 ,9,1,3,6,2,6,8,5}
;
i
ntn=s i
zeo
f(a
)/s i
zeo
f(a
[0]
);
qu
ick(a,0,n-1 )
;
 p
rin
tAr
r(a
,n)
;

r
etu
rn0;
}

Ou
tpu
t:

1235566789

LAB-
4
Pr
obl
em:
I
mpl
eme
ntFr
act
io
nalKn
aps
ackp
rob
lemu
sin
ggr
eed
yap
pro
ach.

I
npu
t:

Noofite
ms:1 0
Weightc[1
0]={
5,7 ,9,1,3,6,2,6,8,5} ;
Pro
fitsv[
10]={50,100,200,1
00,300,60,200,300,1
50,200}
;
ca
paci
tyW=20kg

Co
de:

#i
ncl
ude<
s t
dio
.h>
i
nti,
j,n=1
0,W= 20;
i
ntc[1
0]={5,7 ,9,1,3,6,2,6,8,5} ;
i
ntv[1
0]={50,100,200,100,300,60,200,300,1
50,200}
;
vo
idsi
mple_fil
l(
){
i
ntcur_w;
 fl
oa ttot_v ;
i
nti,ma xi;
i
ntu sed[10];
for(i=0;i<n ;++i )
{
used[i
]=0;
}
cu
r _w=W;
while( c
ur _w>0){
ma xi=- 1
;
fo r(i=0;i<n ;++i )
if((used[i]==0)&&
(
(ma xi= =-1)|
|((fl
oat)
v[i
]/c[i
]>(flo
at)v[
ma x
i]/c[
maxi
])
))
ma xi=i;
used [
ma x i
]=1 ;
cur _w- =c[ma xi
];
tot_v+=v [ma x
i];
if( cur_w> =0)
printf("Add e
do bj
ect%d(%d$,%dKg)comp l
ete
lyintheba
g.Spac
e
l
eft:%d . \
n",ma xi+1,v [maxi
],c[maxi
],cur_w);
else{
printf("Add e
d%d %%(%d$,%dKg)ofobject%dinthebag.
\n"
,(i
nt)
((
1
+(float)cur_w/c [ma xi
])*100)
,v [
ma x
i],c[
ma x
i],ma x
i+1 )
;
tot_v- =v [max i
];
tot_v+=( 1+( floa
t)c
ur_w/c[maxi
])*v[maxi]
;
}
}

p
rin
tf(
"Fi
ll
edt
heb
agwi
tho
bje
ctswo
rth%.
2f$.
\n"
,to
t_v
);
}

i
ntmai
n(i
nta
rgc,char*
argv[
]){
p
rin
tf(
"Fra
cti
ona
lKnapsa
ckProb
lem\
n\n
");
s
impl
e_fi
ll
()
;
 r
etu
rn0;
}

Ou
tpu
t:

Ad
dedobje
ct4(1
00$,1 Kg)co
mplet
elyint heb a
g.Spac
el e
ft:19.
Ad
dedobje
ct5(300$,3Kg)c o
mp l
ete
lyi ntheb a
g.Spacele
ft:16.
Ad
dedobje
ct7(200$,2Kg)c o
mplete
lyint heb a
g.Spac
el e
ft:14.
Ad
dedobje
ct8(300$,6Kg)c o
mplete
lyint heb a
g.Spac
el e
ft:8.
Ad
dedobje
ct10(200$,5Kg)complet
elyint hebag.Sp
aceleft
:3.
Ad
ded33%(200$,9Kg)o fobj
ect3int heb ag.
Fi
ll
edthebagwithobjec
tswort
h1166.67 $.

LAB-
5
Pr
obl
em:

I
mpleme
ntKr uskalal
gori
thm(Singl
esou
rces
hor
tes
tPa
th)fo
rtheGr
aph
gi
venbel
ow.
Kru
skal(
)
{
T={ 0};
foreachv∈V
MakeSet(
v);
sortEbyincreasi
ngedgeweightw
foreach(u,v)∈E( inso
rtedorde
r)
ifFind
Se t
(u)≠FindSet
(v)
T=TU{ {u,
v}};
Uni
on(FindSe
t(u
),Find
Se t
(v)
);
}

I
npu
t:
Co
de:

#i
ncl
ude"
std
io.
h"

v
oidswap(
in
t*i,
int*
j)
{
i
nttemp=*
i;
*
i=*
j;
*
j=te
mp;
}

v
oidsort
(intw[],i
ntv[]
,in
tu[]
){
i
ntmin ;
fo
r (
in
ti =0;i
<11
;i
++){
min=i
;
for(i
ntj=i;
j<1
1;
j++){
if(w[min
]>w[j
]){
min=
j;
}
}
swap(&w[i]
,&w[min]
);
 s
wap
(&u
[i]
,&u
[mi
n])
;
s
wap
(&v
[i]
,&v
[mi
n])
;
}
}
i
ntmai
n (
)
{i
ntV[ 7
]={1,
2,3,4,5,6,7};
i
nti
d[8]={0,1
,2,3,4,5,6,
7 }
;
i
ntT[6]={
0};//s olu
tio
nset
i
ntw[11
]={8,2,1
4 ,
21,25,1
7,13,
19,5,
9,1
};
i
ntu[
11]=
{1,1
,1,
2,3,3,3,4,5,5,6}
;
i
ntv[
11]
={2,4,3,3,4,5,6,
5,6,7,7};
i
ntk=0;
i
ntte
mp ;

so
rt(
w, v,u)
;
pri
ntf("
MSTEd ges:\
n")
;
for
(i
n ti
=0;i<1
1;
i++){
i
f(id[
u[i]
]!=i
d[v[
i]]
){
print
f("
%d-%d\n
",u[i
],v
[i]
);
temp=i
d[u[i
]]
;
for(i
ntj=1
;j<
=7;j++){
if(i
d[j
]==t
emp){
i
d[j
]=i
d[v[
i]];
}
}
T[k++]=w[i]
;
}
}

p
rin
tf("
Krushkal(
Corr
esp
ond
ingWe
ight
s):"
);
f
or(
inti
=0;i<k;
i++){
pri
ntf(
"%d",T[i
])
;
}
 r
etu
rn0;

Outp
ut:
MSTEdges:
6-7
1-
4
5-6
1-
2
3-6
1-
3
Krus
hkal
(Co
rre
spo
ndi
ngWe
ight
s):12581
314
LAB-
6
Pr
obl
em:

I
mplementDijks
traalgor
ithm(Si
ngl
eso
urc
esho
rte
stPa
th)fo
rtheGr
aph
gi
venbelow.
Di
jkstr
a(G)
foreachv∈V
d[v]={ 0};
d[s]=0;S={ 0};Q=V;
while(!empty
(Q))
u=Ex tr
act
Min(
Q) ;
S=SU{ u};
forea c
hv∈u -
> Adj
[]
if(d[v]>d[u
] +w(
u, v
))
d [
v]=d[u]+w(u,v)
;
.
I
nput:
So
urcenodeis2
i
ntV[7]
={2,1,
3,4,5,6,
7} ;
i
ntd[
7]={0,
1000,1
000,1
000, 1
000,1000,1000};
i
ntS[7]
={0};//solu
tio
ns e
t
i
ntw[7]
={ 1
000};
i
nted
geWe i
ght[7
][7]={{0,8,1
4,2,0,0,0} ,
{
8,0,21,0,0,0,0} ,
{
14,
21,0,25, 1
7,13,0},
{2,0,25,0,19,0,0},
{
0,0,1
7 ,1
9,0,5,9} ,
{
0,0,1
3, 0,5,0,1
} ,
{
0,0,0,0,9, 1
,0}};

Co
de:

#i
ncl
ude<
s t
dio.
h>
i
ntvi
sit
ed[7]={1
,2,
3,4,5,6,7};
i
ntmin(
intd[])
{
i
ntmini=
1000,mi
nIn
dex=1
00;
fo
r(i
nti=0;i<
7;i
++)
{
i
f(d
[ i
]<min
i&&v i
si
te
d [
i]!
=2)
{
 mi
ni
=d[
i];
mi
nI
nde
x=i;
}
}
v
isi
te
d[mi
nI
nde
x]=
2;
r
etur
nminI
nde
x;
}
v
oiddi
jksat
ra(i
ntd [],intedgeWe ight[7 ]
[7 ])
{
i
ntnext
node=1;
whi
le(
nextno
d e
! =100){
for(
intj=0;j<7 ;j++)
{
if(edgeWe ight [nextnode][
j]+d[ne
xtno
de]
<d[
j])
d[j]=edgeWe i
ght [nextno
de][j
]+d[n
ext
nod
e];
}
n extnode=min(d)
;
}
for
(i
nti=0;i
< 7
; i++)
{
i
f(i
!=1)
pri
ntf(
"%d-%d:%d\ n",2, i
+1,d[i]);
}
}
v
oidmain(
)
{
i
ntV[7]={2,1,3,4 ,5,6,7 }
;
i
ntd[7]=
{ 1
000, 0, 1
000, 1
000, 1000, 1000, 1
000} ;
i
ntedgeWe i
ght [7][7]={ {1
000, 8,1
4 ,2,1000,1000,1
000},
{8,1000,21, 1
000, 1000, 1000,1
000} ,
{14,21,1
000, 25, 17,13,1000} ,
{2,1000, 25,1000, 19,1000,10000},
{1000,1000, 1
7, 19,1
000, 5,9},
 {
1000,
1000,
13,1
000,5,
1000,
1},
{
1000,
1000,
1000,1
0009,1
,1
000}}
;
d
ij
ksa
tra
(d,
edge
We i
ght)
;
}

Ou
tpu
t:

2-1:8
2-3:21
2-4:1
0
2-5:29
2-6:34
2-7:35
LAB-
7
Pr
obl
em:

Gi
ven10act
ivi
ti
esalo
ngwiththe
irsta
rta
ndendt
imeas
:
Obj
ecti
vei
stosel
ectasmanya
cti
vit
yaspo
ssi
bl
ewhic
haren
oto
ver
lap
ped
.
I
mplemen
tusi
ngGreedyap
proa
ch.
ACTIVITYSELECTOR( s
,f)
0.SortSw. r
.tfin
isht
ime
1.n← l en
gth[s]
2.S← { 1
}
3.j← 1 .
4.fori← 2t on
5. i fsi≥fj
6. S← A∪{ i
}
7. j← i
8.returnA
I
npu
t:

A[
10]={1
,2,
3,4,5,6,7,8,9,1
0}
Si
[1
0]={1
,2,3,
4,7 ,
8,9,9,11
,1
2}
fi
[1
0]={
3,5,4,
7,10,9,
11
, 1
3,1
2,14
}

Co
de:

#i
nclud
e"st
d i
o.h"
v
oidso
rt(
intS[],in
tfi[]
,in
tsi[
]){
i
ntmin
,temp;
for(
inti=
0; i<
10;i
++){
min
= i
;
for
(intj=i
;j<
10;j
++){
i
f(fi
[min]
>fi
[j]
){
min=j
;
}
}
te
mp =fi
[i]
;
fi
[i]=
fi[min]
;
fi
[min]=te
mp;

t
emp=si
[i
];
s
i[
i]=
si[
min]
;
s
i[
min]=
temp;

te
mp= S[i
];
S[i
]=S[min]
;
S[mi
n] =
temp;
}
}
v
oidmai
n()
{
i
ntS[
10]={
1,2,
3,4
,5,
6,7
,8,
9,1
0};
 i
ntSi[
10]={ 1
,2,
3,4,
7 ,
8,9,9,1
1,
12}
;
i
ntfi
[10]={3,5,
4,7
,10,9,
11
,13,
12,1
4};
i
nti
,j;
s
ort(
fi,Si
,S);

i
ntk=0;
pri
ntf("
\nActi
vi
t i
esar
e...
\n"
);p
rin
tf(
"%d
,",
S[0]
);
for(
i=0;i
<10;i
++)
{
i
f(Si
[i]>=
fi[k])
{
pri
ntf("
%d,",S[i
])
;
k=i
;
}
}
}

Ou
tpu
t:

Act
ivi
ti
esar
e..
.
1
,3,4 ,5,9,1
0,

LAB-
8
Pr
obl
em:

I
mpl
eme
ntHe
apSo
rto
fthegi
venl
is
tofn
umb
ers

I
npu
t:
A[
10]
={5,7
,9,1
,3,6,2,6,8,5}
;

Co
de:

#i
ncl
ude< stdi
o.h>
vo
idhea
p ify(i
nta[],intn,in
ti)
{
i
ntla
r ge s
t=i ;
i
ntle
ft=2*i+1 ;
i
ntri
ght=2*i+2;
i
f(le
ft<n&&a [l
eft]>a[l
arge
st]
)
l
arge st=left;
i
f(ri
ght<n&&a [ri
ght]>a[l
arge
st]
)
l
arge st=right;
i
f(la
r ge s
t!=i ){
i
ntte mp=a [i]
;
a
[i]=a [
largest
];
a
[lar ges
t]=t emp;

he
api
fy(
a,n
,la
rge
st)
;
}
}
v
oidheapSor
t(i
nta[
],in
tn)
{
fo
r(inti=n/2-1 ;i>=0;i-
-)
he
ap i
fy(
a,n,i)
;
fo
r(inti=n-1;i>=0;i--
){
i
nttemp=a [
0];
a[
0]=a [i
];
a[
i]=temp;

he
api
fy(
a,i
,0)
;
}
}
v
oidpri
ntArr(i
ntar
r[],i
ntn)
{
fo
r(in
ti=0;i<n ;++i)
{
p
rintf
("%d",a
rr[i
])
;
p
rintf
("");
}

}
i
ntmain
()
{
i
nta[]={5,7,9,1 ,3,6,2,6,8,5};
i
ntn=sizeo
f(a)/si
z e
of(
a[0]
);
he
apSort
(a,n)
;
pr
int
f("
\nAfte
rs o
rtin
garrayel
eme
ntsa
re-\
n")
;
pr
int
Arr(a
,n )
;
re
tur
n0;
}

Ou
tpu
t:

Aft
ers
ort
inga
rra
yel
eme
ntsa
re-
1235566789

LAB-
9
Pr
obl
em:
I
mpl
eme
nt0-
1Kn
aps
ackp
rob
lemu
sin
gdy
nami
cpr
ogr
ammi
ng
fo
rw=0t oW
B[0,w]=0
fo
ri=0t on
B[i
,0]=0
fo
rw=1t oW
i
fwi< =w
if(bi+B[ i
-1
,w-wi]>B[i
-1,
w])
B[i,w]=bi+B[i-1
,w-wi]
els
eB[ i
,w]=B[i-1
,w]
el
seB[i,w]=B[i-
1,w]

I
npu
t:
Weightswt[]=
{ 2,
5,5,3},
Pro
fitsval
[]={5,1
0,8,8}
;
Noofitemsn=4
Maxi
mu mweightW= 10

Co
de:

#i
ncl
ude"stdi
o.h"
i
ntma x
(int
,in
t);
i
ntma i
n()
{
in
twt []={
2,5,5,3},
val
[]={5,
10,
8,8}
;
in
ti,j,n=4,W=10,B[5]
[11
];
for(i=0;i< =n;i++){
for(j=0;j< =W;j ++){
if(i==0||j==0)
B[i][
j]=0;
 e
lsei
f(wt[i-1]<=j)
B[
i][
j]=ma x(v
al[
i-1]+
B[
i-1][j-wt [
i-1]]
,B[
i-1
][j
])
;
e
lse
B[
i][
j]=B[ i-1]
[j];
}
}
i
nttemp=B[ n
][W] ;
prin
tf("
Ma x
imump ro
fit=%d\n",
temp)
;
j=W;
prin
tf("
it
emsare:" )
;
for(
i=n;i
>0&&t emp>0;i
--)
{
i
f(t
emp= =B[i-1
][j
])
{
co
n t
inue
;
}
el
se
{
pri
ntf("
%d",i)
;
te
mp=t e
mp-val[
i-1
];
j=
j-wt[i
-1];
}
}
}
in
tma x(
inta,i
ntb )
{
if(
a>b)
re
turna;
e
lse
re
turnb;
}
Ou
tpu
t:

Max
imu
mp r
ofi
t=23
i
te
msare:421

LAB-
10
Pr
obl
em:

I
mpl
eme
ntAl
lpa
irs
hor
tes
tPa
tha
lgo
rit
hm

Be
gin
fork: =0ton,d o
fori:=0ton ,do
forj:=0t on,do
i
fcost
[i,k]+c o
st[k,j
]<c
ost
[i
,j]
,the
n
c
ost
[i
,j ]=c o
st[
i,k]+c
ost
[k,j
]
Di
spl
aythecurr
entcostmatr
ix
I
npu
t:
Co
sto
fthea
bov
ema
tri
x
d
[5]
[5]={{0,3,8,999,-4},
{999,0,999,1,7}
,
{999,4,0,999,999},
{2,999,-5,0,999},
{999,999,
999, 6,0}};

Co
de:

#i
ncl
ude<s t
dio.h>
i
ntma i
n(
){
i
ntd[5][5]={ {0,3,8,999,-4},
{
999, 0,999,1,7},
{
999, 4,0,999,999},
{
2, 999,-5,0,999},
{999,999,999,
6,0}
};
i
nti,j
,k;
fo
r (
i=
0; i
<5;i++)
{
for(
j=0;j<5;j++)
d[i]
[j]=d[i
][j]
;
 }
fo
r (
k= 0;k<5;k++)
{
for(i=
0; i
<5;i
++)
{
fo r(j
=0;j<
5; j
++)
{
i
f(d[i
][k]+d[k][
j]<
d[i]
[j]
)
d[i]
[j]
= d
[i][
k]+d[k]
[j];
}
}
}
pr
intf("out
putma t
rixwithshort
estpa
th.
...
.\n
");
fo
r (
i=0;i<5;i
++)
{
for(j=0;j<
5;j++)
{
pr i
ntf("
%4d",d[
i][j
])
;
}
pr
intf("\
n "
);
}
}

Ou
tpu
t:

o
utp
utma
tri
xwi
thsho
rte
stp
ath.
...
.
0 1-3 2-4
3 0- 4 1-
1
74053
2- 1-
5 0- 2
8 5 16 0
 LAB-
11
Pr
obl
em:
Gi
venasetofci
ti
esan
dd i
st
ancebet
weeneve
rypai
rofci
ti
esasa
nadja
cenc
y
matr
ix,thepr
obl
emistofin
dtheshort
estpo
ssi
bl
erou
tetha
tvi
sit
seve
ry
ci
tyexac
tlyo
ncean
dretur
nstothesta
rti
ngpoi
nt.

de
ft s
p( S,cit
y=j) :
i
f(S= =full
Ma s
k):
ret
u rndi
st[j
][sou
rce]
i
f(C[ S][j]!=INF) :
re
turnC[ mask][ci
ty];
fo
rc i
ty_iinrange(n)
:
if(S&( 1<
<c i
ty_i
)==0) :
C[S- 1
,ci
ty]=min(C[ S-
1,ci
ty],
d i
st[j][
city
_i]+t s
p(S|(1<<ci
ty_i
),c
it
y_i
))
re
turncost

I
npu
t:

Cos
tmatr
ix(
Dis
tan
c ebet
weenci
ti
es
)
di
s[
4][
4]={{
0,1
0,15,20},{
10,
0,35,25}
,{1
5,35,
0,30}
,{20,
25,
30,
0}}
;
Co
de:

#i
nclu
de<stdi
o .
h>
i
nttsp(
int
, i
nt);
i
ntmin(i
ntx ,in
ty )
{re
turn(
x<y)
?x :
y;}
i
ntexpone
n t(
intx){
inti
= 0,temp=1
;
do{
t
emp *
=2;
i
++;
}while(te
mp !=x
);
returni;
}
i
nt
ful
lmask,C[15][4]
,cost
,n=4,
path[1
5],d
is[
4][
4]=
{{0,
10,
15,
20}
,{1
0,0,
35,
25},{
15,35, 0,30},{
20,25,30,0}};
i
ntts
p(i
ntma s
k, i
ntci
ty){
i
ntcs,cos
t;
i
f(mask==full
mask){
returndis
[cit
y][0];
}
i
f(C[mask][ci
ty]
!=1000){
returnC[mask][cit
y];
}
co
st=1
000;
for(
in
tc =0;c<
n;c++){
if((
ma s
k&( 1<<c)
)==0){
cs=di
s[ci
ty][c
]+tsp(
mask|
(1
<<c)
,c)
;
cost
=min(cs,c
ost)
;
if(
cs<C[mask][ci
ty]
){
C[mask][ci
ty]
=cs;
path[mask]
=(mas
k|(1
<<c
))
;
}
}
}
re
turncost;
}
i
ntmain
(){
i
nti,sou
rce=1;

fo
r(i
ntk=
0;k<
15;
k++)
{
fo
r(i
ntj
=0;j<
4;j
++)
{
C[
k][
j]=
1000;
}
}
ful
lmask=(
1<
< n
)-1
;
c
ost=
tsp(
sour
ce,0);
 p
rin
tf("
Minimumwe i
ght:%d\
n",c
ost)
;
i
=1;
pri
ntf(
"PathforTSP:%d- -
->",sou
rce
);
do{
p
rint
f("%d--->"
,ex
ponen
t(p
ath[i
]-i
)+1
);
i
=pat
h[i]
;
}whi
le(i
!=1
5);
pri
ntf(
"%d"
,sour
ce)
;
}

Ou
tpu
t:

Mi
nimu
mwe i
ght:80
Pa
thforTSP:1---
>2-
-->4-
-->3-
-->1

LAB-
12
Pr
obl
em:
I
mpl
eme
ntSu
bse
tsu
mpr
obl
emu
sin
gba
ckt
rac
kin
g

Al
gor
ithm:

su
b Set
Sum( s
ubse
t,s u
bsetSiz
e,sub
setSum,j _i
te
m)
Begin
i
fs ubs
etSum=t ar
getSum
thend i
spl
aythes u
bset
retur
n
els
e
forallel
ementi=j _it
emton(inthes e
t,)d
o
if(subse
tSum+s et
[i]
,<=targetSum)
subse
t[s
ubsetSi
ze]:=se
t[i]
subSet
Sum(s ub
set,sub
setSize+1,su
bse
tSu
m+s
et[
i]
,i+1
)
done
End

I
npu
t:

I
npu
tse
t[]={3,6,
2,4,
6};
n=5;t
arget
Sum=6;

Co
de:

#i
ncl
ude
<st
dio
.h>
i
ntMa x
Su m= 6,Solu t
ionSet[1
0],w[ ]
={3,6,2,4,
6};
v
oidSubSe tSum(intSu m,intk,i ntTota
lWe i
ght)
{
st
ati
ci ntb =1
;
Sol
utionSet[k]=1;
i
f(Sum+w[ k]==Ma xSum)
{
pri
n t
f ("\
nsubs e
t%d ...\n"
,b++) ;
for(i
nti =1
;i<=k; i
++)
{
if(So l
uti
on Set[
i]==1)
printf(
"%d \t
",w[ i
]);
}
}
el
seif(Su m+w[ k]+w[ k+1]<=Ma x
Sum)
{
SubSe tSum(Su m+w[ k],k+1,Tota
lWe i
ght-w[k]
);
}
i
f(Sum+To ta
lWe i
ght -w[k]>=MaxSum&&Su m+w[k+1
]<=
Max
Sum)
{
Soluti
o nSet
[k] =0;
SubSe tSum(Su m,k+1 ,
TotalWe i
ght-w[k])
;
}
}

i
ntmain(
)
{
i
ntTotal
We ight=21
,k=1,S=0;
i
f(MaxSum>Total
We ight||Tot
alWe
ight
<w[
1])
{
pri
ntf
("Nos u
bset
s");
}
Su
b Se
tSum(S,k,Tota
lWe ight
);
}

Ou
tpu
t:

s
ubs
et1
...
6
s
ubs
et2.
..
24
s
ubs
et3.
..
6

LAB-
13
Pr
obl
em:

I
mpl
eme
nt4Qu
eenPr
obl
emu
sin
gBa
ckt
rac
kin
gap
pro
ach.

Thegoali
stoass
ignei
ghtque
enstoei
ghtpos
it
io
nson
an4x4c hes
sboa
rdsotha
tnoqueen,
acc
ord
ingtotherul
esofno
rmalches
splay
,canatt
acka
ny
ot
herquee
nontheboar
d.

Al
gor
ithm

b
oard[row,c ol
]= {
0};b o
ard.Cols=board
.Rows=4
b
oolSolv
e(b oar
d,c ol)
{if(c ol>=board
.Cols
())
r
e t
urntrue
;//b asecase,pr
inttheso
lut
io
nfoun
d
forrow=0 t oboard.
Ro ws()
{i f(fe a
sib
le(bo
ard,r ow,co
l)
) //Noq ue
eni
nthes
ame
r
ow/colu
mn /di
agonal
{b oar
d[r o
w,c ol]=1//p utqu
eenher
e
 i
f(Sol
ve(
boa
rd,co
l+1))
re
tur
ntrue;//re
curton
extc
olu
mn

el
se
boa
rd[r
ow,c
ol]=
0//fa
il
ed,c
lea
ntheb
oar
d
}
}
r
etu
rnfa
lse
;
}

I
npu
t:
4Quee
ns
Co
de:

#i
ncl
ude<stdi
o.h>
#i
ncl
ude< std
lib
.h>
i
ntSolu
tion[1
0];
i
ntplac
e(int,
int
);
vo
idshow(i
n t
);
vo
idNqueen(i
nt,i
nt)
;
vo
idmain()
{
Nque
en (
1,4)
;
}
i
ntplac
e(intk,i
nti)
{
i
ntj;
fo
r(j
= 1;
j<=k-1;
j++)
{
i
f((Solut
ion
[j]=
=i)|
|(a
bs(
Sol
uti
on[
j]-
i)=
=ab
s(j
-k)
))
{
return0;
 }
}
r
etu
rn1
;
}
v
oidshow(intn )
{
i
nti,j,t
e mp=1;
pr
intf("
\n \
nsoluti
on.....
\n"
);
fo
r (
i=1
;i<=n ;
++i )
print
f (
"\t\t
\t\t%d"
,i)
;
fo
r (
i=1
;i<=n ;
++i )
{
print
f (
"\n\n%d",i
);
for(j
= 1
;j<=n;++j )
{
if(Soluti
on[i]==
j)
pri
n t
f( "
\t\t
\tQ%d"
,te
mp++)
;
else
pri
n t
f( "
\t\t
\t*
")
;
}
}
}
v
oidNqueen(intk, i
ntn)
{
i
nti,j;
fo
r (
i=1
;i<=n ;
i++)
{
i
f(place(k,i
))
{
Solution[k]=i;
if(k==n)
{
show(n);
 }
e
lse
Nq
uee
n(k+1
,n)
;
}
}
}
Out
put
:

s
olu
tio
n..
...
1 2 3 4

1 * Q1 * *

2 * * * Q2

3 Q3 * * *

4 * * Q4 *

s
olu
tio
n..
...
1 2 3 4

1 * * Q1 *

2 Q2 * * *

3 * * * Q3

4 * Q4 * *
LAB-
14
Pr
obl
em:
I
mpl
eme
nt0-
1kn
aps
ackUs
ingBr
anc
h&b
oun
dme
tho
d

Al
gor
ithm

b
ooli
sVal
id(in
tv ,in
twt,in
tpr
ofi
t)
{if((
wt+w[v])>W )
r
eturnfal
se;
re
turntr
ue;
}

v
oidknap01BB(intknap
Set[],i n
tkn apSiz
e,intknapSum, i
n tn
ode
Coun
t
,i
ntpr o
fit)
{if(flag=1&&p ro
fit>B)
{ B= p
rofit
;
dis
playSub
set(kn a
pSet,kn apSi
ze,profit);
retu
rn;
}
el
s e
{ fo r
(inti=nodeCount;i<n ;i++)
{i f(i
sValid(i
,kn a
p Sum,p ro
fit
))
{i
f((profi
t+p[i]+( W- w[i
])*p[i
]/w[i
])<B)
return;
knapSet
[knapSi z
e]=i; fl ag=0;
knap01BB(knap Set
,kn a
pSize+1,kna
pSum+w[i
],i
+1,
p
rofit
+p [
i]);
}e l
s e fl ag=1;
}
}
}

I
npu
t:

We
ight
sw[
]={
10,7
,5,1
5,1
2,20,1
8};
Pro
fit
sp[]={
100,7
0,50,1
50,1
20,1
50,1
00}
;
Noofit
emsn=7
Maxwei
ghtW=35

Co
de:

#i
ncl
ude<stdi
o.h>
i
ntw[]={ 1
0,7 ,5,15,1 2,20,1 8};
i
ntp[]={ 1
00,7 0,50,150,1 20,150,100};
i
ntn=7 ,fla
g;i ntW= 35,B= 200;
vo
iddi
spl
a y
Su b
set(
intknap Set
[],in
tsiz
e,in
tpro
fit
)
{
pr
int
f("s
elect
editems:" )
;
fo
r(i
nti=0;i<s i
z e
;i ++)
{
pr
intf(
"%d\t"
,knapSet[i]
);}

p
rin
tf(
"&&ma
xPr
ofi
t:%d\
n\n
",p
rofi
t)
;

}
i
nti
sVal
id(
in
tv,i
ntwt
,in
tpr
ofi
t)
{
i
f((
wt+w[v]
)>W)
{
r
etur
n0;
}
e
lse
ret
urn1;
}

v
oidkn
ap 01
BB(i
ntkn
apSe
t[]
,in
tkn
apSi
ze,i
ntkn
apSu
m,i
ntn
ode
Cou
nt
,i
ntprofit
)
{
 i
f(fl
ag=1&&p rofit>B)
{
B=pr
ofit
;
di
spl
aySubset(kn apSet,knapSize
,p ro
fit)
;
re
turn;
}
e
lse
{
fo
r(inti=n odeCount;i <n;i++)
{
i
f(i
sValid
(i,kn a
pSu m,pro
fit))
{
i
f((p
r o
fit+p [i
]+(W- w[i
])*p[
i]/
w[i])
<B)
retu
r n;
knap
Se t[knapSize]=i;flag=0;
knap01
BB( knapSet,knapSiz
e+1,knapSu
m+w[
i]
,i+1
,
pro
fit+p[ i
]);
}
el
se
fla
g= 1
;
}
}
}

i
ntmain
()
{
i
ntprofi
t=0;
i
ntsubSet
[n]
;
knap
01BB(su
bSe
t,0,0,0,
pro
fit
);
}

Ou
tpu
t:
s
ele
cte
dit
ems:012 &&ma
xPr
ofi
t:220

s
ele
cte
dit
ems:013 &&ma
xPr
ofi
t:320

s
ele
cte
dit
ems:134 &&ma
xPr
ofi
t:34
0

LAB-
15

Pr
obl
em:

Gi
venapart
ial
lyfil
led9×92Darray‘
gri
d[9]
[9]’
,thegoa
list
oass
ign
di
git
s(fr
om1t o9)totheemp
tyce
llss
othatev
eryrow,c
olu
mn,and
su
bgrido
fsize3×3contai
nse
xac
tlyon
eins
tan
ceofthedi
git
sfro
m1to9.

I
npu
t:

Co
de:

#i
ncl
ude<s
tdi
o.h>
#d
efi
n en9
i
ntS[9][
9]={{3,0,6,5,0,8,4
,0,0}
,
 {5,2,0,0,0,0,0,0,0} ,
{0,8,7 ,0,0,0,0,3,1}
,
{0,0,3,0,1 ,0,0,8,0},
{9,0,0,8,6,3,0,0,5} ,
{0,5,0,0,9,0,6,0,0} ,
{1,3,0,0,0,0,2,5,0} ,
{0,0,0,0,0,0,0,7 ,4},
{0,0,5,2,0,6,3,0,0}} ;
i
ntSafe(in
tr ,intc,intt
emp)
{
i
ntsrow, sc
ol;
sr
ow=r -r%3;
sc
ol=c
- c%3;
for(
in
ti =0;i<
=8;i++)
{
i
f(S[r ]
[i]=
=temp)
return0;
}
for(
in
ti =0;i<
=8;i++)
{
i
f(S[i][c]
==temp)
return0;
}
for(
in
ti =0;i<
3;i++)
{
for(i
ntj=0;j<3;j
++)
{
if(S[i
+srow][j
+scol
]==
temp
)
ret
urn0;
}
}
re
turn1;
}
i
ntSudoku(in
tr,i n
tc)
{
i
f(r==n-1&&c ==n)
retur
n1;
i
f(c==n)
{
r++;
c=0;
}
i
f(S[r][
c ]
>0)
retur
nSu doku(
r,c+1
);
fo
r (
inti
= 1
;i<
=n ;
i++)
{
i
f(Safe(r,c
, i
))
{
S[r][c]
=i;
if(
Su do
ku (
r,c
+1)=
=1)
r e
turn1;
}
S[r][c]
=0;
}
re
turn0;
}

i
ntma i
n(
)
{
i
f(Sudo
ku(0,0)==1
)
{
for(
in
ti=0;i<n;i
++)
{
for(
intj=0;j<
n;j++)
{
pri
n t
f("__%d__|"
,S[
i][
j])
;
 }
p
rin
tf(
"\
n")
;
}
}
e
lse
p
rin
tf(
"nos
olu
tio
n")
;
}

Ou
tpu
t:

__3__|__1__|__6__|__5__|__7__|__8__|__4__|__9__|
__2__|
__5__|__2__|__9__|__1__|__3__|__4__|__7__|__6__|
__8__|
__4__|__8__|__7__|__6__|__2__|__9__|__5__|__3__|
__1__|
__2__|__6__|__3__|__4 __|__1
__|__5__|__9__|__8__|
__7__|
__9__|__7__|__4__|__8__|__6__|__3__|__1__|__2__|
__5__|
__8__|__5__|__1__|__7__|__9__|__2__|__6__|__4__|
__3__|
__1__|__3__|__8__|__9__|__4__|__7__|__2__|__5__|
__6__|
__6__|__9__|__2__|__3__|__5__|__1__|__8__|__7__|
__4__|
__7__|__4__|__5__|__2__|__8__|__6__|__3__|__1__|
__9__|
 LAB-
16
Pr
obl
em:

I
mpl
eme
ntMa
xCl
iq
uePr
obl
emu
sin
gbr
anc
han
dbo
und

I
npu
t:

Adj
ace
ntma t
rix
ad
j[1
00][
100]={
{0,1
,0, 1
,1
,0},
{1
,0,1,0,1
,0},
{0,1
,0, 1
,1
,1
},
{
1,0,1,
0,1,
1},
{
1,1
, 1
,1
,0,1
},
{
0, 0,1
,1
,1,
0}};

Co
de:

#i
ncl
ude
<std
io.
h>
i
ntCli
que
(i
nt,i
nt[
],i
nt,
int
[])
;
i
ntis
Valid(
int,in
t);
v
oidco
py (
int
[ ],i
nt)
;
i
ntadj
[1
00] [100]={{0,1,
0,1,1
,0},
{1,0, 1
,0,1,
0} ,
{0, 1
,0,1,1
,1},
{1,0, 1
,0,1,
1},
{
1,1,1
, 1
,0,1},
{0, 0,1,1
,1,
0}} ;
i
ntmax=0;
i
ntn=7;
i
ntSol
[10];
i
ntCli
que(
intk, i
ntRe m[],i
ntlen
,in
tt e
mps
ol[
]){
i
nta dj
[ 1
0]={0},temp;
i
f(len==0){
if(
k> max)
{
copy(
temps
ol,k)
;
ma x
=k;
}

r
etu
rn1
;
}

fo
r(i
nti=0;i
< l
en;i
++){
te
mp sol[
k]=Rem[i
];
te
mp =0;
for(i
ntj=i+1
;j<l
en;j
++){
i
f(isVal
id(
Rem[i
],Rem[j
])
){//a
dja
cen
t
adj
[te
mp++]=Rem[j
];
}
}
i
f(k+temp >=
ma x
){
Cli
que(k+1,a
dj,t
emp,te
mpsol
);
}
 }
r
etu
rn0;
}

i
ntisVa l
id(inti,i
ntj){
if(adj[i
][j]! =
0){
retur
n1 ;
}
return0;
}
v
oidco py(i
nta rr[]
,intlen)
{
for(i
n ti=0;i
< l
en;i++){
Sol[i
]=arr[
i];
}
}
i
ntma in(
){
in
tRe m[ 10]={0,1,2,3,4,5},
temp=
6;
in
tt emp sol[1
0];
Clique(0,Re m,temp,tempsol
);
printf("Ma xcliq
ueSiz e:
%d\nVert
ic
es:
",ma
x);
f o
r(inti=0; i<
max ;i
++) {
printf("%d",Sol[
i]);
}
}

Ou
tpu
t:

Ma
xCliqu
eSi
ze:
4
Ve
rti
ces
:2345