Data structures and
algorithms
1
JIMMA UNIVERSITY
JIMMA INSTITUTE OF TECHNOLOGY
FACULTY OF COMPUTING AND INFORMATICS
CHAPTER ONE
Introduction to Data
Structures and
Algorithms
Objective
2
At the end of the session, students should have a basic
understanding of
Data structure
Classification of data structure
Algorithm
Characteristics of algorithms
Algorithm analysis
Data structures and algorithms
Introduction to Data structures and Algorithms
3
Program = Algorithm + Data structure
Data Structure:
The way data is organized in a computer’s memory so
that it can be used effectively.
Algorithm :
The sequence of computational steps to solve a
problem.
Data structures and algorithms
Cont’d
4
All of you have programmed;
already been exposed to algorithms and data structure.
Perhaps
you didn't see them as separate entities;
you saw data structures as simple programming constructs
(provided by STL--standard template library).
However, data structures are quite distinctfrom
algorithms, and very important in their own right.
Data structures and algorithms
Why Are Data Structures and Algorithms So
Important?
5
Data structure and algorithms are two of the most important
aspects of computer science.
Data structures allow us to organize and store data, while
algorithms allow us to process that data in a meaningful way.
Learning data structure and algorithms will help you become a
better programmer.
You will be able to write code that is more efficient and more
reliable.
You will also be able to solve problems more quickly and more
effectively.
Data structures and algorithms
Cont’d
6
Model
defines an abstract view to the problem
define the properties of the problem
Properties of the problem include
The data which are affected and
The operations that are involved in the problem.
Data structures and algorithms
Abstract Data Type
7
is an abstraction of a data structure which provides only
the interface to which a data structure must follow.
The interface doesn’t give any specific details about
how something should be implemented or in what
programming language.
Data structures and algorithms
Cont’d
8
Consists of an abstract data structure and operations
Specifies:
What can be stored in the ADT
What operations can be done on/by the ADT
E.g., if we are going to model employees of an organization:
ADT stores employees with
their relevant attributes and
discarding irrelevant attributes.
ADT supports
hiring, firing, retiring, … operations.
Data structures and algorithms
Data structure (DS)
9
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
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.
Data structures and algorithms
CLASSIFICATION OF DATA
STRUCTURE
10
What is data structure
is basically a technique of organizing and storing of
different types of data items in computer memory.
It is considered as not only the storing of data
elements but also the maintaining of the logical
relationship existing between individual data
elements.
Data structures and algorithms
CLASSIFICATION OF DATA
STRUCTURE
11
1. Primitive data structure
2. Non-primitive data structure
Data structures and algorithms
Cont’d
12
Primitive data structure:
also known as basic data structures.
predefinedtypes of data, which are supported by the
programming language.
Non-Primitive data structure:
are highly developed complex data structures.
arenot defined by the programming language, but are instead
created by the programmer.
Are responsible for organizing the group of homogeneous and
heterogeneous data elements.
Data structures and algorithms
Cont’d
13
The linear and non-linear data structure are the
subclassification of non-primitive data structure.
Difference:
Linear data structure arranges the data into a
sequence and follow some sort of order.
Non-linear data structure does not organize the
data in a sequential manner.
Data structures and algorithms
Algorithm
14
An algorithm can be thought of as a set of instructions that specifies
how to solve a particular problem.
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
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
Data structures and algorithms
Properties of algorithm
15
Finiteness :-Algorithms must terminate after a finite number of steps.
Definiteness :- Each instruction of the algorithm should be clear and unambiguous.
Sequence :-Should be written in sequence
Feasibility :-Should be feasible with the available resources.
Correctness: It should produce the correct output.
Language Independent
An algorithm must be language-independent, which means that its
instructions can be implemented in any language and produce the
same results.
Data structures and algorithms
Algorithm Analysis
16
Refers to the process of determining the amount of computing
time and storage space required by different algorithms.
A process of predicting the resource requirement of algorithms
in a given environment.
Main resources are:
Running Time
Memory Usage
Communication Bandwidth
Data structures and algorithms
Approaches to measure the efficiency of algorithms
17
Empirical:
competing algorithms and trying them on different
instances.
It
uses actual clock-time.
Theoretical:
Determining the quantity of resources required
mathematically (Execution time, memory space, etc.) needed
by each algorithm.
Data structures and algorithms
Cont’d
18
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
Input Size, Input Properties
Operating Environment
Data structures and algorithms
Complexity Analysis
19
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.
Cont‘d
20
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.
Benefits
21
Provides the short hand method, to find how much time
algorithm takes (approx.)
Its useful way of estimating the efficiency of an algorithm, without having to
measure actual run times.
Gives the choice to select among the best algorithms
available
Analysis Rules:
22
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
Cont’d
23
3. Running time of a selection statement (if, switch)
is the time for the condition evaluation +
the maximum running times for the individual clauses in the
selection.
Cont‘d
24
4. Loops: The running time for a loop is equal to
the running time for the statements inside the
loop * number of iterations.
Remark:
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.
Cont’d
25
5. The 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.
Exampl
e
26
int count() Time Units to Compute
{ -------------------------------------------------
•1 for the assignment statement: int
int k=0; k=0
•1 for the output statement.
cout<< “Enter •1 for the input statement.
an integer”;
cin>>n;
In the for
for (i=0;i<n;i++) • 1 assignment, n+1 tests,
loop:
k=k+1; increments
and n
• .n loops of 2 units for an
return 0; and an
assignment,
• addition.
1 for the return
}
statement.
T (n)= 1+1+1+(1+n+1+n)+2n+1 =
4n+6 = O(n)
Example
27
void func()
Time Units to Compute
{
-------------------------------------------------
int x=0; int i=0;
1 for the first assignment statement: x=0;
int j=1; 1 for the second assignment statement: i=0;
cout<< ―Enter an Integer 1 for the third assignment statement: j=1;
value‖; cin>>n;
1 for the output statement. 1 for the input
while (i<n){ x++;
statement.
i++; }
In the first while loop:
while (j<n) {
n+1 tests
j++;
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)
Asymptotic Analysis
28
The term asymptotic means approaching a value or curve arbitrarily
closely (i.e., as some sort of limit is taken).
Asymptotic analysis refers to computing the running time of any operation in
mathematical units of computation.
Asymptotic analysis of an algorithm refers to defining the mathematical
boundary/framing of its run-time performance.
Asymptotic Notations are languages that allow us to analyze an algorithm's
running time by identifying its behavior as the input size for the algorithm
increases. This is also known as an algorithm's growth rate.
Simplifying the Bound
29
T(n) = ck nk + ck-1 nk-1 + ck-2 nk-2 + … + c1 n+
co
too complicated
too many terms
Difficult to compare two expressions, each with 10 or
20 terms
Do we really need that many terms?
Simplifications
30
Keep just one term!
the fastest growing term (dominates the runtime)
No constant coefficients are kept
Constant coefficients affected by machines, languages, etc.
Asymptotic behavior (as n gets large) is determined
entirely by the leading term.
Example. T(n) = 10 n3 + n2 + 40n + 800
If n = 1,000, thenT(n) = 10,001,040,800
error is 0.01% if we drop all but the n3 term
Asymptotic
31
T(n) keep one drop coef
3n2+4n+1 3 n2 n2
101 n2+102 101 n2 n2
15 n2+6n 15 n2 n2
a n2+bn+c a n2 n2
They all have the same “growth” rate
Asymptotic Notations
32
Big Oh Notation, Ο
The notation Ο(n) is the formal way to express the upper bound of an
algorithm's running time. It measures the worst case time complexity or the
longest amount of time an algorithm can possibly take to complete.
Omega Notation, Ω
The notation Ω(n) is the formal way to express the lower bound of an
algorithm's running time. It measures the best case time complexity or the
best amount of time an algorithm can possibly take to complete.
Theta Notation, θ
The notation θ(n) is the formal way to express both the lower bound and
the upper bound of an algorithm's running time. It measures the average case
time complexity.
Average, Best, and Worst-Case
33
The time required by an algorithm falls under the following three types −
Average case:
— Average time required for program execution
Real-world distributions difficult to predict
Best case:
— Minimum time required for program execution
Seems unrealistic
Worst case:
— Maximum time required for program execution
Gives an absolute guarantee
On which input instances should the algorithm’s performance be Judged?
We will use the worst-case measure.
Common complexity classes
34
The most common complexity classes are (in ascending order of complexity):
• O(1),
•O(log n),
•O(n),
•O(n log n),
•O(n²),
•O(n3),
•O(2n)
35
o f
n d ne
e e ro
h
T ap te
ch