0% found this document useful (0 votes)

21 views143 pages

M.Sc. Mathematics: Algorithms Course

Q: In what situations might interpolation with unequal intervals be preferred over equal intervals, and why?

Interpolation with unequal intervals might be preferred when the data points are not uniformly distributed, which is common in real-world scenarios where measurements are taken at irregular intervals. This technique allows for more flexibility and can accommodate varying needed precision across the range of data . It is particularly useful when the function's behavior changes abruptly in certain regions, as this method can better handle such variations compared to equal interval interpolation, which assumes a uniform rate of change .

Q: In what scenarios might numerical differentiation be more suitable than analytical differentiation?

Numerical differentiation is more suitable than analytical differentiation when dealing with complex functions for which obtaining an explicit derivative form is difficult or impossible. It is especially useful in scenarios where functions are available in discrete data forms, such as from experimental datasets or simulations, where traditional calculus approaches are infeasible . Numerical techniques provide a practical alternative to approximating derivatives in cases where only tabular data or non-standard functions are available .

Q: Explain how greedy algorithms may fail to find the global optimum solution in certain problems.

Greedy algorithms can fail to find the global optimum solution because they make the best local decision at each step without considering the broader implications. This local optimization does not take into account future consequences, which can prevent reaching the best overall solution in problems that require global awareness. Cases like the Knapsack Problem, where choosing the most valuable item first can block achieving the best use of capacity, or certain pathfinding problems where local choices lead away from the destination, exemplify where greedy methods fall short .

Q: Explain how Simpson's Rule can provide a more accurate estimation of integrals compared to the Trapezoidal Rule.

Simpson's Rule provides a more accurate estimation of integrals than the Trapezoidal Rule by approximating the integrand using a second-order polynomial rather than linear segments. While the Trapezoidal Rule uses straight line segments to approximate the area under a curve, Simpson's Rule fits a parabola through each segment of the curve, thus providing a better approximation if the function being integrated has continuous derivatives. This results in a significant reduction in error, especially for smooth functions, as Simpson's Rule accounts for curvature in a way that the linear approximation of the Trapezoidal Rule cannot .

Q: How do cut-vertices and cut-sets contribute to understanding graph connectivity?

Cut-vertices and cut-sets are crucial in understanding graph connectivity as they identify critical points whose removal results in increased disconnection, thus mapping the robustness and vulnerability of networks. A cut-vertex, when removed, increases the number of connected components in a graph, leading to a partitioning of the graph into smaller subnetworks. Similarly, a cut-set is a collection of edges whose removal increases the number of graph components . Such insights help in designing resilient networks by highlighting parts of the graph that require reinforcement to maintain connectivity .

Q: Why might Kruskal’s Algorithm be preferred over Prim’s Algorithm for certain graphs when constructing minimum spanning trees?

Kruskal's Algorithm might be preferred over Prim's when dealing with sparse graphs because it considers the edges in order of increasing weight, only adding the shortest edges while avoiding cycles . This can make Kruskal’s more efficient for edge-centric operations, as it does not require the graph to keep all vertices active concurrently. It’s particularly effective when the graph's edges are already sorted or when the graph can be easily managed using a disjoint set for cycle detection . On the other hand, Prim's generally performs better on dense graphs as it progressively connects nodes to a growing spanning tree .

Q: Discuss the significance of asymptotic analysis in evaluating algorithm efficiency.

Asymptotic analysis is significant in evaluating algorithm efficiency as it provides a framework to estimate algorithm performance in terms of time and space complexity, especially for large inputs. By using notations such as Big O, Omega, and Theta, it allows for simplifying the growth function of an algorithm, focusing on dominant terms and ignoring lower-order terms and coefficients . This leads to more meaningful comparisons across different algorithms as it highlights the computational limits and potential scalability, which is crucial for understanding real-world performance .

Q: Discuss the advantages and limitations of using Dijkstra’s Algorithm for finding the shortest path in graphs.

Dijkstra's Algorithm is advantageous for finding the shortest path in graphs with non-negative weights as it is efficient and easy to implement, often running in O(V^2) time complexity, which can be improved to O(V log V + E) using a priority queue . Its main limitation is the requirement for non-negative weights, as it doesn't work correctly with graphs having negative weight edges. Additionally, while it efficiently finds the shortest path from a single source to all nodes, it is less efficient if only a single destination node is needed compared to more specialized algorithms like A* .

Q: How does the 'Divide and Conquer' technique enhance algorithm efficiency?

The 'Divide and Conquer' technique enhances algorithm efficiency by breaking a problem into smaller sub-problems, solving each independently, and then combining their solutions. This method is particularly useful for problems that can be recursively divided into similar subcases. It allows algorithms to manage complex tasks by simplifying the computational requirements at each division level, which leads to easier analysis and often a reduction in time complexity . Classic examples include quicksort and merge sort, where divide and conquer allows them to achieve O(n log n) efficiency .

Q: How does the Gauss Seidel method improve upon the Gauss Jacobi method for solving systems of linear equations?

The Gauss Seidel method improves upon the Gauss Jacobi method by iteratively updating the solution vector using the most recent values in each step, leading to faster convergence in many cases. While Gauss Jacobi relies on using values from the previous iteration for all updates, Gauss Seidel uses them immediately in the current iteration as they become available . This immediate update often results in a more rapid convergence, especially when dealing with large systems where convergence speed is critical .

The document outlines the course structure for the M.Sc. Mathematics program at Karnataka State Open University, specifically focusing on the Algorithms and Computations course. It includes details on course content, objectives, and the roles of various committee members involved in the course's development. The course covers topics such as computer fundamentals, numerical algorithms, and graph theoretical algorithms, designed for self-study at the postgraduate level.

Uploaded by

jeevanandasgone

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

21 views143 pages

M.Sc. Mathematics: Algorithms Course

Uploaded by

jeevanandasgone

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

KARNATAKA STATE OPEN UNIVERSITY

Mukthagangothri, Mysuru – 570006

[Link]. MATHEMATICS (CBCS)

(FOURTH SEMESTER)

Course-MMSEC - 2
ALGORITHMS AND COMPUTATIONS
[Link]. MATHEMATICS (CBCS)
FOURTH SEMESTER

Course: MMSEC - 2
ALGORITHMS AND COMPUTATIONS

i
Programme Name: [Link]. Mathematics (CBCS) Year/Semester: IV Semester
Course Code: MMSEC 2 Course Name: Algorithms and Computations
Credit: 2 Unit Number : 1-8
COURSE DESIGN COMMITTEE
Dr. Sharannappa. V. Halse Chairman
Vice Chancellor
Karnataka State Open University
Mukthagangothri, Mysuru-570006
Prof. Lakshmi N Member
Dean (Academic)
Karnataka State Open University
Mukthagangothri, Mysuru-570006
Dr. Pavithra. M Course coordinator
Assistant Professor
DoS in Mathematics, KSOU, Mukthagangothri, Mysuru-06
EDITORIAL COMMITTEE
1. Dr. K. Shivashankara Chairman
BOS Chairman(PG), DoS in Mathematics, KSOU.
Associate Professor, Yuvaraja College,
University of Mysore, Mysuru-06

2. Mr. S. V. Niranjana Member & Convener

Coordinator, (DoS in Mathematics)
Assistant Professor, DoS in Physics
KSOU, Mysuru-06

3. Dr. Pavithra. M Member

Assistant Professor
DoS in Mathematics, KSOU, Mysuru-06

4. Dr. Chandru Hegde Member

Assistant Professor, DoS in Mathematics,
Mangalagangotri, Mangaluru.
COURSE WRITER
Dr. Prathiba R J Block 1 to Block 8
Associate Professor, DoS Computer Science (Block I – II)
JSS Technology University, Mysuru. (Unit 1 to Unit 8)

ii
COURSE EDITOR
Prof. PradeepKumar R
Assistant Professor
Department of Mathematics
GSSSIETW, Mysuru -06
COPYRIGHT
The Registrar
Karnataka State Open University
Mukthagangothri, Mysuru-570006
Developed by the Department of Studies in Mathematics under the guidance of Dean
(Academic), KSOU, Mysuru.
Karnataka State Open University, 2024.
All rights reserved. No part of this work may be reproduced in any form or any other means,
without permission in writing from the Karnataka State Open University.
Further information on the Karnataka State Open University Programmes may be obtained from
the University’s Office at Mukthagangothri, Mysuru – 570 006.

iii
KARNATAKA STATE OPEN UNIVERSITY

Mukthagangothri, Mysore- 570 006, INDIA

Fourth Semester [Link]. Mathematics

MMSEC-2: ALGORITHMS AND COMPUTATIONS

Dr. R. J. PRATHIBHA
Associate Professor
Department of Information Science and Engineering
J S S Science and Technology University,
Mysore-570 006, INDIA
SKILL ENHANCEMENT COURSE-2

FOR FOURTH SEMESTER POST GRADUATION STUDENTS

(Offered from Department of Mathematics)

COURSE CODE: MMSEC-2

COURSE TITLE: ALGORITHMS AND COMPUTATIONS
CREDITS: 02

Block-I: Introduction to Computers, Flowcharts, Algorithms and their features,

Languages, Types of language and translators. Numerical Algorithms - Solving
a simultaneous system of linear equations using iterative and direct methods.
Interpolation algorithms - equal, unequal intervals, central difference and inverse
interpolation. Numerical differentiation and integration and their errors
calculations.

Block-II: Graph theoretical algorithms - Connectivity, finding shortest path

between two vertices, enumeration of all paths, construction of minimum
spanning tree, cutest, cut vertex, coding and decoding. Computation - Algorithms
complexities, strategies, Divide and conquer, greedy technique, Introduction to
NP hard problems.
TABLE OF CONTENTS

BLOCK I

Unit-1. Introduction to Computers, Flowcharts, Algorithms and Their Features, Languages,

Types of Language and Translators.
Unit-2. Numerical Algorithms - Solving a simultaneous system of linear equations using
iterative. Solving a simultaneous system of linear equations direct methods.
Unit-3. Interpolation Algorithms - Equal, Unequal Intervals, Central Difference and Inverse
Interpolation
Unit-4. Numerical differentiation and integration and their errors calculations (not yet
obtained).

BLOCK II

Unit-5. Graph Theoretical Algorithms - Connectivity, Finding Shortest Path Between Two
Vertices, Enumeration of all Paths.
Unit-6. Construction of Minimum Spanning Tree, Cutest, Cut Vertex, Coding and Decoding.
Unit-7. Numerical Algorithms - Solving A Simultaneous System of Linear Equations Using
Iterative. Solving a Simultaneous System of Linear Equations Direct Methods.
Unit-8. Greedy Technique, Introduction to NP Hard Problems
Preface
These notes are intended to serve as text for the course Algorithms and Computations for the
fourth Semester Course of [Link]., Degree in Mathematics offered by Karnataka State Open
University (KSOU), Mysore. This notes covers the topics of introduction to computers,
interpolation algorithms, graph theoretical algorithms and algorithms complexities and
strategies at the post-graduate level spread out in two blocks, each block consists of four Units.
There are no prerequisites except some basic knowledge of computers and mathematics which
are usually covered at the college level.

The first Block on Introduction to Computers and Interpolation Algorithms cover the basics of
computers and different interpolation algorithms to solve simultaneous system of linear
equations using iterative and direct methods.

The second Block on Graph Theoretical Algorithms and their Complexities covers the
construction of minimum spanning tree, computation of space and time complexities of
different algorithms and strategies.

These notes are intended for self-study. Motivations are given at a number of places, each unit
contains definitions, introduction, concepts, algorithms, equations and illustrated with
numerous examples for a better understanding of the topics. Exercises are given at the end of
each unit for practice. I thank the authorities of the Karnataka State Open University (KSOU)
for giving me this opportunity to author these notes.
BLOCK- I
Unit-1. Introduction to Computers, Flowcharts, Algorithms and Their
Features, Languages, Types of Language and Translators.

1. Introduction to Computers
2. Functional Units of Computer
2.1 Categories of Computers
3. Flowcharts
3.1 Introduction
3.2 Symbols Used in Flowchart
3.3 Features of Flowcharts
4. Algorithms
4.1 Introduction
4.2 Features of Algorithms
5. Computer Languages
5.1 Introduction
5.2 Types of Computer Languages
6. Translators
6.1 Introduction
6.2 Types of Translators
7. Summary
8. Keywords
9. Assessment Questions
10. References

1
OBJECTIVES

After studying this unit the student will be able to:

 Describe the functionalities of major blocks of a computer.

 Write flowcharts and algorithms to given problem statement.
 Describe the features of flowcharts and algorithms.
 Distinguish among different types of computer languages.
 Explain the need of different types of translators in computer programming.

1. Introduction to Computers

Computer is an electronic machine designed for processing the input data based on the given
instructions and provides the output as per user’s requirement. A computer comprises of both
hardware and software. Hardware is any element of a computer that is physically present. This
includes monitor, keyboard and also the devices that are present inside the computer like
microchips and hard drives. Software is a set of programs that are used make the computer to
work and to solve problems. Software that is used to operate and control the functionalities of a
computer is called system software and software also called application that is developed to
perform some specific task is called application software.

2. Functional Units of Computer

The computer system contains three main functional units for its operation. They are viz.,i) input
unit, ii) Central processing unit and iii) Output unit. The block diagram of computer is shown in
Figure 1.1.

2
Arithmetic Logic Unit

Control Unit

Input Unit Output Unit

Memory Unit

Figure 1.1: Block Diagram of a Computer

The functionalities of each unit of computer are listed below.

I. Input Unit:
Accepts data and instructions from the user and then converts the input data to
computer understandable form. Sends information or instructions or commands to the
computer. The data received from the input unit is immediately stored in main
memory and then processed based on the given instructions

Examples: Keyboard, Mouse, Light pen, Joystick, Optical Character Recognizer,

Magnetic Ink Character Recognizer and Optical Mark Recognizer.

II. Central Processing Unit (CPU):

The CPU is also called brain of computer. It performs all calculations and makes
decisions based on the instructions. It also controls and co-ordinates all units of
computer. The CPU has the following sub-systems.

(i) Control unit

(ii) Arithmetic and Logical Unit (ALU)
(iii) Memory unit
(a) Primary storage
(b) Secondary storage.

3
(i) Control unit:

The control unit instructs the computer to carry out program instructions. It directs the
flow of data between memory and arithmetic logical unit. The input unit does not
know when to receive data and where to put the data in the storage unit after
receiving it similarly, the control unit instructs the input unit where to store the data
after receiving it from the user. In the same way, it controls the flow of instructions
and data from the storage unit to Arithmetic and Logic Unit during program
execution.

(ii) Arithmetic and Logical Unit (ALU):

Arithmetic and logical unit performs all the arithmetic and logical operations. The
basic arithmetic operations are like addition, subtraction, multiplication and division,
the logical operations are AND, OR and NOT.

(iii) Memory unit

Memory is the part of computer which holds data and instructions. Memory can be
divided into primary memory and secondary memory.

(a) Primary storage: The primary memory is also known as main memory,
system memory, internal, temporary or Random Access Memory (RAM) that stores
and access information very fast usually in the order of nano seconds. Primary storage
is installed on the main computer board (motherboard). This is generally used to hold
the program being currently executed in the computer, the data being received from
the input unit, the intermediate and final results of the program.

(b) Secondary storage: The secondary storage is also known as Auxiliary

Storage to store several programs, documents, databases etc. The program that we

4
want to run on the computer is first transferred to the primary memory. Similarly,
after running the program if need to save the result, we will transfer them to the
secondary storage. The secondary memory is slower and cheaper than the primary
memory. Some of the commonly used secondary memory devices are Floppy
diskette, Hard disk, Magnetic disks, Tapes, pen drives, etc.

III. Output unit:

Devices that are used to get the response or result of a process from computer is
called output unit. The output unit of a computer provides the information and results
of a computation to the outside world. Examples for output devices are Printer,
Plotter, Visual Display Unit (VDU) or monitor.

2.1 Categories of Computers

Computers can be broadly categorized into four types based on their processing speeds and their
capacity to store data.

i) Supercomputers: Supercomputers are high-capacity computers that cost millions of

dollars and are used for doing research like weather forecasting, satellite data
analysis, etc.
ii) Mainframe Computers: Less powerful than supercomputers. Mainframe computers
are fast, large-capacity computers. Mainframes are used by large organizations,
banks, airlines, universities.
iii) Minicomputers: Microcomputers have lesser processing speeds and data-storing
capacities; hence, they have been used by medium-sized companies for specific
purposes, such as accounting.
iv) Microcomputers: Microcomputers are small computers that can fit on a desktop.
Microcomputers are of two types: personal computers and workstations.

5
3. Flowcharts

3.1 Introduction

A flowchart can be defined as a visual or pictorial representation of an algorithm using symbols

like rectangle, parallelogram, arrows, and connecting lines. The rectangles are used to represent
process, diamonds for decision points, arrows for flow or direction, and ovals for start and end
points. Flowchart provides a sequence of operations in a program or process for better
understanding of complex processes.

3.2 Symbols used in Flowchart

The symbols used while writing flowchart are given in Table 1.1. The descriptions for each
symbol are also given for better understanding.

Symbol Symbol Name Description

Flow Lines Used to connect symbols

Terminal Used to start, pause or halt in the program

logic
Input/Output Represents the information entering or
leaving the system
Processing Represents the arithmetic and logical
instructions
Decision Represents a decision to be made

Connector Used to join different flow lines

Sub Function Used to call a function

6
Example 1: Flowchart to print addition of 2 numbers.

Start

Input A, B

Sum = A + B

Print Sum

Stop

Figure 1.2 Flowchart to add two numbers

Example 2: Flowchart to check whether the given number is positive or negative.

Start

Input N

If(N/2)=0

Yes No

Even Number Odd Number

Stop

Figure 1.3 Flowchart to check for positive or negative number

7
3.3 Features of Flowcharts

 Flowcharts provide a structured approach to problem-solving and process design also

help in divide the complex problems into smaller, manageable steps.
 Flowcharts provide a visual representation, making it clear understand the flow of control
and logic of a process or program.
 Flowcharts help in identifying and eliminating errors or inefficiencies in a process and
serve as valuable tools for communication and collaboration between individuals or
teams working on the same problem or project.

4. Algorithms

4.1 Introduction

An algorithm is a step-by-step procedure to solve a specific problem. It is well-defined and

unambiguous sequence of instructions that takes input data, performs computations or
operations, and produces an output. They should be clear and understandable, allowing others to
comprehend and follow the steps easily. Algorithms should be correct, providing the desired
result for all valid inputs, and handle error conditions gracefully. Algorithms can be expressed in
various forms, including natural language, pseudocode, or programming languages.

Example 1: Algorithm to add two numbers.

Step 1: Start.
Step 2: Declare three variables: num1, num2 and sum.
Step 3: Read the first number (num1) from the user.
Step 4: Read the second number (num2) from the user.
Step 5: Add num1 and num2 i.e. (sum = num1 + num2)

Example 2: To check the given input number is odd or even.

Step 1: Start
Step 2: Read N
Step 3: R=N% R.

8
Step 4: If R = 0 Then go to Step 6
Step 5: Print “N is odd” go to step 7
Step 6: Print “N is even”
Step 7: Stop

4.2 Features of Algorithms

 Algorithms provide a precise and detailed set of instructions, enabling implementation of

a solution in programming language.
 Algorithms provide a structured approach to problem-solving and process design also
help in divide complex problems into smaller steps.
 An algorithm is a set of well-defined instructions to solve a specific problem. It takes
input and produces the desired output.

5. Computer Languages

5.1 Introduction
Computer languages are the languages designed and used for communication with computers
through programs. Programs contain set of instructions written using computer languages to
solve problems. Computer languages help the humans to write programs that are easily
understandable and by computer.

5.2 Types of Computer languages

Computer languages are classified into low-level languages and high-level languages as shown
in Figure 1.4. A brief description about each type of computer language is given below.

9
Computer
Languages

Low Level High Level

Language Language

Assembly
Machine Language
Language

Figure 1.4 Different Types of Computer Languages

i) Low-Level Languages: Low-Level Computer Programming languages are easily

understood by computers however it is more difficult for humans to understand and use.
These languages include machine language and assembly language. A brief description
about these low-level languages is given below.

a) Machine language: Machine language consists of binary digits (0s and 1s) that
directly represent the computer's instructions. It is a machine dependent language.

b) Assembly language: Assembly language uses mnemonics and symbols to

represent machine instructions, making it slightly easier to understand by the
humans. It is a machine dependant language.

ii) High-Level Languages: High-level languages are programming languages that are
more human-readable, understandable and easier to use than low-level languages. They
use natural language elements and syntax to express algorithms and instructions. High-
level languages include languages like Python, Java, C, C++, and JavaScript. These
languages provide built-in functions and libraries, making it easier to solve complex
problems and perform various tasks.

10
6. Translators

6.1 Introduction

Translators are software programs that convert code written in one programming
language into machine language form that can be understood and executed by a
computer. It is easy to write computer programs using higher level language because it
uses normal English language. However, these programs cannot be understood by the
computer for processing, because it can understand only the machine language. Hence
there is a need for translator to translate programs written in higher level or assembly
language to machine language.

6.2 Types of Translators

Translators can be classified into three types: assemblers, interpreters and compilers as
shown in Figure 1.5. A brief explanation about each type of translator is given below.

Translators

Assemblers Interpreters Compilers

Figure 1.5 Types of Translators

a) Assemblers: Assemblers convert assembly language code into equivalent machine

code. Generally, assemblers are used to develop software that needs to interact directly
with the computer's hardware. The block diagram of an assembler is shown in Figure 1.6.

(Assembly Object Code

Language) Assembler
(Machine
Language)
11
Figure 1.6 Block diagram of Assembler

b) Interpreters: Interpreters execute instructions directly from the source code line by
line, without translating the entire program before hand. They read and execute the code
in a step-by-step manner, providing immediate results and feedback. Python and
JavaScript are examples of languages that typically use interpreters for execution. The
block diagram of an interpreter is shown in Figure 1.7.

Source Code (high

Interpreter Executable code
level language)

( Get next
instruction

Figure 1.7 Block diagram of an Interpreter

c) Compilers: Compilers translate entire programs written in a high-level language into

machine code before execution. The entire source code is converted into an executable
file, which can be run independently of the compiler. Common examples of compilers
include the GNU Compiler Collection (GCC) for C/C++ and the Java Development Kit
(JDK) for Java. The block diagram of a compiler is shown in Figure 1.8.

Entire Source
Executable code
Code (High Level Compiler
(Machine Language)
Language)

Figure 1.8 Block diagram of Compiler

12
7. Summary

Computer is an electronic device that takes input from the user and process it based on the given
instruction and provides the desired output as a result. A flowchart is a picture of the separate steps
of a process in sequential order. An algorithm is a set of finite rules or instructions to be followed in
calculations or other problem-solving operations. A programming language is a system of
notation for writing computer programs. Programming languages are described in terms of their
syntax and semantics, usually defined by a formal language. A translator is a programming
language processor that converts a computer program from one language to another. It takes a
program written in source code and converts it into machine code. It discovers and identifies the
error during translation.

8. Keywords
Computer, Flowchart, Algorithm, Assembler, Interpreter, Compiler.

9. Assessment Questions
1. With a neat block diagram, explain the functionalities of a computer.
2. Write flowchart and algorithms for the following
i) To compute simple and compound interest
ii) To computer roots of a quadratic equation
iii) To find the area of triangle, rectangle, square, circle.
3. Discuss different types of computer programming languages
4. Distinguish among assembler, interpreter and compiler
5. Explain the need of translators in computers

10. References
1. "Introduction to Computers" by Peter Norton
2. "Computer Concepts" by June Jamrich Parsons
3. Computing Fundamentals: Introduction to Computers" by Faithe Wempen
4. Introduction to Computing Systems: From Bits and Gates to C and Beyond" by Yale N. Patt and
Sanjay J. Patel

13
Unit – 2: Numerical Algorithms - Solving a simultaneous system of linear
equations using iterative. Solving a simultaneous system of linear equations
direct methods.

1. Numerical Algorithms: Solving a simultaneous system of linear equations

1.1 Introduction
1.2 Row operations
1.3 Different Methods for Solving Linear System of Equations
2. Solving A Simultaneous System of Linear Equations Using Direct Methods
2.1 Gaussian Elimination Method
2.2 Gauss Jordon Elimination Method
3. Solving A Simultaneous System of Linear Equations Using Iterative Methods
3.1 Jacobi Iterative Method
3.2 Gauss-Seidel Method
4. Summary
5. Keywords
6. Assessment Questions
7. References

14
OBJECTIVES

After studying this unit the student will be able to:

 Perform row operations on augmented matrix to simplify the matrix.

 Solve a simultaneous system of linear equations using direct methods: Gaussian
elimination and Gauss Jordon Methods.
 Solve a simultaneous system of linear equations using iterative methods: Jacobi method
and Gauss-Seidel method.

1. Numerical Algorithms: Solving a simultaneous system of linear equations

1.1 Introduction

A linear equation is an equation in which the highest power of the variable is always 1. It is also
called a one-degree equation. The standard form of a linear equation in one variable is of the
form Ax + B = 0. Here, x is a variable, A is a coefficient and B is constant. Simultaneous
equations are two or more algebraic equations that share variables such as x and y. They are
called simultaneous equations because the equations are solved at the same time. The number of
variables in simultaneous equations must match the number of equations for it to be solved.

A system of n-linear equations in n-unknowns has a general form

𝑏11 𝑋1 + 𝑏12 𝑋2 + 𝑏13 𝑋3 + ⋯ + 𝑏1𝑛 𝑋𝑛 = 𝑑1

𝑏21 𝑋1 + 𝑏22 𝑋2 + 𝑏23 𝑋3 + ⋯ + 𝑏2𝑛 𝑋𝑛 = 𝑑2
} … … … … … … (1)
⋮
𝑏𝑛1 𝑋1 + 𝑏𝑛2 𝑋2 + 𝑏𝑛3 𝑋3 + ⋯ + 𝑏𝑛𝑛 𝑋𝑛 = 𝑑𝑛

where

d1, d2,- - -,dn are given real constants in the system.

n- Unknowns with n- variable or unknown X1, X2,- - -,Xn.

bᵢ are the constants.

15
The solution for the linear equation can be classified into the following ways;

 If a system of linear equations solved and unique value for X1,X2, - - -,Xn are
obtained then, the system is consistent and independent.
 If system has no definite solution then, it is said to be inconsistent.
 If there are infinitely many solutions to the linear system, it is said to be consistent
but dependent.

1.2 Row operations

Row operations can refer to the arithmetic operations such as addition, subtraction,
multiplication, division on elements of row in a matrix. The purpose of row operations on
augmented matrices is to simplify the matrices as much as possible to solve for the values of
variables in the system of equations they represent.

The following row operations can be performed on the augmented matrix of a system produce
the augmented matrix of an equivalent system

• Rows interchange.

• Multiplication of elements of row by a nonzero constant.

• Replace a row by the sum of itself and a constant multiple of another row of the matrix.

For these row operations, we will use the following notations.

a) Ri ↔ Rj : Interchange of ith row and jth row.

b) αRi : Replace ith row with α times ith row.
c) Ri + αRj means: Replace ith row with the sum of ith row and α times jth row.

1.3 Different Approaches for Solving Linear System of Equations

The different approaches used for the computation of linear system of equations is given in
Figure 1.1.

16
Methods to solve

Direct Methods Iterative Methods

Gauss's
Gauss Jordan Crout's Gauss - Jacobi Gauss - Seidel Relaxation
Elimination
Method Method Method Method Method
Method

Figure 1.1 Different Methods for Solving Linear System of Equations

2. Solving a Simultaneous System of Linear Equations Using Direct Methods

This section covers direct or exact methods for solving linear systems of equations. Direct
methods are used to find the exact solution to a simultaneous system of linear equations.

Commonly used direct methods are namely i) Gaussian elimination method and Gauss Jordon
Method are explained below.

2.1 Gaussian Elimination Method

This is a direct method based on the elimination of the unknowns by combining equations such
that the n equations in n unknowns are reduced to an equivalent upper triangular system which
can be solved by back substitution.

Consider the following n linear equation in n unknowns,

𝑎11 𝑎12 … 𝑎1𝑛 𝑥1 𝑏1

𝑎21 𝑎22 … 𝑎2𝑛 𝑥2 𝑏2
[ … … … … ]*[ ⋮ ] =[ ⋮ ]
𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑛 𝑥𝑛 𝑏𝑛

The system is equivalent to AX = B

17
Where:

𝑎11 𝑎12 … 𝑎1𝑛 𝑥1 𝑏1

𝑎21 𝑎22 … 𝑎2𝑛 𝑥2 𝑏2
A=[ … … … … ], X = [ ⋮ ]and B=[ ⋮ ]
𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑛 𝑥𝑛 𝑏𝑛

Form the augmented matrix form the matrices

𝑎11 𝑎12 … 𝑎1𝑛 ⋮ 𝑏1

𝑎 𝑎22 … 𝑎2𝑛 ⋮ 𝑏2
[ 21 ]
… … … … ⋮ …
𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑛 ⋮ 𝑏𝑛

Dividing the first equation (row) by a11 gives:

− −
1 𝑎12 … 𝑎1𝑛 ⋮ 𝑏1−
𝑎 𝑎22 … 𝑎2𝑛 ⋮ 𝑏2
[ 21 ]
… … … … ⋮ …
𝑎𝑛1 𝑎𝑛2 … 𝑎𝑛𝑛 ⋮ 𝑏𝑛

Multiplying the first row by −𝑎𝑖1 for i -2,…..,n then adding to the ith row to eliminates the first
column except the elements in first row.

− −
1 𝑎12 … 𝑎1𝑛 ⋮ 𝑏1−
− −
0 𝑎22 … 𝑎2𝑛 ⋮ 𝑏2−
[ ]
… … … … ⋮ …
− −
0 𝑎𝑛2 … 𝑎𝑛𝑛 ⋮ 𝑏𝑛−

−
Divide the second row by 𝑎22 gives,

− −
1 𝑎12 … 𝑎1𝑛 ⋮ 𝑏1−
=
0 1 … 𝑎2𝑛 ⋮ 𝑏2=
[ ]
… … … … ⋮ …
− −
0 𝑎𝑛2 … 𝑎𝑛𝑛 ⋮ 𝑏𝑛−

18
−
Multiplying the second row by −𝑎𝑖2 for i = 3,….n then adding to the ith row to eliminates the
second column except the elements in first & second row.

− −
1 𝑎12 … 𝑎1𝑛 ⋮ 𝑏1−
=
0 1 … 𝑎2𝑛 ⋮ 𝑏2=
[ ]
… … … … ⋮ …
=
0 0 … 𝑎𝑛𝑛 ⋮ 𝑏𝑛=

This process is continued until the last row (row n) becomes in the following form (0 0 ….1 ⋮ c)

Note: You have to avoid a zero divisor in the position in each stage by interchanging rows.

Once the process is completed, the matrix becomes as the following triangular form:

1 𝑢12 … 𝑢1𝑛 ⋮ 𝑐1
0 1 … 𝑢2𝑛 ⋮ 𝑐2
[ ]
… … … … ⋮ …
0 0 … 1 ⋮ 𝑐𝑛

The unknowns are then determined by back substation i.e.;

𝑥𝑛 = 𝑐𝑛
𝑥𝑛−1 = 𝑐𝑛−1 − 𝑢𝑛−1 ∗ 𝑥𝑛

⋮
𝑥1 = 𝑐1 − 𝑢12 ∗ 𝑥2 − … − 𝑢1𝑛 ∗ 𝑥𝑛

Example 1: Solve the following systems by Gauss- Elimination method:

x + 2y + z = 3
2x + 3y +3z = 10
3x-y + 2z =13

Solution:

The given system is equivalent to

19
1 2 1 𝑥 3
[ 2 3 3 ] [ 𝑦 ] =[ 10 ]
3 −1 2 𝑧 13

1 2 1 | 3
(A,B) = [ 2 3 3 | 10 ]
3 −1 2 | 13

Now, we will make the matrix an upper triangular

1 2 1 | 3 𝑅2 − 3𝑅1 →𝑅2
𝑅3 − 3𝑅1 →𝑅3
[2 3 3 | 10 ] →
3 −1 2 | 13

𝑅2⁄
1 2 1 | 3 −1 →𝑅2
𝑅2 − 7𝑅2 →𝑅3
[ 0 −1 1 | 4 ] →
0 −7 −1 | 4

Now take 𝑏22 = -1 as the pivot and 𝑏32 as make as zero

1 2 1 | 3 𝑅3⁄ 1 2 1 | 3
−8 →𝑅3
[0 1 −1 | −4 ] → [0 1 −1 | −4 ]
0 0 −8 | −24 0 0 1 | 3

From this, we get

x + 2y + z = 3,
y - z = -4,
z=3
y = -4 + z = -4 + 3 = -1
x = 3 – 2y –z = 3 – 2 * -1-3 = 2

Hence the solution is x = 2, y = -1 and z = 3.

2.2 Gauss Jordon Elimination Method

The steps involved in solving a system of linear equations using Gauss-Jordan elimination
method is given below.
20
Step 1: Write the augmented matrix.
Step 2: Apply row operations to transform the augmented matrix into Reduced Row Echelon
Form (RREF) using the following strategy.
(a) The rows (if any) consisting entirely of zeros are grouped together at the bottom of the
matrix.
(b) In each row that does not consist entirely of zeros, the leftmost nonzero element is a 1.
(c) Each column that contains a leading 1 has zeros in all other entries.
(d) The leading 1 in any row is to the left of any leading 1’s in the rows below it.
Step 3: Stop process in step 2 if you obtain a row whose elements are all zeros except the last
one on the right. In that case, the system is inconsistent and has no solutions. Otherwise, finish
step2 and read the solutions of the system from the final matrix.

Note: When doing step 2, row operations can be performed in any order. Try to choose row
operations so that as few fractions as possible are carried through the computation. This makes
calculation easier when working by hand.

Example 2: Solve the following system by using the Gauss-Jordan elimination method.

𝑥+𝑦+𝑧 =5
{ 2𝑥 + 3𝑦 + 5𝑧 = 8
4𝑥 + 5𝑧 = 2

Solution: The augmented matrix of the system is the following.

1 1 1 5
[ 2 3 5 |8 ]
4 0 5 2

Now perform row operations until we obtain a matrix in reduced row echelon form

1 1 1 5 𝑅2−2𝑅1 1 1 1 5
[ 2 3 5| 8 ]→ [ 0 1 3 | −2 ]
4 0 5 2 4 0 5 2

21
𝑅3 −4𝑅1 1 1 1 5
→ [ 0 1 3 −2 ]
|
0 −4 1 −18

𝑅3 + 4𝑅2 1 1 1 5
→ [ 0 1 3 | −2 ]
0 0 13 −26

1
𝑅 1 1 1 5
13 3
→ [ 0 1 3 | −2 ]
0 0 1 −2

𝑅2 + 3𝑅3 1 1 1 5
→ [ 0 1 0 | 4 ]
0 0 1 −2

𝑅1 + 𝑅3 1 1 1 7
→ [ 0 1 0 | 4 ]
0 0 1 −2

𝑅1 − 𝑅2 1 1 1 3
→ [ 0 1 0 | 4 ]
0 0 1 −2

From the final matrix, we can read the solution of the system. It is

x = 3; y = 4; z = -2

22
3. Solving a Simultaneous System of Linear Equations Using Iterative
Methods

Iterative methods are used to approximate the solution to a simultaneous system of linear
equations. Iterative methods are techniques used to approximate solutions to systems of linear
equations. These methods start with an initial guess and iteratively improve the solution until a
certain convergence criterion is met. Iterative methods are useful with large systems of
equations, as they can be more computationally efficient than direct methods. Iterative methods
are useful with large systems of equations, as they can be more computationally efficient than the
direct methods. Iterative methods are particularly useful for large sparse systems where direct
methods like Gaussian elimination may be computationally expensive or infeasible. Some well-
known iterative methods like i) Jacobi method and ii) Gauss-Seidel method are discussed below.

3.1 Jacobi Iterative Method

The Jacobi iterative method is an iterative algorithm used for finding the solutions for the system
of linear equations, which is diagonally dominant. In this method, an approximate value is filled
in for each diagonal element. This method makes two assumptions:

Assumption 1: The given equations have a unique solution.

𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ 𝑎1𝑛 𝑥𝑛 = 𝑏1

𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ 𝑎2𝑛 𝑥𝑛 = 𝑏2
⋮ ⋮ ⋮
𝑎𝑛1 𝑥1 + 𝑎𝑛2 𝑥2 + ⋯ 𝑎𝑛𝑛 𝑥𝑛 = 𝑏𝑛

Assumption 2: The main diagonal elements of matrix A are non-zeros.

Follow the steps given below to get the solution of a given system of equations.

Step 1: In this method, solve the equations to get the values x1, x2,…. xn.

23
To get the value of x1, solve the first equation using the formula given below:

1
𝑥1 = (𝑏 − 𝑎12 𝑥12 − 𝑎13 𝑥3 − ⋯ − 𝑎1𝑛 𝑥𝑛 ) … . . (1)
𝑎11 1

To get the value of 𝑥2 , solve the second equation using the formula as:

1
𝑥2 = (𝑏 − 𝑎21 𝑥2 − 𝑎23 𝑥3 − ⋯ − 𝑎2𝑛 𝑥𝑛 ) … . . (2)
𝑎22 2

Similarly, to find the value of 𝑥𝑛 , solve the nth equation

1
𝑥𝑛 = (𝑏 − 𝑎𝑛1 𝑥2 − 𝑎𝑛2 𝑥3 − ⋯ − 𝑎𝑛,𝑛−1 𝑥𝑛−1 ) … . . (𝑛)
𝑎𝑛𝑛 𝑛

Step 2; Now, make initial guess of the solution as:

(0) (0) (0) (0)

𝑥 (0) = ( 𝑥1 , 𝑥2 , 𝑥3 , … … , 𝑥𝑛 )

Step 3: Substitute the values obtained in the previous step in equation (1), i.e., into the right hand
side of the rewritten equations in step (1) to obtain the first approximation as:

(1) (1) (1) (1)

𝑥 (1) = ( 𝑥1 , 𝑥2 , 𝑥3 , … … , 𝑥𝑛 )

Step 4: In the same way as done in the previous step, compute

(𝑘) (𝑘) (𝑘) (𝑘)

𝑥 (𝑘) = (𝑥1 , 𝑥2 , 𝑥3 , … … , 𝑥𝑛 ); 𝑘 = 1,2,3 … ….

Example 3: Solve Equations 2x+5y=21,x+2y=8 using Gauss Jacobi method

Solution: 2x+5y=21; x+2y=8
From the above equations
xk+1=12(21-5yk)
yk+1=12(8-xk)
Initial \Gauss (x,y)=(0,0)

24
Solution steps are:

1st Approximation
x1=1/2[21-5(0)]=1/2[21]=10.5
y1=1/2[8-(0)]=1/2[8]=4

2nd Approximation
x2=1/2[21-5(4)]=1/2[1]=0.5
y2=1/2[8-(10.5)]=1/2[-2.5]=-1.25

3rd Approximation
x3=1/2[21-5(-1.25)]=1/2[27.25]=13.625
y3=1/2[8-(0.5)]=1/2[7.5]=3.75

4th Approximation
x4=1/2[21-5(3.75)]=1/2[2.25]=1.125
y4=1/2[8-(13.625)]=1/2[-5.625]=-2.8125

5th Approximation
x5=1/2[21-5(-2.8125)]=1/2[35.0625]=17.5312
y5=1/2[8-(1.125)]=1/2[6.875]=3.4375

6th Approximation
x6=1/2[21-5(3.4375)]=1/2[3.8125]=1.9062
y6=1/2[8-(17.5312)]=1/2[-9.5312]=-4.7656

7th Approximation
x7=1/2[21-5(-4.7656)]=1/2[44.8281]=22.4141
y7=1/2[8-(1.9062)]=1/2[6.0938]=3.0469

Equations are Divergent...

25
Iterations are tabulated as below

Iteration x y

1 10.5 4

2 0.5 -1.25

3 13.625 3.75

4 1.125 -2.8125

5 17.5312 3.4375

6 1.9062 -4.7656

7 22.4141 3.0469

3.2 The Gauss-Seidel Method

Main idea of Gauss – Seidel is given below.

(𝑘)
With the Jacobi method, the value of 𝑥𝑖 obtained in the kth iteration remain unchanged until the
entire (k+1)th iteration has been calculated. With the Gauss – Seidel method, we use the new
(𝑘+1) (𝑘+1)
values 𝑥𝑖 as soon as they are known. For example, once we have computed 𝑥1 from the
(𝑘+1)
first equation, its value is then used in the second equation to obtain the new 𝑥2 , and so on
Example Derive iteration equations for the Jacobi method and Gauss – Seidal method to solve
5𝑥1 − 2𝑥2 + 3𝑥𝑛 = −1
−3𝑥1 + 9𝑥2 + 𝑥𝑛 = 2
2𝑥1 − 𝑥2 − 7𝑥𝑛 = 3
The Gauss- Seidal Method.

(𝑘)
For each k≥1, generate the components 𝑥𝑖 from 𝑥 𝑘 by 𝑥 (𝑘−1) by

26
𝑖−1 𝑛
(𝑥) 1 (𝑘) (𝑘−1)
𝑥𝑖 = [– ∑(𝑎𝑖𝑗 𝑘𝑗 ) − ∑ (𝑎𝑖𝑗 𝑘𝑗 ) + 𝑏𝑖 ] 𝑓𝑜𝑟 𝑖 = 1,2, … . . 𝑛
𝑎𝑖𝑖
𝑗=1 𝑗=𝑖+1

Namely,

(𝑘) (𝑘−1) (𝑘−1)

𝑎11 𝑥1 = −𝑎12 𝑥2 − ⋯ −𝑎1𝑛 𝑥𝑛 + 𝑏2

(𝑘) (𝑘) (𝑘−1) (𝑘−1)

𝑎21 𝑥1 + 𝑎22 𝑥2 = −𝑎22 𝑥3 − ⋯ −𝑎2𝑛 𝑥𝑛 + 𝑏2

(𝑘) (𝑘) (𝑘)

𝑎𝑛1 𝑥1 + 𝑎𝑛2 𝑥2 + … . 𝑎𝑛𝑛 𝑥𝑛 = 𝑏𝑛

Numerical Algorithm of Gauss - Siedel Method

Input A = [aij ], b, 𝑋0 = x (0) , tolerance TOL, maximum number of iterations N.

Step 1 Set k = 1

Step 2 while ( k ≤ n ) do steps 3 to 6

Step 3 For for i = 1,2, … . n

1 𝑖−1 𝑛
𝑥𝑖 = [– ∑ (𝑎𝑖𝑗 𝑥𝑗 ) − ∑ (𝑎𝑖𝑗 𝑋0 𝑗 ) + 𝑏𝑖 ] ,
𝑎𝑖𝑖 𝑗=1 𝑗=𝑖+1

Step 4 If | | x − 𝑋0 | | < 𝑇𝑂𝐿, 𝑡ℎ𝑒𝑛 𝑂𝑈𝑇𝑃𝑈𝑇 ( x1 , x2 , x3 , … … . xn );

STOP

Step 5 Set k = k + 1

Step 6 For for i = 1,2, … . n

Set 𝑋0 𝑖 = x1

Step 7 OUTPUT ( x1 , x2 , x3 , … … . xn );
STOP
27
Example 4: Solve Equations 𝒙 + 𝒚 + 𝒛 = 𝟕, 𝒙 + 𝟐𝒚 + 𝟐𝒛 = 𝟏𝟑, 𝒙 + 𝟑𝒚 + 𝒛 = 𝟏𝟑 using
Gauss Seidel Method

Solution:
𝑥+𝑦+𝑧 =7
𝑥 + 2𝑦 + 2𝑧 = 13
𝑥 + 3𝑦 + 𝑧 = 13

The coefficient matrix of the given system is not diagonally dominant.

Hence, we re-arrange the equations as follows, such that the elements in the coefficient matrix
are diagonally dominant.
𝑥+𝑦+𝑧 = 7
𝑥 + 3𝑦 + 𝑧 = 13
𝑥 + 2𝑦 + 2𝑧 = 13
From the above equations
𝑥𝑘+1 = 1/1(7 − 𝑦𝑘 − 𝑧𝑘 )
𝑦𝑘+1 = 1/3(13 − −𝑧𝑘)
𝑧𝑘 + 1 = 1/2(13 − 𝑥𝑘 + 1 − 2𝑦𝑘 + 1)

Initial gauss (x,y,z)=(0,0,0)

Solution steps are:
1st Approximation
x1=1/1[7-(0)-(0)]=1/1[7]=7
y1=1/3[13-(7)-(0)]=1/3[6]=2
z1=1/2[13-(7)-2(2)]=1/2[2]=1

2nd Approximation
x2=1/1[7-(2)-(1)]=11[4]=4
y2=1/3[13-(4)-(1)]=13[8]=2.6667
z2=1/2[13-(4)-2(2.6667)]=12[3.6667]=1.8333

28
3rd Approximation
x3=1/1[7-(2.6667)-(1.8333)]=1/1[2.5]=2.5
y3=1/3[13-(2.5)-(1.8333)]=1/3[8.6667]=2.8889
z3=1/2[13-(2.5)-2(2.8889)]=1/2[4.7222]=2.3611

4th Approximation
x4=1/1[7-(2.8889)-(2.3611)]=1/1[1.75]=1.75
y4=1/3[13-(1.75)-(2.3611)]=1/3[8.8889]=2.963
z4=1/2[13-(1.75)-2(2.963)]=1/2[5.3241]=2.662

5th Approximation
x5=1/1[7-(2.963)-(2.662)]=1/1[1.375]=1.375
y5=1/3[13-(1.375)-(2.662)]=1/3[8.963]=2.9877
z5=1/2[13-(1.375)-2(2.9877)]=1/2[5.6497]=2.8248

6th Approximation
x6=1/1[7-(2.9877)-(2.8248)]=1/1[1.1875]=1.1875
y6=1/3[13-(1.1875)-(2.8248)]=1/3[8.9877]=2.9959
z6=1/2[13-(1.1875)-2(2.9959)]=1/2[5.8207]=2.9104

7th Approximation
x7=1/1[7-(2.9959)-(2.9104)]=1/1[1.0938]=1.0938
y7=1/3[13-(1.0938)-(2.9104)]=1/3[8.9959]=2.9986
z7=1/2[13-(1.0938)-2(2.9986)]=1/2[5.909]=2.9545

8th Approximation
x8=1/1[7-(2.9986)-(2.9545)]=1/1[1.0469]=1.0469
y8=1/3[13-(1.0469)-(2.9545)]=1/3[8.9986]=2.9995
z8=1/2[13-(1.0469)-2(2.9995)]=1/2[5.954]=2.977

29
9th Approximation
x9=1/1[7-(2.9995)-(2.977)]=1/1[1.0234]=1.0234
y9=1/3[13-(1.0234)-(2.977)]=1/3[8.9995]=2.9998
z9=1/2[13-(1.0234)-2(2.9998)]=1/2[5.9769]=2.9884

10th Approximation
x10=1/1[7-(2.9998)-(2.9884)]=1/1[1.0117]=1.0117
y10=1/3[13-(1.0117)-(2.9884)]=1/3[8.9998]=2.9999
z10=1/2[13-(1.0117)-2(2.9999)]=1/2[5.9884]=2.9942

11th Approximation
x11=1/1[7-(2.9999)-(2.9942)]=1/1[1.0059]=1.0059
y11=1/3[13-(1.0059)-(2.9942)]=1/3[8.9999]=3
z11=1/2[13-(1.0059)-2(3)]=1/2[5.9942]=2.9971

12th Approximation
x12=1/1[7-(3)-(2.9971)]=1/1[1.0029]=1.0029
y12=1/3[13-(1.0029)-(2.9971)]=1/3[9]=3
z12=1/2[13-(1.0029)-2(3)]=1/2[5.9971]=2.9985

13th Approximation
x13=1/1[7-(3)-(2.9985)]=1/1[1.0015]=1.0015
y13=1/3[13-(1.0015)-(2.9985)]=1/3[9]=3
z13=1/2[13-(1.0015)-2(3)]=1/2[5.9985]=2.9993

14th Approximation
x14=1/1[7-(3)-(2.9993)]=1/1[1.0007]=1.0007
y14=1/3[13-(1.0007)-(2.9993)]=1/3[9]=3
z14=1/2[13-(1.0007)-2(3)]=1/2[5.9993]=2.9996
Solution By Gauss Seidel Method.

30
x=1.0007 ≅ 1; y=3 ; z=2.9996 ≅ 3

Iterations are tabulated as below

Iteration x y z

1 7 2 1

2 4 2.6667 1.8333

3 2.5 2.8889 2.3611

4 1.75 2.963 2.662

5 1.375 2.9877 2.8248

6 1.1875 2.9959 2.9104

7 1.0938 2.9986 2.9545

8 1.0469 2.9995 2.977

9 1.0234 2.9998 2.9884

10 1.0117 2.9999 2.9942

11 1.0059 3 2.9971

12 1.0029 3 2.9985

13 1.0015 3 2.9993

14 1.0007 3 2.9996

4. Summary: Iterative methods provide an approximate solution, while direct methods give
an exact solution. However Iterative methods can be faster for large systems, while direct
methods are better suited for small or moderate-sized systems. The choice between iterative and
direct methods depends on the specific requirements, accuracy needs, and computational
resources available. It's important to note that there are several other numerical algorithms and
methods available for solving simultaneous systems of linear equations, and the choice of
method depends on the characteristics of the problem and the desired outcomes.

31
5. Keywords

Linear equations, Gaussian Elimination, Gauss Jordon, Jacobi Iterative Method, Gauss-Seidel
Method.

6. Assessment Questions

1. Solve the following systems by Gauss- Elimination method.

i) x+2y+3z=6
2x+3y-z=7
3x+2y+9z=14
Solution: x=2.28562, y=0.57142, z=1.00006
ii) x + 2 y + z =3
2x +3 y + 3z=10
3x-y+2z=13
Solution: x=2, y=-1, z=3
2. Solve the following systems by Gauss Jordon method
i) x + 2y - 3z = 2
6x + 3y – 9z = 6
7x + 14y – 21z =13
We obtain a row whose elements are all zeros except the last one on the right. Therefore, we
conclude that the system of equations is inconsistent, i.e., it has no solutions.
ii) 4y + z = 2
2x + 6y – 2z = 3
4x + 8y – 5z =4
We can express the solution of this system as

7 1 1
𝑥= 𝑧, 𝑦= − 𝑧
4 2 4

Since there is no specific value for z, it can be chosen arbitrarily. This means that there are
infinitely many solutions for this system. We can represent all the solutions by using a parameter
t as follows.

32
7 1 1
𝑥 = 𝑧𝑡, 𝑦= − 𝑡, 𝑧=𝑡
4 2 4

Any value of the parameter t gives us a solution of the system, For example,

1
t = 4 gives the solution (𝑥, 𝑦, 𝑧) = (7, − 2 , 4)

−7
t = -2 gives the solution (𝑥, 𝑦, 𝑧) = ( 2 , 1, −2).

3. Solve the following Equations using Gauss Jacobi method

i. 2𝑥 + 5𝑦 = 16
3𝑥 + 𝑦 = 11
Solution:
𝑥 = 2.999874 ≅ 3
𝑦 = 1.999916 ≅ 2

ii. 𝑥 + 𝑦 + 𝑧 = 3; 2𝑥 − 𝑦 − 𝑧 = 3; 𝑥−𝑦+𝑧 =9
Solution: Equations are Divergent...

iii. 𝑥 + 𝑦 + 𝑧 = 7; 𝑥 + 2𝑦 + 2𝑧 = 13; 𝑥 + 3𝑦 + 𝑧 = 13

Solution: Equations are Divergent...

4. Solve Equations 2𝑥 + 𝑦 = 8; 𝑥 + 2𝑦 = 1 using Gauss Seidel method

Solution:
𝑥 = 4.9998 ≅ 5
𝑦 = −1.9999 ≅ −2

7. References

1. V. Rajaraman – Computer Oriented Numerical Methods, Prentice Hall of India, 1980.

2. G. Shankar Rao – Numerical Analysis, Prentice Hall of India, 1985.
3. [Link]

33
Unit - 3. Interpolation Algorithms - Equal, Unequal Intervals, Central
Difference and Inverse Interpolation

1. Interpolation Algorithms
1.1 Introduction
2. Interpolation with Equal Intervals
2.1 Introduction
2.2 Newton’s Forward Interpolation Formula
2.3 Newton–Gregory Backward Interpolation Formula
3. Interpolation with Unequal Intervals
3.1 Introduction
3.2 Newton’s General Divided Differences Formula
4. Central Difference Interpolation
4.1 Introduction
4.2 Gauss Forward Interpolation Formula
4.3 Gauss Backward Interpolation Formula
5. Inverse Interpolation
6. Summary
7. Keywords
8. Assessment Questions
9. References

34
OBJECTIVES

After studying this unit the student will be able to:

 Explain the concept of interpolating functions and their role in estimating values between
known data points.
 Define and explain equal and unequal intervals interpolation techniques.
 Discuss how central difference interpolation is applied to estimate derivatives using
equally spaced data points.
 Define inverse interpolation and its significance in solving inverse problems.

1. Interpolation Algorithms

1.1Introduction

Interpolation algorithms are methods used to estimate values between known data points. They
are essential in various fields such as mathematics, computer science, engineering, and data
analysis. Interpolation can be used to compute the values for equal intervals and unequal Intervals.

2. Interpolation with Equal Intervals

2.1 Introduction
The word interpolation denotes the method of computing the value of function y = f(x) for any
given value of the independent variable x when a set of values of y = f(x) for certain values of x
are given.

The study of interpolation is based on the assumption that there are no sudden jumps in the
values of the dependent variable for the period under consideration. It is also assumed that the
rate of change of figures from one period to another is uniform.

Let y = f(x) be a function which takes the values y0, y1, y2, …, yn, corresponding to the values x0,
x1, x2, …, xn of the independent variable x. If the form of the function y = f(x) is known, we can
very easily calculate the value of y corresponding to any value of x. But in most of the practical

35
problems, the exact form of the function is not known. In such cases the function f(x) is replaced
by a simpler function say φ(x) which has the same values as f(x) for x0, x1, x2, ..., xn. The
function φ(x) is called an interpolating function.

2.2 Newton’s Forward Interpolation Formula

Let 𝑦 = 𝑓(𝑥) be a function which takes the values 𝑦0 , 𝑦1 , 𝑦2 , … , 𝑦𝑛 corresponding to the (𝑛 +

1) values 𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 of the independent variable 𝑥. Let the values of 𝑥 be equally spaced,
i.e.,

𝑥𝑟 = 𝑥0 + 𝑟ℎ , 𝑟 = 0, 1, 2, … , ℎ

where h is the interval of differencing. Let φ(x) be a polynomial of the nth degree in 𝑥 taking the
same values as y corresponding to 𝑥 = 𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 , then, 𝜑(𝑥) represents the continuous
function 𝑦 = 𝑓(𝑥)such that 𝑓(𝑥𝑟 ) = 𝜑(𝑥𝑟 ) for r = 0, 1, 2, …, n and at all other points. The
Newton’s Forward Interpolation Formula is given below.

𝛥𝑦0 𝑢 ( 𝑢 − 1) 2 𝑢(𝑢 − 1) … (𝑢 − 𝑛 + 1) 𝑛
𝜙(𝑥) = 𝑦0 + 𝑢 + 𝛥 𝑦0 + … + 𝛥 𝑦0
1! 2! 𝑛!

𝑥− 𝑥0
Where 𝑢 = ℎ

Example 1: Evaluate y = 𝑒 2𝑥 for x= 0.05 using the following table

x 0.00 0.10 0.20 0.30 0.40

y = 𝑒 2𝑥 1.000 1.2214 1.4918 1.8221 2.255

36
Solution: The difference table is

x y = 𝑒 2𝑥 𝛥y 𝛥2y 𝛥3y 𝛥4y

0.000 1.0000
0.2214
0.10 1.2214 0.0490
0.2704 0.0109
0.20 1.4918 0.0599 0.0023
0.3303 0.0132
0.30 1.8221 0.0731
0.4034
0.40 2.2255

We have x0 = 0.00, x = 0.05, h = 0.1

𝑥−𝑥0 0.05 –0.00

𝑢 = = = 0.5
ℎ 0.1

Using Newton’s forward formula

𝑢(𝑢 + 1) 2 𝑢(𝑢 − 1)(𝑢 − 2) 3

𝑓(𝑥) = 𝑦0 + 𝑢𝛥𝑦0 + 𝛥 𝑦0 + 𝛥 𝑦0
2! 3!
𝑢(𝑢 − 1)(𝑢 − 2)(𝑢 − 3) 4
+ 𝛥 𝑦0 + …
4!

0.5(0.5 + 1) 0.5(0.5 − 1)(0.5 − 2)

𝑓(0.05 ) = 1.000 + 0.5 ∗ 0.2214 + (0.0490) + (0.0109 ) +
2 6

0.5(0.5 − 1)(0.5 − 2)0.5 − 3)

(0.0023)
24

= 1.000 + 0.1107 - 0.006125 +0.000681 – 0.000090 = 1105166

𝑓(0.05) ∼ 1.052

37
2.3 Newton–Gregory Backward Interpolation Formula

Newton’s forward interpolation formula cannot be used for interpolating a value of y near the
end of a table of values. For this purpose, we use another formula known as Newton–Gregory
backward interpolation formula as given below.

𝑢 𝛻 𝑦𝑛 𝑢(𝑢 + 1) 2 𝑢(𝑢 + 1)(𝑢 + 2) 3

𝑓(𝑥) = 𝜙(𝑥) = 𝑦𝑛 + + 𝛻 𝑦𝑛 + 𝛻 𝑦𝑛 +
1! 2! 2!

…
𝑢(𝑢 + 1)(𝑢 + 2) … (𝑢 + 𝑛 − 1) 𝑛
+ 𝛻 𝑦𝑛
𝑛!

Example 2: The following data gives the melting point of an alloy of lead and zinc, where t is
the temperature in degrees’ c and P is the percentage of lead in the alloy

P 40 50 60 70 80 90
t 180 204 226 250 276 304

Find the melting point of the alloy containing 84 percent lead.

Solution: The value of 84 is near the end of the table, therefore we use the Newton’s backward
interpolation formula. The difference table is given below.

P t 𝜵 𝜵2 𝜵3 𝜵4 𝜵5
40 184
20
50 204 2
22 0
60 226 2 0
24 0 0
70 250 2 0
26 0
80 276 2
28
90 304

38
We have 𝑥𝑛 = 90, 𝑥 = 94, ℎ = 10, 𝑡𝑛 = 𝑦𝑛 = 304, 𝛻𝑡𝑛 = 𝛻 2 𝑦𝑛 = 2 , 𝑎𝑛𝑑

𝑓ℎ = 𝑓ℎ

𝛻 3 𝑦𝑛 = 𝛻 4 𝑦𝑛 = 𝛻 5 𝑦𝑛 = 0

𝑥− 𝑥𝑛 84−90
𝑢= = = - 0.6
ℎ 10

From, Newton’s backward formula

𝑢 ( 𝑢 + 1) 4
𝑓(84) = 𝑡𝑛 + 𝑢𝛻 𝑡𝑛 + 𝛻 𝑡𝑛 + …
2

−0.6 ( −0.6 + 1)
𝑓(84) = 304 − 0.6 ∗ 28 + 2
2
= 304 − 16.8 − 0.24 = 286.96

3. Interpolation with Unequal Intervals

3.1 Introduction

The Newton’s forward and backward interpolation formulae which were derived in the previous
section are applicable only when the values of n are given at equal intervals. In this section we
study the problem of interpolation when the values of the independent variable x are given at
unequal intervals.

3.2 Newton’s General Divided Differences Formula

Let a function f(x) be given for the (n + 1) values x0, x1 , x2 …, xn as f(x0), f(x1), f(x2), …, f(xn)
where x0, x1, x2 , …, xn are not necessarily equi-spaced.

(𝑥 − 𝑥1 )(𝑥 − 𝑥2 ) … (𝑥 − 𝑥𝑛 )
𝑦 = 𝑓(𝑥) = 𝑓 (𝑥 ) +
(𝑥0 − 𝑥1 )(𝑥0 − 𝑥2 ) … (𝑥0 − 𝑥𝑛 ) 0

(𝑥 − 𝑥0 )(𝑥 − 𝑥2 ) … (𝑥 − 𝑥𝑛 ) (𝑥 − 𝑥0 )(𝑥 − 𝑥1 ) … (𝑥 − 𝑥𝑛−1 )

(𝑓𝑥1 ) + ⋯ + 𝑓(𝑥𝑛 )
(𝑥1 − 𝑥0 )(𝑥1 − 𝑥2 ) … (𝑥1 − 𝑥𝑛 ) (𝑥𝑛 − 𝑥0 )(𝑥𝑛 − 𝑥1 ) … (𝑥𝑛 − 𝑥𝑛−1 )

39
The above formula is called Lagrange’s interpolation formula. It is simple and easy to remember
but the calculations in the formula are more complicated than in Newton’s divided difference
formula. The application of the formula is not speedy and there is always a chance of committing
some error due to the number of positive and negative signs in the numerator and denominator of
each term.

Example 3: Using Lagrange’s interpolation formula, find the value of y corresponding to x = 10,
from the following table.

x 5 6 9 11
y= f(x) 12 13 14 16
Solution: We have 𝑥0 = 5, 𝑥1 = 6, 𝑥2 = 9, 𝑥3 = 11, 𝑦0 = 5, 𝑦0 = 5, 𝑦1 = 13, 𝑦2 = 14, 𝑦3 =
16

Using Lagrange’s interpolation formula, we can write

(𝑥 − 𝑥1 )(𝑥 − 𝑥2 )(𝑥 − 𝑥3 ) (𝑥 − 𝑥0 )(𝑥 − 𝑥2 )(𝑥 − 𝑥3 )

𝑦 = 𝑓(𝑥) = (𝑦0 ) + (𝑦 ) +
(𝑥0 − 𝑥1 )(𝑥0 − 𝑥2 )(𝑥0 − 𝑥3 ) (𝑥1 − 𝑥0 )(𝑥1 − 𝑥2 ) … (𝑥1 − 𝑥3 ) 1

(𝑥 − 𝑥0 )(𝑥 − 𝑥2 )(𝑥 − 𝑥3 ) (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥2 )

(𝑦2 ) + (𝑦 )
(𝑥2 − 𝑥0 )(𝑥2 − 𝑥1 )(𝑥2 − 𝑥3 ) (𝑥3 − 𝑥0 )(𝑥3 − 𝑥1 )(𝑥3 − 𝑥2 ) 3

Substituting we get,

(10 − 6)(10 − 9)(10 − 11) (10 − 5)(10 − 9)(10 − 11)

𝑓(10) = ∗ (12) + ∗ (13)
(5 − 6)(5 − 9(5 − 11 (6 − 5)(6 − 9)(6 − 11

(10 − 5)(10 − 6)(10 − 11) (10 − 5)(10 − 6)(10 − 9)

+ ∗ (14) + ∗ (16)
(9 − 5)(9 − 6)(9 − 11) (11 − 5)(11 − 6)(11 − 9

13 35 16 42
=2− + + =
3 3 3 3

40
4. Central Difference Interpolation
4.1 Introduction: In the preceding sections we have discussed a few interpolation formulae
which were suited for interpolation near the beginning and end values of the tabulated data. For
interpolation near the middle of a difference table, central difference formulae are preferable.

4.2 Gauss Forward Interpolation Formula

The Newton forward interpolation formula is as given below.

𝑢(𝑢 − 1) 2 (𝑢 + 1)𝑢 (𝑢 − 1) 3
𝑦4 = 𝑓(𝑥) = 𝑦0 + 𝑢𝑦0 +  𝑦−1 +  𝑦−1 +
2! 3!

(𝑢 + 1)𝑢 (𝑢 − 1)(𝑢 − 2) 4
 𝑦−2 + ⋯
4!

𝑥− 𝑥0
Where 𝑢 = ℎ

Example 4: Use Gauss forward formula to find y for x = 30 given that

x 21 25 29 33 37
y 18.4708 17.8144 17.1070 16.3432 15.5154

Solution We construct the difference table by taking as

x y y 𝟐 y 𝟑 y 𝟒 y
x0 − 2h = 21 18.4708
-0.6564
x0 − h = 25 17.8144 -0.0510
-0.7074 -0.0054
𝑥0 = 29 17.1070 -0.0564 -0.002
-0.7638 -0.0076
𝑥 + ℎ + 33 16.3432 -0.0640
-0.8278
𝑥0 + 2ℎ = 37 15.5154

41
30 − 29 1
Here h = 4, u = = = 0.25
4 4

u = 0.25 lies between 0 and 1

 Gauss’s forward formula is suitable. Substituting in the Gauss’s Interpolation formula

𝑢 𝑢(𝑢−1) (𝑢+1)𝑢 (𝑢−1)

𝑦 = 𝑦0 + 𝑦0 +
1! 2!
2 𝑦−1 + 3!
3 𝑦−1 +
(𝑢+1)𝑢 (𝑢−1)(𝑢−2)
4!
4 𝑦−2 + ⋯
We get,

(0.25)(−0.75)
𝑦0.25 = 𝑓(0.25) = 17.1070 + (0.25)(−0.7638) + ∗ (−0.0564) +
2
(1.25)(0.25)(−0.75)
6

(1.25)(0.25)(−0.75)(−1.75)
∗ (0.0076) + (−0.0022)
24

=16.9216

4.3 Gauss Backward Interpolation Formula

The Gauss’s Backward interpolation formula is as given below.

𝑢 2 𝑢(𝑢 − 1) 2 3
𝑦 = 𝑓(𝑥) = 𝑦0 + (𝑦−1 +  𝑦−1 ) + ( 𝑦−1 +  𝑦−1 ) + ⋯
1! 2!

𝑢 𝑢(𝑢 − 1) 2 (𝑢 + 1)𝑢 (𝑢 − 1) 3
⇒ 𝑦4 = 𝑦0 𝑦−1 +  𝑦−1 +  𝑦−2
1! 2! 3!
(𝑢 + 2)𝑢 (𝑢 + 1)(𝑢 − 1) 4
+  𝑦−2 ….
4!

Note: The Gauss’s forward interpolation formula employs odd differences above the central line
through y0 and even differences on the central line whereas Gauss’s backward formula employs
odd differences below the central line through y0 and even differences on the central line as
shown in the table given below.

42
x y y 𝟐 y 𝟑 y 𝟒 y 𝟓 y 𝟔 𝒚
𝑥−4 𝑦−4
𝑦−4
𝑥−3 𝑦−3 2 𝑦−4
𝑦−3 3 𝑦−4
𝑥−2 𝑦−2 2 𝑦−3 4 𝑦−4
𝑦−2 3 𝑦−3 5 𝑦−4
𝑥−1 𝑦−1 2 𝑦−2 4 𝑦−3 6 𝑦−4
𝑦−1 3 𝑦−2 5 𝑦−3
𝑥0 𝑦0 2 𝑦−1 4 𝑦−2 6 𝑦−4
𝑦0 3 𝑦−1 5 𝑦−2 l
𝑥1 𝑦1 2 𝑦0 4 𝑦−1 6 𝑦−4
𝑦1 3 𝑦0 5 𝑦−1
𝑥2 𝑦2 2 𝑦1 4 𝑦0
𝑦2
𝑥3 𝑦3 2 𝑦2
𝑦3
𝑥4 𝑦4

Example 5 Use Gauss’s backward formula and find the sales for the year 1966, given that

Year 1931 1941 1951 1961 1971 1981

Sales 12 15 20 27 39 52
(in lakhs)

Solution: We have h=10, we take 1971 as the origin. The central difference table with origin at
1971 is

43
x y y 𝟐 y 𝟑 y 𝟒 y 𝟓 y
-4 12
3
-3 15 2
5 0
-2 20 2 3
7 3 -10
-1 27 5 -7
12 -4
0 39 1
13
1 -52

u at 1996 is
1996 − 1971 −5
𝑢= = = −0.5
10 10

Gauss’s backward formula is

𝑢 𝑢(𝑢 − 1) 2 (𝑢 + 1)𝑢 (𝑢 − 1) 3
𝑦 = 𝑦0 + 𝑦−1 +  𝑦−1 +  𝑦−2 ….
1! 2! 3!

Substituting we get

(0.5)(−0.5) (0.5) ∗ (−0.5) ∗ (−1.5)

𝑦−0.5 = 39 + (0.5)(12) + ∗1+ ∗ (−4) + ⋯.
2 6

= 39 − 0.6 − 0.125 − 0.25

𝑦1966 = 32.625

The sales in the year 1966 is 32.625 lakh of rupees.

5. Inverse Interpolation
In interpolation we have discussed various methods of estimating the missing value of the
function y = f(x) corresponding to a value x intermediate between two given values. Now we

44
discuss inverse interpolation in which we interpolate the value of argument x corresponding
to an intermediate value y of the entry.

(𝑦 − 𝑦1 )(𝑦 − 𝑦2 ) … (𝑦 − 𝑦𝑛 ) (𝑦 − 𝑦0 )(𝑦 − 𝑦2 ) … (𝑦 − 𝑦𝑛 )
𝑥= (𝑥0 ) + (𝑥 ) + ⋯
(𝑦0 − 𝑦1 )(𝑦0 − 𝑦2 ) … (𝑦0 − 𝑦𝑛 ) (𝑦1 − 𝑦0 )(𝑦1 − 𝑦2 ) … (𝑦1 − 𝑦𝑛 ) 1

(𝑦 − 𝑦0 )(𝑦 − 𝑦1 ) … (𝑦 − 𝑦𝑛−1 )
+ (𝑥
(𝑦𝑛 − 𝑦0 )(𝑦𝑛 − 𝑦1 ) … (𝑦𝑛 − 𝑦𝑛−1 ) 𝑛)

The above formula may be used for inverse interpolation.

Example 6: The following table gives the value of the elliptical integral

𝜙
𝑑𝜙
𝐹(𝜙) = ∫
1
0 1 − 2 𝑠𝑖𝑛2 𝜙

For certain values of ϕ. Find the value of ϕ if 𝐹( 𝜙) = 0.3887

ϕ 210 230 250

𝐹(𝑓) 0.3706 0.4068 0.4433
Solution: We have

𝜙 = 210 , 𝜙1 = 230 , 𝜙2 = 250 ,

𝐹 = 0.3887, 𝐹0 = 0.3706, 𝐹1 = 0.4068 𝑎𝑛𝑑 𝐹2 = 0.4433

Using the inverse interpolation formula we can write

(𝐹 − 𝐹1 )(𝐹 − 𝐹2 ) (𝐹 − 𝐹)(𝐹 − 𝐹2 )
𝜙= (𝜙0 ) + (𝜙 )
(𝐹0 − 𝐹1 )(𝐹0 − 𝐹2 ) (𝐹1 − 𝐹0 )(𝐹1 − 𝐹2 ) 1
(𝐹 − 𝐹0 )(𝐹 − 𝐹1 )
+ (𝜙 )
(𝐹𝑛 − 𝐹0 )(𝐹𝑛 − 𝐹1 ) 2
(0.3887 − 0.4068)(0.3887 − 0.4433) (0.3887 − 0.3706)(0.3887 − 0.4433)
⇒𝜙= ∗ 21 + ∗ 23 +
(0.3706 − 0.4068)(0.3706 − 0.4068) (0.4068 − 0.3706)(0.4068 − 0.4433)

(0.3887 − 0.3706)(0.3887 − 0.4068)

∗ 25
(0.4433 − 0.3706)(0.4433 − 0.4068)

𝜙 = 7.884 + 17.20 – 3.087 = 2199922 ∴ 𝜙 = 220

45
6. Summary

Interpolation algorithms are mathematical methods used to estimate the value of a

function between known data points. They are widely used in various fields such as
mathematics, engineering, computer graphics, and data analysis. There are different
interpolation algorithms focusing on Equal Intervals, Unequal Intervals, Central
Difference, and Inverse Interpolation. Each of these interpolation algorithms has its
advantages and limitations, and the choice of method depends on factors such as the
nature of the data, the desired accuracy, and computational efficiency. It's important to
select the most suitable interpolation technique based on the specific requirements of the
problem at hand.

7. Keywords
Interpolation algorithm, Newton’s Forward/Backward Interpolation, Central Difference
Interpolation, Inverse Interpolation.

8. Assessment Questions
i) The values of sin x are given below for different values of x. Find the value of
sin 320

x 300 350 400 450 500

y= sin x 0.5000 0.5736 0.6428 0.7071 0.7660

Solution 𝑥 = 300 is very near to the starting value 𝑥0 = 300 . We compute sin 320 by
using Newton’s forward interpolation formula.

Solution 𝐟(𝟑𝟎)𝟎 = 𝟎. 𝟐𝟗𝟗

ii) In an examination the number of candidates who obtained marks between certain
limits were as follows:

46
Marks 30-40 40-50 50-60 60-70 70-80
No of students 31 42 51 35 31
Find the number of candidates whose scores lie between 45 and 50
Solution 48 (approximately)

iii) Calculate the value of f(7.5) from the given Table using Newton backword formula.

x 1 2 3 4 5 6 7 8
f(x) 1 8 27 64 125 216 343 512

Solution: f(7.5)= 42187

iv) Use Newton dividend difference formula and evaluate f(6), given

x 5 7 11 13 21
f(x) 150 392 1452 2366 9702

Solution: 252

v) Apply Gauss’s forward formula to find the value of 𝑢9 if

𝑢0 = 14, 𝑢4 = 24, 𝑢8 = 32 , 𝑢16 = 40.

Solution: u9 = 33 (approximately)

2 𝑥 2
vi) Compute the value of ∫0 𝑒 −𝑥 𝑑𝑥 𝑤ℎ𝑒𝑛 𝑥 = 0.6538 by using
√𝜋

(a) Gauss’s forward formula

(b) Gauss’s backward formula

47
x 0.62 0.63 0.64 0.65 0.66 0.67 0.68

y 0.6194114 0.6270463 0.634857 0.6420292 0.6496765 0.6566275 0.6637820

Solution:
We have ℎ = 0.01, 𝑥 = 0.6538, 𝑥0 = 0.65 hence 𝑢 = 0.38

a) Using Gauss’s forward interpolation formula

𝑌(0.38) = 0 6448325
b) Using Gauss’s backward interpolation formula
𝑌(0.38) = 0 6448325

9. References
1. V. Rajaraman – Computer Oriented Numerical Methods, Prentice Hall of India, 1980.
2. G. Shankar Rao – Numerical Analysis, Prentice Hall of India, 1985.

48
Unit - 4: Numerical differentiation and integration and their errors
calculations

1. Numerical Differentiation
1.1 Introduction
1.2 Derivatives Using Newton’s Forward Interpolation
1.3 Derivatives Using Newton’s Backward Interpolation
2. Numerical Integration
2.1 Introduction
2.2 Trapezoidal Rule
2.3 Simpson’s Rule
2.3.1 Simpson’s One-Third Rule
2.3.2 Simpson’s Three-Eight Rule
3. Summary
4. Keywords
5. Assessment Questions
6. References

49
OBJECTIVES

After studying this unit the student will be able to:

 Illustrate numerical differentiation methods: Newton’s forward and backward

Interpolation.
 Explain numerical integration methods: Trapezoidal Rule and Simpson’s Rules.
 Apply numerical differentiation and integration techniques to solve complex problems.

1. Numerical Differentiation

1.1 Introduction

The process of computing the value of derivative dy/dx for some particular value of x from the
given data when the actual form of the function is not known is called Numerical differentiation.

When the values of the argument are equally spaced and we are to find the derivative for some
given x lying near the beginning of the table, we can represent the function by Newton–Gregory
forward interpolation formula. When the value of dy/dx is required at a point near the end of the
table, we use Newton’s backward interpolation formula and we may use suitable Central
difference interpolation formula when the derivative is to be found at some point lying near the
middle of the tabulated values.

If the values of argument x are not equally spaced, we use Newton’s divided difference formula
to approximate the function y = f(x).

1.2 Derivatives Using Newton’s Forward Interpolation

𝑑𝑦 1 1 1 1
𝐷𝑦0 = ( ) = [∆𝑦0 − ∆2 𝑦0 + ∆3 𝑦0 − ∆4 𝑦0 + ⋯ ]
𝑑𝑥 𝑥=𝑥0 ℎ 2 3 4

50
2
𝑑2 𝑦 1 11 4
𝐷 𝑦0 = ( 2 ) = 2 [∆2 𝑦0 − ∆3 𝑦0 − ∆ 𝑦0 + ⋯ ]
𝑑𝑥 𝑥=𝑥 ℎ 12
0

1.3 Derivatives Using Newton’s Backward Interpolation

𝑑𝑦 1 1 1 1
( ) = [𝛻𝑦𝑛 − 𝛻 2 𝑦𝑛 + 𝛻 3 𝑦𝑛 − 𝛻 4 𝑦𝑛 + ⋯ ]
𝑑𝑥 𝑥=𝑥𝑛 ℎ 2 3 4

𝑑2𝑦 1 11 4
( 2) = 2 [𝛻 2 𝑦𝑛 − 𝛻 3 𝑦𝑛 − 𝛻 𝑦𝑛 + ⋯ ]
𝑑𝑥 𝑥=𝑥 ℎ 12
𝑛

𝑑𝑦 𝑑2 𝑦
Example 1. From the table of values below compute 𝑎𝑛𝑑 𝑓𝑜𝑟 𝑥 = 1
𝑑𝑥 𝑑𝑥 2

x 1 2 3 4 5 6
y 1 8 27 64 125 216

Solution: The difference table is given below.

x y ∆y ∆2 𝑦 ∆3 𝑦 ∆4 𝑦
1 1
7
2 8 12
19 6
3 27 18 0
37 6
4 64 24 0
61 6
5 125 30
91
6 216

51
We have 𝑥0 = 1, ℎ = 1, 𝑥 = 1 is at the beginning of the table.

We use Newton’s forward formula

𝑑𝑦 1 1 1 1
( ) = [∆𝑦0 − ∆2 𝑦0 + ∆3 𝑦0 − ∆4 𝑦0 + ⋯ ]
𝑑𝑥 𝑥=𝑥0 ℎ 2 3 4

𝑑𝑦 1 1 1
(𝑑𝑥 ) = [7 − 12 + 6− 0+⋯]
𝑥=1 ℎ 2 3

=7−6+2= 3

𝑑2 𝑦 1 11
and (𝑑𝑥 2 ) = [∆2 𝑦0 − ∆3 𝑦0 − ∆4 𝑦0 + ⋯ ]
𝑥=𝑥0 ℎ2 12

𝑑2 𝑦 1
 ( 2) = 2 [12 − 6 ] = 6
𝑑𝑥 𝑥=1 1

𝑑2𝑦 𝑑𝑦
 ( 2) = 3, ( 2 ) = 6.
𝑑𝑥 𝑥=1 𝑑𝑥 𝑥=1

2. Numerical Integration

2.1 Introduction

Numerical integration is used to obtain approximate answers for definite integrals that cannot be
solved analytically.

Numerical integration is a process of finding the numerical value of a definite integral

𝑏
𝐼 = ∫ 𝑓(𝑥)𝑑𝑥,
𝑎

When a function y=f(x) is not known explicitly. But we give only a set of values of the function
𝑦 = 𝑓(𝑥) corresponding to the same values of 𝑥 .

52
To evaluate the integral, we fit up a suitable interpolation polynomial to the given set of values
of 𝑓(𝑥) and then integrate it within the desired limits. Here, we integrate an approximate
interpolation formula instead of 𝑓(𝑥). When this technique is applied on a function of single
variable, the process is called 𝑄𝑢𝑎𝑑𝑟𝑎𝑡𝑢𝑟𝑒.

2.2 Trapezoidal Rule

In Calculus, “Trapezoidal Rule” is one of the important integration rules. The name is
trapezoidal because when the area under the curve is evaluated, then the total area is divided into
small trapezoids instead of rectangles. This rule is used for approximating the definite integrals
where it uses the linear approximations of the functions.

The trapezoidal rule is mostly used in the numerical analysis process. To evaluate the definite
integrals, we can also use Riemann Sums, where we use small rectangles to evaluate the area
under the curve.

Trapezoidal Rule is a rule that evaluates the area under the curves by dividing the total area into
smaller trapezoids rather than using rectangles. This integration works by approximating the
region under the graph of a function as a trapezoid, and it calculates the area. This rule takes the
average of the left and the right sum.

The Trapezoidal Rule does not give accurate value as Simpson’s Rule when the underlying
function is smooth. It is because Simpson’s Rule uses the quadratic approximation instead of
linear approximation. Both Simpson’s Rule and Trapezoidal Rule give the approximation value,
but Simpson’s Rule results in even more accurate approximation value of the integrals.

53
Trapezoidal Rule Formula

Let f(x) be a continuous function on the interval [a,b]. Now divide the intervals [a,b] into n equal
subintervals with each of width,

∆x = (b-a)/n. Such that a = 𝑥0 < 𝑥1 < 𝑥2 < 𝑥3 < … … < 𝑥𝑛 = b

Then the Trapezoidal Rule formula for area approximating the definite integral ∫ 𝑎𝑏

f(x)dx is given by:

𝑏
∆𝑥
∫ 𝑓(𝑥)𝑑𝑥 ≈ 𝑇𝑛 = [𝑓(𝑥0 ) + 2𝑓(𝑥1 ) + 2𝑓(𝑥2 ) + ⋯ 2𝑓(𝑥𝑛−1 ) + 𝑓(𝑥𝑛 )]
𝑎 2

Where, xi = a + i∆x

If n , R. H. S of the expression approaches the definite integral ∫ ab f(x)dx.

Example 2: Approximate the area under the curve y = f(x) between x =0 and x=8 using
trapezoidal rule with n =4 subintervals. A function f(x) is given the table of values.

x 0 2 4 6 8

f(x) 3 7 11 9 3

Solution:

The trapezoidal Rule formula for n = 4 subintervals is given as:

T4 = (∆x⁄2)[ f(x0 ) + 2f(x1 ) + 2f(x2 ) + 2f(x3 ) + f(x4 )]

Here the subinterval width ∆x = 2.

Now, substitute the values from the table, to find the approximate value of the area under the
curve.

A ≈ T4= ( 2⁄2 )[3 + 2(7) + 2(11) + 2(9) + 3 ]

54
A ≈ T4= 3 + 14 + 22 + 18 + 3 = 60

Therefore, the approximation value of area under the curve using Trapezoidal rule is 60.

2.3 Simpson’s Rule

Simpson’s rule is one of the numerical methods which is used to evaluate the definite integral.
Usually, to find the definite integral, we use the fundamental theorem of calculus, where we have
to apply the anti-derivative techniques of integration. However, sometimes, it isn’t easy to find
the anti-derivative of an integral, like in Scientific Experiments, where the function has to be
determined from the observed readings. Therefore, numerical methods are used to approximate
the integral in such conditions. Other numerical methods used are trapezoidal rule, midpoint rule,
left or right approximation using Riemann sums. Here, we will discuss Simpson’s rule formula,
1/3 rule, 3/8 rule and examples.

Simpson’s rule methods are more accurate than the other numerical approximations and its
formula for n+1 equally spaced subdivision is given by;

𝑏
∫ 𝑓(𝑥) 𝑑𝑥 ≈ 𝑆𝑛
𝑎
∆𝑥
= [ 𝑓(𝑥0 ) + 4𝑓(𝑥1 ) + 2 𝑓(𝑥2 ) + 4𝑓(𝑥3 ) + ⋯ + 2 𝑓(𝑥𝑛−2 ) + 4 𝑓(𝑥𝑛−1 )
3
+ 𝑓(𝑥𝑛) ]

where n is the even number, ∆x = b − a⁄n and xi = a + i∆x

If we have f(x) = y, which is equally spaced between [a ,b] and if a = a = x0 , x1 = x0 + h, x2 =

x0 + 2h … , xn = x0 + nh, where h is the difference between the terms, or we can say that
y0 = f(x0 ), y1 = f(x1 ), y2 = f(x2 ), … . , yn = f(xn )are the analogous values of y with each
value of x.

55
2.3.1 Simpson’s One-Third Rule

Simpson’s 1⁄3rd rule is an extension of the trapezoidal rule in which the integrand is
approximated by a second – order polynomial. Simpson rule can be derived from the various
way using Newton’s dividend difference polynomial, Lagrange polynomial and the method of
coefficients, Simpson’s 1⁄3rd rule is defined by:

b
∫ f(x)dx = h⁄3 [ (y0 + yn )
a

+ 4(y1 + y3 + y5 + ⋯ + yn−1 ) + 2 (y2 + y4 + y6 + ⋯ + yn−2 )]

 Simpson’s 𝟏⁄𝟑 Rule for Integration

We can get a quick approximation for definite integrals when we divide a small interval [a, b]
into two parts. Therefore, after dividing the interval we get,

x0 = a, x1 = a, x2 = 𝑏

Hence, we can write the approximation as:

∫ ab f(x)dx ≈ 𝑆2 = h⁄3 [ f(x0 ) + 4(x1 ) + f(x2 )]

S2 = h/3 [ f(a) + 4f ((a + b)/2) + f(b)]

Where h = (b-a)/2

This is the Simpon’s 1⁄3 rule for integration.

56
2.3.2 Simpson’s 𝟑⁄𝟖 Rule

Another method of numerical integration is called “Simpson’s 𝟑⁄𝟖 rule ”. It is completely based

on the cubic interpolation rather than the quadratic interpolation. Simpson’s 𝟑⁄𝟖 rule or three –
eight rule is given by:

∫ ab f(x)dx = 3h⁄8 [(y0 + yn ) + 3(y1 + y2 + y4 + y5 + ⋯ + yn−1 ) + 2(y3 + y6 + y9 + ⋯ + yn−3 )]

1
Example 3: Evaluate ∫0 𝑒 𝑥 𝑑𝑥 , by Simpon’s1⁄3 rule.

Solution:

Let us divide the range [0,1] into six equal parts by taking h = 1/6.

If x0 = 0 then y0 = e0 = 1.

1
Ifx1 = x0 + h = 1⁄6 then y1 = e ⁄6 = 1.1813

1
Ifx2 = x0 + 2h = 2⁄6 = 1⁄3 then y2 = e ⁄3 = 1.3956

1
Ifx3 = x0 + 3h = 3⁄6 = 1⁄2 then y3 = e ⁄2 = 1.6487

2
Ifx4 = x0 + 4h = 4⁄6 = 2⁄3 then y4 = e ⁄3 = 1.9477

5
Ifx5 = x0 + 5h = 5⁄6 then y5 = e ⁄6 = 2.3009

Ifx6 = x0 + 6h = 6⁄6 = 1 then y6 = e1 = 2.7182

We know by Simpon’s 1⁄3 rule

b
∫ f(x)dx = h⁄3 [ (y0 + yn ) + 4(y1 + y3 + y5 + ⋯ + yn−1 ) + 2 (y2 + y4 + y6 + ⋯ + yn−2 )]
a

57
Therefore,

1
∫ 𝑒 𝑥 dx = 1⁄18 [ (1 + 2.7182) + 4(1.1813 + 1.6487 + 2.3009) + 2 (1.39561 + 1.9477)]
0

= 1⁄18 [ 3.7182 + 20.5236 + 6.68662]

= 1.7182 (approx.)

3. Summary

Numerical differentiation and integration are fundamental techniques used in computational

mathematics and scientific computing to approximate derivatives and definite integrals,
respectively, when analytic solutions are difficult or impossible to obtain. The different methods
used for Numerical differentiation are i) forward difference ii) backward difference iii) Central
Difference. The main objective of numerical integration is to approximate the value of a definite
integral of a function over a given interval. The different methods used in numerical integration
are Trapezoidal Rule and Simpson's Rule. Numerical differentiation and integration provide
essential tools for approximating derivatives and integrals in scenarios where analytical solutions
are impractical. These methods are crucial for solving a wide range of problems in various fields
of science, engineering.

4. Keywords
Trapezoidal Rule, Simpson’s One-Third Rule, Simpson’s Three-Eight Rule

5. Assessment Questions

1. Find the solution of the following using Simpson’s rule.

x 0.0 0.1 0.2 0.3 0.4

f(x) 1.0000 0.9975 0.9900 0.9776 0.8604

Solution: 0.39136 is the required solution

58
2. Evaluate the following using Simpson’s ⅜ rule.

x 4 4.2 4.4 4.6 4.8 5.0 5.2

f(x) 1.3863 1.4351 1.4816 1.5261 1.5686 1.6094 1.6487

Solution: 1.827847

3. Approximate the area under the curve y = f(x) between x =-4 and x= 2 using Trapezoidal
Rule with n = 6 subintervals.

A function f(x) is given in the table of values.

x -4 -3 -2 -1 0 1 2

f(x) 0 4 5 3 10 11 2

Solution: Approximate value of area under the curve using Trapezoidal Rule is 34.

4. Find Solution using Trapezoidal rule

x 1.4 1.6 1.8 2 2.2

y 4.0552 4.953 6.0436 7.3891 9.025

Solution: 4.9852

5. Find Solution using Trapezoidal rule

x 0 0.1 0.2 0.3 0.4

y 1 0.9975 0.99 0.9776 0.8604

Solution: 0.38953

59
6. Find Solution using Simpson's 1/3 rule

x 1.4 1.6 1.8 2 2.2

y 4.0552 4.953 6.0436 7.3891 9.025

Solution: 4.9691

7. Find Solution using Simpson's 1/3 rule

x 0 0.1 0.2 0.3 0.4

y 1 0.9975 0.99 0.9776 0.8604

Solution: 0.39136

8. Find Solution using Simpson's 3/8 rule

x 1.4 1.6 1.8 2 2.2

y 4.0552 4.953 6.0436 7.3891 9.025

Solution: 4.5636

9. Find Solution using Simpson's 3/8 rule

x 0 0.1 0.2 0.3 0.4

y 1 0.9975 0.99 0.9776 0.8604

Solution: 0.36668

60
10. Find the value of sin 52 using Newton forward interpolation method.
0
ϴ 45 50 55 60

Sin Ɵ 0.9975 0.99 0.9776 0.8604

Solution: sin 52 = 0.788003

11. Find the Population in 1925 using Newton backward interpolation method.

Year (x) 1891 1901 1911 1921 1931

Population (y): (in

46 66 81 93 101
thousands

Solution: 96.83

6. References:
1. [Link]
2. [Link]
3. [Link]
4. V. Rajaraman – Computer Oriented Numerical Methods, Prentice Hall of India, 1980.
5. G. Shankar Rao – Numerical Analysis, Prentice Hall of India, 1985.

61
BLOCK- II

62
Unit 5: Graph theoretical algorithms - Connectivity, finding shortest path
between two vertices, enumeration of all paths.

1. Introduction
1.1 Types of Graphs
1.2 Computer Representation of Graph
1.3 Connectivity in Graph Theory
2. Finding Shortest Path Between Two Vertices
2.1 Dijkstra’s Algorithm
2.2 The Breadth First Search (BFS) Technique
3. Enumeration of All Paths
3.1 Depth-First Search Algorithm
4. Summary
5. Keywords
6. Assessment Questions
7. Reference

63
OBJECTIVES

After studying this unit, the student will be able to:

 Distinguish different types of graphs.

 Describe the representation of graphs in computer.
 Determine the shortest path between two vertices of weighted and unweighted graphs.
 Explain the enumeration of all paths in a given graph.

1. Introduction

A graph G = (V, E) consists of finite set vertices V = {v1 v2, . . .} and finite set of edges E = {e1,
e2,. . .}. From the Figure 1.1, {v1,v2,v3,v4,v5} represents the vertices and {e1,e2,e3,e4,e5,e6}
represents the edges of graph.

Figure 1.1. Representation of Graph

1.1 Types of Graphs
Different types of graphs with their relevant diagrams are given below.
i) Null Graph: A graph having no edges.
ii) Trivial Graph: Graph having only one vertex.
iii) Undirected Graph: A graph contains edges with no direction.
iv) Directed Graph: A graph in which each edge has direction.
v) Connected Graph: From one node we can visit any other node in the graph is called a
connected graph.

64
vi) Disconnected Graph: A graph in which at least one node is not reachable from the other
node.

3 3

2 5 1
5 1

4 4
Null Graph Trivial Graph Undirected
Graph

3 3
3

5 1 5 1
5 1

4 4
4
Directed Graph Connected Graph Disconnected Graph

Figure 1.2 Different Types of Grpahs

1.2 Computer Representation of Graph: A graph can be represented using 2 data structures
namely i) Adjacency Matrix and ii) Adjacency List. Each representation is explained below.

i) Adjacency Matrix
A graph is stored in the form of the 2 dimensional matrix where columns and rows
represents the vertices. Each element in the matrix represents the weight of the edge
between the vertices.
0 1 2 3
0 1 0 0 1 1 0
1 1 0 1 0
2 1 1 0 1
3 0 0 1 0
2 3

Figure 1.3 Adjacency Matrix of Graph

65
ii) Adjacency List
In this method the graph is represented as a collection of linked lists. There is an array of
pointer which points to the edges connected to that vertex.

0 1 2
0 1

1 0 2

2 3
2 0 1 3

3 2

Figure 1.4 Adjacency List of Graph

1.3 Connectivity in Graph Theory

A graph is a connected graph if, for each pair of vertices, there exists at least one single
path which joins them as shown in Figure 1.5(a). In a connected graph, if any of the
vertices are removed, the graph gets disconnected. Then the graph is called a vertex-
connected graph as shown in Figure 1.5(b). On the other hand, when an edge is removed,
the graph becomes disconnected. It is known as an edge-connected graph as shown in
Figure 1.5(c).

1.5 (a) 1.5 (b) 1.5 (c)

Figure 1.5 (a) Connected Graph; (b) vertex-connected Graph; (c) edge-connected graph

66
2. Finding Shortest Path Between Two Vertices

For a weighted graph G(V,E, W) a shortest path from vertex u to vertex v is a path from u to
v with minimum weight. There might be multiple paths with equal weight, and if so they are
all shortest weighted paths from u to v. Dijkstra’s Algorithm is a popular algorithm for
solving many single-source shortest path problems having non-negative edge weight in the
graphs i.e., it is to find the shortest distance between two vertices on a weighed graph.

2.1 Dijkstra’s Algorithm

The steps involved in finding the shortest path between two vertices are given below.

Step 1: Mark the source node with a current distance of 0 and the rest with infinity.
Step 2: Set the non-visited node with the smallest current distance as the current node.
Step 3: For each neighbor, N of the current node adds the current distance of the adjacent
node with the weight of the edge connecting 0 -> 1. If it is smaller than the current
distance of Node, set it as the new current distance of N.
Step 4: Mark the current node 1 as visited.
Step 5: Go to step 2 if there are any nodes are unvisited.
(recheck with the example)

Let’s see how Dijkstra’s Algorithm works with an example given below:

Dijkstra’s Algorithm will generate the shortest path from Node 0 to all other Nodes in the graph.
Consider the below graph shown in Figure 1.6. For this graph, we will assume that the weight of
the edges represents the distance between two nodes.

Figure 1.6 Connected Graph

67
Initially we have a set of resources given below:

 The Distance from the source node to itself is 0. In this example the source node is 0.

 The distance from the source node to all other node is unknown so we mark all of them as
infinity.

Example: 0 -> 0, 1-> ∞, 2-> ∞, 3-> ∞, 4-> ∞, 5-> ∞, 6-> ∞.

 We will also have an array of unvisited elements that will keep track of unvisited or
unmarked Nodes.

 Algorithm will complete when all the nodes marked as visited and the distance between
them added to the path.
 Unvisited Nodes :- 0 1 2 3 4 5 6.

Step 1: Start from Node 0 and mark Node as visited as you can check in below image
visited Node is marked red.

Step 2: Check for adjacent Nodes. Now we have two choices (Either choose Node1 with
distance 2 or either choose Node 2 with distance 6), so choose Node with minimum distance. In
this step Node 1 is Minimum distance adjacent Node, so marked it as visited and add up the
distance as shown below.

Distance: Node 0 -> Node 1 = 2

68
Step 3: Then Move Forward and check for adjacent Node which is Node 3, so marked it as
visited and add up the distance. Now the distance will be:

Distance: Node 0 -> Node 1 -> Node 3 = 2 + 5 = 7 and Node 0-> Node2 = 6

Step 4: Again two choices for adjacent Nodes (Either choose Node 4 with distance 10 or either
choose Node 5 with distance 15). So choose Node with minimum distance. In this step, Node 4
is Minimum distance adjacent Node, so marked it as visited and add up the distance.

Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 = 2 + 5 + 10 = 17

69
Step 5: Again, Move Forward and check for adjacent Node which is Node 6, so marked it as
visited and add up the distance, now the distance will be:

Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 -> Node 6 = 2 + 5 + 10 + 2 = 19

So, the Shortest Distance from the Source Vertex is 19 which is optimal one.

2.2 The Breadth First Search (BFS) Technique

The general strategy for finding the shortest path between two vertices in an unweighted graph is
a Breadth-First Search (BFS), which visits every node of distance 1 from the starting point, then
every node of distance 2, until it finds the target vertex. BFS is a fundamental graph traversal
algorithm. It involves visiting all the connected nodes of a graph in a level-by-level manner. BFS
is a graph traversal algorithm that explores all the vertices in a graph at the current depth before
moving on to the vertices at the next depth level. It starts at a specified vertex and visits all its
neighbors before moving on to the next level of neighbors.

2.2.1 Breadth First Search (BFS) Algorithm: Let’s discuss the algorithm for the BFS:

Step 1: Initialization: Enqueue the starting node into a queue and mark it as visited.
Step 2: Exploration: While the queue is not empty:
o Dequeue a node from the queue and visit it (e.g., print its value).
o For each unvisited neighbor of the dequeued node:
 Enqueue the neighbor into the queue.
 Mark the neighbor as visited.

70
Step3: Termination: Repeat step 2 until the queue is empty.

This algorithm ensures that all nodes in the graph are visited in a breadth-first manner, starting
from the starting node.

Starting from the root, all the nodes at a particular level are visited first and then the nodes of the
next level are traversed till all the nodes are visited.

To do this a queue is used. All the adjacent unvisited nodes of the current level are pushed into
the queue and the nodes of the current level are marked visited and popped from the queue.

Illustration:

Let us understand the working of the algorithm with the help of the following example.

Step1: Initially queue and visited arrays are empty.

Step2: Push node 0 into queue and mark it visited.

Step 3: Remove node 0 from the front of queue and visit the unvisited neighbours and
push them into queue.

71
Step 4: Remove node 1 from the front of queue and visit the unvisited neighbours and
push them into queue.

Step 5: Remove node 2 from the front of queue and visit the unvisited neighbours and
push them into queue.

Step 6: Remove node 3 from the front of queue and visit the unvisited neighbours and
push them into queue.

72
As we can see that every neighbours of node 3 is visited, so move to the next node that
are in the front of the queue.

Steps 7: Remove node 4 from the front of queue and visit the unvisited neighbours and
push them into queue.
As we can see that every neighbours of node 4 are visited, so move to the next node that
is in the front of the queue.

Now, Queue becomes empty, So, terminate these process of iteration.

3. Enumeration of All Paths

One of the properties of trees is that there is one (and only one) path from the root to every node
in the tree. The path enumeration model stores that path as a string by concatenating either the
edges or the keys of the nodes in the path. Searches are done with string functions and predicates
on those path strings.

73
DFS is a recursive algorithm to search all the vertices of a tree data structure or a graph. The
DFS algorithm starts with the initial node of graph G and goes deeper until we find the goal node
or the node with no children.

Because of the recursive nature, stack data structure can be used to implement the DFS
algorithm. The process of implementing the DFS is similar to the BFS algorithm.

3.1 Depth-First Search Algorithm

The step by step process to implement the DFS traversal is given as follows -
Step 1: First, create a stack with the total number of vertices in the graph.
Step 2: Now, choose any vertex as the starting point of traversal, and push that vertex
into the stack.
Step 3: After that, push a non-visited vertex (adjacent to the vertex on the top of the
stack) to the top of the stack.
Step 4: Now, repeat steps 3 and 4 until no vertices are left to visit from the vertex on the
stack's top.
Step 5: If no vertex is left, go back and pop a vertex from the stack.
Step 6: Repeat steps 2, 3, and 4 until the stack is empty.

Let us understand the working of Depth First Search with the help of the following illustration:
Step1: Initially stack and visited arrays are empty.

74
Step 2: Visit 0 and put its adjacent nodes which are not visited yet into the stack.

Step 3: Now, Node 1 at the top of the stack, so visit node 1 and pop it from the stack and
put all of its adjacent nodes which are not visited in the stack.

Step 4: Now, Node 2 at the top of the stack, so visit node 2 and pop it from the stack and
put all of its adjacent nodes which are not visited (i.e, 3, 4) in the stack

75
Step 5: Now, Node 4 at the top of the stack, so visit node 4 and pop it from the stack and
put all of its adjacent nodes which are not visited in the stack.

Step 6: Now, Node 3 at the top of the stack,

so visit node 3 and pop it from the stack and put all of its adjacent nodes which are not
visited in the stack.

Now, Stack becomes empty, which means we have visited all the nodes and our DFS
traversal ends.
4. Summary
A graph can be represented in two ways in computer namely i) Adjacency Matrix and ii)
Adjacency List for ease of implementations. A graph can be a weighted or unweighted. Shortest
path algorithms like BFS, Dijkstra's, and DFS can find paths efficiently, depending on the
graph's characteristics. Enumerating all paths involves traversal algorithms like DFS and BFS to
find all paths from source node to other nodes in the graph.

76
5. Keywords
Adjacency Matrix and list, Connectivity in graph, weighted and un-weighted graph,
Enumeration.

6. Assessment Questions

1. Find the Shortest Path between Two Vertices for the following weighted graphs using
Dijkstra’s Algorithm.

8 7
1 2 3 9
4
2
11 14
0 8 14 4
4
6
8 7 10
7 6 5
1 2

Solution:

Distance:

0: 0
1: 4 

2: 12 

3: 19 

4: 21 


5: 11

6: 9
7: 8 

8: 14 

77
2. Find the Shortest Path Between Two Vertices for the following un-weighted graphs using
Breadth First Search (BFS) Algorithm.

2 5

1 3 8

4 6 7

So all paths Ti′ s from src = 1 to dest = 8 are

T1 = 1 → 2 → 5 → 8
T2 = 1 → 3 → 8
T3 = 1 → 4 → 6 → 7 → 8

7. References
1. [Link]
introduction/
2. [Link]
3. N. Deo – Graph Theory With Applications to Engineering and Computer Science, Prentice Hall
of India,1987.

78
Unit 6: Construction of minimum spanning tree, Cut set, Cut vertex,
Coding and decoding.

1. Spanning Tree
1.1 Introduction
1.2 Properties of Spanning Tree

2. Minimum spanning tree

2.1 Construction of minimum spanning tree
2.1.1 Kruskal’s Algorithm
2.1.2 Prim’s Algorithm

3. Cut Set and Cut Vertex of Graph

3.1 Connectivity
3.2 Cut Vertex
3.3 Cut Set of a Graph
4. Summary
5. Keywords
6. Assessment Questions
7. Reference

79
OBJECTIVES

After studying this unit the student will be able to:

 Construct spanning tree for the given graph.
 Design minimum spanning tree for the given graph using standard algorithms like Prim’s
Algorithm and Kruskal’s Algorithm
 Check for the Connectivity in the graph

1. Spanning Tree:
A spanning tree of a connected graph G is a tree containing all the vertices of G. A spanning tree
of a graph is a maximal tree sub-graph of that graph.

1.1. Introduction

 Consider the following original graph:

The following Spanning trees are possible from the above graph:

80
1.2 Properties of Spanning Tree

 Number of vertices (V) in the graph and the spanning tree is the same.

 Number of edges in the spanning tree is equal to one less than the total number of
vertices (E = V-1).

 The total cost (or weight) of the spanning tree is defined as the sum of the edge weights
of all the edges of the spanning tree.
 There can be many possible spanning trees for a graph.

2. Minimum Spanning Tree

A minimum spanning tree (MST) is defined as a spanning tree that has the minimum weight
among all the possible spanning trees.

A MST or minimum cost spanning tree is that spanning tree, which covers all the vertices of the
graph with minimum edges and the sum of the weight of those edges is minimum among other
spanning trees of that graph as shown in Figure 1.

Figure. 1 Minimum Spanning Tree

2.1 Construction of Minimum Spanning Tree

The MST has all the properties of a spanning tree with an added constraint of having the
minimum possible weights among all possible spanning trees. There are several algorithms to

81
find the MST from a given graph. The two main methods to find minimum spanning tree are
explained below:

2.1.1 Kruskal’s Algorithm to find Minimum Spanning Tree

This is one of the popular algorithms for finding the MST from a connected, undirected graph.
The steps involved in this algorithm are as below:

Step 1: First, it sorts all the edges of the graph by their weights,

Step 2: Starts the iterations of finding the spanning tree.

Step 3: At each iteration, the algorithm adds the next lowest-weight edge one by one,
such that the edges picked until now does not form a cycle.

Illustration of Kruskal’s Algorithm to find Minimum Spanning Tree

Input Graph:

The graph contains 9 vertices and 14 edges. So, the MST formed will be having (9 – 1) = 8
edges.

82
After sorting:

Weight Source Destination

1 7 6

2 8 2

2 6 5

4 0 1

4 2 5

6 8 6

7 2 3

7 7 8

8 0 7

8 1 2

9 3 4

10 5 4

11 1 7

14 3 5

Now pick all edges one by one from the sorted list of edges

Step 1: Pick edge 7-6. No cycle is formed, include it.

83
Step 2: Pick edge 8-2. No cycle is formed, include it.

Step 3: Pick edge 6-5. No cycle is formed, include it.

Step 4: Pick edge 0-1. No cycle is formed, include it.

84
Step 5: Pick edge 2-5. No cycle is formed, include it.

Step 6: Pick edge 8-6. Since including this edge results in the cycle, discard it. Pick edge 2-3:
No cycle is formed, include it.

Step 7: Pick edge 7-8. Since including this edge results in the cycle, discard it. Pick edge 0-7. No
cycle is formed, include it.

85
Step 8: Pick edge 1-2. Since including this edge results in the cycle, discard it. Pick edge 3-4. No
cycle is formed, include it.

Note: Since the number of edges included in the MST equals to (V – 1) i.e. 9-1 = 8, so the
algorithm stops here.

2.1.2 Prim’s Algorithm to find Minimum Spanning Tree:

The algorithm starts with an empty spanning tree. The idea is to maintain two sets of vertices.
The first set contains the vertices already included in the MST, and the other set contains the
vertices not yet included. At every step, it considers all the edges that connect the two sets and
picks the minimum weight edge from these edges. After picking the edge, it moves the other
endpoint of the edge to the set containing MST.

A group of edges that connects two sets of vertices in a graph is called cut in graph theory. So, at
every step of Prim’s algorithm, find a cut, pick the minimum weight edge from the cut, and
include this vertex in MST Set (the set that contains already included vertices).

Step 1: Determine an arbitrary vertex as the starting vertex of the MST.

Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST
(known as fringe vertex).
Step 3: Find edges connecting any tree vertex with the fringe vertices.
Step 4: Find the minimum among these edges.

86
Step 5: Add the chosen edge to the MST if it does not form any cycle.
Step 6: Return the MST and exit

Note: For determining a cycle, we can divide the vertices into two sets [one set contains the
vertices included in MST and the other contains the fringe vertices.]

Illustration of Prim’s Algorithm:

Consider the following graph as an example for which we need to find the Minimum Spanning
Tree.

Step 1: Firstly, we select an arbitrary vertex that acts as the starting vertex of the Minimum
Spanning Tree. Here we have selected vertex 0 as the starting vertex.

Step 2: All the edges connecting the incomplete MST and other vertices are the edges {0, 1} and
{0, 7}. Between these two the edge with minimum weight is {0, 1}. So include the edge and
vertex 1 in the MST.

87
Step 3: The edges connecting the incomplete MST to other vertices are {0, 7}, {1, 7} and {1, 2}.
Among these edges the minimum weight is 8 which is of the edges {0, 7} and {1, 2}. Let us here
include the edge {0, 7} and the vertex 7 in the MST. [We could have also included edge {1, 2}
and vertex 2 in the MST].

Step 4: The edges that connect the incomplete MST with the fringe vertices are {1, 2}, {7, 6}
and {7, 8}. Add the edge {7, 6} and the vertex 6 in the MST as it has the least weight (i.e., 1).

88
Step 5: The connecting edges now are {7, 8}, {1, 2}, {6, 8} and {6, 5}. Include edge {6, 5} and
vertex 5 in the MST as the edge has the minimum weight (i.e., 2) among them.

Step 6: Among the current connecting edges, the edge {5, 2} has the minimum weight. So
include that edge and the vertex 2 in the MST.

Step 7: The connecting edges between the incomplete MST and the other edges are {2, 8}, {2,
3}, {5, 3} and {5, 4}. The edge with minimum weight is edge {2, 8} which has weight 2. So
include this edge and the vertex 8 in the MST.

89
Step 8: See here that the edges {7, 8} and {2, 3} both have same weight which are minimum.
But 7 is already part of MST. So we will consider the edge {2, 3} and include that edge and
vertex 3 in the MST.

Step 9: Only the vertex 4 remains to be included. The minimum weighted edge from the
incomplete MST to 4 is {3, 4}.

90
The final structure of the MST is as follows and the weight of the edges of the MST is (4 + 8 + 1
+ 2 + 4 + 2 + 7 + 9) = 37.

3. Cut Set and Cut Vertex of Graph

Whether it is possible to traverse a graph from one vertex to another is determined by how a
graph is connected. Connectivity is a basic concept in Graph Theory. Connectivity defines
whether a graph is connected or disconnected.

3.1 Connectivity

A graph is said to be connected if there is a path between every pair of vertex. From every vertex
to any other vertex, there should be some path to traverse. That is called the connectivity of a
graph. A graph with multiple disconnected vertices and edges is said to be disconnected.

3.2 Cut Vertex

Let 'G' be a connected graph. A vertex V ∈ G is called a cut vertex of 'G', if 'G-V' (Delete 'V'
from 'G') results in a disconnected graph. Removing a cut vertex from a graph breaks it in to two
or more graphs.

Note − Removing a cut vertex may render a graph disconnected.

A connected graph 'G' may have at most (n–2) cut vertices.

91
In the following graph, vertices 'e' and 'c' are the cut vertices.

By removing 'e' or 'c', the graph will become a disconnected graph.

Without 'g', there is no path between vertex 'c' and vertex 'h' and many other. Hence it is a
disconnected graph with cut vertex as 'e'. Similarly, 'c' is also a cut vertex for the above graph.

92
3.3 Cut Set of a Graph

Let 'G'= (V, E) be a connected graph. A subset E' of E is called a cut set of G if deletion of all the
edges of E' from G makes G disconnect.

If deleting a certain number of edges from a graph makes it disconnected, then those deleted
edges are called the cut set of the graph.

Take a look at the following graph. Its cut set is E1 = {e1, e3, e5, e8}.

After removing the cut set E1 from the graph, it would appear as follows –

Similarly there are other cut sets that can disconnect the graph −

 E3 = {e9} – Smallest cut set of the graph.

 E4 = {e3, e4, e5}

93
4. Summary

A minimum spanning tree of a connected, undirected graph is a subgraph that is a tree and
connects all the vertices together with the minimum possible total edge weight. There are two
main algorithms commonly used for constructing MSTs namely Kruskal's Algorithm and Prim's
Algorithm. The construction of a minimum spanning tree aims to connect all vertices of a graph
with the minimum total edge weight. Cutest and cut vertices are important concepts in graph
theory that help in understanding graph connectivity and structure, with cutest being edges
whose removal disconnects the graph and cut vertices being vertices whose removal disconnects
the graph.

5. Keywords
minimum spanning tree, Kruskal's Algorithm, Prim's Algorithm, Cutest, cut vertices

6. Assessment Questions:

1. Draw the minimum spanning tree for the following graph using kruskal Algorithm

Solution:

94
2. Draw the minimum spanning tree for the following graph using kruskal Algorithm

Solution:

3. Generate the minimum spanning tree for the following graph using prims Algorithm

95
Solution:

4. Generate the minimum spanning tree for the following graph using prims Algorithm

Solution:

96
5. Generate the minimum spanning tree for the following graph using prims Algorithm

Solution:

7. Reference:
1. N. Deo – Graph Theory with Applications to Engineering and Computer Science, Prentice
Hall of India,1987.
2. E. V. Krishnamurthy – Introductory Theory of Computer Science, Prentice Hall of India,
1980.
3. [Link]
algo-2/
4. [Link]
5. [Link]
6. [Link]

97
Unit 7. Computation - Algorithms complexities and Strategies,
Divide and conquer

1. Introduction

2. Complexities of an Algorithm

2.1 Space Complexity of an Algorithm

2.2 Time Complexity of an Algorithm

3. Asymptotic Notations (O, Ω, Θ)

3.1 Best Case, Worst Case, and Average Case in Asymptotic Analysis

3.2 Measurement of space complexity

3.3 Measurement of time complexity

4. Algorithm Strategies

4.1 Introduction

4.2 Divide and conquer approach

4.2.1 Binary Search

4.2.2 Merge Sort

5. Summary
6. Keywords
7. Assessment Questions
8. Reference

98
OBJECTIVES

After studying this unit the student will be able to:

 Understand the Algorithm complexities like space and time complexity

 Analyze space and time Complexity for a given algorithm.
 Determine the algorithmic complexities for Real-world Applications.
 Understand the Divide and Conquer Paradigm.
 Identify the Components of Divide and Conquer

1. Introduction

An algorithm is a finite set of instructions to be followed to solve problems. It is not language

specific; we can use any language and symbols to represent instructions. All algorithms should
satisfy the following properties.

1. Input: Zero or more inputs are supplied to the algorithm.

2. Output: At least one output is obtained.
3. Definiteness: Each instruction is unambiguous.
4. Finiteness: It will be terminated after a finite number of steps for all different cases.
5. Effectiveness: Each instruction should be very basic, so the purpose of those
instructions must be very clear.

2. Complexities of an Algorithm

Algorithm analysis is an important part of computational complexities. The complexity theory

provides the theoretical estimates for the resources needed by an algorithm to solve any
computational task.

Analysis of the algorithm is the process of analyzing the problem-solving capability of the
algorithm in terms of time and size of memory for storage required while implementation. Hence
the complexity of an algorithm computes the amount of time and space required by an algorithm

99
for an input of size (n). So, the complexity of an algorithm can be divided into two types namely
i) space complexity and ii) time complexity.

2.1 Space Complexity of an Algorithm

Space complexity is defined as the process of defining a formula for prediction of how much
memory space is required for the successful execution of the algorithm. The best
algorithm/program should have a low level of space complexity. The less space required, the
faster it executes. The general formula to calculate space complexity is the sum of Auxiliary
space and primary memory used by input variables.

The Space required by an algorithm is the sum of following components

 A fixed part that is independent of the input and output. This includes memory space
for codes, variables, constants and so on.
 A variable part that depends on the input, output and recursion stack called instance
characteristics

2.2 Time Complexity of an Algorithm

The time complexity is defined as the process of determining a formula for total time required
towards the execution of that algorithm through computer programs. This calculation is totally
independent of implementation and programming language. The time taken by a program is the
sum of the compile time and run or execution time.

3. Asymptotic Notations (O, Ω, Θ)

Asymptotic Notations are programming languages that allow you to analyze an algorithm's run
time by identifying its behavior as its input size grows. You can't compare two algorithms head
to head. It is heavily influenced by the tools and hardware you use for comparisons, such as the
operating system, CPU model, processor generation, and so on. Even if you calculate time and
space complexity for two algorithms running on the same system, the subtle changes in the
system environment may affect their time and space complexity. As a result, you compare space

100
and time complexity using asymptotic analysis. It compares two algorithms based on changes in
their performance as the input size is increased or decreased.

If our algorithm takes a lot of memory to execute, then our compiler will not allow us to run it.
To avoid compiler crashes, we need to compute the space complexity of our algorithm. There are
many notations available to compute space complexity:

i) Big-O notation : O
ii) Omega Notation: Ω
iii) Theta Notation: θ

i) Big-O notation: This big-O notation describes the asymptotic upper bound, the worst case of
space/time complexity. Basically, it's the measure of the maximum amount of space an algorithm
takes to grow with respect to the size of input data. The important big-O notations are as follows:

 Constant complexity: O (1): When the algorithm takes the same amount of space/time
regardless of the input size n, it is called constant complexity.
 Logarithmic complexity: O(logn)
When the algorithm takes space/time proportional to the log of the input size n, it is
called logarithmic complexity.
 Linear complexity: O(n)
When an algorithm takes space/time directly proportional to the input size n, it is called
linear complexity.
 Log-linear complexity: O(nlogn)
When the space/time complexity of an algorithm grows proportionally to the input size n
and a logarithmic factor log( ), it is called log-linear complexity.
 Polynomial complexity: O(n2)
When the space/time complexity grows proportionally to the square of the input size n, it
is called polynomial complexity.

101
ii) Omega notation: Ω

The omega notation describes the asymptotic lower bound. It is the best-case scenario in terms
of time and space complexity. Actually, it's the minimum amount of space/time our algorithm
takes to grow with respect to the input data.

iii) Theta notation: θ

The theta notation means that the space complexity of an algorithm is between its upper-bound
and lower-bound space and time complexity

3.1 Best Case, Worst Case, and Average Case in Asymptotic Analysis

 Best Case: It is defined as the condition that allows an algorithm to complete statement
execution in the shortest amount of time. In this case, the execution time serves as a
lower bound on the algorithm's time complexity.
 Average Case: The running time for each possible input combination is added and take
the average in the average case. Here, the execution time serves as both a lower and
upper bound on the algorithm's time complexity.
 Worst Case: It is defined as the condition that allows an algorithm to complete statement
execution in the shortest amount of time possible. In this case, the execution time serves
as an upper bound on the algorithm's time complexity.

102
3.2 Measurement of Space Complexity

Most developers use big-O notation because it's relatively easy to estimate the maximum amount
of space required. So we'll learn to measure the upper-bound of an algorithm in this section. Let's
take an example of a function that returns the sum of the two variables.

Example 1:

int sum(int arr[ ], int n) // n is the size of array arr

{
int arr_sum =0; // x takes 4 bits as integer variable

for (int i=0; i<n; i++) // i takes 4 bits as integer variable

{
arr_sum = arr_sum + arr[i];
}

return x;

In this program, there are five variables allocated in the memory:

 The array arr[] is integer type with size n so its space complexity is 4∗n bits.
 The integer variables in the int n , int i and int sum will take 4 bytes individually, that is,
bytes ( 4∗3=12 bytes).

The total memory this program takes (4∗n +12) bytes. The space complexity is increasing
linearly with the size nn, it can be expressed in big-O notation as O(n).

3.3 Measurement of Time Complexity

To express the time complexity of an algorithm, we use something called the “Big O notation”.
The Big O notation is a language we use to describe the time complexity of an algorithm. It's
how we compare the efficiency of different approaches to a problem, and helps us to make
decisions.

103
Example 2: Consider the below simple code to print “Hello World”
#include <iostream>
using namespace std;
int main()
{
cout << "Hello World";
return 0;
}

Output

Hello World

Time Complexity: In the above code “Hello World” is printed only once on the screen.
So, the time complexity is constant: O(1) i.e. every time a constant amount of time is required to
execute code, no matter which operating system or which machine configurations you are using.
Auxiliary Space: O(1)

Example 3:

#include <iostream>
using namespace std;

int main()
{

int i, n = 8;
for (i = 1; i <= n; i++) {
cout << "Hello World !!!\n";
}
return 0;
}

104
Output

Hello World !!!

Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!

Time Complexity: In the above code “Hello World !!!” is printed only n times on the screen, as
the value of n can change.

So, the time complexity is linear: O(n) i.e. every time, a linear amount of time is required to
execute code.

Auxiliary Space: O(1)

Example 4:

#include <iostream>
using namespace std;

int main()
{

int i, n = 8;
for (i = 1; i <= n; i=i*2) {
cout << "Hello World !!!\n";
}
return 0;
}

Output

Hello World !!!

105
Hello World !!!
Hello World !!!

Time Complexity: O(log2(n))

Auxiliary Space: O(1)

Example 5:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{

int i, n = 8;
for (i = 2; i <= n; i=pow(i,2)) {
cout << "Hello World !!!\n";
}
return 0;
}

Output

Hello World !!!

Time Complexity: O(log(log n))

Auxiliary Space: O(1)

106
4. Algorithm Strategies:

Algorithmic strategies are approaches or techniques used to design efficient algorithms for
solving problems. Different strategies are employed based on the nature of the problem and the
desired trade-offs between time, space, and other factors. Some common algorithmic strategies
include divide and conquer, greedy technique, dynamic programming and backtracking, etc.

In this chapter the Divide and Conquer approach will be explained. The other two approaches
namely greedy technique and will be explained in Unit 8.

4.1 Introduction

Divide and Conquer is one of the best-known general algorithm design technique. It works
according to the following general plan:
 Given a function to compute on ‘n’ inputs the divide-and-conquer strategy suggests
splitting the inputs into ‘k’ distinct subsets, 1<k<=n, yielding ‘k’ sub problems.
 These sub-problems must be solved, and then a method must be found to combine
sub- solutions into a solution of the whole.

 If the sub problems are still relatively large, then the divide-and-conquer strategy
can possibly be reapplied.

 Often the sub-problems resulting from a divide-and-conquer design are of the same
Type as the original problem. For those cases their application of the divide-and-
conquer principle is naturally expressed by a recursive algorithm.

A typical case with k=2 is diagrammatically shown below.

Problem of size n

Sub Problem of size n/2 Sub Problem of size n/2

Solution to the sub problem 1 Solution to the sub problem 2

107

Solution to the original problem

Control Abstraction for divide and conquer
Algorithm DAndC(P)
{
if Small(P) then return S(P);
else
{
divide P into smaller instances P1 , P2 , … … Pk , k ≥ 1;
Apply DAndC to each of this sub problems;
return Combine (DAndC(P1 ), DAndC(P2 ), … … DAndC(Pk ));
}
}
In the above specification,

 Initially DAndC(P) is invoked, where ‘P’ is the problem to be solved.

 Small (P)is a Boolean-valued function that determines whether the input size is
small enough that the answer can be computed without splitting. If this so, the
function ‘S’ is invoked. Otherwise, the problem P is divided into smaller sub
problems. These sub problems P1, P2 …Pk are solved by recursive application of
DAndC.
 Combine is a function that determines the solution to P using the solutions to the ‘k’
sub problems.

4.2 Divide and conquer approach

4.2.1 Binary Search

Problem definition: Let ai, 1 ≤ i ≤ n be a list of elements that are sorted in non-decreasing
order. The problem is to find whether a given element x is present in the list or not. If x is
present we have to determine a value j (element’s position) such that aj=x. If x is not in the
list, then j is set to zero.
Solution: Let P = (n, ai…al, x) denote an arbitrary instance of search problem where n is

108
the number of elements in the list, ai…al is the list of elements and x is the key element to
be searched for in the given list. Steps used in Binary search algorithm is given below

Step1: Pick an index q in the middle range [i,l] i.e. q=[(𝑛+1)/2] And compare x with aq.

Step2: if x=aq i.e. key element is equal to mid element, the problem is immediately solved.
Step3: if x<aq in this case x has to be searched for only in the sub-list ai,ai+1,……,aq-1.. Therefore
problem reduces to (q-i,ai…aq-1,x).

Step4: if x >aq, x has to be searched for only in the sub-list aq+1,…,al. Therefore, problem reduces
to (l-i, aq+1…al, x).

For the above solution procedure, the Algorithm can be implemented as recursive as shown
below.

Recursive approach

binarySearch(array, element, start, finish)

if start<=finish

midIndex = (start + finish) / 2

if item == array[midIndex]

return midIndex

else if item < array[midIndex]

return binarySearch(array, element, midIndex + 1, finish)

else

return binarySearch(array, element, start, midIndex – 1)

return -1

109
Example 6. Working of Binary Search Algorithm

Now, let’s understand the working of the Binary Search Algorithm. Let’s take an example of a
sorted array:

Let the elements of the array are –

0 1 2 3 4 5 6 7 8

11 13 25 28 35 45 55 60 65

Let the element to search is, K = 60

Now, we need to find out mid of the array with the formula:
(Start+finish)/2
So, in the given array –
start = 0
finish= 8
mid = (0 + 8)/2 = 4. Thus, 4 is in the middle of the array.

0 1 2 3 4 5 6 7 8

11 13 25 28 35 45 55 60 65

A[mid] = 35
A[mid] < K (or, 35 < 60)
So, Start = mid +1 and Finish = 8
Now, mid = (beg + end)/2 = 13/2 = 6

110
0 1 2 3 4 5 6 7 8

11 13 25 28 35 45 55 60 65

A[mid] = 55
A[mid] < K (or, 55 < 60)
So, Start = mid +1 = 7 and Finish = 8
Now, mid = (beg + end)/2 = 15/2 = 7

0 1 2 3 4 5 6 7 8

11 13 25 28 35 45 55 60 65

A[mid] = 60
A[mid] = K (or, 60= 60)
So, position = mid
Now, we got the element at the
7th position of the array

As we have found here the searched element, the index of the matched element will return.

Binary Search Complexity

Now, let’s understand the time and space complexity of Binary Search in the best, average, and
worst cases.

1. Time Complexity:

 Best case complexity: When the element to be searched is found in the first comparison,
i.e. when the searched element is the first middle element, then it is the best case
occurrence. Thus, in the binary search, the best case time complexity is O(1).

111
 Average Case Complexity: In the binary search, the average case of time complexity is
O(log n).
 Worst-case complexity: We need to reduce the search space till it has only a single
element. Thus, the worst case in time complexity is O(log n)

2. Space Complexity:

 O(1) is the space complexity in the binary search algorithm.

4.2.2 Merge Sort using divide and conquer approach

Merge sort is a sorting algorithm that follows the divide-and-conquer approach. It

works by recursively dividing the input array into smaller subarrays and sorting those
sub-arrays then merging them back together to obtain the sorted array.
In simple terms, we can say that the process of merge sort is to divide the array into two
halves, sort each half, and then merge the sorted halves back together. This process is
repeated until the entire array is sorted.
Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows
the divide-and-conquer approach to sort a given array of elements.

Here’s a step-by-step explanation of how merge sort works:

1. Divide: Divide the list or array recursively into two halves until it can no more be
divided.
2. Conquer: Each sub-array is sorted individually using the merge sort algorithm.

3. Merge: The sorted sub-arrays are merged back together in sorted order. The process
continues until all elements from both sub-arrays have been merged.

Example 7. Illustration of Merge Sort:

Let’s sort the array or list [38, 27, 43, 10] using Merge Sort

Step 1: Splitting the array into two equal halves.

112
Partition

38 27 43 10

Step 2: Splitting the sub arrays into two halves.

Partition Partition

38 27 43 10

Step 3: Merging unit length cells into sorted sub arrays.

38 27 43 10

Merge Merge

27 38 10 43

113
Step 4: Merging sorted sub arrays into the sorted array.

27 38 10 43

Merge

10 27 38 43

Let’s look at the working of above example:

Divide:

 [38, 27, 43, 10] is divided into [38, 27] and [43, 10].

 [38, 27] is divided into [38] and [27].

 [43, 10] is divided into [43] and [10].

Conquer:

 [38] is already sorted.

 [27] is already sorted.

 [43] is already sorted.

 [10] is already sorted.

Merge:

 Merge [38] and [27] to get [27, 38].

114
 Merge [43] and [10] to get [10,43].

 Merge [27, 38] and [10,43] to get the final sorted list [10, 27, 38, 43]

Therefore, the sorted list is [10, 27, 38, 43]

Complexity

 Time Complexity — O(nlogn) for best and worst scenarios, even if the array is sorted it
will take the same time
 Notice the steps getting divided by two as we proceed further 4,2,1 ie O(logn)
 If we merge n components at each step. O(n)
 Space Complexity — O(n), helper array space to copy elements to res.

Advantages and Disadvantages of Divide and Conquer

 The divide and conquer strategy involves breaking down a problem into smaller sub-
problems, solving them independently, and then combining the solutions to obtain the
final solution.
 The steps typically involved in the divide and conquer approach are divide, conquer, and
combine.
 The strategy is often implemented using recursion, where a problem is recursively
divided into smaller sub-problems until a base case is reached.
 Examples of algorithms that use the divide and conquer strategy include merge sort,
quicksort, and binary search.

5. Summary

The complexity of an algorithm can be defined as the amount of space and time required by the
algorithm to solve a problem. The space complexity is the amount of space or memory required
by an algorithm while solving a problem. Time complexity measures the amount of time an
algorithm takes to run as a function of the input size. Big O notation is commonly used to
express the worst-case time complexity of an algorithm in terms of a mathematical function.

115
Understanding algorithm complexities and strategies is essential for developing efficient
computational solutions to complex problems. By analyzing time and space complexities,
exploring common strategies such as divide and conquer, dynamic programming, and greedy
algorithms, and applying them to real-world applications, practitioners can design robust and
scalable systems that meet the demands of modern computing environments.

6. Keywords
Algorithms strategy, Time complexity, space complexity, Divide and Conquer

7. Assessment Questions

1. Apply divide and conquer strategy for the following algorithms

 Selection sort
 Insertion sort
 Bubble sort
 Quick sort
 Linear search
 Binary search


2. Analyze the space and time complexity for following sorting algorithms
 Selection sort
 Insertion sort
 Bubble sort
 Quick sort
3. Analyze the space and time complexity for following searching algorithms
 Linear search
 Binary search

116
8. Reference

1. [Link]
2. [Link]
3. E. V. Krishnamurthy – Introductory Theory of Computer Science, Prentice Hall of India,
1980.

4. Horowitz and Sahni – Fundamentals of Computer Algorithms, Addison Wesley, 1987.

117
Unit 8. Greedy technique, Introduction to NP hard problems

1. Greedy Technique
1.1 Introduction
1.2 General Method

2. Greedy Algorithms
2.1 Fractional Knapsack Problem
2.1.1 Knapsack Algorithm

2.2 Huffman Coding

2.2.1 Introduction
2.2.2 Working principle of Huffman Coding
2.2.3 Applications of Greedy Algorithm
2.2.4 Disadvantages / Limitations of Using a Greedy Algorithm

3. Introduction to NP hard problems

3.1 Key Concepts
3.2 Characteristics and Implications
3.3 Applications of NP-Hard Problems

4. Summary
5. Keywords
6. Assessment Questions
7. Reference

118
OBJECTIVES

After studying this unit the student will be able to:

 Explain the basic principles of Greedy algorithms, including making locally optimal
choices.
 Analyze the time and space complexity of Greedy algorithms.
 Illustrate the concept with simple examples such as the Fractional Knapsack problem or
Minimum Spanning Tree algorithms.
 Introduce classic NP-hard problems such as the Traveling Salesman Problem (TSP), the
Knapsack Problem, and the Graph Coloring Problem.
 Discuss real-world applications of NP-hard problems in various fields, including
logistics, network design, and resource allocation.

1. GREEDY TECHNIQUE

1.1 Introduction

The greedy technique is an algorithmic strategy that makes locally optimal choices at each
step in the hope of finding a global optimum solution. Greedy algorithms make the choice
that seems best at the current stage without considering the future consequences. The strategy
does not guarantee an optimal solution for all problems but can be effective in some cases.
The greedy algorithm does not always guarantee the optimal solution however it generally
produces solutions that are very close in value to the optimal.

Understanding algorithm complexities and employing algorithmic strategy like the greedy
technique is crucial for designing efficient and effective algorithms. By analyzing the time
and space complexities of algorithms and choosing appropriate strategies, we can develop
algorithms that solve problems efficiently and provide optimal solutions.

Greedy algorithms seek to optimize a function by making choices (greedy criterion) which
are the best locally but do not look at the global problem. The result is a good solution but
not necessarily the best one. Greedy algorithms are often efficient and easy to implement.

119
Examples of algorithms that use the greedy technique include the Knapsack problem,
Dijkstra's algorithm and the Huffman coding algorithm.

1.2 General Method: The greedy method is the straight forward design technique applicable to
variety of applications. The greedy approach suggests constructing a solution through a sequence
of steps, each expanding a partially constructed solution obtained so far, until a complete
solution to the problem is reached. On each step the choice made must be:

Feasible: it has to satisfy the problem’s constraints.

Locally optimal: it has to be the best local choice among all feasible choices available on that
step.

Irrevocable: Once made, it cannot be changed on subsequent steps of the algorithm

As a rule, greedy algorithms are both intuitively appealing and simple. Given an optimization
problem, it is usually easy to figure out how to proceed in a greedy manner, possibly after
considering a few small instances of the location.

Algorithm Greedy(a,n)
// a[1: n] contains the n inputs
{
Solution :=0 // initialize the solution
For i:= 1 to n do
{ x = select(a);
If feasible(solution, x) then
Solution=union(solution, x);
}
Return solution;

120
2. Greedy Algorithms

Below are some examples of Greedy Algorithm:

 Fractional Knapsack: Optimizes the value of items that can be fractionally included in a
knapsack with limited capacity.
 Huffman coding: Compresses data by assigning shorter codes to more frequent symbols.

2.1 Fractional Knapsack Problem

The knapsack problem states that − given a set of items, holding weights and profit values, one
must determine the subset of the items to be added in a knapsack such that, the total weight of
the items must not exceed the limit of the knapsack and its total profit value is maximum. It is
one of the most popular problems that take greedy approach to be solved. It is called as the
Fractional Knapsack Problem.

To explain this problem a little easier, consider a test with 12 questions, 10 marks each, out of
which only 10 should be attempted to get the maximum mark of 100. The test taker now must
calculate the highest profitable questions – the one that he’s confident in – to achieve the
maximum mark. However, he cannot attempt all the 12 questions since there will not be any
extra marks awarded for those attempted answers. This is the most basic real-world application
of the knapsack problem.

2.1.1 Knapsack Algorithm

The weights (Wi) and profit values (Pi) of the items to be added in the knapsack are taken as an
input for the fractional knapsack algorithm and the subset of the items added in the knapsack
without exceeding the limit and with maximum profit is achieved as the output. The steps
involved in solving knapsack problem is given below.

121
Step 1: Consider all the items with their weights and profits mentioned respectively.

Step 2: Calculate Pi/Wi of all the items and sort the items in descending order based on
their Pi/Wi values.

Step 3: Without exceeding the limit, add the items into the knapsack.

Step 4: If the knapsack can still store some weight, but the weights of other items exceed
the limit, the fractional part of the next time can be added.

Example 1: For the given set of items and the knapsack capacity of 10 kg, find the subset of the items
to be added in the knapsack such that the profit is maximum.

Items 1 2 3 4 5

Weights (in kg) 3 3 2 5 1

Profits 10 15 10 12 8

Solution

Step 1: Given, n = 5

Wi = {3, 3, 2, 5, 1}
Pi = {10, 15, 10, 12, 8}

Step 2: Calculate Pi/Wi for all the items

Items 1 2 3 4 5

Weights (in kg) 3 3 2 5 1

Profits 10 15 10 20 8

Pi/Wi 3.3 5 5 4 8

Arrange all the items in descending order based on Pi/Wi

122
Items 5 2 3 4 1

Weights (in kg) 1 3 2 5 3

Profits 8 15 10 20 10

Pi/Wi 8 5 5 4 3.3

Step 3: Without exceeding the knapsack capacity, insert the items in the knapsack with
maximum profit.

Knapsack = {5, 2, 3}

Step 4: However, the knapsack can still hold 4 kg weight, but the next item having 5 kg weight
will exceed the capacity. Therefore, only 4 kg weight of the 5 kg will be added in the knapsack.

Items 5 2 3 4 1

Weights (in kg) 1 3 2 5 3

Profits 8 15 10 20 10

Knapsack 1 1 1 4/5 0

Hence, the knapsack holds the weights = [(1 * 1) + (1 * 3) + (1 * 2) + (4/5 * 5)] = 10,
with maximum profit of [(1 * 8) + (1 * 15) + (1 * 10) + (4/5 * 20)] = 37.

Time Complexity: O(N * logN)

Auxiliary Space: O(N)

123
2.2 Huffman Coding

2.2.1 Introduction

Huffman Coding is a technique that is used for compressing data to reduce its size without losing
any of its details. It was first developed by David Huffman and was named after him. Huffman
Coding is generally used to compress the data which consists of the frequently repeating
characters. Huffman Coding is a famous Greedy algorithm. It is said to be a Greedy Algorithm
because the size of code assigned to a character depends on the frequency of the character. The
character with higher frequency gets the short-length variable code and vice-versa for characters
with lower frequency. It uses a variable-length encoding which means that it assigns a variable-
length code to all the characters in the given stream of data.

 Prefix Rule
This rule basically means that the code which is assigned to any character should not be the
prefix of any other code.
If this rule is not followed, then some ambiguities can occur during the decoding of the Huffman
tree formed.

Example: To understand more about this rule let's consider an example: For example, code is
given for each character:
a-0
b-1
c – 01
Now assume that the generated bit-stream is 001, while decoding the code it can be written as
follows:

This means that the given string can be aab or else ac, such ambiguities can be avoided if we
follow the prefix rule. Since no code word is a prefix of any other, the code word that starts with
encoded data is unambiguous.

124
2.2.2 Working principle of Huffman Coding

There are mainly two major steps involved in obtaining the Huffman Code for each unique
character:

1. Firstly, build a Huffman Tree from the given stream of data (only taking the unique
characters).
2. Secondly, we need to traverse the Huffman Tree which is formed and assign codes to
characters and decode the given string using these Huffman codes.

 Illustration of Huffman Coding

Steps involved in building the Huffman tree from the given set of characters

Input string str = "abbcdbccdaabbeeebeab"

Here, if Huffman Coding is used for data compression, then we need to determine the following
for decoding:

 Huffman Code for each character

 Average code length
 Length of Huffman encoded message (in bits)

The last two of them are found using formulas that are discussed below.

 Algorithm to Build a Huffman Tree from Input Characters

Step 1: Sort the characters in ascending order of frequency. These are stored in a
priority queue Q/ min-heap.
Step 2: Create a leaf node for every unique character and its frequency from the
given stream of data.
Step 3: Extract the two minimum frequency nodes from the nodes and the sum of
these frequencies is made the new root of the tree.
Step 4: While extracting the nodes with the minimum frequency from the min-heap:

125
o Make the first extracted node its left child and the other extracted node as its right
child.
o Add this node to the min-heap.
o Since the minimum frequency should always be on the left side of the root.

Repeat steps 3 and 4 until the heap contains only one node (i.e, all characters are included
in the tree). The remaining node is the root node and the tree is complete.

Example of Huffman Coding

Character Frequency/count

a 4

b 7

c 3

d 2

e 4

Let us understand the algorithm with the example:

126
Huffman Coding Algorithm

Step 1: Build a min-heap that contains 5 (number of unique characters from the given stream of
data) nodes where each node represents the root of a tree with a single node.

Step 2: Get two minimum frequency nodes from the min heap. Also, add a new internal node
formed by combining the two nodes which are extracted, frequency 2 + 3 = 5.

 Now min-heap contains 4 nodes where 3 nodes are roots of trees with a single element
each, and one heap node is the root of the tree with 2 elements

Step 3: Similarly, get the two minimum frequency nodes from the heap. Also add a new internal
node formed by combining the two nodes which are extracted, the frequency to be added in the
tree is 4 + 4 = 8

127
 Now min heap contains 3 nodes where 1 node is the root of trees with a single element,
and two heap nodes are the root of the tree with more than one node.

Step 4: Get the two minimum frequency nodes. Also add a new internal node formed by
combining the two nodes which are extracted, frequency to be added in the tree is 5 + 7 = 12.

 When designing a Huffman tree, we need to check that the minimum value is placed on
the left side of the tree always and the second one should be on the right side of the tree.
Now the tree formed is shown in the below image:

Step 5: Get the next two minimum frequency nodes. Also, add a new internal node
formed by combining the two nodes which are extracted, the frequency to be added in the
tree is 12 + 8 = 20.

128
Repeat the procedure till all the unique characters are inserted into the tree. The above image is
the Huffman tree formed for the given set of characters.

Now to form the code for each character, for each non-leaf node, assign 0 to the left edge and 1
to the right edge.

Rules to be followed while assigning weights for edges:

 If you assign weight 0 to the left edges, then we should assign weight 1 to the right
edges.
 If you assign weight 1 to the left edges, then we need to assign weight 0 to the right
edges.
 Any of the above two conventions can be followed.
 But use the same convention during decoding the tree as well.

The modified tree after assigning the weights is shown below:

129
The Code obtained for each character is shown below:

Character Frequency/count Code

a 4 01

b 7 11

c 3 101

d 2 100

e 4 00

2.2.3 Applications of Greedy Algorithm

 Assigning tasks to resources to minimize waiting time or maximize efficiency.
 Selecting the most valuable items to fit into a knapsack with limited capacity.
 Dividing an image into regions with similar characteristics.
 Reducing the size of data by removing redundant information.

2.2.4 Disadvantages/Limitations of Using a Greedy Algorithm

 Greedy algorithms may not always find the best possible solution.
 The order in which the elements are considered can significantly impact the outcome.
 Greedy algorithms focus on local optimizations and may miss better solutions that require
considering a broader context.
 Greedy algorithms are not applicable to problems where the greedy choice does not lead
to an optimal solution.

2. Introduction to NP hard problems

NP-Hard problems are a class of computational problems that are considered to be among the
most difficult problems in computer science. They belong to a broader class of problems called
Nondeterministic Polynomial (NP time). Understanding NP-Hard problems is essential for
exploring the limits of computation and algorithmic complexity.
130
3.1 Key Concepts

1. Polynomial Time: A problem is said to be solvable in polynomial time if an algorithm

exists that can solve it in a time that is bounded by a polynomial function of the input
size.
2. Nondeterministic Polynomial Time (NP): NP refers to the class of decision problems
for which a given solution can be verified as correct in polynomial time. This means that
if a solution is proposed, it can be checked efficiently.
3. Reduction: In the context of NP-Hard problems, reduction refers to the process of
transforming one problem into another problem. If problem A can be reduced to problem
B, it means that an algorithm for solving problem B can be used to solve problem A.
4. NP-Completeness: A problem is said to be NP-Complete if it is both in the class NP and
any problem in the NP class can be reduced to it. NP-Complete problems are some of the
most challenging problems in computer science.
5. NP-Hardness: NP-Hard refers to a class of problems that are at least as hard as the
hardest problems in NP, but they may not necessarily be in NP themselves. In other
words, every problem in NP can be reduced to an NP-Hard problem.

3.2 Characteristics and Implications

1. Complexity: NP-Hard problems have exponential or super polynomial time complexity.

This means that there is no known polynomial-time algorithm for solving them, and it is
widely believed that such an algorithm does not exist.
2. Optimal Solutions: NP-Hard problems often require finding optimal solutions or
approximations to solutions. It is generally not feasible to solve them exactly for large
problem sizes, so approximation algorithms or heuristics are used.
3. Real-World Applications: Many practical problems in various domains, such as
scheduling, optimization, and resource allocation, have been shown to be NP-Hard. The
difficulty of these problems poses challenges for finding efficient solutions in real-world
scenarios.
4. Importance: NP-Hard problems have significant theoretical and practical implications.
They are used as benchmarks for algorithmic complexity analysis, and the study of their

131
properties helps in understanding the limits of computation and the classification of
problem difficulty.

3.3 Applications of NP-Hard Problems

1. Traveling Salesman Problem (TSP)

2. Knapsack Problem
3. Graph Coloring Problem
4. 3-SAT (Boolean Satisfiability) Problem
5. Hamiltonian Cycle Problem
6. Subset Sum Problem

NP-Hard problems are highly complex computational problems for which no known polynomial-
time algorithm exists. Understanding NP-Hard problems is crucial for evaluating the difficulty of
computational tasks, developing approximation algorithms, and exploring the boundaries of
computational feasibility.

4. Summary
The Greedy technique is a fundamental strategy used in algorithm design to solve optimization
problems by making locally optimal choices at each step. It operates on the principle of selecting
the best available option at each decision point, without reconsidering previous choices. Greedy
algorithms are easy to conceptualize and implement, often resulting in efficient solutions for a
wide range of problems. Common examples of Greedy algorithms include algorithms for solving
the Fractional Knapsack problem, Minimum Spanning Trees for finding shortest paths in graphs.
NP-hard problems are a class of computational problems that are at least as hard as the hardest
problems in the complexity class NP (nondeterministic polynomial time). They are characterized
by the property that no known polynomial-time algorithm exists to solve them.

5. Keywords
Greedy technique, Minimum Spanning Trees, Fractional Knapsack Problem, Huffman Coding,
NP-hard problem.

132
6. Assessment Questions
1. Find how many bits may be required for encoding the message ‘MISSISSIPPI’ using
Huffman coding
Solution:

Character Frequency Code Code Length

M 1 100 3
P 2 101 3
S 4 11 2
I 4 0 1

Total number of bits

= freq(m) * code length(m) + freq(p) * code_length(p) + freq(s) * code_length(s) + freq(i) *
code length(i)
= 1*3 + 2*3 + 4*2 + 4*1 = 21

2. Find the Huffman Code for each character for the content of following table.

Characters Frequencies
a 10

e 15

i 12
o 3
u 4
s 13
t 1

133
Solution:

a = 111

e = 10

i = 00

o = 11001

u = 1101

s = 01

t = 11000

7. References

1. [Link]
2. [Link]
3. Horowitz and Sahni – Fundamentals of Computer Algorithms, Addison Wesley, 1987.

134

Common questions