Data Structures and
Algorithms (CoSc2041 )
Chapter -1: Introduction to Data
Structures and Algorithms
Amsalu Dinote(MSc)
12
Chapter Outline
• Introduction
• Abstract data types
• Data structures
• Algorithms
• Properties of algorithms
• Algorithm analysis
• Measures of times
13
Introduction
• A program is written in order to solve a problem.
• A solution to a problem actually consists of two things:
A way to organize the data
Sequence of steps to solve the problem
• The way data are organized in a computers memory is
said to be Data Structure and the sequence of
computational steps to solve a problem is said to be an
Algorithm.
• Therefore, a program is nothing but data structures plus
algorithms.
14
Introduction(cont..)
• Given a problem, the first step to solve the problem is obtaining
ones own abstract view, or model, of the problem.
• This process of modeling is called abstraction.
• The model defines an abstract view to the problem.
• This implies that the model focuses only on problem related
stuff and that a programmer tries to define the properties of the
problem.
• These properties include
• The data which are affected and
• The operations that are involved in the problem.
15
Abstract Data Type
• With abstraction you create a well-defined entity that can be
properly handled. These entities define the data structure of the
program.
• An entity with the properties just described is called an
abstract data type (ADT)
• An ADT consists of an abstract data structure and operations.
Put in other terms, an ADT is an abstraction of a data structure.
• The ADT specifies:
What can be stored in the Abstract Data Type
What operations can be done on/by the Abstract Data Type.
• For example, if we are going to model employees of an
organization:
This ADT stores employees with their relevant attributes and
discarding irrelevant attributes.
This ADT supports hiring, firing, retiring, … operations.
16
Abstract Data Type(cont..)
• A data structure is a language construct that the
programmer has defined in order to implement an
abstract data type.
• There are lots of formalized and standard Abstract
data types such as Stacks, Queues, Trees, etc.
• Do all characteristics need to be modeled?
• Not at all!!
It depends on the scope of the model
It depends on the reason for developing the model
17
Abstraction
• Abstraction is a process of classifying characteristics as
relevant and irrelevant for the particular purpose at hand and
ignoring the irrelevant ones.
• Applying abstraction correctly is the essence of successful
programming
• How do data structures model the world or some part of the
world?
The value held by a data structure represents some specific
characteristic of the world
The characteristic being modeled restricts the possible
values held by a data structure
The characteristic being modeled restricts the possible
operations to be performed on the data structure.
• Note: Notice the relation between characteristic, value, and data
structures
• Where are algorithms, then?
18
Example 1: Employee ADT
• If we are going to model employees of an
organization:
• This ADT stores employees with their relevant
attributes and discarding irrelevant attributes.
(some of such attributes can be: name, sex, id,
salary, etc)
• This ADT supports operations such as hiring,
firing, retiring.
19
Example 2: List ADT
• An ADT for a list of integers might specify the following
operations:
Insert a new integer at a particular position in the list.
Return true if the list is empty.
Reinitialize the list.
Return the number of integers currently in the list.
Delete the integer at a particular position in the list.
• From this description, the input and output of each
operation should be clear, but the implementation for
lists has not been specified.
20
Example 3: Other ADTs
• Objects such as lists, sets, and graphs, along with their operations, can
be viewed as ADTs, just as integers, reals, and booleans are data
types.
• Integers, reals, and booleans have operations associated with them, and
so do ADTs.
• For the set ADT, we might have such operations as add, remove, size,
and contains.
• Alternatively, we might only want the two operations union and find,
which would define a different ADT on the set.
• An abstract data type can also be viewed as the realization of a data
type as a software component.
• The interface of the ADT is defined in terms of a type and a set of
operations on that type.
• The behavior of each operation is determined by its inputs and outputs.
• An ADT does not specify how the data type is implemented.
• There are lots of formalized and standard Abstract data types such as
Stacks, Queues, Trees, Graphs etc.
21
Data Structures
• A data structure is the implementation for an ADT.
• With abstraction you create a well-defined entity that can be
properly handled. These entities define the data structure of the
program.
• A data structure is a language construct that the programmer has
defined in order to implement an abstract data type.
• The C++ class (struct too) allows for the implementation of
ADTs, with appropriate hiding of implementation details.
• Thus, any other part of the program that needs to perform an
operation on the ADT can do so by calling the appropriate
method.
• If for some reason implementation details need to be changed, it
should be easy to do so by merely changing the routines that
perform the ADT operations.
• This change, in a perfect world, would be completely transparent
to the rest of the program.
22
