Data Structures

Unit – I (CSCS202)
 Unit -1
• Basic Terminologies
• Linear and Nonlinear Data Structures
• Algorithm
• Definition
• Pseudo Code
• Analysis
• Design Techniques
Basic Terminologies
Data, Attribute, Entity, Entity Set, Domain, Information, Data type, built-in data type, user-defined
data type, field, Record, file

• Data - Data means value or set of values.

Eg.:34, 12/01/1965,Pascal, ISBN 81-203-0000-0,

21,25,28,30,35

• Attribute – An attribute is a property or characteristics that

describes an entity. Eg.: A person entity may have attributes such as
name, age, and address.
• Entity- An entity has certain attributes and can be assigned values. For
example, an employee in an organization is an entity.

• Entity Set: All the employees in an organisation constitute an entity set.

• Each attribute of an entity set has a range of values, and is called the
domain of attribute.

• Domain is the set of all possible values that could be assigned to the
particular attribute. Eg.
• Information - Data with its attribute(s). Defined as meaningful data or
processed data.
Processed data that is meaningful and useful for decision-making.
• Data type - A data type is a term which refers to the kind of data that may
appear in computation.
• Built-in data type - With every programming language, there is a set of data types
called built-in data types.

• Abstract data type - Programmers' own data type is termed as abstract data type.
Abstract data type is also known as user-defined data type.
The programmer focus on how to store value for that data, amount of memory
require to store for a variable, what are the meaningful variable operations. For
example, using struct/class in C/C++
• 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.
Records 2 types: fixed length records and variable length records.
Fixed-Length records, all the records contain the same data items with the same
amount of space assigned to each data item.
Variable-Length records, file records may contain different lengths. Example:
Different number of courses taken by the student.
• File is the collection of records of the entities in a given entity set.

• Data structure is a particular way of storing and organizing data in a computer

so that it can be used efficiently. A data structure is a special format for organizing
and storing data. General data structure types include arrays, files, linked lists,
stacks, queues, trees, graphs and so on.
Linear and Nonlinear Data Structures
Data structure is a particular way of storing and organizing data in a computer so that it can
be used efficiently. A data structure is a special format for organizing and storing data.
General data structure types include arrays, files, linked lists, stacks, queues, trees, graphs and
so on.

Depending on the organization of the elements, data structures are classified into two types:
1) Linear data structures:
Elements are accessed in a sequential order but it is not compulsory to store all elements
sequentially.
Examples: Arrays, Linked Lists, Stacks and Queues.

2) Non – linear data structures:

Elements of this data structure are stored/accessed in a non-linear order.
Examples: Trees and graphs.
• Array is a type of data structure that stores data elements in adjacent
locations.
• A stack is an ordered list in which insertion and deletion are done at one
end, called as top.
• A queue is an ordered list in which insertions are done at one end (rear)
and deletions are done at other end (front).
• Linked list is a linear data structure where elements (nodes) are stored in
sequence, with each node pointing to the next node.
• A tree is a data structure similar to a linked list but instead of each node
pointing simply to the next node in a linear fashion, each node points to a
number of nodes.
• A graph is a pair (V, E), where V is a set of nodes, called vertices, and E is a
collection of pairs of vertices, called edges.
Algorithm
• Algorithm is a step-by-step instructions to solve a problem.
• The concept of an algorithm is fundamental to computer science.
Algorithms exist for many common problems, and designing efficient
algorithms plays a crucial role in developing large-scale computer
systems.
Example
Algorithm for Addition of Two Numbers
Step 1: Start
Step 2: Read the Input of two numbers, a and b
Step 3: Add a and b and store the result in sum
Step 4: Write the Output sum
Step 5: End
Pseudocode
• Pseudocode is an informal method of developing an algorithm.
• Computer programmers use simple informal language to write a pseudocode.
• It does not have any specific syntax to follow.
• Basically, pseudocode represents an algorithm to solve a problem in natural
language and mathematical notations.
• The pseudo-code is a written form representation of the algorithm.
• It differs from the step-form as it uses a restricted vocabulary to define its action
of solving
• the problem.
• Pseudocode is a text based detail design tool.
• Pseudocode is written more close to programming language.
Pseudocode is also written using some specific words and characters, which
are shown below:
➢ To begin the comment double forward slash are used “//“.
➢ Matching braces “{ and }” are used to present blocks of statement
terminated by a semicolon”;“.
➢ All the identifiers start with a letter and the datatype of the variables are
not declared explicitly.
➢ An assignment statement is used for the assigning values to the variables.
➢ Boolean values (i.e., true and false), the logical operators(i.e., AND, OR,
NOT) and the relational operators (i.e., <, ≤, =, =, ≥ and >) are provided.
➢ Input and output are presented by read and write instructions.
➢ “if and then” expressions are used to express a conditional statement.
Example for pseudo-code:

Addition()
{
BEGIN
Input a,b;
sum = a+b;
Output sum;
END
}
ANALYSIS OF ALGORITHMS

Analysis of algorithm helps us to determine which algorithm is most

efficient in terms of time and space consumed.
Performance Analysis of Algorithm:
The space complexity of an algorithm is the amount of memory it needs to
run to completion.
The time complexity of an algorithm is the amount of computer time it
needs to run to completion.
Space Complexity
The space complexity of a program refers to the total amount of memory it
requires to execute, including both fixed and variable memory allocations.
It is composed of the following components:
1. Fixed Space Requirements
These are the memory requirements that remain constant, regardless of the size
of the input. They include:
• Instruction space (code)
• Space for simple variables (e.g., integers, floats)
• Fixed-size structured variables (e.g., arrays of fixed size)
• Constants
This component is denoted by a constant c.
2. Variable Space Requirements
This part depends on the input instance I of the problem. It includes:
• Memory required for dynamically allocated structures (e.g., arrays or linked
lists whose size depends on input)
• Recursive function call (each call add a frame to call stack)
This component is denoted as Sp(I), where:
•Sp(I) varies with the characteristics of the input I
•Characteristics may include number, size, and values of inputs and outputs
Types of Algorithm Analysis:
Best case
Worst case
Average case
• Best case: Define the input for which algorithm takes less time or minimum time. In the best case
calculate the lower bound of an algorithm. Example: In the linear search when search data is present
at the first location of large data then the best case occurs.
• Worst Case: Define the input for which algorithm takes a long time or maximum time. In the worst
calculate the upper bound of an algorithm. Example: In the linear search when search data is not
present at all then the worst case occurs.
• Average case: In the average case take all random inputs and calculate the computation time for all
inputs. And then we divide it by the total number of inputs.
Average case = all random case time / total no of case
Common Time Complexities and Their Growth Rates
Asymptotic Notation

Asymptotic notations are mathematical tools used to describe the time or space
complexity of algorithms as the input size (n) grows large. It helps in analyzing
algorithm performance in a machine-independent way.

Function f(n):
This represents the actual running time (or space) of the algorithm in terms of the input
size n. It is the function that needs to be analysed.

Function g(n):
This represents the reference function that describes the asymptotic behaviour (growth
rate) comparing f(n).
Common examples of g(n) include functions like:
n, n², log n, n log n
 3 common Asymptotic Notation:
Big O Notation (O)
Omega Notation (Ω)
Theta Notation (Θ)
Big O Notation (O)
Definition:
Big O gives an upper bound on the growth rate of an algorithm.
It describes the worst-case time or space complexity.

Formal Definition:
A function f(n) = O(g(n)) if there exist positive constants c and n₀
such that:

f(n)≤c⋅g(n)
for all n≥ n₀

Example:
If f(n) = 3n + 2, then f(n) = O(n).
Omega Notation (Ω)
Definition:
Omega gives a lower bound on the growth rate of an
algorithm.
It describes the best-case time or space complexity.

Formal Definition:
A function f(n) = Ω(g(n)) if there exist positive constants c
and n₀ such that:
f(n)≥c⋅g(n)
for all n≥ n₀

Example:
If f(n) = 2n + 1, then f(n) = Ω(n).
Theta Notation (Θ)
Definition:
Theta gives a tight bound on the growth rate of an
algorithm.
It describes the average-case or exact growth rate.

Formal Definition:
A function f(n) = Θ(g(n)) if there exist positive constants
c₁, c₂, and n₀ such that:

c₁ ⋅g(n) ≤ f(n) ≤ c₂ ⋅g(n)

for all n≥ n₀

Example:
If f(n) = 4n + 3, then f(n) = Θ(n).