Algorithm

Design and Analysis

4:20
Wednesday
-

Friday -

3:30
 August 31 1 2022

Wednesday
•
Algorithm :
simple unambiguous set of steps
. . to carry out
some tasks .

•
Analysis : Predict the cost of an algorithm (how much time/
space it is consuming )

•
Design : It minimizes the cost of the algorithm .

Basic
goals for an
algorithm this course 'll tours on

performance .

→ always correct
→ always terminates

☒ What is scalability?
If the input size is very large can the algorithm
still the correct output in
give a reasonable amount of time ?

•
Algorithm helps us understand scalability .

Algorithmic mathematics provides a language .

•
Performance is the
currency of computing .
① A
programme finds prime numbers between
all the 2

and 1,000,000,000 from scratch in 0.375 ?

'

② does efficiency matters ?

Why
•
Database is huge
challenges -

•
Does it scale •
what to measure
•
Time and space efficiency

• How to /
measure compare ?

•
hoods -

time & inputs relationships .

•
htl a timer or a programme .

→ pros / cons

running time varies between algorithms -

Pros

running time varies between implementations -

cons

running time varies between computers -

come

running time isn't predictable based on small inputs : eons

time varies with the respect to the inputs : pros

relationship between time & input not clear : cons

counting operations : frequency to count / compare algorithms .

pros / cons of counting operations .

 •
growth of programmes runtime : generally we seek upper
bounds of a run-time for

guarantee of performance .

•
kinds of analyses :

1) worst case Cnsnally)

2) average case crave )

3) Best case (never)

• Bottom line :
How to analyse the algorithm to get the curve of
relationship between time and input .

September 7,2022
Wednesday
•

Big 0h .

Wren functions 1- In ) & glh) .

We
say that f- In ) is 01g (n ) ) if there are positive

constant cand no , such that -

tent -
-
our algorithm
41m ≤ cgln) for n ≥ no
gln) Over approximation
=

)
n
cgcn gln )≈n2
cgln)

Nᵗ
a

[Link]#WflD
"
""°

i
i
i.
s
! i
hot no
 Big 0h gives us the upper bound .

we want to find the

behaviour of fln) Find .

the intersection behind

the
1- 1h) and gln ) .

behaviour of curve isn't

predictable before no .

only after no .

1- ( insertion sort) = 0 Cn)

aritbn -1L ≤ Mln ) ~

① 7h -2 is 0 Cn )
7h -2 ≤ Cin
Cc 7) n ≥ -2
-

② 3h -18 is 0 Cn )
3h -18 ≤ c. n c = U

(c- 3) n ≥ 8 no = 8

n≥ 816 3)-
 September 1h , 2022

Wednesday
•
Merge sort

185

y_Yide
2h 1h 50 35 70 98 30

✓
852¥ 3570198301
L k
④ conquer
85/24-114/50 / 35175 98131 ✓
↓
%☐⑨
£ 6

1853129 ID ⑤ 3⑤ ⑦ ☐ merge
& d ↓ ↓

141500 13517°F 130198J

2411850 m=h1z
✓ he

1303517098 /

/1n2h/5085#y
Divide & conquer

/
Conqner
I
y
① Divide ② Merge
114243035/50708598-1
merge sort
(array ,
low , high) f172n5-
\
✓ /
/ 12 17 24 2550 72 go qg
'2 25 72 80
µ
merge sort Merge govt
(array low m )
, , (array ,
m -11 , high)

suppose we have an
array sized h -

F- 01h )

✓
1h17 %) ◦
Cn ) time complexity Olnlogn) -_

he h
☐4n ④ nI%]o(n)
: : :
:
I
n
-
,
•
Recurrence equations

{[Link]
ten)=

[
Otherwise

For
value value

station
=
2.
(21-4122)+4 /2) + Ln

=
24-1-4122) -12cm

1- (a)
=2it(Mzi)+icn

[Link]/zW9h)-(logn)cn2i--n=ntlI)-cnwgni-
Wgn = 0 ( nlogn)
 September 21 , 2022

Wednesday
bound
0 notation
- :
Asymptotic upper

Omega -
r -
notation :
Asymptotic lower bound

f- Chl ≈ or (gcn ) )

It there exists positive constants c and no ,

such that

0≤ c , gens ≤ flh) ,
for all h > no .

f- Ch
fln) =
100W-1 10h -150
f- Cn) = RCN)
flu ) = 5hr

Of cn~≤ 5hr

cñ≤ 5hr

C = 5 no = I

1- Cn ) = Remy

Theta ⊖ notation -

Asymptotic tight bound

fln ) a ① (gcn ) )

If there exists constants [Link] and no . such that

Cigcn ) ≤ fcn ) ≤ czgth) for all h < no .

f::
 sowing recurrences

Recursion substitution Master method

tree

n ?
,
>
M2

¥ '
mutiny :
Olnlogn )
: : :

# leaved = 0th)

Applies to recurrence of this form =

Tch)=aT(n / b) + D-
(nkwgPn )
where ,
a> 1, b> I and 1- is
asymptotically positive then
.
,

① if a > bk then Tcn ) =

Q(nW9ba )

If a=bk then

@ If P > -1 , then 1- In)= -0 (nlogbalogp -1

'm )

⑨ If p= -
1. then Tln ) -
[Link] )
⑨ If Ps -
I. then T(n)=⊖(nw9bh )

If a < bk then

@ If [Link])
⑨ It PSO , then Tln) = ⑦ (nk )
•

Binary search

1- ( n ) =
TIN / 2) + D- (1)
a = 1 b 2
1<=0
=
,
, 12--0
bk = 1

a = bk

1- (n ) ⊖ w9ba
=
(n .
log titles)

(into92 login )
'
= -0

= ⊖ (nologn )
① ( login
=
)
 October 19,2022

Wednesday
•

Dynamic Programming
Related to Divide & Conquer
1) Divide problems into
tub problems .

> Divide into sub problems

2) Store subproblem solution
in a table .
> Solve sub problems
recursively
3) Bottom-up computation
( Wwe only once and

store the solutions .

)
in the tree the . leaves are

created before then order

, they are n

combined into a tree So , 01h1 time

.
F,
done / 01h ) space
the programming is
F
,
If ,
bottom-up /
\fz f-[
.

Fu
• Fibonacci Nnmlock
I \
F2_- Fo
IFF
\
f- 3
Fz ¥2 F1
,
F-
2

{
° if h=0 / 1 1
11
Fn=
,

1
if . n =L 1=2 Fi Fi Fo f Fo
,

Fm , -1 Fn -
z .
Otherwise F ! ¥0
101 I 1 11 21 3/5/81 . . -
.

•
Memorization Fo F
For Fu
, Fz Fs Fb
compute & remember & Reuse

•
Pseudo code -

Fib
Dpln ) -

declare a table of
size n -11

for i in range n -11

if i==0 Or i - =L

table [i] = i

else ,

table [ i ] = table [i ☐ -
+ table [i -2]
return table [n ]
 •
Properties
1) Optimal substructure : Optimal solution to a problem will
have optimal solution to the sub Problems .

2) Overlapping sub problems : small no .

Of sub problems

repeated many times .

( Viji Max
-
-
{ Vci-1,5 ) . Hi -1.5 wtz) -
1- Vi ) }
•
DP for 0-1 knapsack
W 0 I 2 3 45
Item weight value o o o o o o o

a 2 3 I 0 0 3 3 33
g z y o o , n u a
C U 5 3 00 3 9 57
d 5 6 y o o 3 45 → Max value

Tai)= Max { v11 -1,1 ) , ✓ (1-1,1-2) -13 }

↓ ↓
not choosing choosing the
the item item
is
> this
=
ma'
{ v10 , ) v10 # +3Jcancelled
,
,

= ✓ 10,1 )
1- G. 2) =
Max { (1-112)
✓ ,V (1-1,2) ,
✓ (1-1,2-2) -13
}
=
Max { v10.2 ) ,
✓ (0,07+3 }

= Max { 0,3 }
=
3
?⃝
?⃝
 October 21,2022
Friday
•
Matrix chain multiplication
4×6 6×5 4×5

[ ] [ ] [ Fr ✗ -_
>
ooeuments
36 multiplication
6 row u each
row = h row = __

column 5
column -5
-_
-

column __ &

Ai A- 2 Ab
10×100 100×5 5×50

number of individual multiplication

(A- i. A2) -
A } -77500 [10×100×5 -110×5×50]
Ai ( Az .AZ) -775000 [100×5×50 -110×100×50]
this detents optimal parenthesis atioh .

to get the minimal (best value of multiplication .

we can use dynamic programming to find it out .

Ai A- 2 A- 3 Ay
6×4 4×5 5×3 3×4

Ai (Az (Ab .
An) )
Ai ( (Az .
Az)An) )

( (Ai -
A- 2) LA } An)) .

( IA , (A2 And )Au ) .

( ( A. A- 2) A- 3) An
 name of matrix M

I 2 3 4 I 3 4

f
2

° " " "^" " ""

"^"
I
° " "
"" "
"

2 0 60
2 -
(A- Az) Ay
a.
.

3 0 60
3 -

0
y .

4 -

M[1) 2) = A- i. A2 ME }] '
=
Az Az . M[ 3. 4) = A} . Ah

=/6×41 (4*5) =
[4×5] [5×3] =
[5×2] [3×4]
5×3×4
6×4×5 4×5×3
=
= =

= 60
=
120 = 60

m [1,3] = A A- [Link]

]
i.
the
count both and take
= (A- i. A- 2) A }
/ Ai CA , ,A ,
)[ Minimal value

= min {m[ i. 2) + M[3.3] -16×5×2 }

= min { 120 -101-90,0-160+72 }
= min { 210,132 }
= 132

M[2,4 ] -
-

Min { AIA } - Au) .

(Az Az)
. .
An }

=
Minh m[2,2] M[3.4] +
-1×5×4 , m[ 2.3 ] -1mEur] -14×3×4 }
= min { 140,108 }

=
108
 { A (Az Az Au) (Ai A 2) ( 3. An) (A i. A- 2. Az ) An}
A
MEI , 4] = Min , . .
,
, .

= Min { m [in ] -1M [2M] -16×4×4 ,

m [Ii 2) -1m [3^4] * 6*5×4 ,

m [ 1,3 ] m [4.4 ] -16×3×4 }

1-

= win { 01-108-196,120-160 -1120 ,

132-10+72 }

= min { 21h , 300120h }

=
204

optimal parenthesitation of the given multiplication will

be = ( Ai (Az .
Az) ) An

M [i. j ] = min {m [i. K ] + m [K .

]] + d [i i ] ✗ d [K]
- ✗ d G- ] }
i ≤ k≤ j

time complexity = 0 Cn3)