20/11/2023 Date:

DSHADMAN to:
MD, bubmitted
2217 C3E Code: Course
249 222 O11
T5LAM RATSUL MD. Name
Assigment-1
ALGORTHMS
TT AND
51RUCTURE DATA
 Assignment-1

Ans. to the ueS. No-4

wThe maximum sub- ar rray prroblem gives the

highest or maxi mum Sumn ot a Sub-arTcay

when apply brute-force techigue,

we caleulate evry possible contiguous subonng
5uch as
A[1.11, A[1..21, 6..:..'A4.(n-)1,4(4.
[21, ....., n (n-],42..]
[2,...
A

A[n-)..(n1,A[(n-)..n]

using divide amd conguer, the proble

But when
diyded to many sub problens.
i5 divided

4 |:
 S0, the time conplexity is,
T) o(nog)
we krouw, in the conplexity chart otnlogn) <0m
Hen ce, i ide-and conguer takes less time
to solve the prroblem morte effieienty.
Ans. to the Gues. No-2
posz1 2 3 4 5 #
A=-2 3-2 4121
MSA( A, 1,)
3 (6.)
s24)
MSA(A,14) MSA(A, 5,,
5(a.4) 4(4,4) 2 (66) 3(6.3)
r1SAlA,1,2) MSA(A.3,4) MSA(A5.6)
-4(5.5)
2ta4)\a(49) (6)

MSAA,1) MSA0A2 2)
) MAlN3a
MSAlA23) MSA(A,4,4) MSA(As3)
MSAa55) mSA(A,6 )
Explaimation:
Artay oige ¥.
cum 4 Crossimg sum
Left: (1,9)
s(2.
(4 (3.4) 5(2.4
4(414)
(i,)
s(2.2) -(3:2) 4(4,4

Right:
(5.)
a(b.) 4(*)
-(s.) () ’

-4(5.) 2(6)
(s:3) (b/5)

3o, Ginaly. 2) and

arreay is
Max-sub- array NA(A,
 Ans. to the Qes. No-3
4

L=1 5 9 1015|
2 4
11 13

1 2
10 11

1 8 9 14 15

) Compane (L[o], Ro1)

| 2 4
1

2 3

4) (L,R))
1 46]6
 45

4
) Le1, R[31)
4 5 9

) (ea *a)
789

) ((1, RB)
4
L(6], [
13

i) L($], RSI
13

12) L6], R[6]

8 13 14|5
 Ans. to the Que 5. No-4

Ae tieity: a ay
850 1700 300 300soo1206
Arrival : 1000 340

2O 00 835
104o 2000 1800 IG50 1380
Departu re: 1030 1o 30 1040

Nous 9@ have to 50rct them by depar ture

time in aseendimg
a: ordere -’
Actiitye as
1S00 1300 00
Arrüyal 300 840 1O0035O 1200|
Departure; 835 1030| 4090o 1040 |13801650 1206 2000

NOu i we consid er the eondition hat,

therce must b 10 min 5afety break
a

betuseon train's departure and anothere

thoin's artival time., With the gne ed
belection of
choioe prbpa being
tha tir bt actisity, The 5alutio slu
1. ag ’ [8O0, 835
e uson't taKe a2 as 835 to 840 S 0ny 5 mns

[1000, d036)
3. ag ’ [1200, 1386]
4. 1500, J650|
a4 ’ [1700, 2000]
tollo wing the conition
By gnead nethod, the
5 trams CanN come to
that
platform ithout ouissio.

Can e the
10tat Maximum 5 train^
platform.
 Ans. to tho Ques. No-5

n 45
eb 141
2111 1 54

3 57 t 6,9

129(5,)
99(u)
71;0 57,S 49:t
45
843 a

J26
155(0.a)
1
49:t

99

45:0
 49 1

281 210

155 126 99

54: L 45n
84:a 49% 141;2
57S

Code sord:
t
001

oo|ooot|Oto1|
in
btolen 10 de o
For tixed length code 9e need 3 bits, A5
ther ane 7 aharracterrs. So. for y91 characters
we'll ne ed (yol * 2) 14 34 bi ts.
491*3)
forr huffmad eneodig ’
3* (fre. ot a+l+n+0+s+ t 2* tre. e

3* (34 +54+4 +714 5469) + 2 x11|

1362
1 473 -1362
bo, pereentage ot sasing 143
o753 X loo.

A.
oims,. 4too and coin one
ken Coims
to
15t44 =
totaa
m bo,
2 2$ 2. 2
3 2 2 4
2
2¬ |<2
243 2 2
4 434 3 3
2 2 2 1 1
34 3
55 4
445 3 2
6 5
8 2
3|Y
15 12 9
3 2
10 9 8
12
15 14 13
1
L+2 1+22 |+22 ord 3
or 3 or 3
|+0
1+2 42 |(42 1+1 An 9
1+3 t3 (+2 or3or3or3 Z 20
4or or 4 on 3
H2+23)1+2
(+32 orr3 2or
orYo4or5
14 6or or 5 or 1HeQ1+He2|
44
43Y4 43l+2 42-3
orr4or 6
or 2
or 10 or l9
12or
e 10
12. 4 3 2
12 11 9
15 14 3 method Tabular
15 Me Hete
)
No-6 ues. the tDAns.
 Ans.to the ues. No - 7

Lets ta ke ’
5
Length, l:4 4
15 2
value;v 2 11|

In this problem the greedy method is

done
1it4 choose length $4, value te.15
bo, rtemaining length (5-4) -21
So, tetat alup t0+44
Now t takesthe rem aining 1
lorrgth , to tal value = 15+2 : ty
Dut the optimal bolution ip
21 take length 2 and 3.

0, we 00n se0, in t io prob lom the

greed oppro ach does t gle te
optimal 0lution
 Ans. to tho ue4. No-9

This problem aam be identified 'as a /4 Knapsack

problem to mami2e profit. An algorithn
tor this i5 given bolow’
int knaps
int knap sack(int Bi, int i) {
1

if (Bi=6 I| ier 0) retunn o

i4 (n [BiI !) retur returrn m [Bi1 t1
int notTake = knapsack (Bi 1)
int Take

if (Bi >= band[i])$

+ knap 5oc k(Bi- band [1, i-1)
Take = prcice [ij

Ta ke -O

it(not Take >- Ta ke)

dinalyalue not Take
inavalue o Take

retutn = final yalue

 Ang. to the Queb. No- 9
2 4 5

wciglt/3 2 3
Value I80 170 120

Here, Capactty
Using the bottom up opprco ach ’
ite 1 4 5

I50 160 150 150 150

2 180I30 330 B0

350 350 350

3

|70 180
350 350 350
4
5 210 380 00 390
fractional Rropsa ck:
items = 5
capadty
item 2 4y. 5

yalue J50 180 120 210

85 40 T0
Proit(par 9)
item 0 prcofit Remaining

210

420

´picofi t 500
 Ans to the ueb. No-10

CATALAN():
rreturn 1

return memo ]
foreie0 to n1
C= e+ eATA LAN C) * CATALÒN (-t-1)]

meno[n] ee
Teturn e

Recusssive Tree
CATALAN (3)

CA1ALA N(0) CATALAN (2)

CATALAN (6) CATALAN()

Afterr memo the oerriding prto blern solve b
and the table becomes

cATALAN )
Value

1 1

2 2
 Ano. to the Quos. No-41

Algorithmi(n, ) DSt time

1+1
1. for (is t; i(en; isit1)
2. prunt (i)
3. fo rrlj-1;
1<=m;j=j+1) Mt1

4. For (i:3; i<n; iel42) Cy

prùntlij) Cs

T() c4 (n+)+ c, n+ ,C (rm+) +ey (m. )

Cs (m. a)