Unit 1 Introduction to Algorithms
Structure:
1.1 Introduction
Objectives
1.2 Concept of Algorithm
Etymology
Definitions of Algorithm
1.3 Role of Algorithm in Computing
Analysis and design of algorithms
Properties of algorithms
Algorithm, program and psuedocode
Use of algorithms in computing
1.4 Fundamentals of Algorithm
Asymptotic notations
Time and space complexity and efficiency
1.5 Important Types of Algorithm
Simple recursive
Backtracking
Divide and conquer
Dynamic programming
Greedy algorithms
Branch and bound algorithms
Brute force algorithms
Randomized algorithms
1.6 Fundamental Data Structures
Data structure definition
Use of data structure
Data structure classification
Data structure characteristics
1.7 Summary
1.8 Glossary
1.9 Terminal Questions
1.10 Answers
,1.1 Introduction
It is difficult to
to solve problems in a systematic way.
We algorithms
use
Different fields of
definition for an algorithm.
give a single specific
solve their own problems.
development and study use algorithms to
Levitin defines algorithm as given below:
instructions for solving a
"An algorithm is a sequence of unambiguous
required output for any legitimate input in a
problem, ie., for obtaining a
finite amount of time."
This unit covers the various definitions of algorithm, its types, properties and
on solving a problem
the steps for designing it. This unit gives a brief idea
It also introduces
using different algorithmic problem solving techniques.
various data structures, their classification and characteristics.
Objectives:
After studying this unit, you should be able to:
define 'Algorithm
explain the role of algorithm in computing
describe the fundamentals ofalgorithms
list the important types of algorithms
.describe the fundamental data structures
1.2 Concept of Algorithm
We use computers to solve lots of problems in a fast and accurate way.
Therefore we need eficient algorithms for every process in a computer. The
concept of algorithms is in use from the early years of computation and
study. Let us start with the etymology of algorithms. We will also study the
different definitions of algorithms used to solve problems in different areas.
1.2.1 Etymology
The word is derived from the name of Abu Abdullah
'algorithm' Muhammad
lbn Musa al-Khwarizmi, a 9th-century Persian mathematician, astronomer,
geographer and scholar. This scholar wrote the first book on systematic
solution of linear and quadratic equations namely Kitab al-Jabr wa-l
Mugabala. The rules for performing arithmetic using Arabic numerals were
originally known as 'algorism' but later in the 18" century it was changed to
algorithm'.
, 1.2.2 Definitions of algorithm
An algorithm is defined as a set of well defined instructions used to
accomplish a particular task. It is considered as the cornerstone of good
programming. The efficiency of algorithms depends upon speed, size and
resource consumption. Different algorithms may finish the same process
with a different set of instructions in more or less time, space, or effort than
others. There is no fixed definition for an algorithm. It varies according to the
area of use.
Various definitions of algorithms are given below:
It is the exact set of instructions describing the order of actions to
achieve the result of the decision problem in finite time- (Old
interpretation).
"Algorithm is a finite set of rules that defines the sequence of operations
to solve a specific set of goals and has five important features:
finiteness, definiteness, input, output, efficiency"- (D. Knuth).
"Algorithms are all systems of calculations performed on strictly defined
rules, which, after a number of steps obviously leads to the solution of
the problem" - (A. Kolmogorov).
"Algorithm is the exact prescription, defining the computing process,
going from the variable input data to the desired result" - (A. Markov).
"Algorithm is the exact requirement of the performance in a specific
order of certain operations, leading to the solution of all problems of this
type" (Philosophical dictionary, ed. M. Rosenthal).
Self Assessment Questions
1. The rules for performing arithmetic using Arabic numerals were originally
known as
2. The efficiency of algorithms depends upon
and consumption.
3. An algorithm is considered as the cornerstone of
1.3 Role of Algorithm in Computing
In the previous section we discussed the definitions and basic use of
algorithms. Now, let us see how algorithms are used for computing.
We believe that a computer can do anything and everything that we
imagine. But the truth is that the computers work on algorithms written by
Structure:
1.1 Introduction
Objectives
1.2 Concept of Algorithm
Etymology
Definitions of Algorithm
1.3 Role of Algorithm in Computing
Analysis and design of algorithms
Properties of algorithms
Algorithm, program and psuedocode
Use of algorithms in computing
1.4 Fundamentals of Algorithm
Asymptotic notations
Time and space complexity and efficiency
1.5 Important Types of Algorithm
Simple recursive
Backtracking
Divide and conquer
Dynamic programming
Greedy algorithms
Branch and bound algorithms
Brute force algorithms
Randomized algorithms
1.6 Fundamental Data Structures
Data structure definition
Use of data structure
Data structure classification
Data structure characteristics
1.7 Summary
1.8 Glossary
1.9 Terminal Questions
1.10 Answers
,1.1 Introduction
It is difficult to
to solve problems in a systematic way.
We algorithms
use
Different fields of
definition for an algorithm.
give a single specific
solve their own problems.
development and study use algorithms to
Levitin defines algorithm as given below:
instructions for solving a
"An algorithm is a sequence of unambiguous
required output for any legitimate input in a
problem, ie., for obtaining a
finite amount of time."
This unit covers the various definitions of algorithm, its types, properties and
on solving a problem
the steps for designing it. This unit gives a brief idea
It also introduces
using different algorithmic problem solving techniques.
various data structures, their classification and characteristics.
Objectives:
After studying this unit, you should be able to:
define 'Algorithm
explain the role of algorithm in computing
describe the fundamentals ofalgorithms
list the important types of algorithms
.describe the fundamental data structures
1.2 Concept of Algorithm
We use computers to solve lots of problems in a fast and accurate way.
Therefore we need eficient algorithms for every process in a computer. The
concept of algorithms is in use from the early years of computation and
study. Let us start with the etymology of algorithms. We will also study the
different definitions of algorithms used to solve problems in different areas.
1.2.1 Etymology
The word is derived from the name of Abu Abdullah
'algorithm' Muhammad
lbn Musa al-Khwarizmi, a 9th-century Persian mathematician, astronomer,
geographer and scholar. This scholar wrote the first book on systematic
solution of linear and quadratic equations namely Kitab al-Jabr wa-l
Mugabala. The rules for performing arithmetic using Arabic numerals were
originally known as 'algorism' but later in the 18" century it was changed to
algorithm'.
, 1.2.2 Definitions of algorithm
An algorithm is defined as a set of well defined instructions used to
accomplish a particular task. It is considered as the cornerstone of good
programming. The efficiency of algorithms depends upon speed, size and
resource consumption. Different algorithms may finish the same process
with a different set of instructions in more or less time, space, or effort than
others. There is no fixed definition for an algorithm. It varies according to the
area of use.
Various definitions of algorithms are given below:
It is the exact set of instructions describing the order of actions to
achieve the result of the decision problem in finite time- (Old
interpretation).
"Algorithm is a finite set of rules that defines the sequence of operations
to solve a specific set of goals and has five important features:
finiteness, definiteness, input, output, efficiency"- (D. Knuth).
"Algorithms are all systems of calculations performed on strictly defined
rules, which, after a number of steps obviously leads to the solution of
the problem" - (A. Kolmogorov).
"Algorithm is the exact prescription, defining the computing process,
going from the variable input data to the desired result" - (A. Markov).
"Algorithm is the exact requirement of the performance in a specific
order of certain operations, leading to the solution of all problems of this
type" (Philosophical dictionary, ed. M. Rosenthal).
Self Assessment Questions
1. The rules for performing arithmetic using Arabic numerals were originally
known as
2. The efficiency of algorithms depends upon
and consumption.
3. An algorithm is considered as the cornerstone of
1.3 Role of Algorithm in Computing
In the previous section we discussed the definitions and basic use of
algorithms. Now, let us see how algorithms are used for computing.
We believe that a computer can do anything and everything that we
imagine. But the truth is that the computers work on algorithms written by
