Data Structures & Algorithms

Chapter # 1
INTRODUCTION TO DATA
STRUCTURES

By:
Muhammad Imran
Assistant Prof. of Computer Science
Govt. Millat Degree College Mumtazabad, Multan

Lecturer (Visiting Faculty) of I.T

University of Education (Multan Campus) Multan
2 INTRODUCTION TO DATA STRUCTURES

Introduction to Data Structures

Data Structure:
A data structure is a systematic way of organizing data in a computer (memory) so that it
can be used efficiently. The idea is to reduce the space and time complexities of different
tasks. or in other words a data structure is an arrangement of data in computer's memory
in such a way that it could make the data quickly available to the processor for required
calculations. A data structure should be seen as a logical concept that must address two
fundamental concerns. First, how the data will be stored, and second, what operations
will be performed on it? As data structure is a scheme for data organization so the
functional definition of a data structure should be independent of its implementation. The
functional definition of a data structure is known as ADT (Abstract Data Type) which is
independent of implementation. An abstract data type in a theoretical construct that
consists of data as well as the operations to be performed on the data while hiding
implementation. The implementation part is left on developers who decide which
technology better suits to their project needs.

To develop a program of an algorithm we should select an appropriate data structure for

that algorithm. Therefore, data structure is represented as:

Algorithm + Data structure = Program

For example, data types like int, float, char data types only with the knowledge that these
data type can operate and be performed on without any idea of how they are
implemented, similarly on a stack ADT is a structure which supports operations such as
push and pop.

The data structures can also be classified on the basis of the following characteristics:

Types of Data Structures:

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
3 INTRODUCTION TO DATA STRUCTURES

Categories of Data Structures:

Linear: In Linear data structures, the data items are arranged in a linear sequence.
Example: Array

Non-Linear: In Non-Linear data structures, the data items are not in sequence. Example:
Tree, Graph

Homogeneous: In homogeneous data structures, all the elements are of same type.
Example: Array

Non-Homogeneous: In Non-Homogeneous data structure, the elements may or may not

be of the same type. Example: Structures

Static data structures: are those whose sizes and structures associated memory locations
are fixed, at compile time. Example: Array

Dynamic structures: are those which expands or shrinks depending upon the program
need and its execution. Also, their associated memory locations changes. Example:
Linked List created using pointers
Prepared By: Muhammad Imran
Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
4 INTRODUCTION TO DATA STRUCTURES

Operations on Data Structures:

 Inserting
 Deleting
 Searching
 Traversing
 Sorting

What is an Algorithm ?
An algorithm is a finite sequence of instructions, each of which has a clear meaning and
can be performed with a finite amount of effort in a finite length of time. No matter what
the input values may be, an algorithm terminates after executing a finite number of
instructions. Algorithm is written in English like language. Algorithm is not the complete
code or program, it is just the core logic(solution) of a problem, which can be expressed
either as an informal high level description and some language constructs (while, do, for ,
exit etc) as pseudocode or using a flowchart (A graphical representation of Algorithm is
called as Flowchart).
An algorithm consist of following parts:
 Name of Algorithm
 Introductory Comments
 Steps
 Comments
 Variable Name
 Operators
 Assignment Statement
Example
Problem − Design an algorithm to add two numbers and display the result.
step 1 − START ADD
step 2 − get values of a & b
step 3 − c ← a + b
step 4 − display c

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
5 INTRODUCTION TO DATA STRUCTURES

step 5 – STOP
Characteristics of an Algorithm:
Not all procedures can be called an algorithm. An algorithm should have the following
characteristics .
1. Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or
phases), and their inputs/outputs should be clear and must lead to only one meaning.
2. Input − An algorithm should have 0 or more well-defined inputs.
3. Output − An algorithm should have 1 or more well-defined outputs, and should match
the desired output.
4. Finiteness − Algorithms must terminate after a finite number of steps.
5. Feasibility − Should be feasible with the available resources.
6. Independent − An algorithm should have step-by-step directions, which should be
independent of any programming code.

Question: Write Algorithms for the following Problems

1. Exchange the values of two variable

2. Input three numbers and display the maximum number

We design an algorithm to get a solution of a given problem. A problem can be solved in

more than one ways.

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
6 INTRODUCTION TO DATA STRUCTURES

Hence, many solution algorithms can be derived for a given problem. The next step is to
analyze those proposed solution algorithms and implement the best suitable solution.

Algorithm Analysis:
Efficiency of an algorithm can be analyzed at two different stages, before implementation
and after implementation. They are the following –

1. A Priori Analysis − This is a theoretical analysis of an algorithm (by using asymptotic

notation) . Efficiency of an algorithm is measured by assuming that all other factors, for
example, processor speed, are constant and have no effect on the implementation.
2. A Posteriori Analysis − This is an empirical analysis of an algorithm. The selected
algorithm is implemented using programming language. This is then executed on target
computer machine. In this analysis, actual statistics like running time and space
required, are collected.
Algorithm Complexity:
An algorithm is said to be efficient and fast, if it takes less time to execute and consumes
less memory space. The performance of an algorithm is measured on the basis of
following properties:

1. Space Complexity
2. Time Complexity

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
7 INTRODUCTION TO DATA STRUCTURES

1. Space Complexity

Space complexity of an algorithm represents the amount of memory space required by

the algorithm in its life cycle. The space required by an algorithm is equal to the sum of
the following two components:

 A fixed part that is a space required to store certain data and variables, that are
independent of the size of the problem. For example, constants used, program size, etc.
 A variable part is a space required by variables, whose size depends on the size of
the problem. For example, dynamic memory allocation, recursion stack space, etc.

Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed part
and SP(I) is the variable part of the algorithm, which depends on instance characteristic I.
Following is a simple example that tries to explain the concept:

Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop
Here we have three variables A, B, and C and one constant. Hence S(P) = 1+3. Now,
space depends on data types of given variables and constant types and it will be
multiplied accordingly.

Example # 2
Declaring an array in C++ like Int a[100] would take 100 locations of memory, so space
can be reduced of we replace it with a single variable like int a.

E.g.
Suppose we want to add two integer numbers. To solve this problem we have following two
algorithms:
Algorithm 1: Algorithm 2:
Step 1- Input A. Step 1- Input A.
Step 2- Input B. Step 2- Input B.

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
8 INTRODUCTION TO DATA STRUCTURES

Step 3- Set C: = A+ B. Step 3- Write: ‘Sum is ‘, A+B.

Step 4- Write: ‘Sum is ‘, C. Step 4- Exit.
Step 5- Exit.
Both algorithms will produce the same result. But first takes 6 bytes and second takes 4 bytes (2
bytes for each integer). And first has more instructions than the second one. So we will choose
the second one as it takes less space than the first one.

2. Time Complexity
Time complexity of an algorithm represents the amount of time required by the algorithm
to run to completion. Time requirements can be defined as a numerical function T(n),
where T(n) can be measured as the number of steps, provided each step consumes
constant time and n is the size of the input.

For example, addition of two n-bit integers takes n steps. Consequently, the total
computational time is T(n) = c*n, where c is the time taken for the addition of two bits.
Here, we observe that T(n) grows linearly as the input size increases.

E.g.
Suppose we want to add two integer numbers. To solve this problem we have following
two algorithms:
Algorithm 1: Algorithm 2:
Step 1- Input A. Step 1- Input A.
Step 2- Input B. Step 2- Input B.
Step 3- Set C: = A+ B. Step 3- Write: ‘Sum is ‘, A+B.
Step 4- Write: ‘Sum is ‘, C. Step 4- Exit.
Step 5- Exit.
Suppose 1 second is required to execute one instruction. So the first algorithm will take 4
seconds and the second algorithm will take 3 seconds for execution. So we will choose
the second one as it will take less time.

Usually, the time required by an algorithm falls under following three types:
Best Case: In which we analyse the performance of an algorithm for the input, for which
the algorithm takes less time or space.

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
9 INTRODUCTION TO DATA STRUCTURES

Worst Case: In which we analyse the performance of an algorithm for the input, for
which the algorithm takes long time or space.

Average Case: In which we analyse the performance of an algorithm for the input, for
which the algorithm takes time or space that lies between best and worst case.

What is Asymptotic Notation?

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. Does the algorithm suddenly become incredibly
slow when the input size grows? Does it mostly maintain its quick run time as the input
size increases? Asymptotic Notation gives us the ability to answer these questions.

Asymptotic notation of an algorithm is a mathematical representation of its time

complexity.

Types of functions, limits, and simplification

 Logarithmic Function - log n

 Linear Function - an + b

 Quadratic Function - an^2 + bn + c

 Polynomial Function - an^z + . . . + an^2 + a*n^1 + a*n^0, where z is some

constant

 Exponential Function - a^n, where a is some constant

These are some basic function growth classifications used in various notations. The list
starts at the slowest growing function (logarithmic, fastest execution time) and goes on to
the fastest growing (exponential, slowest execution time).

One extremely important note is that for the notations about to be discussed you should
do your best to use simplest terms. This means to disregard constants, and lower order
terms, because as the input size (or n in our f(n) example) increases to infinity
(mathematical limits), the lower order terms and constants are of little to no importance.
Prepared By: Muhammad Imran
Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
10 INTRODUCTION TO DATA STRUCTURES

Since we want simplest form, lets modify our table a bit…

 Logarithmic - log n

 Linear - n

 Quadratic - n^2

 Polynomial - n^z, where z is some constant

 Exponential - a^n, where a is some constant

For example, consider the following time complexities of two algorithms...

 Algorihtm 1 : 5n2 + 2n + 1

 Algorihtm 2 : 10n2 + 8n + 3

Generally, when we analyze an algorithm, we consider the time complexity for larger
values of input data (i.e. 'n' value). In above two time complexities, for larger value of 'n'
the term in algorithm 1 '2n + 1' has least significance than the term '5n2', and the term in
algorithm 2 '8n + 3' has least significance than the term '10n2'.

Here for larger value of 'n' the value of most significant terms ( 5n2 and 10n2 ) is very
larger than the value of least significant terms ( 2n + 1 and 8n + 3 ). So for larger value of
'n' we ignore the least significant terms to represent overall time required by an
algorithm. In asymptotic notation, we use only the most significant terms to represent the
time complexity of an algorithm.

Types of Data Structure Asymptotic Notation

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
11 INTRODUCTION TO DATA STRUCTURES

1. Big-O Notation (Ο) – Big O notation specifically describes worst case scenario.
2. Omega Notation (Ω) – Omega(Ω) notation specifically describes best case scenario.
3. Theta Notation (θ) – This notation represents the average complexity of an algorithm.

1. Big-O Notation (Ο)

Big O notation specifically describes worst case scenario. It represents the upper bound
running time complexity of an algorithm. Lets take few examples to understand how we
represent the time and space complexity using Big O notation.

O(1)

Big O notation O(1) represents the complexity of an algorithm that always execute in
same time or space regardless of the input data.

O(1) example
The following step will always execute in same time(or space) regardless of the size of
input data.

e.g. Accessing array index(int num = arr[5])

O(n)

Big O notation O(N) represents the complexity of an algorithm, whose performance will
grow linearly (in direct proportion) to the size of the input data.

O(n) example
The execution time will depend on the size of array. When the size of the array increases,
the execution time will also increase in the same proportion (linearly)

e.gTraversing an array

O(n^2)

Big O notation O(n^2) represents the complexity of an algorithm, whose performance is

directly proportional to the square of the size of the input data.

O(n^2) example

e.g Traversing a 2D array

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
12 INTRODUCTION TO DATA STRUCTURES

Other examples: Bubble sort, insertion sort and selection sort algorithms (we will discuss
these algorithms later in separate tutorials)

Similarly there are other Big O notations such as:

logarithmic growth O(log n), log-linear growth O(n log n), exponential growth O(2^n)
and factorial growth O(n!).

If I have to draw a diagram to compare the performance of algorithms denoted by these

notations, then I would draw it like this:

O(1) < O(log n) < O (n) < O(n log n) < O(n^2) < O (n^3)< O(2^n) < O(n!)

2. Omega Notation (Ω)

Omega notation specifically describes best case scenario. It represents the lower
bound running time complexity of an algorithm. So if we represent a complexity of
an algorithm in Omega notation, it means that the algorithm cannot be completed
in less time than this, it would at-least take the time represented by Omega

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
13 INTRODUCTION TO DATA STRUCTURES

notation or it can take more (when not in best case scenario).

3. Theta Notation (θ)

This notation describes both upper bound and lower bound of an algorithm so we can say that it
defines exact asymptotic behaviour. In the real case scenario the algorithm not always run on
best and worst cases, the average running time lies between best and worst and can be epresented

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
14 INTRODUCTION TO DATA STRUCTURES

by the theta notation.

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
15 INTRODUCTION TO DATA STRUCTURES

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.
16 INTRODUCTION TO DATA STRUCTURES

Prepared By: Muhammad Imran

Assistant Prof. of Computer Science, Govt. Millat Degree College, Multan.
Lecturer (Visiting Faculty) of I.T, University of Education Multan Campus.