CS201-Data Structures and

Algorithms
• Text Books:
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,
Introduction to Algorithms, MIT Press, 3/e, 2009.
• Y. Langsam, M. J. Augenstein, and A. M. Tenenbaum, Data
Structures Using C and C++, Prentice Hall, 2/e, 2000.
• S. Sahni, Data Structures, Algorithms, and Applications in C++,
Silicon Press, 2/e, 2005.
• Michael T. Goodrich, Roberto Tamassia, and David M., Data
Structures and Algorithms in C++, John Wiley & Sons, Inc., 2/e,
2004
Data Structure and Algorithms
• Program development process will require to:
– Represent data in an effective way
– Develop a suitable step-by-step procedure which can be
implemented as a computer program
• Algorithm:
– Outline of the steps the program has to take
– Processing carried out on the data
• Program:
– Implementation of an algorithm in some programming
language
• Data Structure:
– The way we need to organise data so that it can be
effectively used by program

2
Abstract Data Type (ADT)

3
Data Types
• Data object: A set of instances or values
• Examples:
Boolean = { false, true}
Digit = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
Letter = { A, B, …, Z, a, b, …, z }
Natural Number
= { 0, 1, …, 23, 24, …, 654, 655, … }
String = { a, b, …, aa, bb, …, DSA, Algorithm, Dharwad, … }
• The individual instances of a data object are regarded as
being either primitive (or atomic) or being composed of
instances of another data types
• Element: Individual component of an instance of data object
• The instances of a data object as well as the elements that
constitute the individual instances are generally related in
some way
• A set of functions is generally associated with any data
object
4
Data Structure
• Data structure is a data object together with the
relationships that exists among the instances and
among the individual elements that constitute an
instance
• These relationships are provided by specifying the
functions of interest
• Focus: Representation of data objects (actually
instances) and the function of interest
• The representation of each data object should
facilitate an efficient implementation of the functions

5
Abstract Data Type (ADT)
• ADT provide a specification of the instances and values as
well as the operations that are to be performed
• ADT consists of two parts: value (instance) definition and
operation definition
• ADT specifies what are the operation to be carried out but
not how the operations are carried out
• These operations are defined through interface
• Interface basically giving us the signature of operations
• Different kinds of operations/functions:
• Constructor operation:
• Operation that create an instance of data object
• Access functions:
• Function that access the elements of data object
• Manipulation procedure:
• Function that manipulate or modify the data object

6
Why ADT in Data Structure and Algorithms?
• ADT provides higher level of abstraction
• ADT helps to identify the requirements or building
blocks of algorithmic procedure
• ADT encapsulate data structure and algorithm that
works on the data structure

7
Array Data Structure

8
Array Data Structure
• Array is a composite or structured data type
• One-dimensional array:
– Finite ordered set of homogeneous elements
– Finite:
• There is a specific number of elements in the array
– Ordered:
• Elements are arranged so that zeroth, first, second, third
and so forth
– Homogeneous:
• All elements of array must be of same type

9
Array as ADT
• Value (Instance) definition: A data object whose
instances are of the form (a1, a2,…, aub)
• ub is the finite natural number indicating the length
• ai are the elements of the array
• where, 0 ≤ i < ub
• atype is the type indicator (E.g. integer, character etc)
• Operations on the array
• Extract the element from array – Access function
• Store an element into an array – Manipulation procedure
Array as ADT [1]
• Value definition:
abstract typedef <<atype, ub>> ARRTYPE (ub, atype);
condition type(ub) == int; /* atype a[ub] */

• Operation definition:
abstract atype extract(a, i) /* written a[i] */
ARRTYPE (ub, atype) a;
int i; Access Function

precondition 0 ≤ i < ub;

[1] Y. Langsam, M. J. Augenstein, and A. M. Tenenbaum, Data Structures Using C and C++, Prentice
Hall, 2/e, 2000. 11
Array as ADT [1]
• Value definition:
abstract typedef <<atype, ub>> ARRTYPE (ub, atype);
condition type(ub) == int; /* atype = a[ub] */

• Operation definition:
abstract store(a, i, element) /* written a[i] = element */
ARRTYPE (ub, atype) a; Manipulation
Procedure
int i;
atype element;
Refer er 1 in
precondition 0 ≤ i < ub ha p t
C
n b a um
postcondition a[i] = element; Te ne or more
f
book
et a ils
d
[1] Y. Langsam, M. J. Augenstein, and A. M. Tenenbaum, Data Structures Using C and C++, Prentice
Hall, 2/e, 2000. 12
Algorithms
• Algorithm is a tool for solving well-specified
computational problems
• An algorithm is any well-defined computational
procedure that
– takes some value, or set of values as input
– produces some value, or set of values as output
• Algorithm is a sequence of computational steps that
transform the input into the output

Specification of
output
Specification of Algorithm as
input
function of
input

13
Sorting Problem

Sequence of Sequence of
numbers Sort numbers
a1, a2,…, an a’1, a’2,…, a’n

• The output a’1,a’2,…,a’n is the permutation (reordering)

14
Readings
• Read Chapter 1 and 2 in Corman book
• Read Chapter 1 and 6 in Tenenbaum book

15