COMPUTER SCIENCE

AND APPLICATIONS

National Testing Agency (NTA)

PAPER 2 || VOLUME – 1
 UGC NET PAPER – 2
COMPUTER SCIENCE AND APPLICATIONS
Chapter Pg. No.

UNIT - I : Discrete Structures and Optimization

1. Mathematical Logic 1
2. Sets and Relations 5
3. Counting, Mathematical Induction and Discrete Probability 7
4. Group Theory 14
5. Graph Theory 15
6. Boolean Algebra 21
7. Optimization 27
8. Previous Year Questions 31

UNIT - II : Computer System Architecture

1. Digital Logic Circuits and Components 42
2. Data Representation 54
3. Register Transfer and Microoperations 58
4. Basic Computer Organization & Design 60
5. Programming the Basic Computer 61
6. Microprogrammed Control 62
7. Central Processing Unit 64
8. Pipeline and Vector Processing 65
9. Input-Output Organization 68
10. Memory Hierarchy 69
11. Mulitprocessors 71
12. Previous Year Questions 76

UNIT - III : Programming Languages and Computer Graphics

1. Language Design and Translation Issues 87
2. Elementary Data Types 89
3. Programming in C 90
4. Object Oriented Programming 105
5. Programming in C++ 107
6. Web Programming 110
7. Computer Graphics 114
8. 2-D Geometrical Transforms and Viewing 116
9. 3-D Object Representation, Geometrical Transforms and Viewing 118
10. Previous Year Questions 119
 UNIT - IV : Database Management System
1. Database System Concepts and Architecture 130
2. Data Modeling 135
3. SQL (Structured Query Language) 138
4. Normalization for Relational Database 151
5. Enhanced Data Models 154
6. Data Warehousing and Data Mining 155
7. Big Data Systems 159
8. NoSQL 161
9. Previous Year Questions 163

UNIT - V : System Software and Operating System

1. System Software 180
2. Basics of Operating System 182
3. Process Management 185
4. Threads 187
5. CPU Scheduling 188
6. Deadlock 191
7. Memory Management 194
8. Storage management 196
9. File and Input/ Output System 198
10. Security 201
11. Virtual Machines 206
12. Linux Operating System 207
13. Windows Operating System 208
14. Distributed Systems 210
15. Previous Year Questions 213
 I
Discrete Structures and Optimization
UNIT
Mathematical Logic
Logic which uses a symbolic language to express its principles in precise and unambiguous terms is
known as mathematical logic.
One reason for this is that all efforts at the verification of algorithms inevitably the notation and
methods of logic. Logic, among other things, have provided the theoretical basis for many areas of
computer science such as digital logic design, automata theory and computability, and artificial
intelligence etc.

Propositions:-
A number of words making a complete grammatical structure having a sense and meaning and also
meant an assertion in logic or mathematics is called a sentence.
This assertion may be of two types- declarative and non-declarative.
A proposition is a declarative sentence that is either true or false but not both. A proposition may have
truth value T or F, T stands for the case when the proposition is true and F stands for the case when the
proposition is false.
Propositional logic is the simplest form of logic where all the statements are made by propositions.
The purpose of using propositional logic is to analyze a statement, individually or compositely.
Propositional logic is also called boolean logic as it works on 0 and 1.
For example, “two plus one equals three” and “Three plus three equals seven” are both statements,
the first because it is true and the second because it is false. Similarly “x+y > 1” is not a statement
because for some values of x and y the sentence is true, whereas for others it is false.
For instance, if x = 1 and y = 2, the sentence is true, if x = −3 and y = 1, this is false.
The truth or falsity of a statement is called its truth value. Since only two possible truth values are
admitted this logic is sometimes called two-valued logic.
Questions, exclamations and commands are not propositions.
It is customary to represent simple statements by letters p,q,r,··· known as proposition variables.
Propositional variables can only assume two values, true or false.
In Propositional logic , we use symbolic variables to represent the logic, and we can use any symbol for
a representing a proposition, such as A, B, C, D, P, Q, R etc.
Propositional logic consists of an object, relations or function and logical connectives.

Compound Proposition:-
A proposition consisting of only a single propositional variable or a single propositional constant is
called an atomic (primary, primitive) proposition or simply proposition; that is, they can not be further
subdivided.

ToppersNotes / 98282-86-909 1
In other word, a proposition is called a simple proposition if it cannot be reduced into another simpler
proposition.
A proposition obtained from the combinations of two or more propositions by means of logical
operators or connectives of two or more propositions or by negating a single proposition is referred to
molecular or composite or compound proposition.

Connectives
The words or phrases (or symbols) used to form compound propositions are called connectives. These
connectives are also called logical operators.
There are five basic connectives called
• Negation
• Conjunction
• Disjunction
• Implication or Conditional, and
• Equivalence or Biconditional
Symbol Connective Nature of the compound Symbolic Negation
used word statement formed by the form
connective
∼,¬,N not Negation ∼p ∼(∼p)=p
∧ and Conjunction p∧q (∼p)∨(∼q)
∨ or Disjunction p∨q (∼p)∧(∼q)
⇒,→ if, ··· then Implication(or) Conditional p⇒q p∧(∼q)
⇔,<−> if and only if Equivalence(or) Bi-conditional p⇔q p∧(∼q)]∨[q∧(∼p)]

Proposition and Truth Tables

For Conjunction
Conjunction of propositions p and q is denoted by p ∧ q.
p ∧ q is read as "p and q".
The proposition p ∧ q is true whenever both p and q are true, otherwise p ∧ q is false.
p q p∧q
T T T
T F F
F T F
F F F

For Disjunction
Disjunction of propositions p and q is denoted by p ∨ q.
p ∨ q is read as " p or q".
The statement p ∨ q is true whenever either p or q is true or both p and q are true; otherwise, p ∨ q is
false.
p q p∨q
T T T

ToppersNotes / 98282-86-909 2
 T F T
F T T
F F F

For Negation
Negation of a proposition p is denoted by ~p is read as "not p ".
p ∼p
T F
F T

For Implication / Conditional Proposition

If p and q are proposition, the compound proposition “if p then q” denoted by p ⇒ q is called a
conditional proposition or implication and the connective is the conditional connective. The proposition
p is called antecedent or hypothesis, and the proposition q is called the consequent or conclusion.
p q p→q
T T T
T F F
F T T
F F F

For Biconditional Statement

If p and q are statements, then the compound statement p if and only if q, denoted by p ⇔ q is called a
biconditional statement and the connective if and only if is the biconditional connective. The
biconditional statement p ⇔ q can also be stated as “p is a necessary and sufficient condition for q” or
as “p implies q and q implies p”.
p q p⇔q
T T T
T F F
F T F
F F F

Negation of Compound Statements:-

Negation of Conjunction: A conjunction p ∧ q consists of two sub-statements p and q both of which
exist simultaneously. Therefore, the negation of the conjunction would mean the negation of at least
one of the two sub-statements.
Thus, we have “the negation of a conjunction p ∧ q is the disjunction of the negation of p and the
negation of q”. Equivalently, we write
∼(p∧q) ≡∼p∨∼q.
In order to prove the above equivalence, we prepare the following table.
Negation of Disjunction: A disjunction p ∧ q consists of two sub-statements p and q which are such
that either p or q or both exist.
Therefore, the negation of the disjunction would mean the negation of both p and q simultaneously.

ToppersNotes / 98282-86-909 3
p q p∧q ∼(p∧q) ∼p ∼q ∼p∨∼q
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T

The negation of a disjunction p∧q is the conjunction of the negation of p and the negation of q.
Equivalently, we write
∼(p∨q)≡∼p∧∼q
In order to prove the above equivalence, we prepare the following table.
p q ∼p ∼q ∼p∧∼q p∧q ∼(p∧q)
T T F F F T F
T F F T F T F
F T T F F T F
F F T T T F T

Negation of Implication: If p and q are two statements, then

∼(p⇒q)≡p∧∼q
In order to prove the above equivalence, we prepare the following table.
p q p⇒q ∼(p⇒q) ∼q p∧∼q
T T T F F F
T F F T T T
F T T F F F
F F T F T F

Negation of Biconditional: If p and q are two statements, then

∼(p⇔q) ≡ p⇔∼q ≡ ∼p⇔q
Law of algebra of propostions :-
The laws are listed in the following table
Law Expression(s)
Idempotent Laws 𝑝 ∨ 𝑝 = 𝑝, 𝑝 ∧ 𝑝 = 𝑝
Associative Laws (i) 𝑝 ∨ (𝑞 ∨ 𝑟) = (𝑝 ∨ 𝑞) ∨ 𝑟
(ii) 𝑝 ∧ (𝑞 ∧ 𝑟) = (𝑝 ∧ 𝑞) ∧ 𝑟
Distributive Laws (i) 𝑝 ∨ (𝑞 ∧ 𝑟) = (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)
(ii) 𝑝 ∧ (𝑞 ∨ 𝑟) = (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)
Commutative Laws (i) 𝑝 ∨ 𝑞 = 𝑞 ∨ 𝑝
(ii) 𝑝 ∧ 𝑞 = 𝑞 ∧ 𝑝
Involution Law ∼ (∼ 𝑝) = 𝑝
Identity Laws (i) 𝑝 ∨ F = 𝑝, 𝑝 ∧ T = 𝑝
(ii) 𝑝 ∨ T = T, 𝑝 ∧ F = F
Complement Laws (i) 𝑝 ∨∼ 𝑝 = T, 𝑝 ∧∼ 𝑝 = F
(ii) ∼ T = F, ∼ F = T
De Morgan's Laws (i) ∼ (𝑝 ∨ 𝑞) =∼ 𝑝 ∧∼ 𝑞
(ii) ∼ (𝑝 ∧ 𝑞) =∼ 𝑝 ∨∼ 𝑞

ToppersNotes / 98282-86-909 4
For example,
𝑝 ∨ (𝑝 ∧ 𝑞) = 𝑝
and
𝑝 ∧ (𝑝 ∨ 𝑞) = 𝑝
hold good and are called absorption laws.
These can be derived in the following manner.
Let us consider:
𝑝 ∨ (𝑝 ∧ 𝑞) = (𝑝 ∧ 𝑇) ∨ (𝑝 ∧ 𝑞) [∵ 𝑝 ∧ 𝑇 = 𝑝]
= 𝑝 ∧ (𝑇 ∨ 𝑞) [ Distributive law ]
=𝑝∧𝑇 [∵ 𝑇 ∨ 𝑞 = 𝑇]
=𝑝

De'Morgan Laws:-
(i) ∼ (𝑝 ∧ 𝑞) =∼ 𝑝 ∨∼ 𝑞
(ii) ∼ (𝑝 ∨ 𝑞) =∼ 𝑝 ∧∼ 𝑞
𝑝 𝑞 𝑝∧𝑞 ∼ (𝑝 ∧ 𝑞) ∼𝑝 ∼𝑞 ∼ 𝑝 ∨∼ 𝑞
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T

From the table we see that

−(𝑝 ∧ 𝑞) ≡∼ 𝑝 ∨∼ 𝑞
Similarly, you can verify that
∼ (𝑝 ∨ 𝑞) ≡∼ 𝑝 ∧∼ 𝑞

Sets and Relations

Set operations :-
Set operations include set union, set intersection, set difference, complement of set and cartesian
product.
Union of sets :-
The union of sets A and B ( denoted by A ∪ B) is the set of elements that are in A, in B, or in both A and B.

Intersection of sets:-
The intersection of sets A and B ( denoted by A ∩ B ) is the set of elements which are in both A and B.

ToppersNotes / 98282-86-909 5
 if A and B have no common element, then A ∩ B = ∅.
In this case, the two sets A and B are called disjoint sets.

𝐀∩𝐁 =𝝓
it is obvious that 𝐴 ∩ 𝐵 ⊂ 𝐴, 𝐴 ∩ 𝐵 ⊂ 𝐵.

Difference of sets:-
The set difference of sets A and B (denoted by A -B) is the set of elements that one only in A but not in
B.

Complement of a set :- If U be the universal set of a set A, then the set of all those elements in U which
are not members of A is called the Compliment of A, denoted by AC or A'

clearly,
A' = U - A
Cartesian product / Cross Product :-
if we take two sets A = {a,b} and B= {1, 2}
 the cartesian product of A and B is written as
A *B = {(a,1),(a,2),(b,1),(b,2)}
 the cartesion product of B and A is written as
B * A = {(1,a),(1,b), (2,a),(2,b)}

Laws of the Algebra of sets:-

these laws can be directly used to prove different propositions on set theory.
1. Idempotent laws: 𝑨 ∪ 𝑨 = 𝑨, 𝑨 ∩ 𝑨 = 𝑨
2. Commutative laws: 𝑨 ∪ 𝑩 = 𝑩 ∪ 𝑨, 𝑨 ∩ 𝑩 = 𝑩 ∩ 𝑨
3. Associative laws: 𝑨 ∪ (𝑩 ∪ 𝑪) = (𝑨 ∪ 𝑩) ∪ 𝑪, 𝑨 ∩ (𝑩 ∩ 𝑪) = (𝑨 ∩ 𝑩) ∩ 𝑪
4. Distributive laws : 𝑨 ∪ (𝑩 ∩ 𝑪) = (𝑨 ⊨ 𝑩) ∩ (𝑨 ∩ 𝑪), 𝑨 ∩ (𝑩 ∪ 𝑪) = (𝑨 ∩ 𝑩) ∪ (𝑨 ∩ 𝑪)
5. Identity laws: 𝑨 ∪ 𝝓 = 𝑨, 𝑨 ∪ 𝑼 = 𝑼
6. 𝑨 ∩ 𝑼 = 𝑨, 𝑨 ∩ 𝝓 = 𝝓

ToppersNotes / 98282-86-909 6
7. Complement laws: 𝑨 ∪ 𝑨′ = 𝑼, 𝑨 ∩ 𝑨′ = 𝝓
8. (𝑨′ )′ = 𝑨, 𝑼′ = 𝝓, 𝝓′ = 𝑼
9. De Morgan's laws : (𝑨 ∪ 𝑩)′ = 𝑨′ ∩ 𝑩′
10. (𝑨 ∩ 𝑩)′ = 𝑨′ ∪ 𝑩′.

Counting, Mathematical Induction and Discrete Probability

Fundamental Principle of Counting:-
The fundamental counting principle can be used to determine the
number of possible outcomes for compound events.
It has two basic rules:
1. Sum rule:- If an event can occur in m different ways and another event can occur in n different ways
and if these two events can not be done at the same time i.e they are independent, then either of
the two events can occur in (m + n) ways. The Sum rule of counting can also be generalised to any
number of finite events.
Let A1, A2, ... ... ..., An be disjoint sets, then the number of ways to choose any element from one of
these sets is
|A1 ∪ A2∪ ... ... ... ∪An | = |A1| + |A2| + ... ... ... + |An|
2. Product rule:- If an event can occur in m different ways and if following it, another event can occur
in n different ways, then in the given order, both the events can occur in the given order, both the
events can occur in the m × n, i.e. mn ways.
This principle can be generalised to any finite number of events.
Let A1, A2, ... ... ..., An be finite sets, then the number of ways to choose one element from set in the
order A1, A2, ... ... ... An is,
|A1 × A2 × ... ... ... × An| = |A1| × |A2| × ... ... ... × |An|
where, |Ai| (i = 1, 2, ... ... ... n) denotes the number of elements in the set Ai.

The pigeonhole principle:-

If there are n+1 objects and n boxes, then there is at least one box with two or more objects.
Assume that we have n+1 objects and every boxes has at most one object.
Then the total number of objects is n, which is a contradiction because there are n+1 objects. Hence if
n+1 objects are placed into n boxes, then there is at least one box containing two or more objects.
The generalised pigeonhole principle states that ‘‘If N objects are placed into K boxes, then there is at
least one box containing at least [N / K] objects.’’
Example:-
there are 10 Pigeons and 9 pigeon holes when pigeons fly to home then one of them have to stay two
in one hole.
Permutations :-
The different arrangements that can be made with a given number of things taking some or all of them
of a time are called permutation.
A permutation is an ordered combination.

ToppersNotes / 98282-86-909 7
For example, the permutation of the letters a, b, c taken two at a time are ab, ba, ac, ca, bc, cb.
The symbol nPr or P (n, r) is used to denote the number of
permutations of n distinct things taken r at a time.

Permutation of n-distinct objects:

Theorem: The number of different permutations of n- distinct objects taken r at a time is given by
n
pr = n (n–1) (n–2) ... ... ... [n–(r–2)]
n 𝑛!
pr = (𝑛−𝑟)! [ r <=n]

Note:
1) n! = n(n - 1)!
= n(n - 1)(n - 2)!
= n(n - 1)(n - 2)(n - 3)! etc.
2) In this case, repetition is not allowed.
So, we can fill:
• the first place in n ways,
• the second place in (n - 1) ways,
• the third place in (n - 2) ways,
• and so on,
• until the rth place, which can be filled in [n - (r - 1)] ways.
Thus, the total number of ways to fill r places is:
n × (n - 1) × (n - 2) × ... × [n - (r - 1)] = nPr
3) If repetition is allowed, then each of the r-places can be filled in n ways.
So, we can fill:
Hence, all the r places can be filled in:
n × n × n × ... × n = nʳ ways (r times)
4) The number of permutations of n things taken all at a time is n!
By definition, ⁿPₙ = n(n – 1)(n – 2)...2.1 = n!
𝑛!
5) We have, npr = (𝑛−𝑟)!
𝑛!
Put r = n, npr = (𝑛−𝑛)!
𝑛!
= 0!
𝑛!
or, n! = 0!
𝑛!
∴ 0! = 𝑛!
=1
Thus, 0! = 1
Example 1: Prove the Following Relations
i) ⁿPₙ = n × ⁿ⁻¹Pₙ₋₁
ii) (n + 1) × ⁿPᵣ = (n - r + 1) × ⁿ⁺¹Pᵣ
iii) ⁿPᵣ = ⁿ⁻¹Pᵣ + r × ⁿ⁻¹Pᵣ₋₁
iv) 1 × ¹P₁ + 2 × ²P₂ + 3 × ³P₃ + ... + n × ⁿPₙ = ⁿ⁺¹Pₙ₊₁

ToppersNotes / 98282-86-909 8
Solution: Permutation Identities
i) By definition:
𝑛! 𝑛!
ⁿPₙ = (𝑛−𝑛)! = 0!
= n! [∵ 0! = 1]

Again,
𝑛(𝑛−1) !
n × ⁿ⁻¹Pₙ₋₁ = [(𝑛−1)−(𝑛−1)]!
𝑛(𝑛−1) !
= 0!

= n × (n - 1)! = n!
Hence, ⁿPₙ = n × ⁿ⁻¹Pₙ₋₁
ii) We have:
(𝑛+1)𝑛! !
(n + 1) × ⁿPᵣ = (𝑛−𝑟)!
(𝑛+1)!
= (𝑛−𝑟)!

Again,
(𝑛−𝑟+1)(𝑛+1) !
(n - r + 1) × ⁿ⁺¹Pᵣ =
[(𝑛+1)−𝑟]!
(𝑛+1) !
= (𝑛−𝑟)!

Hence, (n + 1) × ⁿPᵣ = (n - r + 1) × ⁿ⁺¹Pᵣ

Solution :
i) By definition
𝑛
𝑛! 𝑛!
𝑝𝑛 = = = 𝑛! ∵ 0! = 1]
(𝑛 − 𝑛)! 0!
(𝑛 − 1)!
Again 𝑛 ⋅ 𝑛−1 𝑝𝑛−1 = 𝑛
[(𝑛 − 1) − (𝑛 − 1)]
(𝑛 − 1)!
=𝑛
0!
= 𝑛(𝑛 − 1)! = 𝑛!
Hence, 𝑛 𝑝𝑛 = 𝑛. 𝑛−1
𝑝𝑛−1
ii) We have
𝑛! (𝑛 + 1)!
(n + 1)n pr = (n + 1) =
(𝑛 − 𝑟)! (𝑛 − 𝑟)!
(𝑛 + 1)!
Again (n − r + 1)n+1 pr = (n − r + 1) =
[(𝑛 + 1) − 𝑟]!
(𝑛 + 1)!
= (n − r + 1)
[(𝑛 + 1) − 𝑟]!
(n + 1)!
=
(n − r)!
Hence, (𝑛 + 1)𝑛 𝑝𝑟 = (𝑛 − 𝑟 + 1)𝑛+1 𝑝𝑟

ToppersNotes / 98282-86-909 9
iii) We have,
𝑛−1
(𝑛 − 1)! (𝑛 − 1)!
p𝑟 + 𝑟 𝑛−1 p𝑟−1 = +𝑟
(𝑛 − 1 − 𝑟)! [(𝑛 − 1) − (𝑟 − 1)]!
(𝑛 − 1)! (𝑛 − 1)!
= +𝑟
(𝑛 − 1 − 𝑟)! (𝑛 − 𝑟)!
1 𝑟
= (𝑛 − 1)! [ + ]
(𝑛 − 𝑟 − 1)! (𝑛 − 𝑟)!
(𝑛 − 𝑟) 𝑟
= (𝑛 − 1)! [ + ]
(𝑛 − 𝑟)(𝑛 − 𝑟 − 1)! (𝑛 − 𝑟)!
(𝑛 − 𝑟) 𝑟
= (𝑛 − 1)! [ + ]
(𝑛 − 𝑟)! (𝑛 − 𝑟)!
𝑛−𝑟+𝑟
= (𝑛 − 1)! [ ]
(𝑛 − 𝑟)!
𝑛(𝑛 − 1)!
=
(𝑛 − 𝑟)!
𝑛!
= = 𝑛 p𝑟
(𝑛 − 𝑟)!
iv) We have,
1 + 1. 1 𝑝1 +2. 2 𝑝2 + 3. 3 𝑝3 + ⋯ … … + 𝑛. 𝑛 𝑝𝑛
= 1 + 1.1! + 2.2! + 3.3! + ⋯ … … + 𝑛. 𝑛!
= 1 + (2 − 1)! + (3 − 1)2! + (4 − 1)3! + ⋯ … … [𝑛 + 1 − 1]𝑛!
= 1! + (2! − 1!) + (4! − 3!) + ⋯ … … + [(𝑛 + 1) − 𝑛!]
= (𝑛 + 1)!
= 𝑛+1 𝑝𝑛+1

Example 2:
How many three letter words with or without meaning can be formed out of the letters of the word
SWING when repetition of letters is not allowed?
sol:-
here n = 5 ( Swing has 5 letters)
we have to frame 3 letter words (r)
5!
so permitation P(n,r) = (5−3)!
5∗4∗3∗2∗1
=
2∗1
= 60

Example 3 :
How many 3 letter words with or without meaning can be formed out of letters of word SMOKE when
repetition is allowed ?
sol:
SMOKE has 5 alphabets
so n = 5
we have to arrary in 3 form permutation (when repetition is allowed)
53 = (5 ∗ 5 ∗ 5)
= 125

ToppersNotes / 98282-86-909 10
Example 4:
It is reuired to seat 5 men and 4 women in a row so that the women occupy the even places.
how many such arrangements are possible ?
sol:
5 men and 4 women
i.e. total 9 positions
four places can be occupied by 4 women in p(4,4) ways = 4!
= 4∗3∗2∗1
=24 ways
Remaining 5 positions can be occupied by 5 men i.e. 5 !
= 5∗4∗3∗2∗1
= 120 ways
Total no. of ways of seating arrangements = 24 ∗ 120
= 2880 ways

Example 5:
Find the no. of words, with or without meaning, that can be formed with the letters of the words
SWIMMING ?
sol:-
SWIMMING = 8 letters
here, I comes 2 times and M comes 2 times
no. of words formed
8!
=
2! ∗ 2!
8∗7∗6∗5∗4∗3∗2∗1
=
(2 ∗ 1) ∗ (2 ∗ 1)
= 8∗7∗6∗5∗2∗3
=10080
Example 6:
Find the number of words, that can be formed with lettes of the word INDIA
sol:-
INDIA = 5 words
'I' comes twice
Note:- when a letter comes more than once in a word, we divide the factorial of the no. of all letters in
the words by the number of occurrences of each letter.
5!
INDIA = 2!
55 ∗ 4 ∗ 3 ∗ 2 ∗ 1
=
2∗1
= 60

Example:
how many different words can be formed with the letters of the word 'Super' such that the vowels
always come together ?

ToppersNotes / 98282-86-909 11
sol:-
SUPER = 5 letters
SPR ( UE) i.e total 4 letters
S, P, R, UE
No. of way which U and E can be arranged in 2! = 2
we arrange 4 letter 4!
4! = 4∗3∗2∗1
= 24
=24∗2 = 48 ways

Example:
find the no. of different words that can be formed with the letters of word " BUTTER" so that the vowels
are always together.
sol:
BUTTER contains 6 letters
U, E should always come together
so BTTR (UE)
so in total we have 5 words
i.e B, T, T, R, UE
5!
i.e 2!
5∗4∗3∗2∗1
=
2
= 60
No. of way U and E are arranged = 2!
total no. of permutations possible = 60*2
= 120 ways
Combinations:-
Each of the different selections or groups that can be made by taking some or all of them (irrespective
of order) is called a combination.
Arrangement in a particular order
𝑛
𝑛!
Cr =
𝑟! (𝑛 − 𝑟)!
n
Cr = No. of combinations
n = total no. of objects
r = no. of choosing objects
Example:
In a party, every person shakes hands with every other person. If there are 105 handshakes, find the no.
of person in the party.
sol:-
let n be the no. of persons in the party
No. of hand shakes = 105
so, total no. of handshakes nC2

ToppersNotes / 98282-86-909 12
n
C2 = 105
𝑛!
= 105
2! (𝑛 − 2)!
𝑛 ∗ (𝑛 − 1)
= 105
2
n2 -n = 210
n2-n - 210 = 0
n = 15, -14
we can not take -ve value
so n = 15
i.e. No. of persons in party = 15

Example:
A question paper has two part A and B each containing 10 questions. If a student has to choose 8 from
part A and 5 from part B, in how many ways can he choose the questions ?
sol:-
Total questions = 10 in A and 10 in B
we have to choose 8 questions from A
= 10C8
and 5 question from B
= 10C5
hence total no. of ways
10
C8 ∗ 10C5
10 ! 10 !
= ∗
8! (10 − 8)! 5! (10 − 5)!
10 ! 10 !
= ∗
8! ∗ 2! 5! ∗ 5!
10 ∗ 9 ∗ 8! 10 ∗ 9 ∗ 8 ∗ 7 ∗ 6 ∗ 5!
= ∗
8! ∗ 2 ∗ 1 5! ∗ 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1
= (5∗9) ∗ (2∗9∗2∗7)
= 45∗252
=11340

Probability
Total number of ways of achieving success or total number of possible outcomes is known as
Probability.
𝑁𝑜. 𝑜𝑓 𝑓𝑎𝑣𝑜𝑢𝑟𝑎𝑏𝑙𝑒 𝑜𝑢𝑡𝑐𝑜𝑚𝑒
P(A) =
𝑇𝑜𝑡𝑎𝑙 𝑛𝑜. 𝑜𝑓 𝑓𝑎𝑣𝑜𝑢𝑟𝑎𝑏𝑙𝑒 𝑜𝑢𝑡𝑐𝑜𝑚𝑒𝑠
P(A) = Probability of an event "A"

Example:
what is the probability that a card taken from a standard deck, is an ace ?
sol:
Total no. of cards = 52
No. of ace cards = 4

ToppersNotes / 98282-86-909 13
 so, no. of favorable outcomes = 4
𝑁𝑜. 𝑜𝑓 𝑓𝑎𝑣𝑜𝑢𝑟𝑎𝑏𝑙𝑒 𝑜𝑢𝑡𝑐𝑜𝑚𝑒𝑠
P(ACE) =
𝑇𝑜𝑡𝑎𝑙 𝑛𝑜. 𝑜𝑓 𝑓𝑎𝑣𝑜𝑟𝑎𝑏𝑙𝑒 𝑜𝑢𝑡𝑐𝑜𝑚𝑒𝑠
4
=
52
1
=
13

Group Theory
GROUP :-
A monoid (G, ∗) with idntity e, is said to be a group if for every a ∈ G there exists an element b ∈ G such
that a ∗b=e=b∗a.
b is known as inverse of a and we write a-1 = b.
Note that if b is an inverse of a, then a is an inverse of b.
(i) Associativity
(a ∗ b) ∗ c = a ∗ (b ∗ c), for any elements a, b and c in G.
(ii) Existence of Identity
There exists an element e ∈ G such that for all a∈ 𝐺
a ∗e = a = e ∗ a
e is called identity.
(iii) Existence of Inverse
For every a ∈ G, there exists b ∈ G such that
a∗b=e=b∗a
b is called inverse of a.
observe that if (G, ∗) is a group, then ∗ is a binary operation on G, so G must be closed under *, that
is a ∗ b ∈ G for any elements a and b in G.
Furthermore, if ∗ is commutative, G is called an Abelian group.

Abelian Group:-
A group is abelian if the operation is commutative, i.e.
a∗b=b∗a
for all a, b ∈ 𝐺
A group (G,*) is nonabelian or non commutative, if there is some pair of elements a and b in G for which
a∗b≠b∗a

Type of Groups:
finite Group:- A group with a finite number of elements. The number of elements in a group is called
the order of the group.
if G is a group that has a finite number of elements, we say that G is a finite group, otherwise the group
is infinite.
Infinite Group :- A group with an infinite number of elements.

ToppersNotes / 98282-86-909 14
Cyclic Group :-
A group generated by a single element. if a ∈ 𝐺 generates all elements, G is cyclic, and a is a generator
of G.
such that every element of G can be written in the form of an for same n ∈ Z.
The additive group Z of integers is a cyclic group generated of 1, since 1 ∈ 𝑍 and for every integer n, we
have n = n.1
we see that -1 is also a generator of Z, since n = (-n)(-1) for every n ∈Z.
thus Z =< 1 > = <-1>
Order of an Element :- The smallest positive integer n such that an = e, is called the order of a.
where e is the identity.
if no such n exists, the elements has infinite order.
clearly the identity element of a group is the only element of order one.
Note that if 0(a) = n and if for some positive integer m,
am = e them m is multiple of n.

Sub Group:-
A non-empty subset H of a group G is a subgroup of G if H is also a group under the same binary
operation of G. Symbolically, we write H ≤ G.
If e is the identity of G, {e} is also a subgroup of G, called the trivial subgroup of G. All other subgroups
are nontrivial.
G itself is a subgroup of G, called the improper subgroup of G.
All other subgroups are proper.

Graph Theory
Graph are discrete structures consisting of vertices and edges that connects these vertices. There are
several different types of graphs that differ with respect to the kind and number of edges that can a
connect a pair of vertices. Problems in almost every conceivable discipline can be solved using graph
models.
Basic terminology :-
A graph is a collection of nodes (called vertices) and connections (called edges) between them.
A graph is written as: G = (V, E)
Where
• V = set of vertices
• E = set of edges (pairs of vertices)
Vertex (Node) – A point in the graph
Edge (Link) – A line connecting two vertices
Adjacent – Two vertices are adjacent if they are connected by an edge if there is an edge e = (u, v)
connecting vertices u and v, then u and v are called adjacent to each other.
Degree of Vertex – Number of edges connected to a vertex
Indegree: Number of incoming edges (for directed graphs)
Outdegree: Number of outgoing edges

ToppersNotes / 98282-86-909 15
Even and odd vertices : A vertex is said to be an even or odd vertices according as its degree is an even or
odd number.
Path – A sequence of edges connecting a sequence of vertices
Cycle – A path that starts and ends at the same vertex
The most common representation of a graph is by means of a diagram in which the vertices are
represented as points and each edge as a line segment joining its end vertices.

Graph Types :-
1. undirected graph :- A graph is said to be an undirected graph if edges are unordered pairs of distinct
vertices.

In an undirected graph we can refer to an arc joining the vertex pair u and v as either (u, v) or (v, u).
2. directed graph :- A graph is said to be the directed graph if the edges are ordered pairs of vertices.
In this case an edge (u, v) is said to be from u to v and to join u to v.
3. Weighted Graph :-
o Every edge has a weight or cost.
o Weight can represent distance, time, cost, bandwidth, etc.
o Can be either directed or undirected.
4. Unweighted Graph :-
o No weights are assigned to edges.
o All connections are treated equally.
5. Simple Graph:-
o A graph with no loops (edge from a node to itself)
o And no multiple edges between same nodes
6. Multigraph :-
o Allows multiple edges between two vertices
o Can be directed or undirected
7. Complete Graph (Kₙ) :-
o Every pair of vertices is connected by exactly one edge
o A complete graph on n vertices may be denoted by the symbol kn.
o The degree of every vertex is n–1 in a complete graph of n vertices.
o Number of edges = n(n – 1)/2
8. Cyclic Graph:-
o A graph that has at least one closed loop or cycle
o Cycle: A → B → C → A
ToppersNotes / 98282-86-909 16
9. Connected Graph (Undirected) :-
o Every vertex is reachable from every other vertex
o Only one component
10. Disconnected Graph:-
o Has isolated vertices or groups (components) not connected to others
11. Regular Graph:- A graph in which every vertex has the same degree is called a regular graph. If
every vertex has degree K, then the graph is called a k-regular or regular graph of degree K.

Eulerian graph
A graph is Eulerian if it contains a Eulerian circuit, which means:
A closed trail (path) that visits every edge exactly once and returns to the starting vertex.

Rules:-
1. Have even degree in all vertics. Allow odd degree only in two vertices.
2. Edge repeat only once vertices multiple times repeated.
3. Always connected i.e. always connect all the eges.
A path that passes through each edge exactly once but vertices may be repeated is called Euler
path.
A graph that contains an Euler tour or Euler circuit is called an Eulerian graph.
1. Eulerian Trail (or Path)
o A trail that passes through every edge exactly once.
o It does not have to be a cycle, so it may start and end at different vertices.
2. Eulerian Circuit (or Cycle)
o A closed trail that starts and ends at the same vertex.
o It uses every edge exactly once.
o Graph is connected and all vertices have even degree.

Hamiltonian Graphs
A Hamiltonian graph contains a Hamiltonian cycle, which means:
A closed loop that visits every vertex exactly once, and returns to the starting vertex.
Rules:
1. Travel vertices only once
2. First and last vertex are same .
3. This is rule to check graph is hamilitonian or not.
4. No need to travel all edges.

ToppersNotes / 98282-86-909 17