BCSE202L- Data Structures
and Algorithms
Dr. Iyappan Perumal
Associate Professor
School of Computer Science & Engineering
VIT, Vellore.
BCSE202L- Data Structures
and Algorithms- Course
Objective
1. To impart basic concepts of data structures and
algorithms.
2. To differentiate linear, non-linear data structures and
their operations.
3. To comprehend the necessity of time complexity in
algorithms
BCSE202L- Data Structures
and Algorithms- Course
Outcome
1. Understand the fundamental analysis and time
complexity for a given problem.
2. Articulate linear, non-linear data structures and legal
operations permitted on them.
3. Identify and apply suitable algorithms for searching
and sorting.
4. Discover various tree and graph traversals.
5. Explicate hashing, heaps and AVL trees and realize
their applications.
BCSE202L- Data Structures
and Algorithms
Assessment Configuration
◦ Quiz-1
◦ Quiz-2
◦ Course based Design Project/Case Study
◦ CAT-1
◦ CAT-2
BCSE202L- Data Structures and
Algorithms
Module-1: Algorithm Analysis
Module-2: LinearData Structures
Module-3: Searching and Sorting
Module-4: Trees
Module-5: Graphs
Module-6: Hashing
Module-7: Heaps and AVL Trees
BCSE202L- Data Structures and
Algorithms
Text Books:
1. Mark A. Weiss, Data Structures & Algorithm Analysis in C++, 4
th Edition, 2013,Pearson Education.
Reference Books:
1. Alfred V. Aho, Jeffrey D. Ullman and John E. Hopcroft, Data
Structures and Algorithms,1983, Pearson Education.
2. Horowitz, Sahni and S. Anderson-Freed, Fundamentals of Data
Structures in C, 2008, 2nd Edition, Universities Press.
3. Thomas H. Cormen, C.E. Leiserson, R L. Rivest and C. Stein,
Introduction to Algorithms, 2009, 3rd Edition, MIT Press.
Module 1: Algorithm Analysis(8 Hours)
Importance of algorithms and data structures
Fundamentals of Algorithm Analysis( Space and
Time Complexity)
Asymptotic notations and orders of growth.
Efficiency of Algorithm
Analysis of non-recursive and recursive algorithms
Asymptotic analysis for recurrence relation:
◦ Iteration Method
◦ Substitution Method
◦ Master Method
◦ Recursive Tree Method
Importance of algorithms and data
structures
Data
Data are characteristics or information, usually
numerical, that are collected through observation. In a
more technical sense, data is a set of values of
qualitative or quantitative variables about one or more
persons or objects, while a datum (singular of data) is a
single value of a single variable.
What is an Algorithm ?
• An algorithm is a finite set of instructions or logic,
written in order, to accomplish a certain predefined
task.
• Every Algorithm must satisfy the following properties:
• Input- There should be 0 or more inputs supplied
externally to the algorithm.
• Output- There should be at least 1 output obtained.
• Definiteness- Every step of the algorithm should be
clear and well defined.
• Finiteness- The algorithm should have finite number
of steps.
• Correctness- Every step of the algorithm must
generate a correct output.
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 :
Time Complexity
Space Complexity
Data Structure
A data structure is a data organization,
management, and storage format that enables
efficient access and modification. More
precisely, a data structure is a collection
of data values, the relationships among them,
and the functions or operations that can be
applied to the data.
Other Definitions
A data structure is a way of organizing
data that considers not only the items
stored but also their relationship to each
other.
Basic Operations
◦ Insertion
◦ Deletion
◦ Traversal
◦ Search
◦ Sort
◦ Merge
Basic Terminologies in DS
Data: Data are simply values or sets of values.
Data items: Data items refers to a single unit of values.
Group: Data items that are divided into sub-items are called Group
items.
Elementary items: Data items that are not able to divide into sub-
items are called Elementary items.
Entity: An entity is something that has certain attributes or
properties which may be assigned values. The values may be either
numeric or non-numeric.
Field is a single elementary unit of information representing an
attribute of an entity.
Record is the collection of field values of a given entity.
File is the collection of records of the entities in a given entity set.
Fundamentals of Algorithm Analysis
Stages of algorithm development
• Describing the problem
• Identifying a suitable technique
• Design of an Algorithm
• Proof of Correctness of the Algorithm
• Computing the time complexity of the Algorithm
Algorithm Efficiency- Performance
Analysis
Based on Time and Space Complexity
◦ Best Case( Min Amount of Time)
◦ Worst Case( Max Amount of Time)
◦ Average Case( Average amount of Time)
Time Complexity
The amount of time taken by an
algorithm to run to completion
It is measured by number of primitive
operations required to produce output.
Time complexity is independent of
◦ Speed
◦ Word length
◦ OS
◦ Translation Time
Space complexity
The amount of space required by an
algorithm to run to completion.
Mostly, time and space complexity is
computed as a function of input size
Calculation of Time Complexity
Two Approaches
◦ Frequency Count or Step Count
◦ Asymptotic Notions
Frequency Count/Step Count
Method
Number of times a statement is executed.
RULES:
◦ For comments, declarations, STEP COUNT=0
◦ For return, assignment statements, STEP COUNT=1
◦ Ignore lower order exponents when higher order
exponents are present.
◦ Ignore constant multipliers
Example: Sum of N Numbers(Time Complexity)
Algorithm Step Count
--
Alg sum(a[],n)
--
{
1
sum=0;
N+1
for(i=1 to n) do
N
sum=sum+a[i];
1
return sum;
}
2N+3
TOTAL
O(N)
Example: Sum of N Numbers(Space Complexity)
Algorithm
Alg sum(a[],n) A[]– n words
{ n=one word
sum=0; Sum=one word
for(i=1 to n) do i= one word
sum=sum+a[i];
return sum;
}
TOTAL N+3
O(n)
Try Some Other examples
Matrix Addition
Matrix Multiplication
Bubble sort
Insertion Sort
Selection Sort
Linear Search
Binary search
Thank You