Chapter

Introduction
1
1.1 History of
Algorithms
While looking around and marveling at the technological 1.2 Definition,
advancements of this world—both within and without, one cannot Structure and
but perceive the intense and intrinsic association of the disciplines Properties of
of Science and Engineering and their allied and hybrid counterparts, Algorithms
with the ubiquitous machines called computers. In fact it is difficult 1.3 Development of an
to spot a discipline that has distanced itself from the discipline of Algorithm
computer science. To quote a few, be it a medical surgery or
diagnosis performed by robots or doctors on patients half way 1.4 Data structures and
across the globe, or the launching of space crafts and satellites into Algorithms
outer space, or forecasting tornadoes and cyclones, or the more 1.5 Data structure—
mundane needs of online reservations of tickets or billing at Definition and
the food store, or control of washing machines etc. one cannot but Classification
deem computers to be omnipresent, omnipotent, why even 1.6 Organization of the
omniscient ! (Refer Fig. 1.1.) Book

Fig. 1.1 Omnipresence of computers

2 Data Structures and Algorithms

In short, any discipline that calls for problem-solving using computers, looks up to the
discipline of computer science for efficient and effective methods and techniques of solutions to
the problems in their respective fields. From the point of view of problem solving, the discipline
of computer science could be naively categorized into the following four sub areas notwith-
standing the overlaps and grey areas amongst themselves:
l Machines What machines are appropriate or available for the solution of a problem?
What is the machine configuration – its processing power, memory capacity
etc., that would be required for the efficient execution of the solution?
l Languages What is the language or software with which the solution of the problem
needs to be coded? What are the software constraints that would hamper the
efficient implementation of the solution?
l Foundations What is the model of a problem and its solution? What methods need to be
employed for the efficient design and implementation of the solution? What is
its performance measure?
l Technologies What are the technologies that need to be incorporated for the solution of the
problem? For example, does the solution call for a web based implementation
or needs activation from mobile devices or calls for hand shaking broadcasting
devices or merely needs to interact with high end or low end peripheral
devices?
Figure 1.2 illustrates the categorization of the discipline of computer science from the point of
view of problem solving.
One of the core fields that belongs to the
foundations of computer science deals with
the design, analysis and implementation of
algorithms for the efficient solution of the
problems concerned. An algorithm may be
loosely defined as a process, or procedure or
method or recipe. It is a specific set of rules
to obtain a definite output from specific
inputs provided to the problem.
The subject of data structures is intrin-
sically connected with the design and
implementation of efficient algori-thms.
Data structures deals with the study of
methods, techniques and tools to organize or
structure data. Fig. 1.2 Discipline of computer science from the
Next, the history, definition, classification, point of view of problem solving
structure and properties of algorithms are
discussed.

History of Algorithms 1.1

The word algorithm originates from the Arabic word algorism which is linked to the name of the
Arabic mathematician Abu Jafar Mohammed Ibn Musa Al Khwarizmi (825 A.D.). Al Khwarizmi
Introduction 3

is considered to be the first algorithm designer for adding numbers represented in the Hindu
numeral system. The algorithm designed by him and followed till today, calls for summing up
the digits occurring at specific positions and the previous carry digit, repetitively moving from
the least significant digit to the most significant digit until the digits have been exhausted.

Example 1.1 Demonstration of Al Khwarizmi’s algorithm for the addition of 987 and 76:
987 + 987 + 987 +
76 fi 76 + fi 76 +
Carry 1 Carry 1
(Carry 1) 3 (Carry 1) 63 1063

Definition, Structure and Properties of Algorithms 1.2

Definition An algorithm may be defined as a finite sequence of instructions each of which has
a clear meaning and can be performed with a finite amount of effort in a finite length of time.

Structure and properties

An algorithm has the following structure:
(i) Input step (iv) Repetitive step
(ii) Assignment step (v) Output step
(iii) Decision step

Example 1.2 Consider the demonstration of Al Khwarizmi’s algorithm shown on the addition
of the numbers 987 and 76 in Example 1.1. In this, the input step considers the two operands 987
and 76 for addition. The assignment step sets the pair of digits from the two numbers and the
previous carry digit if it exists, for addition. The decision step decides at each step whether the
added digits yield a value that is greater than 10 and if so, to generate the appropriate carry digit.
The repetitive step repeats the process for every pair of digits beginning from the least significant
digit onwards. The output step releases the output which is 1063.
An algorithm is endowed with the following properties:
Finiteness an algorithm must terminate after a finite number of steps.
Definiteness the steps of the algorithm must be precisely defined or unambiguously specified.
Generality an algorithm must be generic enough to solve all problems of a particular
class.
Effectiveness the operations of the algorithm must be basic enough to be put down on pencil
and paper. They should not be too complex to warrant writing another algorithm
for the operation!
Input-Output the algorithm must have certain initial and precise inputs, and outputs that
may be generated both at its intermediate and final steps.
An algorithm does not enforce a language or mode for its expression but only demands
adherence to its properties. Thus one could even write an algorithm in one’s own expressive way
to make a cup of hot coffee! However, there is this observation that a cooking recipe that calls for
4 Data Structures and Algorithms

instructions such as “add a pinch of salt and pepper’, ‘fry until it turns golden brown’ are “anti-
algorithmic” for the reason that terms such as ‘a pinch’, ‘golden brown’ are subject to ambiguity
and hence violate the property of definiteness!
An algorithm may be represented using pictorial representations such as flow charts. An
algorithm encoded in a programming language for implementation on a computer is called a
program. However, there exists a school of thought which distinguishes between a program and
an algorithm. The claim put forward by them is that programs need not exhibit the property of
finiteness which algorithms insist upon and quote an operating systems program as a counter
example. An operating system is supposed to be an ‘infinite’ program which terminates only
when the system crashes! At all other times other than its execution, it is said to be in the ‘wait’
mode!

Development of an Algorithm 1.3

The steps involved in the development of an algorithm are as follows:
(i) Problem statement (v) Implementation
(ii) Model formulation (vi) Algorithm analysis
(iii) Algorithm design (vii) Program testing
(iv) Algorithm correctness (viii) Documentation
Once a clear statement of the problem is done, the model for the solution of the problem is to
be formulated. The next step is to design the algorithm based on the solution model that is
formulated. It is here that one sees the role of data structures. The right choice of the data
structure needs to be made at the design stage itself since data structures influence the efficiency
of the algorithm. Once the correctness of the algorithm is checked and the algorithm
implemented, the most important step of measuring the performance of the algorithm is done.
This is what is termed as algorithm analysis. It can be seen how the use of appropriate data
structures results in a better performance of the algorithm. Finally the program is tested and the
development ends with proper documentation.

Data Structures and Algorithms 1.4

As was detailed in the previous section, the design of an efficient algorithm for the solution of the
problem calls for the inclusion of appropriate data structures. A clear, unambiguous set of
instructions following the properties of the algorithm alone does not contribute to the efficiency
of the solution. It is essential that the data on which the problems need to work on are
appropriately structured to suit the needs of the problem, thereby contributing to the efficiency of
the solution.
For example, let us consider the problem of searching for a telephone number of a person, in
the telephone directory. It is well known that searching for the telephone number in the directory
is an easy task since the data is sorted according to the alphabetical order of the subscribers’
names. All that the search calls for, is to turn over the pages until one reaches the page that is
approximately closest to the subscriber’s name and undertake a sequential search in the relevant
page. Now, what if the telephone directory were to have its data arranged according to the order
in which the subscriptions for telephones were received. What a mess would it be! One may need
Introduction 5

to go through the entire directory–name after name, page after page in a sequential fashion until
the name and the corresponding telephone number are retrieved!
This is a classic example to illustrate the
significant role played by data structures
in the efficiency of algorithms. The
problem was retrieval of a telephone
number. The algorithm was a simple
search for the name in the directory
and thereby retrieve the corresponding
telephone number. In the first case since
the data was appropriately structured
(sorted according to alphabetical order),
the search algorithm undertaken turned
out to be efficient. On the other hand, in
the second case, when the data was
unstructured, the search algorithm turned
out to be crude and hence inefficient.
For the design of efficient programs and
for the solution of problems, it is essential
that algorithm design goes hand in hand
with appropriate data structures. (Refer Fig. 1.3 Algorithms and Data structures for effi-
Fig. 1.3.) cient problem solving using computers

Data Structure—Definition and Classification 1.5

Abstract data types
A data type refers to the type of values that variables in a programming language hold. Thus the
data types of integer, real, character, Boolean which are inherently provided in programming
languages are referred to as primitive data types.
A list of elements is called as a data object. For example, we could have a list of integers or
list of alphabetical strings as data objects.
The data objects which comprise the data structure, and their fundamental operations are
known as Abstract Data Type (ADT). In other words, an ADT is defined as a set of data objects
D defined over a domain L and supporting a list of operations O.

Example 1.3 Consider an ADT for the data structure of positive integers called POSITIVE _
INTEGER defined over a domain of integers Z+, supporting the operations of addition (ADD),
subtraction(MINUS) and check if positive (CHECK_POSITIVE). The ADT is defined as follows:
L = Z+, D = {x | x ΠL}, Q = {ADD, MINUS, CHECK_POSITIVE}
A descriptive and clear presentation of the ADT is as follows:
Data objects
Set of all positive integers D
D = {x|x ΠL}, L = Z+
6 Data Structures and Algorithms

Operations
l Addition of positive integers INT1 and INT2 into RESULT
ADD ( INT1, INT2, RESULT)
l Subtraction of positive integers INT1 and INT2 into RESULT
SUBTRACT ( INT1, INT2, RESULT)
l Check if a number INT1 is a positive integer
CHECK_POSITIVE( INT1) (Boolean function)

An ADT promotes data abstraction and focuses on what a data structure does rather than how
it does. It is easier to comprehend a data structure by means of its ADT since it helps a designer
to plan on the implementation of the data objects and its supportive operations in any
programming language belonging to any paradigm such as procedural or object oriented or
functional etc. Quite often it may be essential that one data structure calls for other data structures
for its implementation. For example, the implementation of stack and queue data structures calls
for their implementation using either arrays or lists.
While deciding on the ADT of a data structure, a designer may decide on the set of operations
O that are to be provided, based on the application and accessibility options provided to various
users making use of the ADT implementation.
The ADTs for various data structures discussed in the book are presented as box items in the
respective chapters.

Classification
Figure 1.4 illustrates the classification of data structures. The data structures are broadly classified
as linear data structures and non-linear data structures. Linear data structures are uni-
dimensional in structure and represent linear lists. These are further classified as sequential and
linked representations. On the other hand, non-linear data structures are two-dimensional
representations of data lists. The individual data structures listed under each class have been
shown in Fig. 1.4.

Fig. 1.4 Classification of data structures

Introduction 7

Organization of the book

The book is divided into five parts. Chapter 1 deals with an introduction to the subject of data
structures and algorithms. Chapter 2 introduces analysis of algorithms.
Part I discusses linear data structures and includes three chapters pertaining to sequential
data structures. Chapters 3, 4 and 5 discuss the data structures of arrays, stacks and queues.
Part II also discusses linear data structures and incorporates two chapters on linked data
structures. Chapter 6 discusses linked lists in its entirety and Chapter 7 details linked stacks and
queues.
Part III discusses the non-linear data structures of trees and graphs. Chapter 8 discusses trees
and binary trees and Chapter 9 details on graphs.
Part IV discusses some of the advanced data structures. Chapter 10 discusses binary search trees
and AVL trees. Chapter 11 details B trees and tries. Chapter 12 deals with red–black trees and
splay trees. Chapter 13 discusses hash tables and Chapter 14 describes methods of file
organizations.
The ADTs for some of the fundamental data structures discussed in PARTS I, II, III and IV
have been provided towards the end of the appropriate chapters.
Part V deals with searching and sorting techniques. Chapter 15 discusses searching techniques,
Chapter 16 details internal sorting methods and Chapter 17 describes external sorting methods.

Summary
Ø Any discipline in Science and Engineering that calls for solving problems using computers,
looks up to the discipline of Computer Science for its efficient solution.
Ø From the point of view of solving problems, computer science can be naively categorized
into the four areas of machines, languages, foundations and technologies.
Ø The subjects of Algorithms and Data structures fall under the category of foundations. The
design formulation of algorithms for the solution of problems and the inclusion of
appropriate data structures for their efficient implementation must progress hand in hand.
Ø An Abstract Data Type (ADT) describes the data objects which constitute the data structure
and the fundamental operations supported on them.
Ø Data structures are classified as linear and non linear data structures. Linear data structures
are further classified as sequential and linked data structures. While arrays, stacks and
queues are examples of sequential data structures, linked lists, linked stacks and queues are
examples of linked data structures.
Ø The non-linear data structures include trees and graphs
Ø The tree data structure includes variants such as binary search trees, AVL trees, B trees,
Tries, Red Black trees and Splay trees.