Chapter One

Introduction to Data
Structure and Algorithm
Outline
 Data Structures
 Abstract Data Types
 Abstraction
 Algorithms
 Properties of an algorithm
Introduction to Data Structures and Algorithms Analysis
Introduction to Data Structures and Algorithms Analysis

A program
 A set of instruction which 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

 To implement a program, we should select an

appropriate data structure for that algorithm.
 Introduction....(continued)
 The way data are organized in a computers
memory is said to be Data Structure.

 A data structure is a technique of organizing the data so

that the data can be utilized efficiently.

 The sequence of computational steps to solve a problem

is said to be an Algorithm.

 To implement a program of an algorithm, we should

select an appropriate data structure for that
algorithm.

5
 Therefore, a program is Data structures + Algorithm.
Introduction to Data Structures
 The first step to solve the problem is
obtaining ones own abstract view, or
model, of the problem.

 Thisprocess of modeling is called

abstraction.
 Introduction....(continued)

Abstraction

 The model defines an abstract view to

the
problem.

 Themodel should only focus on 7

problem
Abstraction

 Abstraction is a process of classifying characteristics

as relevant and irrelevant for the particular
purpose at hand and ignoring the irrelevant ones.

 Example: model students of UoG.

 Relevant:
Char Name[15];
Char ID[11];
Char Dept[20];
int Age, year;
 Non relevant
float hieght, weight; 8
 Abstraction....(continued)

 Using the model, 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

 An entity with the properties just described 9

is called an abstract data type (ADT).

 Abstract Data Types
 Consists of data to be stored and operations
supported on them.

 Is a specification that describes a data set and

the operation on that data.

 The ADT specifies:

 What data is stored.
 What operations can be done on the data.

 Does not specify how to store or how to

implement the operation.
 Is independent of any programming language10
 ADT....(continued)
Example: ADT employees of an organization:

 This ADT stores employees with their relevant

attributes and discarding irrelevant attributes.

Relevant:- Name, ID, Sex, Age, Salary, Dept,

Address
Non Relevant :- weight, color, height

11
Data Structure

12
 Data Structure
Static Vs Dynamic DS

The static data structure is a kind of data structure, in

which once memory space is allocated it cannot extend,

i.e. the memory allocation for the data structure takes

place at compile-time that cannot be changed
afterwards.
Example: Array

Dynamic Data Structure is another kind of data

structure, which can be extended or shrink during the
execution,

i.e., the memory allocation as well as memory de- 13

allocation for the data structure takes place at run-
 Data Structure

Data Structure can be used for the following

purpose:

 Organizing the data – How data items are

organized in the main memory?

 Accessing methods – How data items can be

accessed?

 Specifying the degree of associativity – How

data items are interrelated?

 Processing alternatives for data – How many

14
different ways are there in which these data
 Application Area of Data Structure
Data Structure is used in various fields of Computer
Science, such as:
o Compiler Design
o Operating System
o Database Management System
o Statistical Analysis
o Numerical Analysis
o Graphics
o Artificial Intelligence
15
o Simulation
 Operations in Data Structure
Operatio Description
ns
Creation Allocation of memory for the data structure, the creation of
data structure may take place either during compile-time or
during run-time.
Insertion Insert a data item in the data structure.
Deletion Delete a data item from the data structure.
Traversin Accessing and processing each data item of the data
g structure exactly once.
Searching Find the location of the key value within the data structure.
Sorting Arranging all the data items in a data structure either in
ascending or in descending order or in lexicographical order
(for Strings).
Merging Combining the data items of two different sorted lists 16
into a
single sorted list.
 Data Structure
 Example:
struct Student_Record
{
char name[20];
char ID_NO[10];
char Department[10];
int age;
};

 Attributes of each variable:

 Name: Textual label.

 Address: Location in memory.

 Scope: Visibility in statements of a program.

 Type: Set of values that can be stored + set of operations that can be performed.

 Size: The amount of storage required to represent the variable.

17
 Life time: The time interval during execution of a program while the variable exists.
 Algorithm

 isa well-defined computational procedure

that takes some value or a set of values as input
and produces some value or a set of values as
output.

Inputs Algorithm
Outputs

 An algorithm is a specification of a behavioral

process. It consists of a finite set of instructions
that govern behavior step-by-step.
18
 Is part of what constitutes a data structure
 Algorithm
 Data structures model the static part of the
world. They are unchanging while the world
is changed.

 Inorder to model the dynamic part of the

world we need to work with algorithms.

 Algorithmsare the dynamic part of a

program’s world model.

19
 Algorithm
 What is the purpose of algorithms in programs?
 Take values as input. Example: cin>>age;

 Change the values held by data structures.

Example: age=age+1;

 Change the organization of the data structure:

Example:
Sort students by name

 Produce
outputs:
Example: Display student’s information 20
 Algorithm
 The quality of a data structure is related to its
ability to successfully model the characteristics
of the world (problem).

 Similarly, the quality of an algorithm is related

to its ability to successfully simulate the
changes in the world.

21
 Algorithm

 The quality of data structure and algorithms is

determined by their ability to work together
well.

 Generally
speaking, correct data structures lead
to simple and efficient algorithms.

 And correct algorithms lead to accurate and

efficient data structures.

22
 Properties of Algorithms
Finiteness:

Algorithm must complete after a finite

number of steps.
 Algorithm should have a finite number of
steps.
Finite  int i=0; Infinite while(true){
while(i<10){ cout<<“Hello”;
cout<< i; }
i++;
23
}
Definiteness (Absence of ambiguity):


Each step must be clearly defined, having
one and only one interpretation.

 At each point in computation, one should be

able to tell exactly what happens next.

24
Sequential:


Each step must have a uniquely defined
preceding and succeeding step.

 The first step (start step) and last step (halt

step) must be clearly noted.

25
Feasibility:

It must be possible to perform each

instruction.
 Each instruction should have possibility to
be executed.
1) for(int i=0; i<0; i++){
cout<< i; // there is no possibility
} that this statement to
be executed.
2) if(5>7) {
cout<<“hello”; // not executed.
}
26
Correctness

 It must compute correct answer for all

possible legal inputs.
 => GIGO
 The
output should be as expected and
correct.
Language Independence:

 It must not depend on any one of

programming
Completeness:
language.
27

 It must solve the problem completely.

Effectiveness:

 Doing the right thing. It should yield the

correct result all the time for all of the
Efficiency:
possible cases.

 It must solve with the least amount of

computational resources such as time and
space.
 Producing an output as per the requirement
28
 E x a mp le:

Write a program that takes a number and

displays the square of the number.
1) int x;
cin>>x;
cout<<x*x*x;

2) int x,y;
cin>>x;
y=x*x*x;
cout<<y;
29
 E x a mp le:

Write a program that takes two numbers and

displays the sum of the two.
Program a Program b Program c
cin>>a; cin>>a;
cin>>a;
cin>>b; cin>>b; cin>>b;
sum = a+b; a = a+b; cout<<a+b;
cout<<sum; cout<<a;
Which one is most efficient and which are effective?
Program c the most efficient
All are effective but with different efficiencies.

30
Input/output:

There must be a specified number of input

values, and one or more result values.

Precision:
 The result should always be the same if the
algorithm is given identical input.

31
Simplicity:

 A good general rule is that each step should carry out

one logical step.
 Whatis simple to one processor may not be simple to
another.

Levels of abstraction:
 Used to organize the ideas expressed in
algorithms.
Used to hide the details of a given activity and
refer to just a name for those details.
The simple (detailed) instructions are hidden
inside modules.
32
Well-designed algorithms are organized in terms
 Next Class

Algorithm Analysis Concepts

 Complexity Analysis
 Formal Approach to Analysis
 Asymptotic Analysis
 The Big-Oh Notation
 Big-Omega Notation
 Theta Notation