CHAPTER 1:

INTRODUCTION TO DATA
STRUCTURE AND
ALGORITHM
BIBHA STHAPIT
ASST. PROFESSOR
IoE, PULCHOWK CAMPUS
SYLLABUS OUTLINE
• 1. Concept of Data Structure
• 2. The stack and queue
• 3. List
• 4. Linked List
• 5. Recursion

Chapter 1
• 6. Trees
• 7. Sorting
• 8. Searching
• 9. Growth functions
• 10. Graphs

• Text Book: Data Structures using C and C++ -> Langsam, 2

Augenstein and Tanenbaum
Introduction to Data Structure
• NEED??
• To apply the best practices for developing efficient solutions
using computer programming.

Chapter 1
• To understand the relevant concepts and decisions to apply
the best fit data structure for the particular requirements.

• It deals with architecting, designing, developing and

optimizing the applications using computer programming.

• Data structure helps the programmers to develop effective 3

and reliable solutions.
Data Structure
• To know about the data structure, we’ll have to know about the
computer programming

Some mysterious
Input Output
processing

Chapter 1
Example :
• Data structure for storing data of students:-
• Arrays , Linked Lists
• Issues
• Space needed
• Operations efficiency (Time required to complete operations) 4
• Retrieval, Insertion, Deletion
Data Structure
• Data structures let the input and output be represented in a way
that can be handled efficiently and effectively.

array

Chapter 1
Linked list

queue
5

tree stack
Data Structure
• DEFINITION:
• Particular way of storing and organizing data in a computer so
that it can be used efficiently

• Data :

Chapter 1
• A piece of information
• Taken as input, processed within a computer, and provided as
output as information
• Can be “atomic” or “composite”
• Atomic data takes single value like integer 123
• Composite data which can be further broken down to subfields
like student record consists of roll_no, name, faculty, year etc.
6
Data Structure
• Data type:
• Kind of data that a variable can store.
• Built-in data types are system defined data types like int, float,
char.
• User-defined data type are created according to the need of the

Chapter 1
program like structure, union, class.

• Hence in brief, a data structure :

• Depicts the logical representation of data in computer memory
• Represents the logical relationship between various data
elements
• Helps in efficient manipulation of stored data elements 7
• Allows programs to process data in efficient manner
Types of Data Structure
• Static and dynamic data structure
• Static can store data upto fix number/size. E.g. Array
• Dynamic allows to change its size during program execution. E.g.
Linked-list

Chapter 1
• Linear and non-linear data structure
• In linear, data is stored in consecutive memory i.e. every element
has unique predecessor and unique successor. E.g. Array, linked
list, stack, queue
• In non-linear, data is stored in non-consecutive memory. Eg. Tree,
graph

8
Types of Data Structure
• Primitive and non-primitive data structure
• Primitive data structures are generally primary or built-in types and
are directly operated upon by machine instructions. E.g. integers,
floating points, characters
• Non-primitive emphasizes on structuring of homogeneous or

Chapter 1
heterogeneous data. E.g. Array, lists, linked list, tree

• Homogeneous and non-homogeneous data structure

• Homogeneous consist same type of data. E.g. Array
• Heterogeneous consists data of different types. E.g.. Structures, class

9
Types of Data Structure
• Sequential and direct/random access data structure
• In sequential, we must access preceding (n-1) data to access nth data.
E.g. Linked list
• In direct access, we can directly access nth element. E.g. array

Chapter 1
10
Types of Data Structure
Data Structure

Primitive/ Non Primitive /

Physical logical

Chapter 1
Non
Linear
Linear

Tree
Stack

Graph
Queue
11
Linked
lists
Overview of different Data Structures
• Arrays:
• Collection of similar data elements
• Elements are stored in consecutive memory.
• Have random access to data
• Application:

Chapter 1
• Used in program that require storing
large collection of similar data

12
Overview of different Data Structures
• Linked list
• It provides a flexible storage system by dynamically assigning the
required memory.
• Linked lists are special list of some data elements linked to one
another.

Chapter 1
• Application:
• Used wherever dynamic memory allocation is needed

13
Overview of different Data Structures
• Stack:
• List of elements with insertions and deletions permitted at one
end only – called stack top
• A stack data structure exhibits the LIFO (last in first out) property
• Application:

Chapter 1
• System processes such as compilation and program control

14
Overview of different Data Structures
• Queue
• A list of elements with insertions permitted at one end—called
the rear, and deletions permitted from the other end—called the
front
• a queue data structure exhibits the FIFO (first in first out)

Chapter 1
property.
• Application:
• Used in CPU scheduling, resource sharing

15
Overview of different Data Structures
• Trees:
• Non- linear data structure
• Arranges its nodes in the form of hierarchal tree structure
• Application:
• Used for storing hierarchical data, implementing search trees,

Chapter 1
maintaining sorted data.

16
Overview of different Data Structures
• Graphs:
• A graph is a structure made of two components: a set of vertices
V, and a set of edges E
• Application:
• Modelling of networking systems, costing of network paths

Chapter 1
17
Operations on Data Structures
• Traversing
• Accessing each record of data structure exactly once
• Searching
• Identifying location of record that consists specific key value
• Inserting

Chapter 1
• Adding new record
• Deleting
• Removing existing record
• Sorting
• Arranging data in specific order
• Merging
• Combining two different sorted records to produce single sorted data set. 18
Algorithm
• Once the data structure of particular application is chosen, an
algorithm must be developed to manipulate related data
items stored in it.

• It is a precise plan for performing sequence of actions

Chapter 1
• Definition:
• It is step-by-step finite set of instructions to solve a well-defined
computational problem.
• Sum of Two Numbers:
• step 1 − START ADD
• step 2 − get values of a & b
• step 3 − c ← a + b
• step 4 − display c 19
• step 5 − STOP
Algorithm
• Every algorithm must satisfy following criteria –

• input: there are zero or more quantities which are externally supplied;

• output: at least one quantity is produced;

Chapter 1
• definiteness: each instruction must be clear and unambiguous;

• finiteness: if we trace out the instructions of an algorithm, then for all

cases the algorithm will terminate after a finite number of steps;

• effectiveness: every instruction must be sufficiently basic that it can in

principle be carried out by a person using only pencil and paper. It is
20
not enough that each operation be definite as in (iii), but it must also
be feasible.
Algorithm design techniques
• Top down approach
• dividing the complex algorithm into one or more modules.
• These modules can further be decomposed into one or more sub-
modules, and this process of decomposition is iterated until the
desired level of module complexity is achieved.

Chapter 1
• Bottom up approach
• designing the most basic or concrete modules and then proceed
towards designing higher level modules.
• The higher level modules are implemented by using the operations
performed by lower level modules.
• Thus, in this approach sub-modules are grouped together to form a
higher level module.This process is repeated until the design of the
complete algorithm is obtained 21
Algorithm design techniques
• Brute Force
• goes through all the possible solutions one after another until you find
the optimum solution.
• Linear Search algorithm

Chapter 1
• Divide and conquer
• This algorithm solves a problem by dividing the original problem into
smaller chunks which are similar sub-problems.
• The solutions of these smaller sub problems are later combined to get
the solution of the given original problem.
• Quick sort and merge sort

22
 Algorithm design techniques
• Greedy
• works by taking a decision that appears the best at the moment,
without thinking about the future.
• A greedy algorithm solution isn't necessarily an overall optimal solution
since it only goes from one best solution to the next. Additionally, there
is no backtracking involved if it chooses the wrong option or step.

Chapter 1
• Djikstra’s algorithm, Prim’s algorithm

• Branch and bound

• The first solution is remembered by the algorithm and set as a
benchmark. It returns the original or the first solution if no solution is
found after the algorithm completes the whole search space.
• Travelling salesman problem
23
 Algorithm design techniques
• Randomized
• Here, random numbers are used to make some decisions. These
randomized algorithms are approximated using a pseudo – random
number generator.
• Quick sort using random number for pivot element, Monte-Carlo

Chapter 1
algorithm

• Simple Recursive
• Process in which a problem is defined in terms of itself.
• The problem is solved by repeatedly breaking it into smaller problems,
which are similar in nature to the original problems.
• Fibonacci series, Tower of Hanoi
24
 Algorithm design techniques
• Backtracking
• finds all the possible combinations of a solution and evaluates if it isn't
optimal. If it isn't, the algorithm backtracks and starts evaluating other
solutions.
• Backtracking algorithms share a common approach with the brute force
algorithm design technique but are much faster than brute-force

Chapter 1
algorithms.
• Depth-first recursive search in a tree

25
 Algorithm design techniques
• Dynamic programming
• solves problems that have overlapping sub-problems. Therefore, they are
well-suited for problems where certain sub-problems get solved repeatedly.
• optimizes the solution by storing the answers to sub-problems in an
optimal structure and retrieving them when needed.
• for example, generating a Fibonacci sequence. If we found the 4th number,

Chapter 1
we must have found all the ones before. Therefore, they are handy for
finding the 5th number.

26
Analysis of algorithm
• The two factors of Algorithm Complexity are:
• Time Factor:
• Time is measured by counting the number of key operations such as
comparisons in the sorting algorithm.
• Space Factor:

Chapter 1
• Space is measured by counting the maximum memory space
required by the algorithm.

27
 Analysis of algorithm
• Therefore the complexity of an algorithm can be divided into two types:

• Space Complexity:
• Space complexity of an algorithm refers to the amount of memory
that this algorithm requires to execute and get the result. This can be

Chapter 1
for inputs, temporary operations, or outputs.
• Generally, the space needed by a program depends on the following
two parts:
• Fixed part: It varies from problem to problem. It includes the space
needed for storing instructions, constants, variables, and structured
variables (like arrays and structures).
• Variable part: It varies from program to program. It includes the space
needed for recursion stack, and for structured variables that are allocated
space dynamically during the runtime of a program. 28
 Analysis of algorithm
• Time Complexity:
• Time complexity of an algorithm refers to the amount of time that this
algorithm requires to execute and get the result. This can be for normal
operations, conditional if-else statements, loop statements, etc.
• It is basically the running time of a program as a function of the input
size. In other words, the number of machine instructions which a

Chapter 1
program executes is called its time complexity. This number is primarily
dependent on the size of the program’s input and the algorithm used.

29
 Analysis of algorithm
• Worst case running time
• It denotes the behaviour of an algorithm with respect to the worst
possible case of the input instance.
• The worst-case running time of an algorithm is an upper bound on the
running time for any input. Therefore, having the knowledge of worst-
case running time gives us an assurance that the algorithm will never go
beyond this time limit.

Chapter 1
• Average case running time
• It is an estimate of the running time for an ‘average’ input. It specifies the
expected behaviour of the algorithm when the input is randomly drawn
from a given distribution. Average-case running time assumes that all
inputs of a given size are equally likely

• Best case running time

30
• It is used to analyse an algorithm under optimal condition
• For example, the best case for a simple linear search on an array occurs
when the desired element is the first in the list.
Abstract Data Type (ADT)
• Data abstraction
• Asks you to think what you can do to a collection of data
independently of how you do it
• Allows you to develop each data structure in relative isolation
from the rest of the solution

Chapter 1
• An abstract data type (ADT) is composed of
• A collection of data
• A set of operations on that data

• Specifications of an ADT indicate what the ADT operations do (but

not how to implement them)
• Implementation of an ADT includes choosing a particular data 31
structure
Abstract Data Type (ADT)
• An ADT consists of
• Declaration of data
• Declaration of operations
• Encapsulation of data and operations : data is hidden from
user and can be manipulated only by means of operations`

Chapter 1
32
 Abstract Data Type (ADT)
• To implement an ADT, you need to choose:
• A data representation (VALUE DEFINITION)
• must be able to represent all necessary values of the ADT
• It consists:
• definition clause (required)

Chapter 1
• condition clause (optional)

• An algorithm for each of the necessary operation (OPERATOR DEFINITION):

• must be consistent with the chosen representation
• It consists:
• header/definition clause
• precondition (optional)
• post-condition (action/result)
33
Abstract Data Type (ADT)
Array as ADT:
//value definition
abstract typedef <element_type, index_type> Array
//definition clause

Chapter 1
element_type A [max_size]
index_type i
//condition clause
index_type = = integer

34
 Abstract Data Type (ADT)
//operator definitions
abstract <element_type> Extract (A, i) //written as A[i]
integer i
Array A
//precondition
0 <= i <max_size

Chapter 1
//postcondition
Extract = = A[i]

abstract <element_type> Store(A, i, value)

Array A
index_type i
element_type value
//precondition
35
0 <= i <max_size
//postcondition
A[i] = = value
Abstract Data Type (ADT)

Chapter 1
36
THANK YOU!

Chapter 1
37