UNIT #1

BASICS OF ALGORITHMS AND

MATHEMATICS
[Link] Kotak
 What is an algorithm?
2

 Informally, an algorithm is
 any well-defined computational procedure
 takes some value, or set of values, as input

 produces some value, or set of values, as output.

 An algorithm is
a sequence of computational steps that transform the
input into the output.
 a tool for solving a well-specified computational
problem.

[Link] Kotak Thursday, July 25, 2019

 What is an algorithm?
3

 An algorithm is
a set of rules for carrying out calculation either by hand
or on a machine
 finite step-by-step procedure to achieve a required
result
 sequence of computational steps that transform the
input into the output
 operations performed on data that have to be
organized in data structures

[Link] kotak Thursday, July 25, 2019

 Algorithms
4

 Algorithmic is a branch of computer science that consists

of designing and analyzing computer algorithms

1. The “design” pertain to

I. The description of algorithm at an abstract level by
means of a pseudo language
II. Proof of correctness that is, the algorithm solves the given
problem in all cases.
2. The “analysis” deals with performance evaluation
(complexity analysis).
[Link] kotak Thursday, July 25, 2019
 Algorithmic Sets
5

 Set : A set is a collection of different things

(distinguishable objects or distinct objects)
represented as a unit.
 The objects in a set are called its elements or
members.
 If an object x is a member of a set S,
 we write x ∈ S.
 On other hand, if x is not a member of S,
 we write x ∉ S.

[Link] kotak Thursday, July 25, 2019

 Algorithmic Sets
6

 A set cannot contain the same object more than

once, and its elements are not ordered.
 ie, consider the set S= {7, 21, 57} then
7 ∈ {7, 21, 57} and 8 ∉ {7, 21, 57} or
 7 ∈ S and 8 ∉ S.

 We can also describe a set containing elements

according to some rule.
 We write {n : rule about n}
 Thus, {n : n = m2 for some m ∈ N } means that a set of
perfect squares.
[Link] kotak Thursday, July 25, 2019
 Algorithmic Sets
7

 Empty Set
A Set contain no member, denoted as ∅ or {}.
 Infinite Set
A set contains infinite elements. For example, set of
integers, set of negative integers, etc.
 Sub Set
 For two sets A and B, we say that A is a subset of B,
written A⊆ B,
 if every member of A also is a member of B.
 Formally, A ⊆ B if x ∈ A implies x ∈ B Written x ∈ A
=> x ∈ B.

[Link] kotak Thursday, July 25, 2019

 Algorithmic Sets
8

 Proper Subset
 Set A is a proper subset of B, written A ⊂ B,
 if A is a subset of B and not equal to B.

 That is, a set A is proper subset of B if A ⊆ B but A ≠ B.

 Equal Sets
 The sets A and B are equal, written A = B,
 if each is a subset of the other.

 let A and B be sets. A = B if A ⊆ B and B ⊆ A.

[Link] kotak Thursday, July 25, 2019

 Algorithmic Sets
9

 Set Cardinality
 The number of elements in a set is called cardinality or
size of the set, denoted |S| or sometimes n(S).
 Two sets have same cardinality if their elements can be
put into a one-to-one correspondence.
 It is easy to see that the cardinality of an empty set is
zero i.e., |∅| .

[Link] kotak Thursday, July 25, 2019

 Algorithmic Sets
10

 Multiset
 Ifwe do want to take the number of occurrences of
members into account, we call the group a multiset.
 For example, {7} and {7, 7} are identical as set but {7}
and {7, 7} are different as multiset.

[Link] kotak Thursday, July 25, 2019

 Algorithmic Sets
11

 Power Set
 Let A be the set. The power of A, written P(A) or 2A, is
the set of all subsets of A.
 That is, P(A) = {B : B ⊆A}.
 For example, consider A={x, y, z}. The power set of A is
{{}, {x}, {y}, {z}, {x, y}, {y, z}, {x, z}, {x, y, z}}.

[Link] kotak Thursday, July 25, 2019

 Algorithmic Sets
12

 Union of Sets
 Theunion of A and B, written A ∪ B, is the set we get by
combining all elements in A and B into a single set.
 That is, A ∪ B = { x : x ∈ A or x ∈ B}.

[Link] kotak Thursday, July 25, 2019

 Algorithmic Sets
13

 Intersection of Sets
 The intersection of set A and B, written A∩B, is the set
of elements that are both in A and in B.
 That is, A ∩ B = { x : x ∈ A and x ∈ B}.

[Link] kotak Thursday, July 25, 2019

 Algorithmic Sets
14

 Difference of Sets
 Let A and B be two sets. The difference of A and B is A
- B = {x : x ∈ A and x ∉ B}.
 For example, let A = {1, 2, 3} and B = {2, 4, 6, 8}. The
set difference A - B = {1, 3}
while B - A = {4, 6, 8}.

[Link] kotak Thursday, July 25, 2019

 Solve the example
15

 1) A={1,3,5,7} B={3,5,9,8}

Find the
1)Power set A & B
2) Union of Sets
3) Intersection of Sets
4) Difference of Sets
A-B ,B-A

[Link] kotak Thursday, July 25, 2019

 Algorithmic Sets
16

 Universal Set
 Allset under consideration are subset of some large set
U called universal set.

[Link] kotak Thursday, July 25, 2019

 Algorithmic Sets
17

 Complement of a Set
 Given a universal set U, the complement of A, written
A’, is the set of all elements under consideration that
are not in A.

 Formally,
let A be a subset of universal set U. The
complement of A in U is
 A’ = U - A OR A’ = {x : x ∈ U and x ∉ A}

 For any set A ⊆ U, we have following

 1) A’’ = A 2) A ∩ A’ = ∅ 3) A ∪ A’ = U
[Link] kotak Thursday, July 25, 2019
 Algorithmic Sets
18

 Cartesian Product or Cross Product

 Let A and B are two sets,
 the cross product of A and B, written A x B,
 the set of all pairs wherein the first element is a
member of the set A and the second element is a
member of the set B.
 Formally, A x B = {(a, b) : a ∈ A, b ∈ B}.
 ie, let A = {1, 2} and B = {x, y, z} then
 A x B = {(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)}.
 When A and B are finite sets, the cardinality of their product is
|A x B| = |A| . |B|

[Link] kotak Thursday, July 25, 2019

 Functions and Relations
19

 A function assigns outputs to inputs. More precisely, a

function assigns a single output value to each element
of a set of so-called input values.
 In mathematics, there are lots of well-known functions
that map real numbers to real numbers.
 Negation function that maps, for example, 0.1 to −0.1 and
2 to -2.
 The square function that maps, for example, 1 to 1, 2 to 4,
10 to 100, and 0.1 to 0.01.

[Link] kotak Thursday, July 25, 2019

 Functions and Relations
20

 Note that the square function maps both 1 and −1 to 1;

 A function maps each input value to a single output value,
but several input values may be mapped to the same
output value.
 Other well-known functions are the sine, cosine and
tangent functions, which map angles to real, and area
and volume.
 Area maps a two-dimensional object to a real number;
Volume does the same to a three-dimensional object.

[Link] kotak Thursday, July 25, 2019

 Functions and Relations
21

 In mathematics, we often investigate relationships

between certain objects (numbers, functions, sets,
figures, etc.).
 If an element ‘a’ of a set A is related to an element
‘b’ of a set B, we might write
a is related to b
or shortly
 a related b
or even more shortly
a R b

[Link] kotak Thursday, July 25, 2019

 Functions and Relations
22

 The essential point is we have two objects, a and b, that

are related in some way.
 Also, we say “a is related to b”, not “b is related to a”,
so the order of a and b is important.
 In other words, the ordered pair (a,b) is distinguished
by the relation. This observation suggests the following
formal definition of a relation.
 Definition: Let A and B be two sets. A relation R from A
to B is a subset of the Cartesian product A x B.

[Link] kotak Thursday, July 25, 2019

 Functions and Relations
23

 Let X and Y be two sets. Any subset P of their

Cartesian product X x Y is a relation.
 When x ∈ X and y ∈ Y, we say that x is in relation
with y according to P, denoted x P y, if and only if
(x, y) ∈ P.
 For instance, one may think of the relation “≤” over the
integers as the set of pairs of integers such that the first
component of the pair is less than or equal to the
second. Ie. (2,6)

[Link] kotak Thursday, July 25, 2019

 Functions and Relations
24

 Consider any relation ‘f’ between X and Y. The relation

is called a function if, for each x ∈ X, there exists one
and only one y ∈ Y such that (x, y) ∈ f.
 This is denoted f : X → Y, which is read “f is a function
from X to Y”.

 Given x ∈ X, the unique y ∈ Y such that (x, y) ∈ f, is

denoted f(x).
 The set X is called the domain of the function, Y is its
image, and the set f[X] = { f(x) | x ∈ X } is its range.
 In general , f[Z] denotes { f(x) | x ∈ Z } provided that Z
⊆ X.
[Link] kotak Thursday, July 25, 2019
 Functions and Relations X Y
25

 Injective: A function f: X → Y is injective

if there do not exist two distinct x1, x2 ∈ Injective
X such that f(x1) = f(x2).
X Y
 Surjective: A function f: X → Y is
surjective if for each y ∈ Y there exists at
least one x ∈ X such that f(x)=y.
 In other words, it is surjective if its range is Surjective
the same as its image.
X Y
 Bijective: A function f: X → Y is bijective
if it is both injective and surjective.

Bijective
[Link] kotak Thursday, July 25, 2019
 Vectors and Matrices
26

 A vector, V, means a list (or n-tuple) of numbers: V =

(V1, V2, . . . , Vn) where Vi are called the
components of V.

 If all the Vi are zero, then V is called the zero

vector.

 Given vectors V and U are equal i.e., V = U, if they

have the same number of components and if
corresponding components are equal.
[Link] kotak Thursday, July 25, 2019
 Vectors and Matrices
27

 Addition of Two Vectors

 Sum of two vectors V and U, (V + U) is the vector
obtained by adding corresponding components from V
and U.

V U
 v1 , v ,  v  u , u ,  u 
2 n 1 2 n

 v  u , v  u ,  v  u 
1 1 2 2 n n

[Link] kotak Thursday, July 25, 2019

 Vectors and Matrices
28

 Multiplication of a vector by a Scalar

 The product of a scalar k and a vector V i.e., kV, is the
vector obtained by multiplying each component of V by
k.

kV  k v1 , v,
2
 v   kv , kv ,
n 1 2
 kv  n

› Here, we define -V = (-1)V and V-U = V +(-U).

› It is not difficult to see k(V + U) = kV + kU where k is
a scalar and V and U are vectors.

[Link] kotak Thursday, July 25, 2019

 Vectors and Matrices
29

 Matrix
 In
algorithmic (study of algorithms), we like to write a
matrix A as A(aij).
 Column Vector
A matrix with only one column is called a column vector.
 Zero Matrix
A matrix whose entries are all zero is called a zero
matrix and denoted by 0.

[Link] kotak Thursday, July 25, 2019

 Vectors and Matrices
30

 Matrix Addition › Scalar Multiplication

A B kA
 a11 a12 a  b b b   a11 a12 a 
  
13 11 12 13 13
 a21 a22 a   b b b
23 21 22 23
 k  a 21 a22 a 23
a a a  b b b  a 
 31 32 33 31 32 33  31 a32 a 33

 a11  b11 a  b a  b   ka11 ka12


12 12 13 13

ka  13
 a21  b21 a b a b   ka21 ka22
a  b
22 22 23 23 ka  23

 31 31 a  b a  b 
32 32 33 33 ka
 31 ka32 ka  33

[Link] kotak Thursday, July 25, 2019

 Vectors and Matrices
31

 Properties of Matrix under Addition and Scalar

Multiplication

Let A, B, and C be matrices of same size and let k and l be

scalars.
1. A+B=B+A
2. A+0=0+A=A
3. A + (-A) = (-A) + A = 0
4. k(A + B) = kA + kB
5. (k + l)A = kA + lA
6. (kl)A = k(lA)

[Link] kotak Thursday, July 25, 2019

 Vectors and Matrices
32

 Matrix Multiplication
A and B are two matrices such that the number of
columns of A is equal to number of rows of B.
 matrix A is an m×p matrix and matrix B is a p×n matrix.
 The product of A and B is the m×n matrix.
 ij-entry is obtained by multiplying the elements of the ith row
of A by the corresponding elements of the jth column of B and
then adding them.
 It is important to note that if the number of columns of A
is not equal to the number of rows of B, then the
product AB is not defined.

[Link] kotak Thursday, July 25, 2019

 Vectors and Matrices
33

 Matrix Multiplication
 a11 a12 a13  b11 b12 b13
   
A  B  a 21 a 22 a 23  b21 b22 b23
a   
 31 a32 a33 b31 b32 b33
 a11b11  a12 b21  a13 b31 a11b12  a12 b22  a13 b32 a b  a12 b23  a13 b33 
 
11 13
 a 21b11  a 22 b21  a 23 b31 a 21b12  a 22 b22  a 23 b32 a b
21 13
 
a22 b23 a23 b33
a b  a b  a b a31b12  a32 b22  a33 b32 a b  a32 b23  a33 b33
 31 11 32 21 33 31 31 13

[Link] kotak Thursday, July 25, 2019

 Vectors and Matrices
34

 Properties of Matrix Multiplication

Let A, B, and C be matrices and let k be a scalar.

1. (AB)C = A(BC)
2. A(B+C) = AB + AC
3. (B+C)A = BA + CA
4. k(AB) = (kA)B = A(kB)

[Link] kotak Thursday, July 25, 2019

 Vectors and Matrices
35

 Transpose of Matrix
 The transpose of a matrix A is obtained by writing the row
of A, in order, as columns and denoted by AT.
 It is not hard to see that if A is an m×n matrix, then AT is an
n×m matrix.

 a11 a 
 
12
 a11 a a 
A   a 21 a22 A
T
 21 31

a  a12 a a 32
 31 a32 
22

[Link] kotak Thursday, July 25, 2019

 Vectors and Matrices
36

 Determinants
The determinant of order one is: a 11
 a 11

The determinant of order two is:

a
11 a 12
 a11 a 22  a21 a12
a
21 a 22

The determinant of order three is:

a a a
11 12 13

a a a
21 22 23

a a a
31 32 33

a a a
11
22 23
 a12 a21 a  a a
23
a 13
21 22

a a 32 33 [Link]
31 a kotak aThursday,
33 a July 25, 2019
31 32
 Linear Inequalities
37

 Inequalities
 The term inequality is applied to any statement
involving one of the symbols <, >, ≤, ≥.

Examples of inequalities are:

1. x1 ≥ 1

2. x + y + 2z > 16

3. p + q ≤ ½

4. ax + by > 1

[Link] kotak Thursday, July 25, 2019

 Linear Inequalities
38

 Fundamental Properties of Inequalities

1. If a ≤ b and c is any real number, then a + c ≤ b + c.

For example, -3 ≤ -1 implies -3+4 ≤ -1 + 4.
2. If a ≤ b and c is positive, then ac ≤ bc.
For example, 2 ≤ 3 implies 2(4) ≤ 3(4).
3. If a ≤ b and c is negative, then ac ≥ bc.
For example, 3 ≤ 9 implies 3(-2) ≥ 9(-2).
4. If a ≤ b and b ≤ c, then a ≤ c.
For example, -1/2 ≤ 2 and 2 ≤ 8/3 imply -1/2 ≤ 8/3.
[Link] kotak Thursday, July 25, 2019
 Linear Inequalities
39

 Geometric Interpretation of Inequalities

 An inequality in two variable x and y describes a
region in the x-y plane (called its graph), namely, the
set of all points whose coordinates satisfy the
inequality.

[Link] kotak Thursday, July 25, 2019

 Linear Inequalities
40

 Geometric Interpretation of Inequalities(cont... )

 The y-axis divide xy-plane into two regions, called half-
planes.

1. Right half-plane :
The region of points whose
coordinates satisfy inequality
x > 0.
2. Left half-plane :
The region of points whose
coordinates satisfy inequality
x < 0.
[Link] kotak Thursday, July 25, 2019
 Linear Inequalities
41

 Geometric Interpretation of Inequalities(cont... )

 Similarly, the x-axis divides xy-plane into two half-
planes.

1. Upper half-plane :
In which inequality y > 0
is true.
2. Lower half-plane : In
which inequality y < 0 is
true.
[Link] kotak Thursday, July 25, 2019
 Linear Inequalities
42

 Geometric Interpretation of Inequalities(cont... )

 Every line ax + by = c divides the xy-plane into two
regions called its half-planes.

1. On one half-plane
ax + by > c is true
2. On the other half-
plane ax + by < c is
true.

[Link] kotak Thursday, July 25, 2019

 Linear Equations
43

 One Unknown
A linear equation in one unknown can always be stated
into the standard form ax = b
 where x is an unknown and a and b are constants.

 If a is not equal to zero, this equation has a unique

solution
x = b/a

[Link] kotak Thursday, July 25, 2019

 Linear Equations
44

 Two Unknowns
A linear equation in two unknown, x and y, can be put
into the form ax + by = c
 where x and y are two unknowns and a, b, c are real
numbers.
 Also, we assume that a and b are non zero.

[Link] kotak Thursday, July 25, 2019

 Linear Equations
45

 Solution of Linear Equation

A solution of the equation consists of a pair of numbers,
u = (k1, k2), which satisfies the equation ax + by = c.
 Mathematically speaking, a solution consists of u = (k1,
k2) such that ak1 + bk2 = c.
 Geometrically, any solution u = (k1, k2) of the linear
equation ax + by = c determine a point in the
Cartesian plane.
 Since a and b are not zero, the solution you correspond
precisely to the points on a straight line.
[Link] kotak Thursday, July 25, 2019
 Linear Equations
46

 Two Equations in Two Unknowns

A system of two linear equations in two unknowns x and
y is
a1x + b1y = c1
a2x + b2y = c2
 Where a1, a2, b1, b2 are not zero.

 A pair of numbers which satisfies both equations is

called a simultaneous solution of the given equations or
a solution of the system of equations.

[Link] kotak Thursday, July 25, 2019

 Linear Equations
47

 Two Equations in the Two Unknowns (cont... )

 Geometrically, there are three cases of a simultaneous
solution
1. If the system has exactly
one solution,
the graph of the linear
equations intersect in one
point.

[Link] kotak Thursday, July 25, 2019

 Linear Equations
48

 Two Equations in the Two Unknowns (cont... )

 Geometrically, there are three cases of a simultaneous
solution
2. If the system has no
solutions,
the graphs of the linear
equations are parallel.

[Link] kotak Thursday, July 25, 2019

 Linear Equations
49

 Two Equations in the Two Unknowns (cont... )

 Geometrically, there are three cases of a simultaneous
solution
3. If the system has an
infinite number of
solutions, the graphs of
the linear equations
coincide.

[Link] kotak Thursday, July 25, 2019

50 Thank You.

[Link] kotak Thursday, July 25, 2019