WOLLEGA UNIVERSITY

DEPARTMENT OF Informatics
Library and Information Science program
Chapter 1: Introduction to Data structures

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---------------------------------------------Data Structure
 Sequence of steps to solve the problem -----------------------------Algorithm
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.
Data Structure is a systematic way to organize data in order to use it efficiently. Following
terms are the foundation terms of a data structure.

 Interface − Each data structure has an interface. Interface represents the set of
operations that a data structure supports. An interface only provides the list of supported
operations, type of parameters they can accept and return type of these operations.

 Implementation − Implementation provides the internal representation of a data

structure. Implementation also provides the definition of the algorithms used in the
operations of the data structure.

Characteristics of a Data Structure

 Correctness − Data structure implementation should implement its interface correctly.

 Time Complexity − Running time or the execution time of operations of data structure
must be as small as possible.

 Space Complexity − Memory usage of a data structure operation should be as little as

possible.

1
Need for Data Structure
As applications are getting complex and data rich, there are three common problems that
applications face now-a-days.

 Data Search − Consider an inventory of 1 million(10 6) items of a store. If the

application is to search an item, it has to search an item in 1 million(10 6) items every
time slowing down the search. As data grows, search will become slower.

 Processor speed − Processor speed although being very high, falls limited if the data
grows to billion records.
 Multiple requests − As thousands of users can search data simultaneously on a web
server, even the fast server fails while searching the data.
To solve the above-mentioned problems, data structures come to rescue(to save something from
danger). Data can be organized in a data structure in such a way that all items may not be
required to be searched, and the required data can be searched almost instantly(without delay).
 A Data Structure is a logical model of a particular organization of data.

There are two types of data structure:-

1. linear Data Structure: the elements form a sequence, linear lists e.g. Arrays,
stacks, queues, linked lists. /*LINEAR SEARCH PROGRAM */
#include<iostream.h>
int main()
{
int a[10],i,n,m,c=0;
cout<<"Enter the size of an array: ";
cin>>n;
cout<<"Enter the elements of the array: ";
for(i=0;i<=n-1;i++)
{
cin>>a[i]; }
Cout<<”Enter the number to be search: ";
Cin>>m;
for(i=0;i<=n-1;i++)
{
if(a[i]= =m){
c=1;
break;

2
} }
if(c= =0)
cout<<”The number is not in the list";
else
cout<<”The number is found";
return 0;}
2. Non-Linear Data Structure: the elements do not form a sequence, e.g. Graphs,
trees
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).
Abstract Data Type and Abstraction
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. What can be stored in the Abstract Data Type?
2. 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.

ADT: is a set of objects together with a set of operations; they are mathematical abstractions,
objects such as lists and graphs along with operations can be abstract data types.(Booleans,
integers along with operations also an abstract data type)
A Data structure is a language construct that the programmer has defined in order to implement
an abstract data type.

3
 There are lots of formalized and standard Abstract data types(ADT) 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
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.
Algorithm and Algorithm Analysis
2.1 Properties of Algorithm
2.2 Analysis of Algorithm
Algorithm
An algorithm is the method of solving a problem. It is a sequence of instructions that act on some
input data to produce some output in a finite number of steps.
“The ends justify the means (algorithm)”…..does not always work in CS
Getting a correct solution late is as bad as getting a wrong solution
It 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.
 Data structures model the static part(no change) of the world.
 They are unchanging while the world is changing.
In order to model the dynamic part of the world we need to work with algorithms.
 Algorithms are the dynamic part of a program‘s world model.
An algorithm transforms data structures from one state to another state in two ways:
 An algorithm may change the value held by a data structure
 An algorithm may change the data structure itself

4
 The quality of a data structure is related to its ability to successfully model the
characteristics of the world. Similarly,
 The quality of an algorithm is related to its ability to successfully simulate the changes in
the world.
However, independent of any particular world model, 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.
Algorithm basically fall under two broad categories:
Iterative- use loops and conditional statements
Recursive:- use divide and conquer(dominate) strategy
Properties of Algorithm
• Finiteness: Algorithm must complete after a finite number of steps.
• Definiteness: Each step must be clearly defined, having one and only one interpretation
(constraction). 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 for 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.

5
Analysis of Algorithm
 Analysis of algorithms gives us the scientific reason
 To determine which algorithm should be choosen to solve the problem.
But, it does not give a formula that helps us determine how many seconds or computer cycles
a particular algorithm will take to solve a problem. This is not useful information to choose
the right algorithm because:
It involves lots of variables like:
 Type of computer
 Instruction set used by the Microprocessor
 What optimization compiler performs on executable code
Algorithm Analysis Concepts
Algorithm analysis refers to the process of determining the
 amount of computing time and
 storage space
required by different algorithms. 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(accurete) ways of analyzing them in terms of resource
requirement.
The main resources are:
 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.

6
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.
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.
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:

 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.

7
Analysis Rules:
1. We assume an arbitrary time unit.
2. Execution of one of the following operations takes time 1:
 Assignment Operation
 Single Input/Output Operation
 Single Boolean Operations
 Single Arithmetic Operations
 Function Return
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. Loops: Running time for a loop is equal to the running time for the statements inside the loop *
number of iterations.
The total running time of a statement inside a group of nested loops is the running time of the
statements multiplied by the product of the sizes of all the loops.
For nested loops, analyze inside out.
 Always assume that the loop executes the maximum number of iterations possible.
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‖; T (n)= 1+1+1+(1+n+1+n)+2n+1 =
cin>>n; 4n+6 = O(n)
for (i=0;i<n;i++) 2. int total(int n)
k=k+1; {
return 0;} int sum=0;
Time Units to Compute for (int i=1;i<=n;i++)
------------------------------------------------- sum=sum+1;
1 for the assignment statement: int k=0 return sum;
1 for the output statement.1 for the input }
statement. Time Units to Compute
In the for loop: -------------------------------------------------
1 assignment, n+1 tests, and n increments. 1 for the assignment statement: int sum=0
n loops of 2 units for an assignment, and an In the for loop:
addition. d 1 assignment, n+1 tests, and n increments.
1 for the return statement. n loops of 2 units for an assignment, and an
addition.

8
1 for the return statement.
-------------------------------------------------------- 3. void func()
----------- {
T (n)= 1+ (1+n+1+n)+2n+1 = 4n+4 int x=0;
= O(n) int i=0;
int j=1;
cout<< ―Enter an Integer value‖;
cin>>n;
while (i<n){
x++;
i++;
}
while (j<n)
{
j++;
}
}
Time Units to Compute
-------------------------------------------------
1 for the first assignment statement: x=0;
1 for the second assignment statement: i=0; 10
1 for the third assignment statement: j=1;
1 for the output statement.
1 for the input statement.
In the first while loop:
n+1 tests
n loops of 2 units for the two increment
(addition) operations
In the second while loop:
n tests
n-1 increments
--------------------------------------------------------
-----------
T (n)= 1+1+1+1+1+n+1+2n+n+n-1
= 5n+5 = O(n)
4. int sum (int n)
{
int partial_sum = 0;
for (int i = 1; i <= n; i++)
partial_sum = partial_sum +(i * i * i);
return partial_sum;
}
Time Units to Compute
-------------------------------------------------
1 for the assignment.
1 assignment, n+1 tests, and n increments.
n loops of 4 units for an assignment, an
addition, and two multiplications.

9
1 for the return statement. --------------------------------------------------------
-----------
T (n)= 1+(1+n+1+n)+4n+1 = 6n+4 = O(n)

Measures of Times

In order to determine the running time of an algorithm it is possible to define three functions
Tbest(n), Tavg(n) and Tworst(n) as the best, the average and the worst case running time of the
algorithm respectively.
Average Case (Tavg): The amount of time the algorithm takes on an "average" set of inputs.
Worst Case (Tworst): The amount of time the algorithm takes on the worst possible set of inputs.
Best Case (Tbest): The amount of time the algorithm takes on the smallest possible set of inputs.
We are interested in the worst-case time, since it provides a bound for all input – this is called the
“Big-Oh” estimate.

10