Bule Hora University Data Structure and Algorithm

Chapter one

Introduction to Data Structures and Algorithms Analysis

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 computer’s 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.
Program=Algorithm + Data structure
Data structure is the building blocks of a program. Data structure should be represented in such
way that it utilizes maximum efficiency. Data structure the design of both the structural and
functional aspect of the program.

Introduction to Data Structures

Data structure:-is the structural representation of logical relationship between elements of data.
In other word it is the way of organizing data items by considering its relationship to each other.
Given a problem, the first step to solve the problem is obtaining one’s 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.

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).
Classification of Data structure
Data structures are broadly divided in two:-
1. Primitive data structures.
2. Non primitive data structures.
Primitive data structures: These are the basic data structure and are directly operated up on the
machine instruction, which is in primitive level. They are integers, floating point numbers,
characters, string constants, pointers etc.
These primitive data structure are the basis for the discussion of more sophisticated (non-
primitive) data structures.
Non primitive Data structures:- It is more sophisticated data structure emphasizing on
structuring of a group of homogenous (same type) or heterogeneous (different type) data items.
Array, list, files, linked list, trees and graph fall in this category.

Abstract Data Types

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:

1
Bule Hora University Data Structure and Algorithm

1. What can be stored in the Abstract Data Type

2. What operations can be done on/by the Abstract Data Type.
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.

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.

Chapter Two

Algorithm and Algorithm Analysis

Algorithm is a step by step procedure to solve a problem. E.g. industrial activities, Student
Registration, etc, all need an algorithm to follow. More than one algorithm is possible for the
same task. An algorithm is a 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.

Properties of an algorithm

• Finiteness: Algorithm must complete after a finite number of steps.

• Definiteness: 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.
• Sequence: Each step must have a unique defined preceding and succeeding step. The
first step (start step) and last step (halt step) must be clearly noted.
• Feasibility: It must be possible to perform each instruction.
• Correctness: It must compute correct answer all possible legal inputs.
• Language Independence: It must not depend on any one programming language.
• Completeness: It must solve the problem completely.
• Effectiveness: It must be possible to perform each step exactly and in a finite amount
of time.
• Efficiency: It must solve with the least amount of computational resources such as
time and space.
• Generality: Algorithm should be valid on all possible inputs.
• Input/Output: There must be a specified number of input values, and one or more
result values.

Algorithm Analysis Concepts

Algorithm analysis refers to the process of determining how much computing time and storage
that algorithms will require. In other words, it’s a process of predicting the resource requirement
of algorithms in a given environment.

In order to solve a problem, there are many possible algorithms. One has to be able to choose the
best algorithm for the problem at hand using some scientific method. To classify some data
structures and algorithms as good, we need precise ways of analyzing them in terms of resource
requirement. The main resources are:

2
Bule Hora University Data Structure and Algorithm

 Running Time
 Memory Usage
 Communication Bandwidth

Running time is usually treated as the most important since computational time is the most
precious resource in most problem domains.

There are two approaches to measure the efficiency of algorithms:

• Empirical: Programming competing algorithms and trying them on different
instances.
• Theoretical: Determining the quantity of resources required mathematically
(Execution time, memory space, etc.) needed by each algorithm.

However, it is difficult to use actual clock-time as a consistent measure of an algorithm’s

efficiency, because clock-time can vary based on many things. For example,

 Specific processor speed

 Current processor load
 Specific data for a particular run of the program
o Input Size
o Input Properties
 Operating Environment

Accordingly, we can analyze an algorithm according to the number of operations required, rather
than according to an absolute amount of time involved. This can show how an algorithm’s
efficiency changes according to the size of the input.

1.2.3. Complexity Analysis

Complexity Analysis is the systematic study of the cost of computation, measured either in time
units or in operations performed, or in the amount of storage space required.
Complexity analysis is concerned with determining the efficiency of algorithms.
What is Efficiency depends on?
 Execution speed (most important)
 Amount of memory used
Efficiency differences may not be noticeable for small data, but become very important for large
amounts of data.

The goal is to have a meaningful measure that permits comparison of algorithms independent of
operating platform.
There are two things to consider:
 Time Complexity: Determine the approximate number of operations required to solve a
problem of size n.
 Space Complexity: Determine the approximate memory required to solve a problem of
size n.

Complexity analysis involves two distinct phases:

3
Bule Hora University Data Structure and Algorithm

 Algorithm Analysis: Analysis of the algorithm or data structure to produce a function T

(n) that describes the algorithm in terms of the operations performed in order to measure
the complexity of the algorithm.
 Order of Magnitude Analysis: Analysis of the function T (n) to determine the general
complexity category to which it belongs.

There is no generally accepted set of rules for algorithm analysis. However, an exact count of
operations is commonly used.
Analysis Rules:
1. We assume an arbitrary time unit.
2. Execution of one of the following operations takes time 1:
 Assignment Operation E.g.Sum=0;
 Single Input/Output Operation E.g.cin>>sum;cout<<sum;
 Single Boolean Operations E.g.!done
 Single Arithmetic Operations E.g.a+b,a-b
 Function Return E.g.return(sum);
3. Running time of a selection statement (if, switch) is the time for the condition evaluation
+ the maximum of the running times for the individual clauses in the selection.
4. Loop statement
 ∑(no of iteration of Body) +1 + n+1 + n (initialization time + checking +
update)

5. Running time of a function call is 1 for setup + the time for any parameter
calculations + the time required for the execution of the function body.

Examples:
1. int count(){
int k=0;
cout<< “Enter an integer”;
cin>>n;
for (i=0;i<n;i++)
k=k+1;
return 0;}
Time Units to Compute
-------------------------------------------------
1 for the assignment statement: int k=0
1 for the output statement.
1 for the input statement.
In the for loop:
1 assignment, n+1 tests, and n increments.
n loops of 2 units for an assignment, and an addition.
1 for the return statement.
-------------------------------------------------------------------
T (n)= 1+1+1+(1+n+1+n)+2n+1 = 4n+6 = O(n)

2. int total(int n)
{
int sum=0;
for (int i=1;i<=n;i++)
sum=sum+1;

4
Bule Hora University Data Structure and Algorithm

return sum;
}
Time Units to Compute
-------------------------------------------------
1 for the assignment statement: int sum=0
In the for loop:
1 assignment, n+1 tests, and n increments.
n loops of 2 units for an assignment, and an addition.
1 for the return statement.
-------------------------------------------------------------------
T (n)= 1+ (1+n+1+n)+2n+1 = 4n+4 = O(n)

3. for(i=1;i<=n;i++)
for(j=1;j<=n; j++)
k++;
T(n)=1+n+1+n+n(1+n+1+n+n)=3n2+4n+2

4. Sum=0;
if(test==1)
{
for (i=1;i<=n;i++)
sum=sum+i
}
else
{
cout<<sum;
}
• T(n)=1+1+Max(1+n+1+n+2n,1)= 4n+4