AI notes as per communciations skill and
sukhpreet76
11 views
158 slides
Aug 18, 2024
Slide 1 of 158
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
About This Presentation
AI notes
Slide Content
All Important Topics of CS
e All Important Theorem
IGvwa qrorh with (E) edge ond n vertices
je Vea VE rm - Im? then
¿um =2181 | >
4
on cl 1
i» peer |
he king Husum
a digas sl grat
a of graph in alwoys even. |
ES |
t h
No of varhen of odd dp tA Ge ance
( —
E At) Za 2 (720 Ns
a even \ add deg Aer
ee A
v —
je Vea VE rm - Im? then
¿um =2181 | >
4
on cl 1
i» peer |
he king Husum
a digas sl grat
a of graph in alwoys even. |
ES |
t h
No of varhen of odd dp tA Ge ance
( —
E At) Za 2 (720 Ns
a even \ add deg Aer
ee A
v —
Complement of a Graph
Ea Smpu geoph Aw
puch ot the will oe
At thos
a geoph A, on Ye
Complain
weap ven oS oF 4
soot
élan hoo: Vestes CHAO) Ma a
ty ine, edge. ASE (uy na
mn & > HF y ms, not adjaunkin a
> luv) e adjacsnt
OH IE OI
ZE (kn)
Pre
Ea Smpu geoph Aw
puch ot the will oe
At thos
a geoph A, on Ye
Complain
weap ven oS oF 4
soot
élan hoo: Vestes CHAO) Ma a
ty ine, edge. ASE (uy na
mn & > HF y ms, not adjaunkin a
> luv) e adjacsnt
OH IE OI
ZE (kn)
Pre
Theorem 1 (Degree-Sum Formula). For any graph G
dv) = 2G]|
Theorem 2. In a graph G, the average vertex degree is =, and hence
6(G) < : < A(G)
Theorem 3. In any graph, the number of vertices of odd degree is even
Theorem 4. A k-regular graph with n vertices has Æ edges.
Theorem 5. Ifk > 0, then a k-regular bipartite graph has the same number
of vertices in each partite set
dv) = 2G]|
Theorem 2. In a graph G, the average vertex degree is =, and hence
6(G) < : < A(G)
Theorem 3. In any graph, the number of vertices of odd degree is even
Theorem 4. A k-regular graph with n vertices has Æ edges.
Theorem 5. Ifk > 0, then a k-regular bipartite graph has the same number
of vertices in each partite set
«the Spanning tree is minimally connected maximally acyclic Graph
“Spanning tree
«From a complete graph, , We can construct a spanning
tree.
«A complete graph can have
«number of different spanning trees in a complete bipartite graph. If we write the bipartite
graph of n elements in one part and m elements in another part, the number t of
different spanning trees of Kn,m is given by the formula:
“Spanning tree
«From a complete graph, , We can construct a spanning
tree.
«A complete graph can have
«number of different spanning trees in a complete bipartite graph. If we write the bipartite
graph of n elements in one part and m elements in another part, the number t of
different spanning trees of Kn,m is given by the formula:
Dig kedar Algaritinm
> D Select Sounce verter en)
2DSek dintence of sounce verter ko 0-
ds] <0
Obun verkan to 2
den au ve v-ist
Ark[v] re
4
Suu one vertex and tory bo sulox otheo verter
dake shontent Path:
HE IE (arutwlwv) < ALv]) ton
atvi= diu) + lv, v)
> D Select Sounce verter en)
2DSek dintence of sounce verter ko 0-
ds] <0
Obun verkan to 2
den au ve v-ist
Ark[v] re
4
Suu one vertex and tory bo sulox otheo verter
dake shontent Path:
HE IE (arutwlwv) < ALv]) ton
atvi= diu) + lv, v)
A connected multigraph (and simple graph) with at least two vertices has a Euler circuit if
and only if each of its vertices has an even degree
A connected multigraph (and simple graph) has an Euler path but not an Euler circuit if and
only if it has exactly two vertices of odd degree
The total number of Hamiltonian cycles in a complete graph are
(n-1)!/2, where n is number of vertices.
and only if each of its vertices has an even degree
A connected multigraph (and simple graph) has an Euler path but not an Euler circuit if and
only if it has exactly two vertices of odd degree
The total number of Hamiltonian cycles in a complete graph are
(n-1)!/2, where n is number of vertices.
Dirac's Theorem="If Cri asimple graph with vertices with > B such that the degree of every
vertex in Cris atleast 7 N. then G has a Hamiltonian circuit
Ore's Theorem- “If G is a simple graph with N vertices with N > 3 such that
deg(u) + deg(v) > n for every pair of non-adjacent vertices U and Y in G, then G has a
Hamiltonian circuit.”
the above theorems are sufficient but not necessary conditions
for the existence of a Hamiltonian circuit in a graph, there are
certain graphs which have a Hamiltonian circuit but do not
follow the conditions in the above-mentioned theorem.
For example, the cycle C5 has a Hamiltonian circuit but does
not follow the theorems.
Note: Kn is Hamiltonian circuit for n >= 3
vertex in Cris atleast 7 N. then G has a Hamiltonian circuit
Ore's Theorem- “If G is a simple graph with N vertices with N > 3 such that
deg(u) + deg(v) > n for every pair of non-adjacent vertices U and Y in G, then G has a
Hamiltonian circuit.”
the above theorems are sufficient but not necessary conditions
for the existence of a Hamiltonian circuit in a graph, there are
certain graphs which have a Hamiltonian circuit but do not
follow the conditions in the above-mentioned theorem.
For example, the cycle C5 has a Hamiltonian circuit but does
not follow the theorems.
Note: Kn is Hamiltonian circuit for n >= 3
Graph Colouring
+ chromatic number of a complete graph X, = n.
+ By Vizing's theorem, the number of colors needed to
edge color a simple graph is either its
maximum degree BE
+ For some graphs, such as bipartite graphs and high-
degree planar graphs, the number of colors is
always il
+ and for multigraphs, the number of colors may be as
large as
+ The four-color theorem states that any map in a plane
can be colored using four-colors
+ chromatic number of a complete graph X, = n.
+ By Vizing's theorem, the number of colors needed to
edge color a simple graph is either its
maximum degree BE
+ For some graphs, such as bipartite graphs and high-
degree planar graphs, the number of colors is
always il
+ and for multigraphs, the number of colors may be as
large as
+ The four-color theorem states that any map in a plane
can be colored using four-colors
e All Important notes to remeber
Important notes to remember:
For a set with n element
1.total number of possible relations is 2"? .
2.The number of reflexive relations on an n-
element set is 27"? ="
3.The number of ordered pairs in the largest and
the smallest equivalence relations on S
are n42 and n.
4.Total number of symmetric relations is 27(0+0/2,
For a set with n element
1.total number of possible relations is 2"? .
2.The number of reflexive relations on an n-
element set is 27"? ="
3.The number of ordered pairs in the largest and
the smallest equivalence relations on S
are n42 and n.
4.Total number of symmetric relations is 27(0+0/2,
n(AU B) — n(A) + n(B)
If À and B are overlapping set,
masser a (4 UB) —mn(A) +n(B)
n(A) = n(AU B) + n(AN B) — n(B)
n(AN B) = n(A) + n(B) -n(AUB
n(B) = n(AU B)+n(ANB)—n(A
n(U n(A) +n(B) n(AN B)+n((A U B)
n((AUB)) = n(U) +n(A NB) — n(A) — n(B)
n(AU B) = n(A — B)+n(B — A) +n(ANB)
n(A — B) = n(AU B)— n(B)
1B)
n(A — B) = n(A) — n(A
1. n(A°) = n(U) — n(A)
n(Ar
B)
If À and B are overlapping set,
masser a (4 UB) —mn(A) +n(B)
n(A) = n(AU B) + n(AN B) — n(B)
n(AN B) = n(A) + n(B) -n(AUB
n(B) = n(AU B)+n(ANB)—n(A
n(U n(A) +n(B) n(AN B)+n((A U B)
n((AUB)) = n(U) +n(A NB) — n(A) — n(B)
n(AU B) = n(A — B)+n(B — A) +n(ANB)
n(A — B) = n(AU B)— n(B)
1B)
n(A — B) = n(A) — n(A
1. n(A°) = n(U) — n(A)
n(Ar
B)
Refle: Relation: A relation R on a set A is called reflexive if (a,a) € R holds
for every element a € A..i.c. if set A = {a,b} then R = {(a,a), (b,b)} is reflexive
relation
Symmetric Relation: A relation R on a set A is called symmetric if (b,a)
ER holds when (a,b) € R.i.e. The relation R=((4,5),(5,4),(6,5),(5,6)) on set
A=(4,5,6) is symmetric.
AntiSymmetric Relation: A relation R on a set A is called antisymmetric
if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.i.e. The
relation R = {(a,b)— Rla = b) is anti-symmetric since as bandbsa
implies a = b.
Transitive Relation: A relation R on a set A is called transitive if (a,b) € R
and (b,c) € R then (a,c) € R for all a,b,c € A.i.e. Relation
R={(1,2),(2,3),(1,3)} on set A=(1,2,3) is transitive.
for every element a € A..i.c. if set A = {a,b} then R = {(a,a), (b,b)} is reflexive
relation
Symmetric Relation: A relation R on a set A is called symmetric if (b,a)
ER holds when (a,b) € R.i.e. The relation R=((4,5),(5,4),(6,5),(5,6)) on set
A=(4,5,6) is symmetric.
AntiSymmetric Relation: A relation R on a set A is called antisymmetric
if (a,b)€ R and (b,a) € R then a = b is called antisymmetric.i.e. The
relation R = {(a,b)— Rla = b) is anti-symmetric since as bandbsa
implies a = b.
Transitive Relation: A relation R on a set A is called transitive if (a,b) € R
and (b,c) € R then (a,c) € R for all a,b,c € A.i.e. Relation
R={(1,2),(2,3),(1,3)} on set A=(1,2,3) is transitive.
A relation is equivalence if it is Reflexive, Symmetric and
Transitive
APOSET or a partial order set if it is Reflexive, Anti Symmetric
and Transitive
Transitive
APOSET or a partial order set if it is Reflexive, Anti Symmetric
and Transitive
Proposiuonak 1 Logic
Proporition in any Arche e
p Mm in a Aasalive Abatement Which can have
two valur then T on F o
ENE of Propopition
TE aso of entradiekten | |
9f » ok tue Ik ho» de be false.
e ==
=T]
se a ung ” nt fee ik hes ke be tout
Fe)
im te we
Rana th wabhing, shit Guth Abe
Exeo hing 19 I sahve
dat Mead Tae]
den ato teu LD) > Rare (A) but Ue con rob Le
de pane Kime
Lakh
No maddli portion > porte
Proporition in any Arche e
p Mm in a Aasalive Abatement Which can have
two valur then T on F o
ENE of Propopition
TE aso of entradiekten | |
9f » ok tue Ik ho» de be false.
e ==
=T]
se a ung ” nt fee ik hes ke be tout
Fe)
im te we
Rana th wabhing, shit Guth Abe
Exeo hing 19 I sahve
dat Mead Tae]
den ato teu LD) > Rare (A) but Ue con rob Le
de pane Kime
Lakh
No maddli portion > porte
* Trote Poles (univenely ) / bepicelly "Dni Minen ta
When ok combinakion “Bure / Ex pra ion give abu 1
/ 0
# Saki | Conken gency :
T/F ( Expremion que my value other than :0/ 1%
)
J
* Unsakistiabibity /Conkrecketion
AM Fabre | Expourrion ge gout 0.
When ok combinakion “Bure / Ex pra ion give abu 1
/ 0
# Saki | Conken gency :
T/F ( Expremion que my value other than :0/ 1%
)
J
* Unsakistiabibity /Conkrecketion
AM Fabre | Expourrion ge gout 0.
Re dinjunchion of
d
Dinjackve Sl gum
{wo pan
hb tome and one in fala
okhen
then
when (pv a) 1> true
and pied
ung ha ©
pe tu
we con, londtudı
Ahakı
Go 4 ls
at argus
—
how fo be tour
pra
Pa
L F
when (eva)in Mur
ond q
dun p hove ko
he tu
We com “oneluae
Hor:
So this NA
void 3 Don
Congunekive pegan
eng 0 —
Tre eongunckion
das und one i>
& be fa
mena)
LL
er
wha(pna) ls folic,
fed pus Pus
the q. han to
Le fahr.
of tuo
Joue okhan ho
pre mines m
Aena) a
|
a
Pal
when (pna) % falte
ond 4 ip
Ane g has to
he. Laine
Lou
d
Dinjackve Sl gum
{wo pan
hb tome and one in fala
okhen
then
when (pv a) 1> true
and pied
ung ha ©
pe tu
we con, londtudı
Ahakı
Go 4 ls
at argus
—
how fo be tour
pra
Pa
L F
when (eva)in Mur
ond q
dun p hove ko
he tu
We com “oneluae
Hor:
So this NA
void 3 Don
Congunekive pegan
eng 0 —
Tre eongunckion
das und one i>
& be fa
mena)
LL
er
wha(pna) ls folic,
fed pus Pus
the q. han to
Le fahr.
of tuo
Joue okhan ho
pre mines m
Aena) a
|
a
Pal
when (pna) % falte
ond 4 ip
Ane g has to
he. Laine
Lou
*
pa = Pa
¿poa etre
[lero Nok Same
[Rene] tot sane
cesa AIR [Ca] Some
pa = Pa
¿poa etre
[lero Nok Same
[Rene] tot sane
cesa AIR [Ca] Some
e All Important Formulas and tables
Numbering System
System Base | Digits
Binary 2 /0,1
Octal 8 | 0,1,2,3,4,5,6,7
Decimal 10 | 0,1,2,3,4,5,6,7,8,9
Hexadecimal} 16 | 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
System Base | Digits
Binary 2 /0,1
Octal 8 | 0,1,2,3,4,5,6,7
Decimal 10 | 0,1,2,3,4,5,6,7,8,9
Hexadecimal} 16 | 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
Decimal Binary Octal Hexadecimal
o 0000 o o
1 0001 1 1
2 0010 2 2
3 0011 3 3
4 0100 4 4
s 0101 3 5
6 0110 6 6
i 0111 7 7
8 1000 10 8
E 1001 11 E
10 1010 12 A
11 1011 13 B
12 1100 14 e
13 1101 15 D
14 1110 16 e
15 1111 17 F
o 0000 o o
1 0001 1 1
2 0010 2 2
3 0011 3 3
4 0100 4 4
s 0101 3 5
6 0110 6 6
i 0111 7 7
8 1000 10 8
E 1001 11 E
10 1010 12 A
11 1011 13 B
12 1100 14 e
13 1101 15 D
14 1110 16 e
15 1111 17 F
1 >
>
OR
AJB] Output
ojo [e]
o|ı 1
1/0 en
ET z
XOR
AB] Output
ofo o
oi 1
1 lo 1
1[i o
B| Output
2
AND
AIB] Output
ojo o
CE: [e]
110 Q
SE eq
NAND
A|B| Output
ojo E
CE: 1
1[0 a
fr] o
-[-[o[o[»>
o
Q
0 Q
Q
XNOR
A|B| Output
ojo À,
o|ı o
110 oO
fifi] 1
>
OR
AJB] Output
ojo [e]
o|ı 1
1/0 en
ET z
XOR
AB] Output
ofo o
oi 1
1 lo 1
1[i o
B| Output
2
AND
AIB] Output
ojo o
CE: [e]
110 Q
SE eq
NAND
A|B| Output
ojo E
CE: 1
1[0 a
fr] o
-[-[o[o[»>
o
Q
0 Q
Q
XNOR
A|B| Output
ojo À,
o|ı o
110 oO
fifi] 1
Law/Theorem Law of Addition Law of Multiplication
Identity Law x+0=x x<1=x
Complement Law |x + x’ = 1 x: x’ =0
Idempotent Law |x +x = x X:X=X
Dominant Law x+1=1 x: 0=0
Involution Law (UY =x
Commutative Law|x + y = y +x x"Y=y:x
Associative Law
x+(y+z) = (x+y)+z
xX-(y:z)=(x-y)-z
Distributive Law
X-(yY+Z)= x: y+x-Zz
x+y- Z = (x+y) - (x+2)
Demorgan's Law
(y) = x y’
Ley) =x + y
Absorption Law
xt Y)=x
x-(k+y¥) =x
Identity Law x+0=x x<1=x
Complement Law |x + x’ = 1 x: x’ =0
Idempotent Law |x +x = x X:X=X
Dominant Law x+1=1 x: 0=0
Involution Law (UY =x
Commutative Law|x + y = y +x x"Y=y:x
Associative Law
x+(y+z) = (x+y)+z
xX-(y:z)=(x-y)-z
Distributive Law
X-(yY+Z)= x: y+x-Zz
x+y- Z = (x+y) - (x+2)
Demorgan's Law
(y) = x y’
Ley) =x + y
Absorption Law
xt Y)=x
x-(k+y¥) =x
Logical Equivalence
L Equivalenes y —
e
e = - E
tou Tdentity Law |
d
— Dominaken Law» ]
Tiempo |
TT publ wegekon oud
D CR 1 __ |
OY Ste Gommukalive. Ae
pna= LAR
PVC Y) Asrocralive Laso o
enaynr E PA (any)
L Equivalenes y —
e
e = - E
tou Tdentity Law |
d
— Dominaken Law» ]
Tiempo |
TT publ wegekon oud
D CR 1 __ |
OY Ste Gommukalive. Ae
pna= LAR
PVC Y) Asrocralive Laso o
enaynr E PA (any)
E ent Equa
u Equisabnes En
PYlanr)® va) (ev)
en YT) =i EP MS
ee
alpn a) = 1 "M a
alpva)= ee
FT u
y
>
|
Dirige kuss
Be roger oso » Low
wwe oop Aton Ao)
Negekton ES
u Equisabnes En
PYlanr)® va) (ev)
en YT) =i EP MS
ee
alpn a) = 1 "M a
alpva)= ee
FT u
y
>
|
Dirige kuss
Be roger oso » Low
wwe oop Aton Ao)
Negekton ES
Logicol. equivalence.
invetuirg
Lödjent Fquivalenees Involvini
conditional Sheemants O erdarachonal Stolemen-
Cae le | pea =(pa)n (290) Equaalanes
Page AP 4274
f Para = (PAL VPA T4)
Pa rtp#a) SP a
a (pa) En POL
34) N Pr) =P? (e
(par) A (a> Y)=(ra)>r
(Pa d)v er Y)
(amv (49) 2 (Pnay?r
[cenaprr ele? Gr)
(era) fera) e]
Reduch
À Ne
Ar
y On pordahon, Laso
ad
dum
invetuirg
Lödjent Fquivalenees Involvini
conditional Sheemants O erdarachonal Stolemen-
Cae le | pea =(pa)n (290) Equaalanes
Page AP 4274
f Para = (PAL VPA T4)
Pa rtp#a) SP a
a (pa) En POL
34) N Pr) =P? (e
(par) A (a> Y)=(ra)>r
(Pa d)v er Y)
(amv (49) 2 (Pnay?r
[cenaprr ele? Gr)
(era) fera) e]
Reduch
À Ne
Ar
y On pordahon, Laso
ad
dum
7 I Minterms I, Maxterms
X|Y|Z| | Product Terms [| Sum Terms
0 0 m,=X-Y-Z= min(X,Y,Z M,=X+Y+Z=max(X,Y,Z)
0 1 m, =X-Y-Z=min(X,Y,Z M,=X+Y+Z=max(X,Y,Z)
D:|£| 6 m, = -Y-Z=min(X,Y,Z M,=X+Y+Z=max(X,Y,Z)
0 1 1 m,=X Y -Z=min(X.Y,Z M,=X+ Y +Z =max(X,Y,Z) |
11010 m, =X-Y-Z=min(X,Y,Z M, =X+Y+Z=max(X.Y,Z) |
ılo|ı| | m,=x-¥.z=min(x,¥,z) | | m,=X+Y+Z=max(X,y,z) |
rE | @ m, =X-Y-Z = min(X,Y,Z M,=X+Y+Z - max(X,Y,Z)
¿lila m, =X-Y-Z=min(X,Y.Z) | | M,=X+Y+Z=max(X,Y,Z)
X|Y|Z| | Product Terms [| Sum Terms
0 0 m,=X-Y-Z= min(X,Y,Z M,=X+Y+Z=max(X,Y,Z)
0 1 m, =X-Y-Z=min(X,Y,Z M,=X+Y+Z=max(X,Y,Z)
D:|£| 6 m, = -Y-Z=min(X,Y,Z M,=X+Y+Z=max(X,Y,Z)
0 1 1 m,=X Y -Z=min(X.Y,Z M,=X+ Y +Z =max(X,Y,Z) |
11010 m, =X-Y-Z=min(X,Y,Z M, =X+Y+Z=max(X.Y,Z) |
ılo|ı| | m,=x-¥.z=min(x,¥,z) | | m,=X+Y+Z=max(X,y,z) |
rE | @ m, =X-Y-Z = min(X,Y,Z M,=X+Y+Z - max(X,Y,Z)
¿lila m, =X-Y-Z=min(X,Y.Z) | | M,=X+Y+Z=max(X,Y,Z)
YZ
WX
00
01
WX
WX
WX
WX’
[00] Y'Z’ [01] YZ [11] YZ [10] YZ
0 0 1 0
0 1 3 2
1 0 1 0
4 5 7 6
1 0 0 0
12 13 15 14
0 0 0 0
8 9 11 10
WX
00
01
WX
WX
WX
WX’
[00] Y'Z’ [01] YZ [11] YZ [10] YZ
0 0 1 0
0 1 3 2
1 0 1 0
4 5 7 6
1 0 0 0
12 13 15 14
0 0 0 0
8 9 11 10
no need of this group as
we've already covered those 1's
Groups of two elements
in one group
we've already covered those 1's
Groups of two elements
in one group
1
ge ——— Groups overlapping.
Groups not overlapping.
ge ——— Groups overlapping.
Groups not overlapping.
5- variable Karnaugh map (overlay)
DE
D'E
DE DE"
5 Variable
D'E
DE DE"
5 Variable
6 variable
3-variable Truth table of F
x yz yz yz yz
m0 ml m3 m2
x |xyz | xyz xyz | x
0 1 3 2
m4 m5 m7 mó
y | xyz xyz xyz xyz’
4 5 Hd 6
3-Variable K-Map, minterm and cell position
x yz yz yz yz
m0 ml m3 m2
x |xyz | xyz xyz | x
0 1 3 2
m4 m5 m7 mó
y | xyz xyz xyz xyz’
4 5 Hd 6
3-Variable K-Map, minterm and cell position
Important notes to remember:
+ An encoder is a combinational circuit that converts binary information in the form of a
+ Adecoder does the opposite job of an encoder. It is a combinational circuit that
converts n lines of input into 2” lines of output.
* a multiplexer has an even number of 2" data input lines and a number of “control”
inputs that correspond with the number of data inputs.
+ For Demultiplexer the control lines just doing the reverse
+ An encoder is a combinational circuit that converts binary information in the form of a
+ Adecoder does the opposite job of an encoder. It is a combinational circuit that
converts n lines of input into 2” lines of output.
* a multiplexer has an even number of 2" data input lines and a number of “control”
inputs that correspond with the number of data inputs.
+ For Demultiplexer the control lines just doing the reverse
Set
Forbidden
0
1
Previous
State
Forbidden
0
1
Previous
State
Excitation table
SR Flip-flop D Flip-flop
Q® Qt+1) Ss R QU) Q(+I) DR
0 0 0 x 0 0 0
0 1 1 0 0 1 1
1 0 0 1 1 0 0
1 1 x 0 1 1 1
JK flip-flop T flip-flop
Qt) __ Qt+1) J K Qt) Q(+l) DR
0 0 0 x 0 0 0
0 1 1 x 0 1 1
1 0 x 1 1 0 1
1 1 x 0 1 1 0
SR Flip-flop D Flip-flop
Q® Qt+1) Ss R QU) Q(+I) DR
0 0 0 x 0 0 0
0 1 1 0 0 1 1
1 0 0 1 1 0 0
1 1 x 0 1 1 1
JK flip-flop T flip-flop
Qt) __ Qt+1) J K Qt) Q(+l) DR
0 0 0 x 0 0 0
0 1 1 x 0 1 1
1 0 x 1 1 0 1
1 1 x 0 1 1 0
e All Important formula charts and tables to remember
1 Byte
1024 Bytes
1024 Kilobytes
1024 Megabytes
1024 Gigabytes
| 1024 Terabytes
En |
2410
2420
2430
2440
2450
3 Bits
1 Kilobyte
1 Megabyte
1 Gigabyte
1 Terabyte
1 Petabyte
1024 Bytes
1024 Kilobytes
1024 Megabytes
1024 Gigabytes
| 1024 Terabytes
En |
2410
2420
2430
2440
2450
3 Bits
1 Kilobyte
1 Megabyte
1 Gigabyte
1 Terabyte
1 Petabyte
Important formulas to remember:
level 1 hit rate( level 1 access time)
+
(level1 miss rate)(level 2 hit rate)(level 2 access
time)
$
(level 1 miss rate)( level 2 miss rate) (main memory
access time)
level 1 hit rate( level 1 access time)
+
(level1 miss rate)(level 2 hit rate)(level 2 access
time)
$
(level 1 miss rate)( level 2 miss rate) (main memory
access time)
Important formulas to remember of OS:
(TLB_search_time + memory_access_time)* hit_ratio.
+
(TLB_search_time + 2*memory_access_time) * (1- hit_ratio)
Unify Study — United Information for you
(TLB_search_time + memory_access_time)* hit_ratio.
+
(TLB_search_time + 2*memory_access_time) * (1- hit_ratio)
Unify Study — United Information for you
Important formulas to remember:
ET, =k+n-41 cycles = (k +n - 1) Tp
pipeline
ETnon-pipeline = n * k * Tp
speedup (S) =ETnon-pipeline / ETpipeline
=> S= [n*k* Tp]/[(k + n— 1) * Tp]
S=[n*k]/[k+n- 1]
Efficiency = S / k
Throughput = n / (k + n-— 1) * Tp
ET, =k+n-41 cycles = (k +n - 1) Tp
pipeline
ETnon-pipeline = n * k * Tp
speedup (S) =ETnon-pipeline / ETpipeline
=> S= [n*k* Tp]/[(k + n— 1) * Tp]
S=[n*k]/[k+n- 1]
Efficiency = S / k
Throughput = n / (k + n-— 1) * Tp
CACHE Mapping
Techniques
Techniques
Cache Mapping
Virtual Memory Mapping
Secondary
Registers
Processor
Words
Cache
Blocks
+ > Storage
Pages
Main Memory
Virtual Memory Mapping
Secondary
Registers
Processor
Words
Cache
Blocks
+ > Storage
Pages
Main Memory
Cache Mapping Techniques-
Cache mapping is performed using following three different
techniques-
1.Direct Mapping
2.Fully Associative Mapping
3.K-way Set Associative Mapping (Set-associative Mapping)
Cache mapping is performed using following three different
techniques-
1.Direct Mapping
2.Fully Associative Mapping
3.K-way Set Associative Mapping (Set-associative Mapping)
Division of Physical Address-
In direct mapping, the physical address is divided as-
Tag Line Number Block / Line Offset
Block Number
Division of Physical Address in Direct Mapping
In direct mapping, the physical address is divided as-
Tag Line Number Block / Line Offset
Block Number
Division of Physical Address in Direct Mapping
Need of Replacement Algorithm-
In direct mapping,
«There is no need of any replacement algorithm.
«This is because a main memory block can map only to a particular line of
the cache.
Thus, the new incoming block will always replace the existing block (if
any) in that particular line.
In direct mapping,
«There is no need of any replacement algorithm.
«This is because a main memory block can map only to a particular line of
the cache.
Thus, the new incoming block will always replace the existing block (if
any) in that particular line.
Fully Associative
Mapping
For UGC NET, GATE & PHD Entrance
Mapping
For UGC NET, GATE & PHD Entrance
In fully associative mapping,
«A block of main memory can map to any line of the cache that is
freely available at that moment.
«This makes fully associative mapping more flexible than direct
mapping.
Here,
«All the lines of cache are freely available.
«Thus, any block of main memory can map to any line of the
cache.
«Had all the cache lines been occupied, then one of the existing
blocks will have to be replaced.
«A block of main memory can map to any line of the cache that is
freely available at that moment.
«This makes fully associative mapping more flexible than direct
mapping.
Here,
«All the lines of cache are freely available.
«Thus, any block of main memory can map to any line of the
cache.
«Had all the cache lines been occupied, then one of the existing
blocks will have to be replaced.
Need of Replacement Algorithm-
In fully associative mapping,
«A replacement algorithm is required.
*Replacement algorithm suggests the block to be replaced if all
the cache lines are occupied.
“Thus, replacement algorithm like FCFS Algorithm, LRU Algorithm
etc is employed.
In fully associative mapping,
«A replacement algorithm is required.
*Replacement algorithm suggests the block to be replaced if all
the cache lines are occupied.
“Thus, replacement algorithm like FCFS Algorithm, LRU Algorithm
etc is employed.
Division of Physical Address-
In fully associative mapping, the physical address is divided as-
Block Number / Tag | Block / Line Offset
Division of Physical Address in Fully Associative Mapping
In fully associative mapping, the physical address is divided as-
Block Number / Tag | Block / Line Offset
Division of Physical Address in Fully Associative Mapping
K way Set Associative
Mapping
Mapping
In k-way set associative mapping
*Cache lines are grouped into sets where each set contains k number of lines.
+A particular block of main memory can map to only one particular set of the cache.
«However, within that set, the memory block can map any cache line that is freely available.
«The set of the cache to which a particular block of the main memory can map is given by-
Cache set number
= ( Main Memory Block Address ) Modulo (Number of sets in Cache)
If k = 2 then each set contains two cache lines.
«If cache contains 6 lines, then number of sets in the cache = 6 / 2 = 3 sets.
«Cache set number = (Main memory block address) Mod 3
*Cache lines are grouped into sets where each set contains k number of lines.
+A particular block of main memory can map to only one particular set of the cache.
«However, within that set, the memory block can map any cache line that is freely available.
«The set of the cache to which a particular block of the main memory can map is given by-
Cache set number
= ( Main Memory Block Address ) Modulo (Number of sets in Cache)
If k = 2 then each set contains two cache lines.
«If cache contains 6 lines, then number of sets in the cache = 6 / 2 = 3 sets.
«Cache set number = (Main memory block address) Mod 3
Need of Replacement Algorithm-
»Set associative mapping is a combination of direct mapping and fully associative
mapping.
«lt uses fully associative mapping within each set.
Thus, set associative mapping requires a replacement algorithm.
Special Cases-
*If k = 1, then k-way set associative mapping becomes direct mapping
‘If k = Total number of lines in the cache, then k-way set associative mapping becomes fully
associative mapping.
»Set associative mapping is a combination of direct mapping and fully associative
mapping.
«lt uses fully associative mapping within each set.
Thus, set associative mapping requires a replacement algorithm.
Special Cases-
*If k = 1, then k-way set associative mapping becomes direct mapping
‘If k = Total number of lines in the cache, then k-way set associative mapping becomes fully
associative mapping.
Division of Physical Address-
In set associative mapping, the physical address is divided as-
Tag Set Number Block / Line Offset
Division of Physical Address in K-way Set Associative Mapping
In set associative mapping, the physical address is divided as-
Tag Set Number Block / Line Offset
Division of Physical Address in K-way Set Associative Mapping
Types of Cache
misses
For UGC NET, GATE & PHD Entrance
misses
For UGC NET, GATE & PHD Entrance
Types of Cache Misses
Cache Miss occurs when data is not available in the Cache
Memory. When the CPU detects a miss, it processes the miss by
fetching requested data from main memory.
Types of Cache misses :
These are various types of cache misses as follows below.
1.Compulsory Miss —
It is also known as cold start misses or first references misses.
These misses occur when the first access to a block happens.
Block must be brought into the cache.
Cache Miss occurs when data is not available in the Cache
Memory. When the CPU detects a miss, it processes the miss by
fetching requested data from main memory.
Types of Cache misses :
These are various types of cache misses as follows below.
1.Compulsory Miss —
It is also known as cold start misses or first references misses.
These misses occur when the first access to a block happens.
Block must be brought into the cache.
2.Capacity Miss —
These misses occur when the program working set is much larger than the
cache capacity. Since Cache can not contain all blocks needed for program
execution, so cache discards these blocks.
3.Conflict Miss —
It is also known as collision misses or interference misses. These misses
occur when several blocks are mapped to the same set or block frame.
These misses occur in the set associative or direct mapped block placement
strategies. In Fully Associative mapping there is no conflict miss.
Coherence Miss —
It is also known as Invalidation. These misses occur when other external
processors, i.e., I/O updates memory.
These misses occur when the program working set is much larger than the
cache capacity. Since Cache can not contain all blocks needed for program
execution, so cache discards these blocks.
3.Conflict Miss —
It is also known as collision misses or interference misses. These misses
occur when several blocks are mapped to the same set or block frame.
These misses occur in the set associative or direct mapped block placement
strategies. In Fully Associative mapping there is no conflict miss.
Coherence Miss —
It is also known as Invalidation. These misses occur when other external
processors, i.e., I/O updates memory.
Example:
Consider a physical memory of 1MB size and a direct mapped
cache of 8KB size with block size 32 bytes.
Let there be a sequence of block accesses given by
2, 216, 100, 256, 2048, 728, 256, 216
No. of blocks in cache =8KB/32B=256
Just we have to do mod 256
Consider a physical memory of 1MB size and a direct mapped
cache of 8KB size with block size 32 bytes.
Let there be a sequence of block accesses given by
2, 216, 100, 256, 2048, 728, 256, 216
No. of blocks in cache =8KB/32B=256
Just we have to do mod 256
Thus
2 2
216 | 216
100 100
256 0
2048 0
728 | 216
256 Oo
216 | 216
Now, lets classify the misses happened here:
2 2
216 | 216
100 | 100
256 0
2048 0
728 | 216
256 0
216 | 216
Compulsory Miss
Sompulsory Miss
Compulsory Miss
Sompulsory Mis
Compulsory Mis
Compulsory Miss
Conflict Miss
Conflict Miss
2 2
216 | 216
100 100
256 0
2048 0
728 | 216
256 Oo
216 | 216
Now, lets classify the misses happened here:
2 2
216 | 216
100 | 100
256 0
2048 0
728 | 216
256 0
216 | 216
Compulsory Miss
Sompulsory Miss
Compulsory Miss
Sompulsory Mis
Compulsory Mis
Compulsory Miss
Conflict Miss
Conflict Miss
Types of Addressing Modes
1.Implied / Implicit Addressing Mode
2.Stack Addressing Mode
3.Immediate Addressing Mode
4.Direct Addressing Mode
5.Indirect Addressing Mode
6.Register Direct Addressing Mode
7.Register Indirect Addressing Mode
8.Relative Addressing Mode
9.Indexed Addressing Mode
10.Base Register Addressing Mode
11.Auto-Increment Addressing Mode
12.Auto-Decrement Addressing Mode
1.Implied / Implicit Addressing Mode
2.Stack Addressing Mode
3.Immediate Addressing Mode
4.Direct Addressing Mode
5.Indirect Addressing Mode
6.Register Direct Addressing Mode
7.Register Indirect Addressing Mode
8.Relative Addressing Mode
9.Indexed Addressing Mode
10.Base Register Addressing Mode
11.Auto-Increment Addressing Mode
12.Auto-Decrement Addressing Mode
BEA ¿NFA)
Same power
but
# NPDA ond DPDA
Nok Same power
PF war com Le done doy
FA can be done hy PI
and Sa: en hub”
| vne veroa nat toa
== : |
FA peral. Language | |
ern
ee nok tue.
Same power
but
# NPDA ond DPDA
Nok Same power
PF war com Le done doy
FA can be done hy PI
and Sa: en hub”
| vne veroa nat toa
== : |
FA peral. Language | |
ern
ee nok tue.
E
Lrea
> i
[EM
Requian expression
de
Only ondeung
Fi En comparison
on
LpeeL
cra /Type2
m A
LnerL
x
y —_
FFSA]
Pera]
Infinite Caper
Stack 4
Beh
> PoP
eeu / Tyre |
Lesı
[Eer]
Tape
b One Compasinion
douk not follow
LiFo ondan
2. Mone khan one
Comparison
push pop push pop
Cluan Nok clean
single cop: Muti pte
of "ve y copy oh mel
>07
?
L=Sararen |n
oth? €
an a LAL lea
eres)
Lrea
> i
[EM
Requian expression
de
Only ondeung
Fi En comparison
on
LpeeL
cra /Type2
m A
LnerL
x
y —_
FFSA]
Pera]
Infinite Caper
Stack 4
Beh
> PoP
eeu / Tyre |
Lesı
[Eer]
Tape
b One Compasinion
douk not follow
LiFo ondan
2. Mone khan one
Comparison
push pop push pop
Cluan Nok clean
single cop: Muti pte
of "ve y copy oh mel
>07
?
L=Sararen |n
oth? €
an a LAL lea
eres)
5
a
De ei
r Ze. -
Bee]
we
Is punh 2 pop
in luar
Ara copy of
m/c
Le [nos
Fa
=
a
NCeL
u-
INPDA]
we
D purh 4 pop
Mot Chron
2) muttipte copy
of m/e
Lei ww
BAkhbLBba? Not c
Minor image.
d
Not =acepted hy
Depa
a
De ei
r Ze. -
Bee]
we
Is punh 2 pop
in luar
Ara copy of
m/c
Le [nos
Fa
=
a
NCeL
u-
INPDA]
we
D purh 4 pop
Mot Chron
2) muttipte copy
of m/e
Lei ww
BAkhbLBba? Not c
Minor image.
d
Not =acepted hy
Depa
Union Yes Yes No Yes Yes
Intersection Yes No Yes Yes
Set Difference Yes No Yes Yes
Complementation Yes Yes Yes
Intersection with RL Yes Yes Yes Yes
Concatenation Yes Yes No Yes Yes
Kleen Closure Yes Yes No Yes Yes
Kleen Plus Yes Yes No Yes Yes
Reversal Yes Yes No Yes Yes
Homomorphism Yes Yes No No No |
e-free Homomorphism Yes Yes No Yes Yes
Inverse Homomorphism Yes Yes Yes Yes
Substitution Yes Yes No
e-free Substitution Yes Yes No Yes Yes
Intersection Yes No Yes Yes
Set Difference Yes No Yes Yes
Complementation Yes Yes Yes
Intersection with RL Yes Yes Yes Yes
Concatenation Yes Yes No Yes Yes
Kleen Closure Yes Yes No Yes Yes
Kleen Plus Yes Yes No Yes Yes
Reversal Yes Yes No Yes Yes
Homomorphism Yes Yes No No No |
e-free Homomorphism Yes Yes No Yes Yes
Inverse Homomorphism Yes Yes Yes Yes
Substitution Yes Yes No
e-free Substitution Yes Yes No Yes Yes
pune Property
Joue rape)
Joue rape)
Type 2 regalos | yey cha Type Joso. | ÿre 0/ Une
+ = == | = —
(2 tal (> R
> 8/p "Tran | E perl | ás
of we | À \ 2
a pie. pall E —
ha Reif man FEW (oc e vor)
‘ ? A A
Ware &,ß © T|Tanwal)| ont variable any | Las aus | pius pa
y lw Lis Comifratid can re’ mag | > n da
and Be MO) of lac cdo ea n
2 a Vankalı ke pS /
f can be € on + ; . a
pub x cannok de € tuple £30Sa Jon | ie N
UTE " r
Trogale (A> ge )RHS | aa Bcd .
l aa o 5% r)e sage Ww] one fumo LHS ¢
= Try Ic» abel Laa length 4 R
Ú [m ps a } D > cd ey Cee.
| J :
Teese Lu Lingth of HHS [oboe
i | E opus | AO
i | Ungin et |
+ = == | = —
(2 tal (> R
> 8/p "Tran | E perl | ás
of we | À \ 2
a pie. pall E —
ha Reif man FEW (oc e vor)
‘ ? A A
Ware &,ß © T|Tanwal)| ont variable any | Las aus | pius pa
y lw Lis Comifratid can re’ mag | > n da
and Be MO) of lac cdo ea n
2 a Vankalı ke pS /
f can be € on + ; . a
pub x cannok de € tuple £30Sa Jon | ie N
UTE " r
Trogale (A> ge )RHS | aa Bcd .
l aa o 5% r)e sage Ww] one fumo LHS ¢
= Try Ic» abel Laa length 4 R
Ú [m ps a } D > cd ey Cee.
| J :
Teese Lu Lingth of HHS [oboe
i | E opus | AO
i | Ungin et |
Type-3 (Regular | Aa or A>aB Regular Finite Automata |Union, Intersection,
Grammar) where A,B € N(non Complementation,
terminal) and Concatenation, Kleene
|aeT(Terminal) Closure
Type-2 (Context |A—p where AEN |Context Free Push Down Union, Concatenation,
Free Grammar) [and p € (TUN)' Automata Kleene Closure
Type-1 (Context [uf where Context Sensitive [Linear Bound Union, Intersection,
Sensitive a, BE (TUN) and Automata Complementation,
Grammar) |len(a) <= len(B) and a Concatenation, Kleene
should contain atleast Closure
1 non terminal.
Type-0 a =p where| Recursive Turing Machine | Union, Intersection,
(Recursive a, B € (TUN)* and a|Enumerable Concatenation, Kleene
Enumerable) contains atleast 1 non- Closure
[terminal
Grammar) where A,B € N(non Complementation,
terminal) and Concatenation, Kleene
|aeT(Terminal) Closure
Type-2 (Context |A—p where AEN |Context Free Push Down Union, Concatenation,
Free Grammar) [and p € (TUN)' Automata Kleene Closure
Type-1 (Context [uf where Context Sensitive [Linear Bound Union, Intersection,
Sensitive a, BE (TUN) and Automata Complementation,
Grammar) |len(a) <= len(B) and a Concatenation, Kleene
should contain atleast Closure
1 non terminal.
Type-0 a =p where| Recursive Turing Machine | Union, Intersection,
(Recursive a, B € (TUN)* and a|Enumerable Concatenation, Kleene
Enumerable) contains atleast 1 non- Closure
[terminal
Does ‘w’ belongs to language L? (i.e, D D D D D UD
membership problem, where ‘w’ is any
string)
Is L= null? (i.e, emptiness problem) D D D UD UD UD
Is L= E” ? (i.e, completeness D D UD UD UD UD
problem.where, E” is set of all languages
possible over given alphabet)
Is L1= L2 ? (i.e, equality problem. L1 and D D UD UD UD UD
L2 are languages of same type.)
Is L1 subset of L2 ? (i.e, subset problem) D UD UD UD UD uD
Is L1 intersection of L2= null? D UD UD UD UD UD
membership problem, where ‘w’ is any
string)
Is L= null? (i.e, emptiness problem) D D D UD UD UD
Is L= E” ? (i.e, completeness D D UD UD UD UD
problem.where, E” is set of all languages
possible over given alphabet)
Is L1= L2 ? (i.e, equality problem. L1 and D D UD UD UD UD
L2 are languages of same type.)
Is L1 subset of L2 ? (i.e, subset problem) D UD UD UD UD uD
Is L1 intersection of L2= null? D UD UD UD UD UD
Is ‘U finite or not? (i.e, finiteness problem) D D D UD UD UD
Is compliment of ‘Ua language of same D D UD D D UD
type or not?
Is intersection of two languages of same D UD UD D D UD
type or not?
Is 'L regular language or not? (‘U is any D D UD UD UD UD
language.)
Is compliment of ‘Ua language of same D D UD D D UD
type or not?
Is intersection of two languages of same D UD UD D D UD
type or not?
Is 'L regular language or not? (‘U is any D D UD UD UD UD
language.)
Note:
1.Regular language: It Decidable for all problems.
2.CFL: It is decidable for emptiness problem, finiteness problem, and
membership problem.
3.CSL and REC.L: Both are decidable for membership problem, Is
compliment of 'L' a language of same type or not?, and (Is
intersection of two languages of same type or not?.
4.REC: It is decidable for (Is intersection of two languages of same
type or not?)
5.DCFL Itis decidable for everything decidable in CFL plus (Is
compliment of “L' a language of same type or not?), (Is ‘L’ regular
language?).
1.Regular language: It Decidable for all problems.
2.CFL: It is decidable for emptiness problem, finiteness problem, and
membership problem.
3.CSL and REC.L: Both are decidable for membership problem, Is
compliment of 'L' a language of same type or not?, and (Is
intersection of two languages of same type or not?.
4.REC: It is decidable for (Is intersection of two languages of same
type or not?)
5.DCFL Itis decidable for everything decidable in CFL plus (Is
compliment of “L' a language of same type or not?), (Is ‘L’ regular
language?).
Normalization
Unnormalized Form
Paine alee wings cal, Value clench eisumn beeng te same domain
box can determine ade alt, Every Col Should hve unge name
* Fully Funeinaly dependent
on cont ay Full parol he LHS Should be candidate hey, ere aheuld ot be any paral dependency
> ZIP ent CX tren RS shou be prime
{von Pmeohen Prime) SUF LS and RH both ar on prime tn o problem in 2NF
In allowed in Zur
ai Le or supe hey
Mo trame dependen
K then check prime
shouldbe alowed Sin prime tb lee
“en re on rie x * LAS and RH both nen prime i nt allowed in NF = =
Igrme>nen prime) X
not alowed
ae key must e aa
primenonprme>prime) a ame
otallored
grimeinon prime non pms)
Unnormalized Form
Paine alee wings cal, Value clench eisumn beeng te same domain
box can determine ade alt, Every Col Should hve unge name
* Fully Funeinaly dependent
on cont ay Full parol he LHS Should be candidate hey, ere aheuld ot be any paral dependency
> ZIP ent CX tren RS shou be prime
{von Pmeohen Prime) SUF LS and RH both ar on prime tn o problem in 2NF
In allowed in Zur
ai Le or supe hey
Mo trame dependen
K then check prime
shouldbe alowed Sin prime tb lee
“en re on rie x * LAS and RH both nen prime i nt allowed in NF = =
Igrme>nen prime) X
not alowed
ae key must e aa
primenonprme>prime) a ame
otallored
grimeinon prime non pms)
Kork nd Lorn Decompesikien. _.
Thine mut be a Commen alleubutes in the clecomporel able Ri ond R;
fon Aomdırs desmpantien *
we Common apte ¿hd be Ch en SK of eithası Ri o7 Ri on Bath.
den lon Ascomporition
*RUR2ZR
+ RONR FR A
à + à
+ Rond Re © Karn den if and 2 re re
OR. By Ako Pre 2 ony ont of them
Ruin La SA E)
Thine mut be a Commen alleubutes in the clecomporel able Ri ond R;
fon Aomdırs desmpantien *
we Common apte ¿hd be Ch en SK of eithası Ri o7 Ri on Bath.
den lon Ascomporition
*RUR2ZR
+ RONR FR A
à + à
+ Rond Re © Karn den if and 2 re re
OR. By Ako Pre 2 ony ont of them
Ruin La SA E)
S) R(A4B,C) with FD (A2) 1» dicompord imo Ri (A,B) and Ry (80)
Chuck ohAhen the decomposition is Ano y on hors hey
Rin Rı > Ri Raf
*
= A |
A A (@,¢) > (me) -(@,¢ | Deduct the
da PA (8 I N 2) VE y) [ Gammon element
à in
BE = A from Ist one]
le tea ED [8> A] > prue In the FT
OR not 4 = 2
uen ED to [a> 78], {som ther we cant ollenmine |B A
+
2 N nr sunt in É
Sota le Es BoE cowt be Adermine
+ [Ro A Rs a de e] fem the gwen FD:
Seq So, Non of fm
In the FD:
co 2 en E (Ge) Ea ay Or contain
EV — —
B > E Hence. Decomporition
w kay
7
Chuck ohAhen the decomposition is Ano y on hors hey
Rin Rı > Ri Raf
*
= A |
A A (@,¢) > (me) -(@,¢ | Deduct the
da PA (8 I N 2) VE y) [ Gammon element
à in
BE = A from Ist one]
le tea ED [8> A] > prue In the FT
OR not 4 = 2
uen ED to [a> 78], {som ther we cant ollenmine |B A
+
2 N nr sunt in É
Sota le Es BoE cowt be Adermine
+ [Ro A Rs a de e] fem the gwen FD:
Seq So, Non of fm
In the FD:
co 2 en E (Ge) Ea ay Or contain
EV — —
B > E Hence. Decomporition
w kay
7
_Dependaneg Pronorving clissmponiiton _
Re ducomp ten of the sation R with FD’s (FT toren
sita info Rı and Ra with 'FP'S -A 4 Fr srerpectively .
fs cmd te a Arperctenay pee ff
Guada
ROLE)
R —
1 AL
CE (EL) da
Pe Reet and Ft cover F2
= K po ond Ft equivalence
Fretnum)t © (vr)t
Re ducomp ten of the sation R with FD’s (FT toren
sita info Rı and Ra with 'FP'S -A 4 Fr srerpectively .
fs cmd te a Arperctenay pee ff
Guada
ROLE)
R —
1 AL
CE (EL) da
Pe Reet and Ft cover F2
= K po ond Ft equivalence
Fretnum)t © (vr)t
CI Any set
O Relalermkip FE E ki} Altsahukt
el ED andes bs
© Heck Roktormbip oy Key Conkretab
| ao total. pasterpatrer
I Cora to ent)
My chedluke
en;
OT N Grue Ab
C ke Pisa
HS ampere. Me. | ZO pim ento
© 7
= mulpvalud Assnte = $
re :
|
O Relalermkip FE E ki} Altsahukt
el ED andes bs
© Heck Roktormbip oy Key Conkretab
| ao total. pasterpatrer
I Cora to ent)
My chedluke
en;
OT N Grue Ab
C ke Pisa
HS ampere. Me. | ZO pim ento
© 7
= mulpvalud Assnte = $
re :
|
EE
| ant
as
Rshapalton
: | oh bah moy ne of al
coro a mnmum ne of salons i ne
an enktly con pookreipale in hich on ent Can PAPE
1 0%
rra tooo
HR
ED)
an entity À
arrocrased sith
not one entity ES
| ant
as
Rshapalton
: | oh bah moy ne of al
coro a mnmum ne of salons i ne
an enktly con pookreipale in hich on ent Can PAPE
1 0%
rra tooo
HR
ED)
an entity À
arrocrased sith
not one entity ES
DDL DMI DeL
RENAME cat
RENAME cat
The following are the most commonly used SQL aggregate
functions:
*AVG - calculates the average of a set of values.
«COUNT - counts rows in a specified table or view.
«MIN - gets the minimum value in a set of values.
«MAX - gets the maximum value in a set of values.
*SUM - calculates the sum of values.
functions:
*AVG - calculates the average of a set of values.
«COUNT - counts rows in a specified table or view.
«MIN - gets the minimum value in a set of values.
«MAX - gets the maximum value in a set of values.
*SUM - calculates the sum of values.
SQL Logical Operators:
In SQL, we use Log ors such as AND, OR, NOT, IN, BETWEEN, ALL, EXISTS,
LIKE. CH or the description of each operator
Operator Description
ALL TRUE if all of the subquery values meet the condition
AND TRUE if all the conditions separated by AND is TRUE
ANY TRUE if any of the subquery values meet the condition
BETWEEN [TRUE if the operand is within the range of comparisons
IN TRUE if the operand is equal to one of a list of expressions
NOT Displays a record if the condition(s) is NOT TRUE
OR TRUE if any of the conditions separated by OR is TRUE
EXISTS TRUE if the subquery retums one or more records
LIKE TRUE if the operand matches a pattern
In SQL, we use Log ors such as AND, OR, NOT, IN, BETWEEN, ALL, EXISTS,
LIKE. CH or the description of each operator
Operator Description
ALL TRUE if all of the subquery values meet the condition
AND TRUE if all the conditions separated by AND is TRUE
ANY TRUE if any of the subquery values meet the condition
BETWEEN [TRUE if the operand is within the range of comparisons
IN TRUE if the operand is equal to one of a list of expressions
NOT Displays a record if the condition(s) is NOT TRUE
OR TRUE if any of the conditions separated by OR is TRUE
EXISTS TRUE if the subquery retums one or more records
LIKE TRUE if the operand matches a pattern
Commands Description Syntax Format
SELECT Retrieving and display data, value or | SELECT [* | field(s)] FROM
even a database object. nameTable WHERE conditions(s)
This can be followed by a SQL
FROM clause that specifies the table
name or the source of the data
INSERT Entering new data into the database | INSERT INTO nameTable VALUES
table that has previously been (value(s));
created
UPDATE Updating data that exists in the UPDATE nameTable SET
database table. field(s)=value(s) WHERE
condition(s);
DELETE Deleting data that exists in the DELETE FROM nameTable WHERE
database table
condition(s);
SELECT Retrieving and display data, value or | SELECT [* | field(s)] FROM
even a database object. nameTable WHERE conditions(s)
This can be followed by a SQL
FROM clause that specifies the table
name or the source of the data
INSERT Entering new data into the database | INSERT INTO nameTable VALUES
table that has previously been (value(s));
created
UPDATE Updating data that exists in the UPDATE nameTable SET
database table. field(s)=value(s) WHERE
condition(s);
DELETE Deleting data that exists in the DELETE FROM nameTable WHERE
database table
condition(s);
EN
Application Application User application service
Data
SMTP
Presentation Application Formats the data sothatitcanbe Data JPG,GIF,HTTPS,SSL
viewed by user, encrypt, decrypt
Session Application Established or end connection Data NetBIOS, PPTP
between hosts
Transport Transport Transport protocol and error Segment TCP, UDP
handling
Network Network Transfer packet from host to Packets Router,
destination using IP address in Layer 3 Switches
different network
(Logical addressing)
Moving frame from one hop to hop Frames Switches
in same network
(Physical Addressing)
Pe oe | Send data on physical wire Bits Repeater, Hubs
Application Application User application service
Data
SMTP
Presentation Application Formats the data sothatitcanbe Data JPG,GIF,HTTPS,SSL
viewed by user, encrypt, decrypt
Session Application Established or end connection Data NetBIOS, PPTP
between hosts
Transport Transport Transport protocol and error Segment TCP, UDP
handling
Network Network Transfer packet from host to Packets Router,
destination using IP address in Layer 3 Switches
different network
(Logical addressing)
Moving frame from one hop to hop Frames Switches
in same network
(Physical Addressing)
Pe oe | Send data on physical wire Bits Repeater, Hubs
Physic
al
Physic
al
Data
link
Data
link
Netwo
tk
Netwo
tk
One to one
port
Broadcasting
MAC address
MAC address
IP address
IP address
Signal
bits
frames
frames
packets
message
regenerate the signal
(Attenuation)
basically a multiport
repeater
Send data to destination
using MAC address
Store data to buffer, send
after
Error checking
Send data to another
network using ip address
(connect LAN and WAN)
Entrance to different
network model or
architecture (interoperate
message)
al
Physic
al
Data
link
Data
link
Netwo
tk
Netwo
tk
One to one
port
Broadcasting
MAC address
MAC address
IP address
IP address
Signal
bits
frames
frames
packets
message
regenerate the signal
(Attenuation)
basically a multiport
repeater
Send data to destination
using MAC address
Store data to buffer, send
after
Error checking
Send data to another
network using ip address
(connect LAN and WAN)
Entrance to different
network model or
architecture (interoperate
message)
Class A
Class B
Class C
Class D
Class E
Byte 1
NET ID
Byte 2
Byte3 . Byte4
HOST IO
HOST ID
Class B
Class C
Class D
Class E
Byte 1
NET ID
Byte 2
Byte3 . Byte4
HOST IO
HOST ID
169.254.0.0 - 169.254.0.16 : Link local addresses
127.0.0.0 - 127.0.0.8 : Loop-back addresses
0.0.0.0 — 0.0.0.8 : used to communicate within the current network.
called DHCP address used when host was booted first time.
255.255.255.255 : Broadcast (Sent to all interface in network)
Private IP address space
10.0.0.0 10.255.255.255
172.16.0.0 172.31.255.255
192.168.0.0 192.168.255.255
127.0.0.0 - 127.0.0.8 : Loop-back addresses
0.0.0.0 — 0.0.0.8 : used to communicate within the current network.
called DHCP address used when host was booted first time.
255.255.255.255 : Broadcast (Sent to all interface in network)
Private IP address space
10.0.0.0 10.255.255.255
172.16.0.0 172.31.255.255
192.168.0.0 192.168.255.255
Pulbie kay Algorilam (AAymmesscc ku)
€ u : ¢
reia — RolLuman,
peration Procedure
pe q oh et
gundom prime numbers
i
two olalinal
L Choose
ea
such trab 1<€ <n
fy BL congruence. aulahen
ESA .
Ge Tae public. ky In (we) and Hu pawale key vs (mua
pig. and P end
Kup al
€ u : ¢
reia — RolLuman,
peration Procedure
pe q oh et
gundom prime numbers
i
two olalinal
L Choose
ea
such trab 1<€ <n
fy BL congruence. aulahen
ESA .
Ge Tae public. ky In (we) and Hu pawale key vs (mua
pig. and P end
Kup al
Data Structure
TREE Data Structure
Parent Node
hild Node
#
Root
Leaf Node
Tree Data Structure
A tree is a nonlinear data structure,
compared to arrays, linked lists, stacks
and queues which are linear data
structures. A tree can be empty with no
nodes or a tree is a structure consisting of
one node called the root and zero or one
or more subtrees.
Tree represents the nodes connected
by edges.
hild Node
#
Root
Leaf Node
Tree Data Structure
A tree is a nonlinear data structure,
compared to arrays, linked lists, stacks
and queues which are linear data
structures. A tree can be empty with no
nodes or a tree is a structure consisting of
one node called the root and zero or one
or more subtrees.
Tree represents the nodes connected
by edges.
What is Binary Tree Data Structure?
A binary tree is a tree-type non-
linear data structure with a
maximum of two children for each
parent. Every node in a binary
tree has a left and right reference
along with the data element. The
node at the top of the hierarchy of
a tree is called the root node. The
nodes that hold other sub-nodes
are the parent nodes.
Son ee seu
A binary tree is a tree-type non-
linear data structure with a
maximum of two children for each
parent. Every node in a binary
tree has a left and right reference
along with the data element. The
node at the top of the hierarchy of
a tree is called the root node. The
nodes that hold other sub-nodes
are the parent nodes.
Son ee seu
Terminologies associated with Binary Trees and Types of Binary Trees
«Node: It represents a termination point in a tree.
“Root: A tree's topmost node.
“Parent: Each node (apart from the root) in a tree that has at least one sub-
node of its own is called a parent node
«Child: A node that straightway came from a parent node when moving
away from the root is the child node.
*Leaf Node: These are external nodes. They are the nodes that have no
child.
“Internal Node: As the name suggests, these are inner nodes with at least
one child.
*Depth of a Tree: The number of edges from the tree’s node to the root is.
«Height of a Tree: It is the number of edges from the node to the deepest
leaf. The tree height is also considered the root height.
«Node: It represents a termination point in a tree.
“Root: A tree's topmost node.
“Parent: Each node (apart from the root) in a tree that has at least one sub-
node of its own is called a parent node
«Child: A node that straightway came from a parent node when moving
away from the root is the child node.
*Leaf Node: These are external nodes. They are the nodes that have no
child.
“Internal Node: As the name suggests, these are inner nodes with at least
one child.
*Depth of a Tree: The number of edges from the tree’s node to the root is.
«Height of a Tree: It is the number of edges from the node to the deepest
leaf. The tree height is also considered the root height.
Binary Tree Components
There are three binary tree components. Every binary tree node has these three
components associated with it. It becomes an essential concept for
programmers to understand these three binary tree components:
LEFT_DATA RIGHT
A
1.Data element
2.Pointer to left subtree
3.Pointer to right subtree
B
x yaa
Kem RR Re
There are three binary tree components. Every binary tree node has these three
components associated with it. It becomes an essential concept for
programmers to understand these three binary tree components:
LEFT_DATA RIGHT
A
1.Data element
2.Pointer to left subtree
3.Pointer to right subtree
B
x yaa
Kem RR Re
Types of Binary Trees
1. Full Binary Tree
It is a special kind of a binary tree that has
either zero children or two children. It means
that all the nodes in that binary tree should
either have two child nodes of its parent
node or the parent node is itself the leaf
node or the external node.
1. Full Binary Tree
It is a special kind of a binary tree that has
either zero children or two children. It means
that all the nodes in that binary tree should
either have two child nodes of its parent
node or the parent node is itself the leaf
node or the external node.
2. Complete Binary Tree
ISA 1% [6] Ar
A complete binary tree is another specific
type of binary tree where all the tree levels
are filled entirely with nodes, except the
lowest level of the tree. Also, in the last or
the lowest level of this binary tree, every
node should possibly reside on the left side.
ISA 1% [6] Ar
A complete binary tree is another specific
type of binary tree where all the tree levels
are filled entirely with nodes, except the
lowest level of the tree. Also, in the last or
the lowest level of this binary tree, every
node should possibly reside on the left side.
3. Perfect Binary Tree
A binary tree is said to be
‘perfect’ if all the internal nodes
have strictly two children, and
every external or leaf node is at
the same level or same depth
within a tree. A perfect binary
tree having height ‘h’ has 2%(h - 1)
+ 1 node.
A binary tree is said to be
‘perfect’ if all the internal nodes
have strictly two children, and
every external or leaf node is at
the same level or same depth
within a tree. A perfect binary
tree having height ‘h’ has 2%(h - 1)
+ 1 node.
4. Balanced Binary Tree
A binary tree is said to be ‘balanced’ if
the tree height is O(logN), where ‘N’ is the
number of nodes. In a balanced binary
tree, the height of the left and the right
subtrees of each node should vary by at
most one. An AVL Tree and a Red-Black
Tree are some common examples of data
structure that can generate a balanced
binary search tree.
A binary tree is said to be ‘balanced’ if
the tree height is O(logN), where ‘N’ is the
number of nodes. In a balanced binary
tree, the height of the left and the right
subtrees of each node should vary by at
most one. An AVL Tree and a Red-Black
Tree are some common examples of data
structure that can generate a balanced
binary search tree.
5. Degenerate Binary Tree
A binary tree is said to be a degenerate binary
tree or pathological binary tree if every
internal node has only a single child. Such
trees are similar to a linked list performance-
wise.
A binary tree is said to be a degenerate binary
tree or pathological binary tree if every
internal node has only a single child. Such
trees are similar to a linked list performance-
wise.
Tree Traversals (Inorder, Preorder and Postorder)
Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which
have only one logical way to traverse them, trees can be traversed in
different ways. Following are the generally used ways for traversing trees.
CG) Depth First Traversals:
A à" (a) Inorder (Left, Root, Right): 42 513
@) G) (b) Preorder (Root, Left, Right):12453
©) O (c) Postorder (Left, Right, Root) : 45 231
Breadth First or Level Order Traversal :1234 5
Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which
have only one logical way to traverse them, trees can be traversed in
different ways. Following are the generally used ways for traversing trees.
CG) Depth First Traversals:
A à" (a) Inorder (Left, Root, Right): 42 513
@) G) (b) Preorder (Root, Left, Right):12453
©) O (c) Postorder (Left, Right, Root) : 45 231
Breadth First or Level Order Traversal :1234 5
Binary Tree Properties
1) The maximum number of nodes at level ’ of a binary tree is 2.
Here level is the number of nodes on the path from the root to the node (including
root and node). Level of the root is 0.
This can be proved by induction.
For root, | = 0, number of nodes = 2° = 1
Assume that the maximum number of nodes on level ‘l’ is 2!
Since in Binary tree every node has at most 2 children, next level would have twice
nodes, i.e. 2 * 2!
1) The maximum number of nodes at level ’ of a binary tree is 2.
Here level is the number of nodes on the path from the root to the node (including
root and node). Level of the root is 0.
This can be proved by induction.
For root, | = 0, number of nodes = 2° = 1
Assume that the maximum number of nodes on level ‘l’ is 2!
Since in Binary tree every node has at most 2 children, next level would have twice
nodes, i.e. 2 * 2!
2) The Maximum number of nodes in a binary tree of height ‘h’ is 2*1 - 1.
Here the height of a tree is the maximum number of nodes on the root to leaf path
Height of a tree with a single node is considered as 1.
This result can be derived from point 2 above. A tree has maximum nodes if all levels
have maximum nodes. So maximum number of nodes in a binary tree of height h is 1+
2+4+.. +2". This is a simple geometric series with h terms and sum of this series is
2h- 4.
In some books, the height of the root is considered as O. In this convention, the above
formula becomes 2*1 — 1
Here the height of a tree is the maximum number of nodes on the root to leaf path
Height of a tree with a single node is considered as 1.
This result can be derived from point 2 above. A tree has maximum nodes if all levels
have maximum nodes. So maximum number of nodes in a binary tree of height h is 1+
2+4+.. +2". This is a simple geometric series with h terms and sum of this series is
2h- 4.
In some books, the height of the root is considered as O. In this convention, the above
formula becomes 2*1 — 1
3) In a Binary Tree with N nodes, minimum possible height or the minimum number of
levels is? Log,(N+1)
This can be directly derived from point 2 above. If we consider the convention where
the height of a root node is considered as 0, then above formula for minimum
possible height becomes | Log,(N+1) | - 1
4) A Binary Tree with L leaves has at least / Log,L [+ 1 levels
A Binary tree has the maximum number of leaves (and a minimum number of levels)
when all levels are fully filled. Let all leaves be at level l, then below is true for the
number of leaves L.
5) In Binary tree where every node has 0 or 2 children, the number of leaf nodes is
always one more than nodes with two children.
levels is? Log,(N+1)
This can be directly derived from point 2 above. If we consider the convention where
the height of a root node is considered as 0, then above formula for minimum
possible height becomes | Log,(N+1) | - 1
4) A Binary Tree with L leaves has at least / Log,L [+ 1 levels
A Binary tree has the maximum number of leaves (and a minimum number of levels)
when all levels are fully filled. Let all leaves be at level l, then below is true for the
number of leaves L.
5) In Binary tree where every node has 0 or 2 children, the number of leaf nodes is
always one more than nodes with two children.
Binary Search Tree
Binary Search Tree is a node-based binary tree data
structure which has the following properties:
«The left subtree of a node contains only nodes with keys
lesser than the node’s key.
«The right subtree of a node contains only nodes with keys
greater than the node’s key.
«The left and right subtree each must also be a binary
search tree.
Binary Search Tree is a node-based binary tree data
structure which has the following properties:
«The left subtree of a node contains only nodes with keys
lesser than the node’s key.
«The right subtree of a node contains only nodes with keys
greater than the node’s key.
«The left and right subtree each must also be a binary
search tree.
one
ICP fu pika
for
)-2 (q wg) in Letter
| t= © (qu) )> Goth ont
equvelint +
=
Qu
ep
ICP fu pika
for
)-2 (q wg) in Letter
| t= © (qu) )> Goth ont
equvelint +
=
Qu
ep
Maker" Mos
Sha secusaunea rdatten v m the fam of
(2) + fn) ) FUEL
ve funckior
where o and L ane Comitan “a fn ew po
ay, by 2 GO
we finest calculate d
[ge oy" 2] Now ane» 3 Cone.
mt
4 _————1 AT:
= S
le) > Of) |
eee
0G?
dhe function gin) a
Sha secusaunea rdatten v m the fam of
(2) + fn) ) FUEL
ve funckior
where o and L ane Comitan “a fn ew po
ay, by 2 GO
we finest calculate d
[ge oy" 2] Now ane» 3 Cone.
mt
4 _————1 AT:
= S
le) > Of) |
eee
0G?
dhe function gin) a
“TE Ä
The monje mathoal op plied do su Cunnences of the nm
Thy =A T("4) tn)
, bo and Lw ang pe really porte.
+ findrg cupones whan werten» ea GP
fom = AT (Ve y 4-6 In’ toy kn)
FD = boga
de À
Y kyo ? © (n° dog n)
Then In) >
| \ go 2 8 (0% dog gr)
[ib k<1 > ley on")
\
The monje mathoal op plied do su Cunnences of the nm
Thy =A T("4) tn)
, bo and Lw ang pe really porte.
+ findrg cupones whan werten» ea GP
fom = AT (Ve y 4-6 In’ toy kn)
FD = boga
de À
Y kyo ? © (n° dog n)
Then In) >
| \ go 2 8 (0% dog gr)
[ib k<1 > ley on")
\
$$$
Quick Sore
Menge Sant
Posy
DPS, BFS
Bert Cone Ave Bot | Worf Ge
[Bon Sesoch | où. IE NET
a = Be a
Sequinkak Storch | 0(1) Mon Oth) | Any
IE
Quick Sore
Menge Sant
Posy
DPS, BFS
Bert Cone Ave Bot | Worf Ge
[Bon Sesoch | où. IE NET
a = Be a
Sequinkak Storch | 0(1) Mon Oth) | Any
IE
Comparison based sorting algorithms
«In a comparison based sorting algorithms, we compare elements of an array with each other to
determines which of two elements should occur first in the final sorted list.
Time Complexity ‘Space Complexity
Sorting Algorithms. Best Case Average Case Worst Case Worst Case
Bubble Sort Q(N) @(N*2) O(N'2) 00)
Selection Sort a(n"2) en?) 0(N2) o(1)
Insertion Sort an) @(N'2) O(N‘2) o(1)
Quick Sort AN log N) O(N log N) O(N°2) O(N)
Merge Sort ON log N) O(N log N) O(N log N) O(N)
Heap Sort Q(N log N) @(N log N) O(N log N) o(1)
«In a comparison based sorting algorithms, we compare elements of an array with each other to
determines which of two elements should occur first in the final sorted list.
Time Complexity ‘Space Complexity
Sorting Algorithms. Best Case Average Case Worst Case Worst Case
Bubble Sort Q(N) @(N*2) O(N'2) 00)
Selection Sort a(n"2) en?) 0(N2) o(1)
Insertion Sort an) @(N'2) O(N‘2) o(1)
Quick Sort AN log N) O(N log N) O(N°2) O(N)
Merge Sort ON log N) O(N log N) O(N log N) O(N)
Heap Sort Q(N log N) @(N log N) O(N log N) o(1)
Space
Time Complexity Complexity
Sorting Special Input Condition
Algorithms Best Case | Average Case| Worst Case | Worst Case
Each input element is an
Counting Sort | integerin the range 0- K ON +K) O(N+K) | o(N+K) ok)
Given n digit number in
Radix Sort — | which each digit can take on
up to K possible values ag ain a an
Input is generated by the
random process that
Bucket Sort distributes elements AN +k) e(N+k) | Of“) on)
uniformly and independently
over the interval [0, 1)
Time Complexity Complexity
Sorting Special Input Condition
Algorithms Best Case | Average Case| Worst Case | Worst Case
Each input element is an
Counting Sort | integerin the range 0- K ON +K) O(N+K) | o(N+K) ok)
Given n digit number in
Radix Sort — | which each digit can take on
up to K possible values ag ain a an
Input is generated by the
random process that
Bucket Sort distributes elements AN +k) e(N+k) | Of“) on)
uniformly and independently
over the interval [0, 1)
Sorting
Algorithm
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quicksort
Counting Sort
Radix Sort
Bucket Sort
Heap Sort
Shell Sort
Time
Complexity -
Best
n
n2
n
nlog n
nlog n
n+k
n+k
n+k
nlog n
nlog n
Time
Complexity -
Worst
n2
n2
n2
nlog n
n2
n+k
n+k
n2
nlog n
n2
Time
Complexity -
Average
n2
n2
n2
nlog n
nlog n
n+k
n+k
nlog n
nlog n
Space
Complexity
log n
max
max
n+k
Algorithm
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quicksort
Counting Sort
Radix Sort
Bucket Sort
Heap Sort
Shell Sort
Time
Complexity -
Best
n
n2
n
nlog n
nlog n
n+k
n+k
n+k
nlog n
nlog n
Time
Complexity -
Worst
n2
n2
n2
nlog n
n2
n+k
n+k
n2
nlog n
n2
Time
Complexity -
Average
n2
n2
n2
nlog n
nlog n
n+k
n+k
nlog n
nlog n
Space
Complexity
log n
max
max
n+k
Sorting Algorithms
In - Place Stable
Bubble Sort Yes Yes
Selection Sort Yes No
Insertion Sort Yes Yes
Quick Sort Yes No
No
Merge Sort (because it requires an extra array to Yes
merge the sorted subarrays)
Heap Sort Yes No
In - Place Stable
Bubble Sort Yes Yes
Selection Sort Yes No
Insertion Sort Yes Yes
Quick Sort Yes No
No
Merge Sort (because it requires an extra array to Yes
merge the sorted subarrays)
Heap Sort Yes No
Time and Space Complexity of Heap data structure operations
List of Operations
«Insertion
+ Best Case: O(1)
+ Worst Case: O(logN)
+ Average Case: O(logN)
-Deletion
+ Best Case: O(1)
+ Worst Case: O(logN)
+ Average Case: O(logN)
«Searching
+ Best Case: O(1)
+ Worst Case: O(N)
+ Average Case: O(N)
Getting max value & min value
+ Sorting O(NlogN)
+ Creating a Heap O(NlogN)
+ Heapify O(N)
List of Operations
«Insertion
+ Best Case: O(1)
+ Worst Case: O(logN)
+ Average Case: O(logN)
-Deletion
+ Best Case: O(1)
+ Worst Case: O(logN)
+ Average Case: O(logN)
«Searching
+ Best Case: O(1)
+ Worst Case: O(N)
+ Average Case: O(N)
Getting max value & min value
+ Sorting O(NlogN)
+ Creating a Heap O(NlogN)
+ Heapify O(N)
Basis of comparison
Lookups
Colour
Insertion and
removal
Storage
Searching
Uses
Balance Factor
Balancing
Red Black Trees
Red Black Trees has fewer lookups
because they are not strictly balanced.
In this, the color of the node is either Red
or Black.
Red Black Trees provide faster insertion
and removal operations than AVL trees as
fewer rotations are done due to relatively
relaxed balancing.
Red Black Tree requires only 1 bit of
information per node.
It does not provide efficient searching.
Red-Black Trees are used in most of the
language libraries like map, multimap,
multiset in C++, etc.
It does not gave balance factor
Take less processing for balancing i.e.;
maximum two rotation required
AVL Trees
AVL trees provide faster lookups than Red-
Black Trees because they are more strictly
balanced.
In this, there is no color of the node.
AVL trees provide complex insertion and
removal operations as more rotations are
done due to relatively strict balancing.
AVL trees store balance factors or heights
with each node thus requiring storage for
an integer per node.
It provides efficient searching.
AVL trees are used in databases where
faster retrievals are required.
Each node has a balance factor whose
value will be 1,0,-1
Take more processing for balancing
Lookups
Colour
Insertion and
removal
Storage
Searching
Uses
Balance Factor
Balancing
Red Black Trees
Red Black Trees has fewer lookups
because they are not strictly balanced.
In this, the color of the node is either Red
or Black.
Red Black Trees provide faster insertion
and removal operations than AVL trees as
fewer rotations are done due to relatively
relaxed balancing.
Red Black Tree requires only 1 bit of
information per node.
It does not provide efficient searching.
Red-Black Trees are used in most of the
language libraries like map, multimap,
multiset in C++, etc.
It does not gave balance factor
Take less processing for balancing i.e.;
maximum two rotation required
AVL Trees
AVL trees provide faster lookups than Red-
Black Trees because they are more strictly
balanced.
In this, there is no color of the node.
AVL trees provide complex insertion and
removal operations as more rotations are
done due to relatively strict balancing.
AVL trees store balance factors or heights
with each node thus requiring storage for
an integer per node.
It provides efficient searching.
AVL trees are used in databases where
faster retrievals are required.
Each node has a balance factor whose
value will be 1,0,-1
Take more processing for balancing
Bellman Ford’s Algorithm
Dijkstra’s Algorithm
Bellman Ford’s Algorithm works when there
is negative weight edge, it also detects the
negative weight cycle.
The result contains the vertices which
contains the information about the other
vertices they are connected to.
Dijkstra's Algorithm may or maynot work
when there is negative weight edge.But will
definitely not work when there is a negative
weight cycle.
The result contains the vertices containing
whole information about the network, not only
the vertices they are connected to.
It can easily be implemented in a distributed
way.
It can not be implemented easily in a
distributed way.
It is more time consuming than Dijkstra's
algorithm. Its time complexity is O(VE).
It is less time consuming. The time
complexity is O(E logV).
Dynamic Programming approach is taken to
implement the algorithm.
Greedy approach is taken to implement the
algorithm.
Dijkstra’s Algorithm
Bellman Ford’s Algorithm works when there
is negative weight edge, it also detects the
negative weight cycle.
The result contains the vertices which
contains the information about the other
vertices they are connected to.
Dijkstra's Algorithm may or maynot work
when there is negative weight edge.But will
definitely not work when there is a negative
weight cycle.
The result contains the vertices containing
whole information about the network, not only
the vertices they are connected to.
It can easily be implemented in a distributed
way.
It can not be implemented easily in a
distributed way.
It is more time consuming than Dijkstra's
algorithm. Its time complexity is O(VE).
It is less time consuming. The time
complexity is O(E logV).
Dynamic Programming approach is taken to
implement the algorithm.
Greedy approach is taken to implement the
algorithm.
Dijkstra's Algorithm
Floyd Warshall Algorithm
Dijkstra's Algorithm is one example of a single-source
shortest or SSSP algorithm, i.e., given a source vertex it
finds shortest path from source to all other vertices.
Floyd Warshall Algorithm is an example of all-pairs
shortest path algorithm, meaning it computes the
shortest path between all pair of nodes.
Time Complexity of Dijkstra's Algorithm: O(E log V)
Time Complexity of Floyd Warshall: O(V3)
Dijkstra's algorithm don't work for negative edges.
Floyd Warshall works for negative edge but but
no negative cycle
Floyd Warshall Algorithm
Dijkstra's Algorithm is one example of a single-source
shortest or SSSP algorithm, i.e., given a source vertex it
finds shortest path from source to all other vertices.
Floyd Warshall Algorithm is an example of all-pairs
shortest path algorithm, meaning it computes the
shortest path between all pair of nodes.
Time Complexity of Dijkstra's Algorithm: O(E log V)
Time Complexity of Floyd Warshall: O(V3)
Dijkstra's algorithm don't work for negative edges.
Floyd Warshall works for negative edge but but
no negative cycle
P Problems
NP Problems
P problems are set of problems which can be
solved in polynomial time by deterministic
algorithms.
NP problems are problems which can be solved
in nondeterministic polynomial time.
P Problems can be solved and verified in
polynomial time
The solution to NP problems cannot be obtained
in polynomial time, but if the solution is given, it
can be verified in polynomial time.
P problems are a subset of NP problems
NP Problems are a superset of P problems
All P problems are deterministic in nature
All the NP problems are non-deterministic in
nature
Example: Selection sort, Linear search
Example: Travelling Salesman Problem,
Knapsack problem
NP Problems
P problems are set of problems which can be
solved in polynomial time by deterministic
algorithms.
NP problems are problems which can be solved
in nondeterministic polynomial time.
P Problems can be solved and verified in
polynomial time
The solution to NP problems cannot be obtained
in polynomial time, but if the solution is given, it
can be verified in polynomial time.
P problems are a subset of NP problems
NP Problems are a superset of P problems
All P problems are deterministic in nature
All the NP problems are non-deterministic in
nature
Example: Selection sort, Linear search
Example: Travelling Salesman Problem,
Knapsack problem
NP-hard
NP-Complete
NP-Hard problems(say X) can be solved
if and only if there is a NP-Complete
problem(say Y) that can be reducible
into X in polynomial time.
NP-Complete problems can be solved
by a non-deterministic Algorithm/Turing
Machine in polynomial time.
To solve this problem, it do not have to
be in NP.
To solve this problem, it must be both
NP and NP-hard problems.
Time is unknown in NP-Hard.
Time is known as it is fixed in NP-Hard.
NP-hard is not a decision problem.
NP-Complete is exclusively a decision
problem.
Not all NP-hard problems are NP-
complete.
All NP-complete problems are NP-hard
Do not have to be a Decision problem.
It is exclusively a Decision problem.
It is optimization problem used.
It is Decision problem used.
Example: Halting problem, Vertex cover
problem, etc.
Example: Determine whether a graph
has a Hamiltonian cycle, Determine
whether a Boolean formula is satisfiable
or not, Circuit-satisfiability problem,
etc.
NP-Complete
NP-Hard problems(say X) can be solved
if and only if there is a NP-Complete
problem(say Y) that can be reducible
into X in polynomial time.
NP-Complete problems can be solved
by a non-deterministic Algorithm/Turing
Machine in polynomial time.
To solve this problem, it do not have to
be in NP.
To solve this problem, it must be both
NP and NP-hard problems.
Time is unknown in NP-Hard.
Time is known as it is fixed in NP-Hard.
NP-hard is not a decision problem.
NP-Complete is exclusively a decision
problem.
Not all NP-hard problems are NP-
complete.
All NP-complete problems are NP-hard
Do not have to be a Decision problem.
It is exclusively a Decision problem.
It is optimization problem used.
It is Decision problem used.
Example: Halting problem, Vertex cover
problem, etc.
Example: Determine whether a graph
has a Hamiltonian cycle, Determine
whether a Boolean formula is satisfiable
or not, Circuit-satisfiability problem,
etc.
BFS
DFS
BFS stands for Breadth First Search.
DFS stands for Depth First Search.
BFS(Breadth First Search) uses Queue data
structure for finding the shortest path.
DFS(Depth First Search) uses Stack data
structure.
BFS is a traversal approach in which we first
walk through all nodes on the same level
before moving on to the next level.
DFS is also a traversal approach in which the
traverse begins at the root node and
proceeds through the nodes as far as
possible until we reach the node with no
unvisited nearby nodes.
BFS builds the tree level by level.
It works on the concept of FIFO (First In First
Out).
DFS builds the tree sub-tree by sub-tree.
It works on the concept of LIFO (Last In First
Out).
BFS is more suitable for searching vertices
closer to the given source.
DFS is more suitable when there are
solutions away from source.
BFS considers all neighbors first and
therefore not suitable for decision-making
trees used in games or puzzles.
DFS is more suitable for game or puzzle
problems. We make a decision, and the then
explore all paths through this decision. And if
this decision leads to win situation, we stop
DFS
BFS stands for Breadth First Search.
DFS stands for Depth First Search.
BFS(Breadth First Search) uses Queue data
structure for finding the shortest path.
DFS(Depth First Search) uses Stack data
structure.
BFS is a traversal approach in which we first
walk through all nodes on the same level
before moving on to the next level.
DFS is also a traversal approach in which the
traverse begins at the root node and
proceeds through the nodes as far as
possible until we reach the node with no
unvisited nearby nodes.
BFS builds the tree level by level.
It works on the concept of FIFO (First In First
Out).
DFS builds the tree sub-tree by sub-tree.
It works on the concept of LIFO (Last In First
Out).
BFS is more suitable for searching vertices
closer to the given source.
DFS is more suitable when there are
solutions away from source.
BFS considers all neighbors first and
therefore not suitable for decision-making
trees used in games or puzzles.
DFS is more suitable for game or puzzle
problems. We make a decision, and the then
explore all paths through this decision. And if
this decision leads to win situation, we stop
BFS
DFS
The Time complexity of BFS is O(V + E) when
Adjacency List is used and O(V*2) when
Adjacency Matrix is used, where V stands for
vertices and E stands for edges.
The Time complexity of DFS is also O(V + E)
when Adjacency List is used and O(V22) when
Adjacency Matrix is used, where V stands for
vertices and E stands for edges.
Here, siblings are visited before the children.
Here, children are visited before the siblings.
Nodes that are traversed several times are
deleted from the queue.
The visited nodes are added to the stack and
then removed when there are no more nodes
to visit.
In BFS there is no concept of backtracking.
DFS algorithm is a recursive algorithm that
uses the idea of backtracking
BFS is used in various applications such as
bipartite graphs, shortest paths, etc.
DFS is used in various applications such as
acyclic graphs and topological order etc.
BFS requires more memory.
DFS requires less memory.
BFS is optimal for finding the shortest path.
DFS is not optimal for finding the shortest
path.
DFS
The Time complexity of BFS is O(V + E) when
Adjacency List is used and O(V*2) when
Adjacency Matrix is used, where V stands for
vertices and E stands for edges.
The Time complexity of DFS is also O(V + E)
when Adjacency List is used and O(V22) when
Adjacency Matrix is used, where V stands for
vertices and E stands for edges.
Here, siblings are visited before the children.
Here, children are visited before the siblings.
Nodes that are traversed several times are
deleted from the queue.
The visited nodes are added to the stack and
then removed when there are no more nodes
to visit.
In BFS there is no concept of backtracking.
DFS algorithm is a recursive algorithm that
uses the idea of backtracking
BFS is used in various applications such as
bipartite graphs, shortest paths, etc.
DFS is used in various applications such as
acyclic graphs and topological order etc.
BFS requires more memory.
DFS requires less memory.
BFS is optimal for finding the shortest path.
DFS is not optimal for finding the shortest
path.
BFS
DFS
In BFS, the space complexity is more critical
as compared to time complexity.
DFS has lesser space complexity because at
a time it needs to store only a single path
from the root to the leaf node.
BFS is slow as compared to DFS.
DFS is fast as compared to BFS.
In BFS, there is no problem of trapping into
finite loops.
In DFS, we may be trapped in infinite loops.
When the target is close to the source, BFS
performs better.
When the target is far from the source, DFS
is preferable.
DFS
In BFS, the space complexity is more critical
as compared to time complexity.
DFS has lesser space complexity because at
a time it needs to store only a single path
from the root to the leaf node.
BFS is slow as compared to DFS.
DFS is fast as compared to BFS.
In BFS, there is no problem of trapping into
finite loops.
In DFS, we may be trapped in infinite loops.
When the target is close to the source, BFS
performs better.
When the target is far from the source, DFS
is preferable.
Al
Observable Yes Yes! No No
Deterministic Yes Strategic Partly No
Episodic No No No No
Static Yes Semi Semi No
Discrete Yes Yes Yes No
Single-agent Yes No Yesll No
Deterministic Yes Strategic Partly No
Episodic No No No No
Static Yes Semi Semi No
Discrete Yes Yes Yes No
Single-agent Yes No Yesll No
Environment
Chess with a clock
Chess without a clock
Poker
Backgammon
Taxi driving
Medical diagnosis system
Image-analysis system
Part-picking robot
Refinery controller
Interactive English tutor
essible
Deterministic
Episodic
Static
Discrete
Chess with a clock
Chess without a clock
Poker
Backgammon
Taxi driving
Medical diagnosis system
Image-analysis system
Part-picking robot
Refinery controller
Interactive English tutor
essible
Deterministic
Episodic
Static
Discrete
Uninformed Search
No information about the path, cost from the current
state to goal state. Don’t know any domain specific
information.
It doesn’t use knowledge for searching process.
It finds solution slow as compared to informed search.
Less Effective, Cost is high.
Problem to be solved with the given information.
No suggestion is given regarding the solution in it.
Breath First Search
Depth First search
Depth limited Search
Interactive deepening Search
nformed Search
The path cost from the current state to goal state is
calculated, to select the minimum path cost as the next
state. Knowledge about the domain.
It uses knowledge for the searching process.
It finds solution more quickly.
More Effective, Cost is low
Additional info can be added as assumption to solve the
problem.
It provides the direction regarding the solution.
Graph Search
Greedy Search
A* Search
Hill Climbing
No information about the path, cost from the current
state to goal state. Don’t know any domain specific
information.
It doesn’t use knowledge for searching process.
It finds solution slow as compared to informed search.
Less Effective, Cost is high.
Problem to be solved with the given information.
No suggestion is given regarding the solution in it.
Breath First Search
Depth First search
Depth limited Search
Interactive deepening Search
nformed Search
The path cost from the current state to goal state is
calculated, to select the minimum path cost as the next
state. Knowledge about the domain.
It uses knowledge for the searching process.
It finds solution more quickly.
More Effective, Cost is low
Additional info can be added as assumption to solve the
problem.
It provides the direction regarding the solution.
Graph Search
Greedy Search
A* Search
Hill Climbing
Comparing the Uninformed Search Algorithms:
+ Simple BES and BDS are complete and optimal but expensive with respect to space
+ and time.
+ DES requires much less memory if the maximum tree depth is limited, but has no
+ guarantee of finding any solution, let alone an optimal one. DLS offers an
+ improvement over DFS if we have some idea how deep the goal is.
+ The best overall is DFID(Depth First Iterative Deepening) which is complete, optimal and has low memory
* requirements, but still exponential time.
Strategy Complete Optimal | Time Complexity | Space Complexity
BFS Yes Yes Od) Of)
DFS No No 08”) O(bm)
DLS Ifl2d No O@)
DFIDS Yes Yes O(bd)
BDS Yes Yes 006°)
+ Simple BES and BDS are complete and optimal but expensive with respect to space
+ and time.
+ DES requires much less memory if the maximum tree depth is limited, but has no
+ guarantee of finding any solution, let alone an optimal one. DLS offers an
+ improvement over DFS if we have some idea how deep the goal is.
+ The best overall is DFID(Depth First Iterative Deepening) which is complete, optimal and has low memory
* requirements, but still exponential time.
Strategy Complete Optimal | Time Complexity | Space Complexity
BFS Yes Yes Od) Of)
DFS No No 08”) O(bm)
DLS Ifl2d No O@)
DFIDS Yes Yes O(bd)
BDS Yes Yes 006°)
Comparison of search algorithm
COMPARISON OF VARIOUS SEARCH ALGORITHMS
The performance of the algorithm is evaluated based on four parameters as follows:
1. Time complexity: Time taken by the algorithm to find a solution.
2. Space complexity: Memory required by the algorithm to perform the search.
3. Optimality: Solution provided by the algorithm will always be optimal or not.
4. Completeness: Is that calculation ensured to discover an answer when there would one say
one is? an algorithm is complete if it terminates with a solution when one exists
Algorithm BFS DFS ucs At BFS (greedy search)
Time Complexity O(b*d) O(b*m) O(b(t+C!e)) O(bd) O(bd)
Space Complexity O(b*d) O(bm) O(b(1+*C1e)) O(bd) O(bd)
Optimality Yes No Yes Yes No
Completeness Yes No Yes Yes Yes x
Admissible heuristics are a type of search algorithm that guarantees to
find the shortest path from a given starting point to a goal state, given
that a path exists. There are many benefits of using admissible heuristics
in Al.
COMPARISON OF VARIOUS SEARCH ALGORITHMS
The performance of the algorithm is evaluated based on four parameters as follows:
1. Time complexity: Time taken by the algorithm to find a solution.
2. Space complexity: Memory required by the algorithm to perform the search.
3. Optimality: Solution provided by the algorithm will always be optimal or not.
4. Completeness: Is that calculation ensured to discover an answer when there would one say
one is? an algorithm is complete if it terminates with a solution when one exists
Algorithm BFS DFS ucs At BFS (greedy search)
Time Complexity O(b*d) O(b*m) O(b(t+C!e)) O(bd) O(bd)
Space Complexity O(b*d) O(bm) O(b(1+*C1e)) O(bd) O(bd)
Optimality Yes No Yes Yes No
Completeness Yes No Yes Yes Yes x
Admissible heuristics are a type of search algorithm that guarantees to
find the shortest path from a given starting point to a goal state, given
that a path exists. There are many benefits of using admissible heuristics
in Al.
CONCLUSION
We conclude that heuristic search is more efficient and acceptable than blind search.
From the example explained above (open and closed list for UCS and A*), it is clear
that in UCS 11 nodes are required to expand to reach the goal state. While in A* only
6 nodes are required to expand to reach the goal state. Also, UCS is more time
consuming then A*. So A* is more efficient and optimal than UCS. Also when all
means costs are similar, instead of UCS, BFS is optimal because it always expands
the shallowest unexpanded node. Hence heuristic search finds an optimal solution
then blind search.
We conclude that heuristic search is more efficient and acceptable than blind search.
From the example explained above (open and closed list for UCS and A*), it is clear
that in UCS 11 nodes are required to expand to reach the goal state. While in A* only
6 nodes are required to expand to reach the goal state. Also, UCS is more time
consuming then A*. So A* is more efficient and optimal than UCS. Also when all
means costs are similar, instead of UCS, BFS is optimal because it always expands
the shallowest unexpanded node. Hence heuristic search finds an optimal solution
then blind search.
Hill Climbing Drawbacks
Local maximum
+ Local maxima
+ Plateaus
+ Diagonal ridges
Local maximum
+ Local maxima
+ Plateaus
+ Diagonal ridges
hould
jump or not ?
Knowledge Reasoning Dig
Based agent E
Properties of a Knowledge Representation system:
There are following properties of a Knowledge Representation system:
»Representational Adequacy: It is the ability of the system to represent all kinds of knowledge
needed in a specific domain.
-Inferential Adequacy: It is the ability of a knowledge representation system to manipulate the
current stored knowledge so that newly gained knowledge could be added.
«Inferential Efficiency: It is the ability of the system to directly add new knowledge in the system
with efficiency
*Acqusistional Efficiency: It is the ability of the system to automatically acquire new knowledge
from the environment. This leads the system to give more productive result as more knowledge adds
up with the current knowledge
jump or not ?
Knowledge Reasoning Dig
Based agent E
Properties of a Knowledge Representation system:
There are following properties of a Knowledge Representation system:
»Representational Adequacy: It is the ability of the system to represent all kinds of knowledge
needed in a specific domain.
-Inferential Adequacy: It is the ability of a knowledge representation system to manipulate the
current stored knowledge so that newly gained knowledge could be added.
«Inferential Efficiency: It is the ability of the system to directly add new knowledge in the system
with efficiency
*Acqusistional Efficiency: It is the ability of the system to automatically acquire new knowledge
from the environment. This leads the system to give more productive result as more knowledge adds
up with the current knowledge
Types of machine learning Algorithms
Supervised learning
Unsupervised Learning
Reinforcement
learning
Semi-supervised Learning
Reinforcement Learning
Supervised Learning is further divided into two categories:
«Classification
"Regression
Unsupervised Learning is also divided into below categories:
*Clustering
"Association Rule
*Dimensionality Reduction
Supervised learning
Unsupervised Learning
Reinforcement
learning
Semi-supervised Learning
Reinforcement Learning
Supervised Learning is further divided into two categories:
«Classification
"Regression
Unsupervised Learning is also divided into below categories:
*Clustering
"Association Rule
*Dimensionality Reduction
1. Regression
Regression algorithms are used if there
is a relationship between the input
variable and the output variable. It is
used for the prediction of continuous
variables, such as Weather forecasting,
Market Trends, etc. Below are some
popular Regression algorithms which
come under supervised learning:
Regression
1. Regression
+ Simple Linear Regression
+ Multiple Linear Regression
Supervised Learning
Classification
2. Classification
Classification algorithms are used
when the output variable is
categorical, which means there are
two classes such as Yes-No, Male-
Female, True-false, Spam Filtering, etc.
2. Classification
1
* Polynomial Regression 2
+ Support Vector Machines à
* Decision Tree Regression .
+ Random Forest Regression 6
+ Non-Linear Regression
+ Bayesian
«Linear Models
Logistic Regression
Support Vector Machines
. Non-Linear Models
K-Nearest Neighbours(KNN)
Kernel SVM
Naive Bayes
Decision Tree Classification
Random Forest Classification
Regression algorithms are used if there
is a relationship between the input
variable and the output variable. It is
used for the prediction of continuous
variables, such as Weather forecasting,
Market Trends, etc. Below are some
popular Regression algorithms which
come under supervised learning:
Regression
1. Regression
+ Simple Linear Regression
+ Multiple Linear Regression
Supervised Learning
Classification
2. Classification
Classification algorithms are used
when the output variable is
categorical, which means there are
two classes such as Yes-No, Male-
Female, True-false, Spam Filtering, etc.
2. Classification
1
* Polynomial Regression 2
+ Support Vector Machines à
* Decision Tree Regression .
+ Random Forest Regression 6
+ Non-Linear Regression
+ Bayesian
«Linear Models
Logistic Regression
Support Vector Machines
. Non-Linear Models
K-Nearest Neighbours(KNN)
Kernel SVM
Naive Bayes
Decision Tree Classification
Random Forest Classification
*Clustering: Clustering is a method of
grouping the objects into clusters
such that objects with most
similarities remains into a group and
has less or no similarities with the
objects of another group. Cluster
analysis finds the commonalities
between the data objects and
categorizes them as per the presence
and absence of those commonalities.
Unsupervised Learning
Association
*Association: An association rule is an
unsupervised learning method which is
used for finding the relationships
between variables in the large database.
It determines the set of items that occurs
together in the dataset. Association rule
makes marketing strategy more effective.
Such as people who buy X item (suppose
a bread) are also tend to purchase Y
(Butter/lam) item. A typical example of
Association rule is Market Basket Analysis.
grouping the objects into clusters
such that objects with most
similarities remains into a group and
has less or no similarities with the
objects of another group. Cluster
analysis finds the commonalities
between the data objects and
categorizes them as per the presence
and absence of those commonalities.
Unsupervised Learning
Association
*Association: An association rule is an
unsupervised learning method which is
used for finding the relationships
between variables in the large database.
It determines the set of items that occurs
together in the dataset. Association rule
makes marketing strategy more effective.
Such as people who buy X item (suppose
a bread) are also tend to purchase Y
(Butter/lam) item. A typical example of
Association rule is Market Basket Analysis.
1
achine Learning Types
Supervised Learning |
ERA
Unsupervised
Learning Learning
| I
| Semi-supervised
Reinforcement
Learning
PEE
Continuous Categorical
Target
get Variable ie
Bun
Torget variable not available Categorical Target Voriable
| | Categorie Target variable
| | Target Variable
|
ca
[
ot
Regression Clossificatior | | Classification | | Clustering
T T T T Ss
| | 1 I 1 1
x x x x y Y
Housing Price Medica! Customer Market Basket ext Lane-finding
Prediction Imaging
Segmentation Analysis Classification | | on GPS data
Control
n—
I 1
y L
Optimized Driverless Cars
Marketing.
achine Learning Types
Supervised Learning |
ERA
Unsupervised
Learning Learning
| I
| Semi-supervised
Reinforcement
Learning
PEE
Continuous Categorical
Target
get Variable ie
Bun
Torget variable not available Categorical Target Voriable
| | Categorie Target variable
| | Target Variable
|
ca
[
ot
Regression Clossificatior | | Classification | | Clustering
T T T T Ss
| | 1 I 1 1
x x x x y Y
Housing Price Medica! Customer Market Basket ext Lane-finding
Prediction Imaging
Segmentation Analysis Classification | | on GPS data
Control
n—
I 1
y L
Optimized Driverless Cars
Marketing.
Machine Learning
i
ie, Random forest
Classification Association
=e
ON + Apriori a
e Tross e FP-Growth 4) 2 Categorical
+ Logistic Regression
Hidden Markev
© Naive-Bayes na
esvm
L}
i
ie, Random forest
Classification Association
=e
ON + Apriori a
e Tross e FP-Growth 4) 2 Categorical
+ Logistic Regression
Hidden Markev
© Naive-Bayes na
esvm
L}
Supervised
Learning
Classification
ed data
Machine
Learning
Reinforcement
Unsupervised
Learning Learning
Medel training with unlabelled data
received sate updates ane feedbacks
Regression Clustering
er Ensrormen
.. Model
Learning
Classification
ed data
Machine
Learning
Reinforcement
Unsupervised
Learning Learning
Medel training with unlabelled data
received sate updates ane feedbacks
Regression Clustering
er Ensrormen
.. Model
Comparison Table
Criteria Supervised ML
Definition
Learns by using
labelled data
Type of data Labelled data
ype of problems
Supervision
Algorithms
Aim G
lication
Forecas
outcomes
Risk Evaluation,
Sales
Unsupervised ML
eans,
Apriori
Discover underlying
ns
Recommendation
S
stem, Anomaly
tection
Reinforcement ML
Wor
on interacting
with the environment
No - pret
defined data
Exploitation or
Exploration
No supe
vision
Q- Learning
SARSA
Learn a series of
elf Driving
ars,
Gaming, Healthcare
Criteria Supervised ML
Definition
Learns by using
labelled data
Type of data Labelled data
ype of problems
Supervision
Algorithms
Aim G
lication
Forecas
outcomes
Risk Evaluation,
Sales
Unsupervised ML
eans,
Apriori
Discover underlying
ns
Recommendation
S
stem, Anomaly
tection
Reinforcement ML
Wor
on interacting
with the environment
No - pret
defined data
Exploitation or
Exploration
No supe
vision
Q- Learning
SARSA
Learn a series of
elf Driving
ars,
Gaming, Healthcare
Initialize Population
Y
Fitness Evaluation —
y
eS Termination
Criterion?
Mutation
No A
Vv
Select Population > Crossover
> Output Optimal Results
Figure 2: Ba
structure of Genetic Algorithm
Y
Fitness Evaluation —
y
eS Termination
Criterion?
Mutation
No A
Vv
Select Population > Crossover
> Output Optimal Results
Figure 2: Ba
structure of Genetic Algorithm
NTA UGC NET
COMPUTER GRAPHICS
@ Priyanka Chatterjee
COMPUTER GRAPHICS
@ Priyanka Chatterjee
Tramsokien Rokakan |" song | meo fee
m. | pnbolels wine darle] 1. | =
nn [fe sx | a .
ye y4ty \v) \y ÿ'e Sy. y ak
i) Isme oe ||. 2 En “3
Joy te | tal ergo ae Ea 1 rh ail
\ \ \ 5! Si ro
gieorelythy out den | Ie NARA
| ce o | eut y os
pul |: o te) A \ CHE Lil ss pes . \ wenn
ep) BSI as
1
\ ls ot el he (Se Syd) Sendas > 13]
\ | yt] Flo 1
Jam mating hamagenau| Mer Cad = \ (susy) Sueras L LI]
equakın We add [yersme | Lo tom ahouk Akh an
one sa & Comimn ae aia” D qu po LE 0} 7% )
se [yum frayyade | PA bla
m. | pnbolels wine darle] 1. | =
nn [fe sx | a .
ye y4ty \v) \y ÿ'e Sy. y ak
i) Isme oe ||. 2 En “3
Joy te | tal ergo ae Ea 1 rh ail
\ \ \ 5! Si ro
gieorelythy out den | Ie NARA
| ce o | eut y os
pul |: o te) A \ CHE Lil ss pes . \ wenn
ep) BSI as
1
\ ls ot el he (Se Syd) Sendas > 13]
\ | yt] Flo 1
Jam mating hamagenau| Mer Cad = \ (susy) Sueras L LI]
equakın We add [yersme | Lo tom ahouk Akh an
one sa & Comimn ae aia” D qu po LE 0} 7% )
se [yum frayyade | PA bla
Line Generation Algorithm
A line connects two points. It is a basic element in graphics. To draw a line, you need two
points between which you can draw a line. In the following three algorithms, we refer the
one point of line as X0,YO and the second point of line as X1,Y1
DDA Line Drawing Algorithm
Line Drawing Algorithms Bresenham Line Drawing Algorithm
Mid point Line Drawing Algorithm
A line connects two points. It is a basic element in graphics. To draw a line, you need two
points between which you can draw a line. In the following three algorithms, we refer the
one point of line as X0,YO and the second point of line as X1,Y1
DDA Line Drawing Algorithm
Line Drawing Algorithms Bresenham Line Drawing Algorithm
Mid point Line Drawing Algorithm
Simple DDR wed of Line Decana (Digit Diffownce Arayas)
Tao inp points Blu, Y, ) and ACA
gs sb dt=Go-4S YY)
3. Spa Mm dy/dx
4 viol Pink ZF Xe and Yey
it me) _ BESSER wem
Th imi <1 kun OMe ESA
pan x£X2 | ik ingument YŸ=Y+
lt. Ingumert Le Al We Col je KeXt /m
ca aaa WE Round off vol)
We Pound ott > {var se vine a |
ve € oe
e n
ve flot pal (uy)
vr End OAL une ae
|
PES ==
Tao inp points Blu, Y, ) and ACA
gs sb dt=Go-4S YY)
3. Spa Mm dy/dx
4 viol Pink ZF Xe and Yey
it me) _ BESSER wem
Th imi <1 kun OMe ESA
pan x£X2 | ik ingument YŸ=Y+
lt. Ingumert Le Al We Col je KeXt /m
ca aaa WE Round off vol)
We Pound ott > {var se vine a |
ve € oe
e n
ve flot pal (uy)
vr End OAL une ae
|
PES ==
Inem SDA teebhed of Line Dancing
I po input points Pele Er ond Pe 92)
2)
or gtk deL)? Ay =(y.-Y)
Shope mody/dx
etm and Y=y
4. Imttak Mint
me mt
ME mie am eee (ot rg
| skp ey [at
& compute xine. AL] step and Yne = Ay (steps
E: Le A+ Ala
4- Y=yr Jime
gr Round off y valus
I po input points Pele Er ond Pe 92)
2)
or gtk deL)? Ay =(y.-Y)
Shope mody/dx
etm and Y=y
4. Imttak Mint
me mt
ME mie am eee (ot rg
| skp ey [at
& compute xine. AL] step and Yne = Ay (steps
E: Le A+ Ala
4- Y=yr Jime
gr Round off y valus
suma mbo
Brenenham method of Li a \
Brerenham method of Line Drawing) mal (HAS y my
Tao pub points A Po Lay yy miel En hz Wey)
one As Az Ne Pso tun
a) YA
Je dr = E
A ( we u-TEPLo eun Imesemod- Y= y+)
mittal Aremien parameen o hs Ps =
Pe Prada
Sige a iy pd wp=p+2dy er
rial Rick A md YaY wees Bee
ON Kid
A incum Ye y41
E P=P+2d1 - 2d
P= PH dy -2d El
q [art
e F
| oe |plekprxel Loy)
plok pixel (UY) á
End ont
End ont
Brenenham method of Li a \
Brerenham method of Line Drawing) mal (HAS y my
Tao pub points A Po Lay yy miel En hz Wey)
one As Az Ne Pso tun
a) YA
Je dr = E
A ( we u-TEPLo eun Imesemod- Y= y+)
mittal Aremien parameen o hs Ps =
Pe Prada
Sige a iy pd wp=p+2dy er
rial Rick A md YaY wees Bee
ON Kid
A incum Ye y41
E P=P+2d1 - 2d
P= PH dy -2d El
q [art
e F
| oe |plekprxel Loy)
plok pixel (UY) á
End ont
End ont
Line Clipping:
It is performed by using the line clipping algorithm. The line clipping
algorithms are:
1.Cohen Sutherland Line Clipping Algorithm
2.Midpoint Subdivision Line Clipping Algorithm
3.Liang-Barsky Line Clipping Algorithm
Other Line clipping algorithm:
Nicholl-Lee-Nicoll algorithm
Cyrus-Beck algorithm
Fast clipping algorithm
Skala algorithm
It is performed by using the line clipping algorithm. The line clipping
algorithms are:
1.Cohen Sutherland Line Clipping Algorithm
2.Midpoint Subdivision Line Clipping Algorithm
3.Liang-Barsky Line Clipping Algorithm
Other Line clipping algorithm:
Nicholl-Lee-Nicoll algorithm
Cyrus-Beck algorithm
Fast clipping algorithm
Skala algorithm
[2_min,y_max
Partially
Inside
Completely
Outside
x_min,y_min
Completely
Inside
x_maxy_min
Partially
Inside
Partially
Inside
Completely
Outside
x_min,y_min
Completely
Inside
x_maxy_min
Partially
Inside
3. Clipping Case: If the line is neither visible case nor invisible case. It is considered to be
clipped case. First of all, the category of a line is found based on nine regions given
below. All nine regions are assigned codes. Each code is of 4 bits. If both endpoints of the
line have end bits zero, then the line is considered to be visible.
region | region region
1 2 3
region region region
4 5 6
region | region region
y 8
9 region
Top, Bottom, Right, Left
1001 1000 1010
0001 0010
y max
Y min
0101 0100 0110
X min X mex
bits assigned to 9 regions
clipped case. First of all, the category of a line is found based on nine regions given
below. All nine regions are assigned codes. Each code is of 4 bits. If both endpoints of the
line have end bits zero, then the line is considered to be visible.
region | region region
1 2 3
region region region
4 5 6
region | region region
y 8
9 region
Top, Bottom, Right, Left
1001 1000 1010
0001 0010
y max
Y min
0101 0100 0110
X min X mex
bits assigned to 9 regions
Representation of Objects
It represents any given object in a different way- as
we view it on a telescope.
It represents any given object in a three-
[dimensional manner.
Shape and Size of Objects
It does not alter the shape or the size of the given
object on a plane.
In this perspective, the objects that stay
far away appear to be smaller in size,
while the ones near to the viewer's eyes
appear bigger in size.
Distance from Center of
Projection
The distance of the given object is infinite from the
center of the projection.
[The distance of the given object is finite
from the center of the projection
Accuracy of View
It can provide a user with an accurate view of the
given object.
It cannot provide a user with an accurate
view of the given object. The shapes and
sizes of the projection tend to differ from
its origination,
Lines of Projection
The parallel projection lines are parallel to each
other.
The perspective projection lines are not
parallel to each other.
Projector
The projector is also parallel
[The projector is not at all parallel.
Types of Projection
There are basically two types of parallel projections
“oblique
Orthographic
There are basically three types of
perspective projections:
"One Point
«Two Point
“Three Point
Realistic View
Parallel Projection does not form a realistic view of
the world and its objects.
Perspective Projection generates a very
realistic view of the world and the objects|
present in it.
It represents any given object in a different way- as
we view it on a telescope.
It represents any given object in a three-
[dimensional manner.
Shape and Size of Objects
It does not alter the shape or the size of the given
object on a plane.
In this perspective, the objects that stay
far away appear to be smaller in size,
while the ones near to the viewer's eyes
appear bigger in size.
Distance from Center of
Projection
The distance of the given object is infinite from the
center of the projection.
[The distance of the given object is finite
from the center of the projection
Accuracy of View
It can provide a user with an accurate view of the
given object.
It cannot provide a user with an accurate
view of the given object. The shapes and
sizes of the projection tend to differ from
its origination,
Lines of Projection
The parallel projection lines are parallel to each
other.
The perspective projection lines are not
parallel to each other.
Projector
The projector is also parallel
[The projector is not at all parallel.
Types of Projection
There are basically two types of parallel projections
“oblique
Orthographic
There are basically three types of
perspective projections:
"One Point
«Two Point
“Three Point
Realistic View
Parallel Projection does not form a realistic view of
the world and its objects.
Perspective Projection generates a very
realistic view of the world and the objects|
present in it.
Ja
>
Zee
J
ee
(a)
Parallel projection from 'arallel projection from lel projection from
top i.e. A direction top i.e. B direction top i.e. C direction
(b) (ce) (a)
>
Zee
J
ee
(a)
Parallel projection from 'arallel projection from lel projection from
top i.e. A direction top i.e. B direction top i.e. C direction
(b) (ce) (a)
Parallel Projection
Isometric Dimetric
Cavalier Cabinet
Isometric Dimetric
Cavalier Cabinet
Gouraud shading, named after Henri
Gouraud.
Gouraud first published the technique in
1971.
Computes illumination at border vertics and
interpolates.
Interpolates colors along edges and scanline.
Not So expensive.
Requires Moderate processing and time.
Lighting Equation used at each Vertex.
Gourard shading is in between the two: like
Phong shading, each polygon has one normal
vector per vertex, but instead of
interpolating the vectors, the color of each
vertex is computed and then interpolated
across the surface of the polygon.
Smooth surfaces.
Phong Shading model named after Bui
Tuong Phong.
Phong Shading published
the technique in 1973.
Illumination at every point of polygon
surface.
Interpolates normals instead of colors
More Expensive than Gouraud Shading
Required Complex processing and it is
Slower. Its Produce Good Quality.
Lighting Equation used at each pixel.
Each rendered polygon has one normal
vector per vertex; shading is performed
by interpolating the vectors across the
surface and computing the color for
each point of interest.
Smooth and shining surfaces.
Gouraud.
Gouraud first published the technique in
1971.
Computes illumination at border vertics and
interpolates.
Interpolates colors along edges and scanline.
Not So expensive.
Requires Moderate processing and time.
Lighting Equation used at each Vertex.
Gourard shading is in between the two: like
Phong shading, each polygon has one normal
vector per vertex, but instead of
interpolating the vectors, the color of each
vertex is computed and then interpolated
across the surface of the polygon.
Smooth surfaces.
Phong Shading model named after Bui
Tuong Phong.
Phong Shading published
the technique in 1973.
Illumination at every point of polygon
surface.
Interpolates normals instead of colors
More Expensive than Gouraud Shading
Required Complex processing and it is
Slower. Its Produce Good Quality.
Lighting Equation used at each pixel.
Each rendered polygon has one normal
vector per vertex; shading is performed
by interpolating the vectors across the
surface and computing the color for
each point of interest.
Smooth and shining surfaces.
Boundary fill and Flood fill Algorithm | Computer Graphics
Boundary Filled Region
Interior or Flood Filled Region
Boundary Filled Region
Interior or Flood Filled Region
Boundary fill and Flood fill Algorithm | Computer Graphics
Boundary-fill Algorithm
This is an area filling algorithm. This is used where we have to do an interactive
painting in computer graphics, where interior points are easily selected. If we have a
specified boundary in a single color, then the fill algorithm proceeds pixel by pixel until
the boundary color is encountered. This method is called the boundary-fill algorithm.
(x-1,y-1)| (x-1,y) [p1,y+1)
(x,y-1) 7— (xy) —b6y+1)
Kx#+1,y-1)| (x+1,y) [x+1,y+1
Boundary-fill Algorithm
This is an area filling algorithm. This is used where we have to do an interactive
painting in computer graphics, where interior points are easily selected. If we have a
specified boundary in a single color, then the fill algorithm proceeds pixel by pixel until
the boundary color is encountered. This method is called the boundary-fill algorithm.
(x-1,y-1)| (x-1,y) [p1,y+1)
(x,y-1) 7— (xy) —b6y+1)
Kx#+1,y-1)| (x+1,y) [x+1,y+1
Spline
A spline curve can be
B-Spline
specified by giving a specified The B-Spline curves are
set of coordinate positions,
called control points which
indicate the general shape of
the curve.
It follows the general shape
of the curve
Typical CAD application for
spline include the design of
automobile bodies, aircraft
and spacecraft surfaces and
ship hulls.
specified by Bernstein basis
function that has limited
flexibiity.
These curves are a result of
the use of open uniform basis
function.
These curves can be used to
construct blending curves.
Bezier
The Bezier curves can be
specified with boundary
conditions, with a
characterizing matrix or with
blending function.
The curve generally follows
the shape of a defining
polygon.
These are found in painting
and drawing packages as
well as in CAD applications.
A spline curve can be
B-Spline
specified by giving a specified The B-Spline curves are
set of coordinate positions,
called control points which
indicate the general shape of
the curve.
It follows the general shape
of the curve
Typical CAD application for
spline include the design of
automobile bodies, aircraft
and spacecraft surfaces and
ship hulls.
specified by Bernstein basis
function that has limited
flexibiity.
These curves are a result of
the use of open uniform basis
function.
These curves can be used to
construct blending curves.
Bezier
The Bezier curves can be
specified with boundary
conditions, with a
characterizing matrix or with
blending function.
The curve generally follows
the shape of a defining
polygon.
These are found in painting
and drawing packages as
well as in CAD applications.
Spline
It possess a high degree of
smoothness at the places
where the polynomial
pieces connect.
Aspline curve is a
mathematical
representation for which it
is easy to build
an interface that will allow a
user to design and control
the shape of complex
curves and surfaces.
B-Spline
The B-Spline allows the
order of the basis function
and hence the degree of
the resulting curve is
independent of number of
vertices.
In B-Spline, there is local
control over the curve
surface and the shape of
the curve is affected by
every vertex.
Bezier
The degree of the
polynomial defining the
curve segment is one less
than the number of defining
polygon point.
It is a parametric curve
used in related fields.
It possess a high degree of
smoothness at the places
where the polynomial
pieces connect.
Aspline curve is a
mathematical
representation for which it
is easy to build
an interface that will allow a
user to design and control
the shape of complex
curves and surfaces.
B-Spline
The B-Spline allows the
order of the basis function
and hence the degree of
the resulting curve is
independent of number of
vertices.
In B-Spline, there is local
control over the curve
surface and the shape of
the curve is affected by
every vertex.
Bezier
The degree of the
polynomial defining the
curve segment is one less
than the number of defining
polygon point.
It is a parametric curve
used in related fields.
Bezier Curve-
bt
Bezier Curve is parametric curve »
defined by a set of control points. con Payson, #
*Two points are ends of the curve. FT coor Core
«Other points determine the shape of
the curve. :
bo A es
The concept of bezier curves was
given by Pierre Bezier. u
b2
Bezier Curve Example
Here,
«This bezier curve is defined by a set of control points bo, b,, b, and bs.
*Points by and b, are ends of the curve.
*Points b, and b, determine the shape of the curve.
bt
Bezier Curve is parametric curve »
defined by a set of control points. con Payson, #
*Two points are ends of the curve. FT coor Core
«Other points determine the shape of
the curve. :
bo A es
The concept of bezier curves was
given by Pierre Bezier. u
b2
Bezier Curve Example
Here,
«This bezier curve is defined by a set of control points bo, b,, b, and bs.
*Points by and b, are ends of the curve.
*Points b, and b, determine the shape of the curve.
Tags
Categories
TechnologyDownload
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 11
- Slides 158
- Age 478 days
Related Slideshows
11
8-top-ai-courses-for-customer-support-representatives-in-2025.pptx
JeroenErne2
60 views
10
7-essential-ai-courses-for-call-center-supervisors-in-2025.pptx
JeroenErne2
56 views
13
25-essential-ai-courses-for-user-support-specialists-in-2025.pptx
JeroenErne2
44 views
11
8-essential-ai-courses-for-insurance-customer-service-representatives-in-2025.pptx
JeroenErne2
44 views
21
Know for Certain
DaveSinNM
26 views
17
PPT OPD LES 3ertt4t4tqqqe23e3e3rq2qq232.pptx
novasedanayoga46
30 views