UNIT – II

 Reference Book
1. Discrete Mathematics and Its Application – Kenneth H. Rosen

 Additional Resources
 Introduction to Algorithms-Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest
 The Art of Computer Programming Vol. 1-4A-Donald E. Knuth
 Data Structures and Algorithms Made Easy: Data Structures and Algorithmic Puzzles-
Narasimha Karumanchi
 Learn Pascal -Sam A. Abolrous
 Pascal, Programming and Problem Solving-Larry R. Nyhoff and Sanford Leestma
 [Link]
 [Link]

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 2

 Algorithms and their Characteristics
 Algorithms on Integers
 Algorithms on Matrices
 Recursive Algorithms
 Searching Algorithms
 Sorting Algorithms
 Complexity of Algorithms

 (Note: Programs in PASCAL will be displayed in class.)

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 3

4

[1] Section 3.1: Pages 191-194, 202-204

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022

INFORMAL DEFINITION OF AN ALGORITHM
USED IN A COMPUTER

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 5

 An Algorithm is a finite set of precise instructions for performing a computation or
for solving a problem.

 Example: Describe an algorithm for finding the maximum value in a finite

sequence of integers.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 6

FINDING THE LARGEST INTEGER
AMONG FIVE INTEGERS

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 7

 Pseudocode provides an intermediate step between an English language
description of an algorithm and an implementation of this algorithm in a
programming language. The steps of the algorithm are specified using
instructions resembling those used in programming languages.

 Example
procedure max(a1, a2, . . . , an: integers)
max := a1
for i := 2 to n
if max < ai then max := ai
return max{max is the largest element}

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 8

program maximum;
var i, max, n: integer;
a: array[1..100] of integer;
begin
writeln('Input how many integers to be entered?');
readln(n);
writeln('Input the integers');
for i:=1 to n do
readln(a[i]);
max:= a[1];
for i:= 2 to n do
if max < a[i] then max := a[i];
writeln('Maximum is ',max);
end.
Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 9
 Write a program in any programming language to find the minimum of a set of real
numbers.

 Note: Always mention the programming language you are using.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 10

1. Input
2. Output
3. Definiteness
4. Correctness
5. Finiteness
6. Effectiveness
7. Generality

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 11

1. Define: an algorithm.
2. State any 2 characteristics of an algorithm.
3. Consider the following part of a code:
while (y > 0) do
begin
r:=x mod y;
x:=y;
y:=r;
end;
Perform a dry run for x = 56 and y = 12. What are the final values of x and r?

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 12

procedure max(a1, a2, . . . , an: integers)
max := a1
for i := 2 to n
if max < ai then max := ai
return max{max is the largest element}

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 13

 Show that the program on finding maximum of a list of numbers has all the properties of an
algorithm.
 List all steps used to find the maximum of the list 1, 8, 12, 9, 11, 2, 14, 5, 10, 4. (Dry run)
 WAP
 That finds the average of a set of integers.
 That finds the absolute value of a number.
 That swaps two numbers using a temporary variable.
 That finds out how many positives, negatives and zeroes are there in a list of 5 numbers.
 That changes marks to a letter grade.
 That finds the product of a set of integers.
 That inserts an integer x in the appropriate position into the list 𝑎 , 𝑎 , ⋯ , 𝑎 of integers that are in
increasing order.
 That will count the number of 1s in a bit string by examining each bit of the string to determine
whether it is a 1-bit.
Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 14
15

[1] Sections 3.3, 4.1-4.3: Pages 230; 239-240, 246-249, 255-259, 267-268, 272-
274

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022

  Base b Expansions
 Division Algorithm
 Euclidean Algorithms
 Horner’s Algorithm
 Finding primes

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 16

 Decimal to Binary

Also
.
Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 17
  Example: Find the binary expansion of the decimal number 65.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 18

  To base 5:

Also
.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 19

 Base b expansion of n:
Result: Let b be an integer greater than 1. Then if n is a positive integer, it can
be expressed uniquely in the form

where k is a nonnegative integer, , ,..., are nonnegative integers less

than b, and .

Questions:
1. Find the octal (base-8) expansion of the decimal number 12345.
2. WAP
i. To convert a Decimal number to its binary equivalent.
ii. To convert a Decimal number to any base b.
iii. To convert a binary number to its decimal equivalent.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 20

 Answer the following questions?
1. For the decimal number 223, find its equivalent base 7 representation.
2. Convert to the corresponding decimal number.
3. Consider the following part of a code:
i:=0; while(q<>0) do
begin
i:=i+1;
a[i]:=q mod b;
q:= q div b;
end;
Perform a dry run for q := 50 ; b := 4. What are the values of a[i]?
Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 21
 THE DIVISION ALGORITHM: Let a be an integer and d a non zero integer. Then
there are unique integers q and r, with 0 ≤ r < |d|, such that a = dq + r.

 Example: If a = 100 and d = -7, find q and r.

 Ans: 100 = (-7)*(-14)+2 (Here, q=-14, r=2. Observe .

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 22

 Definition: d is called the divisor, a is called the dividend, q is called the quotient,
and r is called the remainder.

 Notation: q = a div d, r = a mod d.

 Note: mod function gives you remainder when a is divided by d and div gives you the
quotient.

 Questions:
 What are the quotient and remainder when 101 is divided by 11?
 WAP to see the implementation of Division Algorithm.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 23

 Used to find greatest common divisor (GCD) of two integers.
 Example: Find gcd(91, 287).
Ans:

gcd(91, 287)=7
 Lemma: Let a = bq + r, where a, b, q, and r
are integers.
Then gcd(a, b) = gcd(b, r).
 Questions:
 Find the GCD of 414 and 662 using the
Euclidean algorithm.
WAP for Euclidean
SimiCyriac Algorithm.
Discrete Mathematics Algorithms 25 August 2022 24
 Used to find the value of at .
 Example: Evaluate at by using Horner’s Algorithm.
Here n=2, c=2, , =1.
Initial: y:=
For i:=1to n do y:=y*c+
i:=1; y:=3*2+ =7
i:=2; y:=7*2+ =15

 Question: WAP for Horner’s Algorithm

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 25

  Example: Evaluate at by using Horner’s
Algorithm. Show all steps.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 26

 Definition: An integer p greater than 1 is called prime if the only positive factors of
p are 1 and p. A positive integer that is greater than 1 and is not prime is called
composite.
 Theorem: If n is a composite integer, then n has a prime divisor less than or equal
to √n.

 Question: WAP to find whether the user-input positive integer is prime or not.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 27

1. Convert the decimal number 231 to its binary notation.
2. Definition: One’s complement is used to represent positive and negative
integers with absolute value less than 2n−1, a total of n bits is used. The leftmost
bit is used to represent the sign. A 0 bit in this position is used for positive
integers, and a 1 bit in this position is used for negative integers. For positive
integers, the remaining bits are identical to the binary expansion of the integer.
For negative integers, the remaining bits are obtained by first finding the binary
expansion of the absolute value of the integer, and then taking the complement
of each of these bits, where the complement of a 1 is a 0 and the complement of a
0 is a 1.
i. Find the one’s complement using bit string of length 6 for 22.
ii. What integer does 11001 represent?
iii. WAP for one’s complement.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 28

 Answer the following questions?
1. Use Horner’s algorithm to find the value of at x = -1

2. Let A = ,B = . Can you find:

(i) A+B
(ii) AB
(iii) BA
(iv)

3. Find the values for those which you can.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 29

 Answer the following questions?
1. Definition: If a and b are integers and m is a positive integer, then a is congruent
to b modulo m if m divides a − b.
Notation: a ≡ b (mod m).
Write a pseudocode for finding if .

2. Perform a dry run for:

a:=24; b:=14; m:=6

3. Let . Find f(-2) using Horner’s Algorithm. Explain all steps.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 30

31

[1] Section 2.6: Pages 178-185

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022

  Matrix Addition
 Matrix Multiplication
 Transpose of a Matrix
 Boolean product of Zero-One Matrices

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 32

 Definition: Let A = and B = [ ] be m × n matrices. The sum of A and B,
denoted by A + B, is the m × n matrix that has + as its (i, j )th element.
That is, A + B = [ + ].
 Definition: Let A be an m × p matrix and B be a p × n matrix. The product of A
and B, denoted by AB, is the m × n matrix with its (i, j )th entry equal to the sum of
the products of the corresponding elements from the ith row of A and the j th
column of B.
That is, if AB = [ ], then = + +・ ・ ・+ .
 Definition: Let A = [ ] be an m × n matrix. The transpose of A, denoted by ,
is the n × m matrix obtained by interchanging the rows and columns of A.
That is, if =[ ], then = for i = 1, 2, . . . , n and j = 1, 2, . . . , m.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 33

 Definition: A matrix all of whose entries are either 0 or 1 is called a zero–one
matrix.

 Definition: = b1 meet b2 = b1 and b2

 Definition: = b1 join b2 = b1 or b2.

 Definition: Let A = [aij ] and B = [bij ] be m × n zero–one matrices. Then the join of
A and B is the zero–one matrix with (i, j )th entry aij bij . The join of A and B is
denoted by A B.
 The meet of A and B is the zero–one matrix with (i, j )th entry aij bij . The meet of
A and B is denoted by A B.

 Example: Find the join and meet of the zero–one matrices A = ,B=
.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 34

 Definition: Let A = [aij ] be an m × p zero–one matrix and B = [bij ] be a p × n
zero–one matrix. Then the Boolean product of A and B, denoted by , is the
m × n matrix with (i, j )th entry cij where
cij = (ai1 b1j ) (ai2 b2j ) ・・・ (aip bpj ).

 Example: Find the Boolean product of A and B, where A = ,B =

.
 Questions:
1. How many bit operations are used to find , where A and B are n × n zero
one matrices?
2. WAP to find :
i. Sum of two matrices
ii. Product of two matrices
iii. Transpose of a matrix.
iv. Boolean Product of two zero-one matrices.
v. Inverse of a 2×2 matrix.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 35

 Answer the following questions?

1. Let A = ,B = . Find:

(i)

(ii)

(iii)

2. Find factorial of 6.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 36

37

[1] Section 5.4: Pages 360-361, 365-367, 370-371

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022

  Fibonacci Series
 Factorial of a non-negative number

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 38

 Definition: An algorithm is called recursive if it solves a problem by reducing it to
an instance of the same problem with smaller input.
 It requires a recursive definition and initial value(s).

 Definition:

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 39

 Definition: The Fibonacci sequence, is defined by the initial
conditions and the recurrence relation for n = 2,
3, 4, . . . .
 Example: Find the Fibonacci numbers .

 Questions:
Write a recursive program to:
i. Find factorial of a non-negative integer.
ii. Display Fibonacci sequence.
iii. Compute where a is a non-zero real number and n is a non-negative
integer.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 40

 Give a recursive program for computing nx where n is a positive integer and x
is an integer.
 Describe a recursive program for multiplying two non-negative integer x and y
based on the fact that

 Devise a recursive program to find the nth term of the sequence defined by
for

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 41

 Answer the following questions?

1. Define a recursive algorithm.

2. Find the first 5 terms of the sequence defined by .

3. For qs 2, define the function of the corresponding program.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 42

43

[1] Section 3.1: Pages 194-196, 202-204

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022

  Linear Search
 Binary Search

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 44

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 45
 It is also called as sequential search.

 The algorithm searches for an element x in the list and

returns the location i if or -1 if it is not in the list.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 46

 Example of a Linear Search

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 47

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 48
 Assumptions
1. Elements in the array are unique.
2. Array is ordered. Either increasing or decreasing.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 49

 Example of a binary search

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 50

1. WAP to implement
 Linear search
 Binary search
2. The ternary search algorithm locates an element in a list of increasing integers
by successively splitting the list into three sublists of equal (or as close to equal as
possible) size, and restricting the search to the appropriate piece. Write a program
for this algorithm.
3. Rewrite the binary search algorithm, if the list entered is in descending order.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 51

 Answer the following questions?

Mention all steps for searching 19 in the following list using:

1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22

1. Linear Search

2. Binary Search

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 52

 Answer the following question?

How will the following program segment run for the a[i] values 7, 5, 10, 2, 3?

for i:=1 to n-1 do

for j:=1 to n-i do
if a[j] > a[j+1] then
begin
t:=a[j];
a[j]:=a[j+1];
a[j+1]:=t;
end;
Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 53
54

[1] Section 3.1: Pages 196-198, 202-204

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022

  Selection Sort
 Bubble Sort
 Insertion Sort

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 55

 These algorithms sorts a list in either increasing or
decreasing order.

 Sorting can be done starting from the first element or from the last
element.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 56

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 57
 Example of selection sort

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 58

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 59
 Answer the following question?

How will selection sort display 7, 5, 10, 2, 3 in ascending order? Show dry run.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 60

 Sort 3,2,4,1,5 in increasing order.
 First pass: 3,2,4,1,5-> 2,3,4,1,5-> 2,3,4,1,5->2,3,1,4,5->2,3,1,4,5

 Second pass: 2,3,1,4,5-> 2,3,1,4,5-> 2,1,3,4,5->2,1,3,4,5

 Third pass: 2,1,3,4,5-> 1,2,3,4,5->1,2,3,4,5

 Fourth pass: 1,2,3,4,5->1,2,3,4,5

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 61

 Insertion sort

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 62

 Example of insertion sort

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 63

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 64
1. Use bubble sort to put 3, 2, 4, 1, 5 into an increasing order.
2. Use insertion sort to put 3, 2, 4, 1, 5 into an increasing order.
3. WAP to show implementation of
i. Selection sort
ii. Bubble sort
iii. Insertion sort

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 65

 Answer the following questions?

Use following sorting to put 7, 9, 19, 15, 12 into decreasing order.

1. Selection sort

2. Bubble sort

3. Insertion sort

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 66

 Answer the following question?

How will insertion sort display 7, 5, 10, 2, 3 in descending order? Show dry run.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 67

68

[1] Section 3.2: Pages 204-214, 216-218

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022

 Definition: Let f and g be functions from the set of integers or the set of real
numbers to the set of real numbers. f (x) is said to be O(g(x)) if there are
constants C and k such that
|f (x)| ≤ C|g(x)| whenever x > k.
 Note: C and k need not be unique.
 Only one pair (C,k) is required.

 Remarks: 1. f (x) is O(g(x)) says that f (x) grows slower than some fixed
multiple of g(x) as x grows without bound.
 2. One of the advantages of using big-O notation is that the growth of a
function can be estimated without worrying about constant multipliers or
smaller order terms.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 69

 Show that is .

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 70

 Answer the following question?

1. Use the definition of “f (x) is O(g(x))” to show that x4 + 9x3 + 4x + 7 is O(x4).

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 71

 Let f (x) = anxn + an−1 xn−1 +· · ·+a1x + a0, where a0, a1, . . . , an−1, an are
real numbers. Then f (x) is O(xn).

 Big-O estimate of the sum of the first n positive integers is .

 Big-O estimate of n! is .

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 72

 Suppose that f1(x) is O(g1(x)) and that f2(x) is O(g2(x)). Then (f1 + f2)(x)
is O(max(|g1(x)|, |g2(x)|)).

 Suppose that f1(x) is O(g1(x)) and that f2(x) is O(g2(x)). Then (f1 f2)(x) is
O(g1(x) g2(x)).

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 73

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 74
Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 75
 Determine whether each of these functions is O(x).
a) f (x) = 10 b) f (x) = 3x + 7

 Show that x3 is O(x4) but that x4 is not O(x3).

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 76

77

[1] Section 3.3: Pages 218-222, 229-231

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022

 An analysis of the time required to solve a problem of a particular size involves the
time complexity of the algorithm.
 An analysis of the computer memory required involves the space complexity of
the algorithm.
 Worst-case analysis of an algorithm means the largest number of operations
needed to solve the given problem using this algorithm on input of specified size.
 Average-case analysis is the average number of operations used to solve the
problem over all possible inputs of a given size.

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 78

 1. Describe the time complexity of Algorithm for finding the maximum element in a
finite set of integers.
 2. Describe the time complexity of the linear search algorithm.
 3. Describe the time complexity of the binary search in terms of the number of
comparisons used (ignoring the time required to compute (i + j)/2 in each iteration
of the loop in the algorithm).
 4. Describe the average-case performance of the linear search algorithm in terms
of the average number of comparisons used, assuming that the integer x is in the
list and it is equally likely that x is in any position.
 5. What is the worst-case complexity of the bubble sort in terms of the number of
comparisons made?

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 79

 6. What is the worst-case complexity of the insertion sort in terms of the
number of comparisons made?
 7. How many additions of integers and multiplications of integers are used by
the Algorithm to multiply two n × n matrices with integer entries?
 8. How many bit operations are used to find A B, where A and B are n × n
zero–one matrices?
 9. In which order should the matrices A, B, and C—where A is 30 × 20, B is 20
× 40, and C is 40 × 10, all with integer entries—be multiplied to use the least
number of multiplications of integers?

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 80

 How many comparisons are used by the algorithm to find the smallest natural
number in a sequence of n natural numbers?
 Suppose that an element is known to be among the first four elements in a list of 32
elements. Would a linear search or a binary search locate this element more
rapidly?

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 81

 Answer the following questions?

1. Define time complexity.

2. For , find .

3. What operations are used to calculate time complexity?

Simi Cyriac Discrete Mathematics Algorithms 25 August 2022 82