PCA25C02T DATA STRUCTURES AND ALGORITHMS

CLASS –I MCA C
UNIT-1

Overview and importance of algorithms Algorithm specification,

Performance analysis, Asymptotic Notation, The Big-O,Omega and Theta
notation, Programming Style, Refinement of Coding, Introduction to Data
structures, Abstract Data type, Data Representation, Complexity of
Algorithms, Operations, Types of Data structures – Linear and Non Linear,
Arrays, Representation of Arrays, Types of Arrays, Arrays operations,
Application of Arrays, Introduction to lists, Representation of Linked list ,
Operations, Types of Linked List, Header Linked List, Circularly Linked List,
Doubly Linked List

OVERVIEW AND IMPORTANCE OF ALGORITHMS

What is an Algorithm?

An algorithm is a step-by-step set of instructions or rules designed to solve a specific

problem or perform a task. It is a well-defined procedure that takes input, processes it through
a finite sequence of operations, and produces output.

Overview of Algorithms

● Definition: A finite sequence of unambiguous instructions.

● Purpose: To solve problems or perform computations efficiently.
● Characteristics:
o Finiteness: Must terminate after a finite number of steps.
o Definiteness: Each step must be clear and unambiguous.
o Input: Algorithms may take zero or more inputs.
o Output: At least one output should be produced.
o Effectiveness: All operations must be basic enough to be performed exactly.

Importance of Algorithms

1. Problem Solving
Algorithms provide a systematic approach to solve problems, whether simple or
complex. They allow breaking down problems into manageable steps.
 2. Efficiency
Well-designed algorithms optimize the use of resources such as time and memory.
This leads to faster and more cost-effective solutions.
3. Automation
Algorithms are the foundation of computer programs, enabling automation of
repetitive or complex tasks in fields like finance, healthcare, engineering, and more.
4. Scalability
Good algorithms can handle large inputs and scale efficiently, which is critical in
data-driven applications and big data processing.
5. Reusability and Maintenance
Algorithms can be reused across different applications, making software development
easier and more consistent. Clear algorithms also improve maintainability.
6. Foundation of Computer Science
Algorithms form the core of computer science theory and practice, influencing data
structures, programming, artificial intelligence, cryptography, and more.

Algorithm Specification

Algorithm Specification is the detailed description of an algorithm’s steps and its behavior,
often expressed in a clear, precise way so it can be understood and implemented.

Key components of algorithm specification include:

1. Input
What data the algorithm receives before it starts. Inputs must be clearly defined.
2. Output
What the algorithm produces after processing the input. This should be well specified.
3. Definiteness
Each step should be clearly and unambiguously described.
4. Preconditions
Conditions or assumptions about the input before the algorithm starts.
5. Postconditions
Conditions that should be true after the algorithm finishes execution.
6. Algorithm Description
The step-by-step process, usually described in:
o Natural language
o Pseudocode (structured, language-like representation)
o Flowcharts or diagrams

Purpose:
Algorithm specification acts like a contract or blueprint for implementation, ensuring
everyone understands exactly what the algorithm does and how.

Performance Analysis of Algorithms

Performance analysis evaluates how well an algorithm performs, mainly in terms of:

1. Time Complexity
 o Measures how the running time of an algorithm grows with the size of the
input (usually denoted as n).
o Expressed using Big O notation (e.g., O(n), O(log n), O(n²)) which describes
the upper bound of time growth.
o Helps predict the algorithm’s efficiency on large inputs.
2. Space Complexity
o Measures the amount of memory an algorithm uses relative to the input size.
o Also expressed in Big O notation.
o Important for applications with limited memory.
3. Other factors
o Best-case, worst-case, and average-case performance: How the algorithm
performs in different scenarios.
o Scalability: How performance changes as input grows very large.
o Practical considerations: Such as simplicity, ease of implementation, and
constant factors hidden in Big O.

Importance of Performance Analysis Matters

● Helps choose the most efficient algorithm for a problem.

● Identifies bottlenecks and opportunities for optimization.
● Ensures algorithms run effectively in real-world applications, saving time and
resources.
● Supports informed trade-offs between time and space usage.

Asymptotic Notation
Asymptotic notation is a way to describe the growth rate of an algorithm’s running time or
space requirements as the input size (n) grows large. It helps us understand the efficiency and
scalability of algorithms without getting bogged down by hardware specifics or constant
factors.
1. Big-O Notation (O)
● Purpose: Gives an upper bound on the growth rate of an algorithm’s running time or
space.
● Interpretation: The running time will not grow faster than this rate, up to a
constant factor, for sufficiently large inputs.
● Example:
If an algorithm takes at most 5n² + 3n + 10 steps, its time complexity is O(n²),
because the n² term dominates as n grows.
Formally:
f(n) = O(g(n)) means there exist positive constants c and n₀ such that
f(n) ≤ c * g(n) for all n ≥ n₀.

2. Omega Notation (Ω)

● Purpose: Gives a lower bound on the growth rate.
 ● Interpretation: The running time will be at least this fast for sufficiently large inputs.
● Example:
If an algorithm takes at least n steps, then its time complexity is Ω(n).
Formally:
f(n) = Ω(g(n)) means there exist positive constants c and n₀ such that
f(n) ≥ c * g(n) for all n ≥ n₀.

3. Theta Notation (Θ)

● Purpose: Provides a tight bound — both upper and lower bound.
● Interpretation: The running time grows exactly at the rate of g(n), ignoring constant
factors.
● Example:
If an algorithm’s running time is both O(n²) and Ω(n²), then it is Θ(n²).
Formally:
f(n) = Θ(g(n)) means there exist positive constants c₁, c₂, and n₀ such that
c₁ * g(n) ≤ f(n) ≤ c₂ * g(n) for all n ≥ n₀.

Programming Style
Good programming style is essential for writing readable, maintainable, and efficient code.
It helps other developers (and your future self) understand, debug, and improve code.
Key aspects include:
● Consistent Naming: Use meaningful variable and function names.
● Indentation and Formatting: Keep consistent indentation and spacing to show
structure clearly.
● Comments: Explain why certain code exists, especially complex logic.
● Modularization: Break code into functions or modules, each with a clear purpose.
● Avoid Redundancy: Don’t repeat code — use functions or loops instead.
● Follow Language Conventions: Adhere to style guides for the programming
language you're using.

Refinement of Coding
Refinement is the process of improving and optimizing code after writing an initial version.
It includes:
1. Improving clarity: Simplify complex logic, add comments.
2. Optimizing performance: Use more efficient algorithms or data structures.
3. Error handling: Add checks and validations to avoid crashes.
 4. Removing redundancy: Factor out repeated code.
5. Testing: Run test cases and fix bugs.
Refinement is iterative: Code is gradually improved through multiple cycles.

Introduction to Data Structures

A data structure is a way of organizing, managing, and storing data in a computer so that it
can be accessed and modified efficiently. Different data structures are suited for different
kinds of applications, and some are highly specialized to specific tasks.
Examples include:
● Arrays: Store elements in contiguous memory locations.
● Linked Lists: Elements (nodes) linked via pointers.
● Stacks & Queues: Follow specific order rules for insertion/removal.
● Trees & Graphs: Represent hierarchical or networked data.
● Hash Tables: Provide fast access using keys.

Abstract Data Type (ADT)

An Abstract Data Type is a theoretical concept that defines a data type by its behavior
(operations allowed) rather than its implementation details.
● What it specifies:
o The set of data values.
o The operations possible on the data (like insert, delete, search).
o The behavior of these operations (what they do).
● What it hides:
o How the data and operations are implemented internally.
Example:
A Stack ADT specifies operations like push, pop, peek and their behavior (LIFO order), but
doesn’t say whether it uses an array or linked list internally.

Data Representation
Data representation refers to how data is actually stored in computer memory. The physical
layout impacts efficiency and capabilities.
Examples of data representation:
● Primitive types: Integers, floats, characters are stored as binary values.
● Arrays: Stored as contiguous blocks of memory.
 ● Linked lists: Nodes stored at different memory locations, linked by pointers.
● Trees: Represented as nodes with references to child nodes.
● Graphs: Stored via adjacency matrices or adjacency lists.
Choosing the right data representation is critical because it affects:
● Access speed
● Memory usage
● Ease of implementing operations
Complexity of Algorithms
Algorithm complexity measures how the resource usage of an algorithm (usually time or
space) changes as the input size grows.

Types of Complexity
1. Time Complexity
o How the running time increases with input size n.
o Expressed with asymptotic notations like Big-O, which describe worst-case or
average-case scenarios.
o Example: An algorithm with time complexity O(n²) means the running time
grows roughly proportional to the square of the input size.
2. Space Complexity
o How much additional memory an algorithm uses as input size increases.
o Also expressed in Big-O notation.

Common Operations & Their Complexity

When analyzing algorithms, it’s useful to understand the complexity of basic operations on
data structures:
Operation Array Linked List Stack Queue Binary Search Tree

Access (by index) O(1) O(n) O(n) O(n) O(log n)*

Search O(n) O(n) O(n) O(n) O(log n)*

Insertion O(n) (worst) O(1) at head O(1) push O(1) enqueue O(log n)*

Deletion O(n) (worst) O(1) at head O(1) pop O(1) dequeue O(log n)*

Types of Data Structures

1. Linear Data Structures
In linear data structures, elements are arranged in a sequential order, one after another. Each
element has a unique predecessor and successor (except the first and last).
Examples:
● Array: Collection of elements stored at contiguous memory locations, accessible by
index.
● Linked List: A sequence of nodes where each node points to the next node.
● Stack: Follows Last-In-First-Out (LIFO) order. Elements added and removed from
the top.
● Queue: Follows First-In-First-Out (FIFO) order. Elements added at the rear, removed
from the front.

Characteristics:
● Data elements form a sequence.
● Traversal is straightforward (usually from first to last).
● Easy to implement and use.
● Examples of operations: insertion, deletion, traversal.

2. Non-Linear Data Structures

In non-linear data structures, elements are not arranged sequentially but in a hierarchical or
interconnected manner. One element can be connected to multiple elements.
Examples:
● Tree: Hierarchical structure with a root node and child nodes forming a hierarchy.
o Example: Binary tree, Binary Search Tree, AVL tree.
● Graph: Set of nodes (vertices) connected by edges. Can represent networks, social
connections, etc.
Characteristics:
● Elements have multiple relationships.
● Traversal is more complex (e.g., depth-first, breadth-first).
● Suitable for representing complex data models.
● Operations often involve searching, insertion, deletion in a non-linear context.
Arrays
An array is a collection of elements of the same data type stored in contiguous memory
locations. It allows storing multiple values under a single name and accessing them using an
index.

Representation of Arrays
● Memory Layout:
Elements are stored sequentially in memory. For example, if an array starts at
memory address A, the element at index i is stored at address:
A + i * size_of_element

● Indexing:
Most programming languages use zero-based indexing, so the first element is at
index 0, second at 1, and so on.
● Accessing Elements:
Accessing an element at index i is done directly using the formula above, which
makes access very fast (O(1)).

Types of Arrays
1. One-Dimensional Array (1D Array)
o A linear sequence of elements.
o Example: int arr[5] = {10, 20, 30, 40, 50};
o Represents a simple list of elements.
2. Two-Dimensional Array (2D Array)
o An array of arrays; elements arranged in rows and columns (like a matrix).
o Example: int matrix[3][4]; represents 3 rows and 4 columns.
o Used to represent tables, grids, matrices.
3. Multi-Dimensional Arrays
o Arrays with three or more dimensions, e.g., int arr[3][4][5];
o Used for more complex data like 3D graphics, scientific computations.

Summary Table
Array Type Structure Example Usage

List of scores
One-Dimensional Linear sequence
 Array Type Structure Example Usage

Rows and columns Spreadsheet data,

Two-Dimensional
(matrix form) images

Multi-Dimensional More than 2 dimensions 3D models, simulations

Operations on Arrays

1. Traversal
● Accessing each element of the array one by one.
● Used to display or process every element.
● Time Complexity: O(n), where n is the number of elements.
2. Insertion
● Adding an element at a specific position.
● If inserting at the end (and space is available), simply place the element.
● If inserting elsewhere, shift elements to the right to make space.
● Time Complexity:
o O(1) if inserting at the end (for dynamic arrays with capacity).
o O(n) if inserting at any other position (due to shifting).

3. Deletion
● Removing an element from a specific position.
● After removal, elements to the right are shifted left to fill the gap.
● Time Complexity: O(n) (due to shifting elements).

4. Searching
● Finding whether an element exists in the array and its index.
● Types of searching:
o Linear Search: Check each element until found or end reached. O(n) time.
o Binary Search: Efficient search on sorted arrays. O(log n) time.

5. Update
 ● Changing the value of an element at a given index.
● Direct access allows O(1) time complexity.

Applications of Arrays
1. Storing Data Collections
● Arrays are used to store multiple values of the same type, like a
list of student marks, temperature readings, or product prices.
● Easy to access any element using an index.
2. Implementing Other Data Structures
● Arrays are the building blocks for other data structures such as:
o Stacks
o Queues
o Heaps
o Hash Tables (underlying storage often uses arrays)
3. Matrix Operations
● 2D arrays (matrices) are essential for mathematical
computations like multiplication, addition, and transformations
in graphics.
● Used in image processing, scientific simulations, and machine
learning.
4. Sorting and Searching Algorithms
● Many sorting algorithms (like Bubble Sort, Quick Sort) and
searching algorithms (like Binary Search) work directly on
arrays.
● Arrays provide quick access to elements needed during these
algorithms.
5. Hashing
● Arrays provide fast indexed storage for hash tables, enabling
constant-time average access for key-value pairs.
6. Data Representation
● Arrays are used to represent tabular data in databases, grids in
games, adjacency matrices for graphs, and more.
7. Buffer Management
● Arrays serve as buffers for input/output streams (like keyboard
input, network data, or file reading).
Introduction to Lists
A list is a collection of elements arranged in a linear order. Unlike
arrays, lists can easily grow and shrink dynamically without needing a
contiguous block of memory.

Linked List
A Linked List is a type of list where elements are stored in nodes, and
each node contains:
● The data (value)
● A reference (or pointer) to the next node in the sequence
Unlike arrays, linked lists do not store elements in contiguous memory
locations.

Representation of Linked List

● Node Structure:
+-------+---------+
| Data | Next |

● Each node points to the next node.

● The last node points to NULL (or None), indicating the end of the list.
Example:
Head -> [Data|Next] -> [Data|Next] -> [Data|NULL]
Types of Linked Lists
● Singly Linked List: Nodes have a pointer to the next node only.
● Doubly Linked List: Nodes have pointers to both next and previous nodes.
● Circular Linked List: The last node points back to the head, forming a loop.

Operations on Linked List

Operation Description Time Complexity

Traversal Visit each node to process or display data O(n)

Insertion Add a new node (at beginning, end, or middle) O(1) at head, O(n) elsewhere

Deletion Remove a node by value or position O(1) if node known, O(n) to search

Search Find a node with a given value O(n)

Operation Description Time Complexity

Update Modify data in a node O(n) (search first)

Types of Linked Lists

1. Singly Linked List
● Each node contains data and a pointer/reference to the next node only.
● Traversal is one-way, from head to the last node.
● The last node points to NULL indicating the end.
● Simple to implement, but no backward traversal.
2. Doubly Linked List
● Each node contains data and two pointers:
o One to the next node
o One to the previous node
● Allows two-way traversal (forward and backward).
● More flexible but uses extra memory for the previous pointer.
3. Circular Linked List
● The last node’s next pointer points back to the head node, forming a circle.
● Can be singly or doubly linked.
● Useful for applications needing cyclic traversal (e.g., round-robin scheduling).

Header Linked List

A Header Linked List is a variation of a linked list where a special node called the header
node is used at the beginning of the list.
Characteristics:
● The header node does not contain actual data or contains metadata like the count of
nodes.
● It serves as a starting point of the list and can simplify certain operations.
● The actual data nodes come after the header node.
● Helps in easier handling of empty lists or boundary cases.
Example:
Header -> Node1 -> Node2 -> Node3 -> NULL
Summary Table
Linked List Type Description Traversal Extra Memory Usage

Singly Linked List Nodes point to next node only One direction Low

Doubly Linked Nodes point to next and

Both directions Higher
List previous

Circular Linked
Last node points to head node Circular Same as singly/doubly
List

Header Linked Has a special header node at Simplifies Slightly higher due to
List start management header

Circularly Linked List

A Circularly Linked List is a variation of a linked list where the last node points back to
the first node, forming a circle. This means the list has no NULL or None at the end — you
can keep traversing the list indefinitely by following the next pointers.

Types of Circularly Linked Lists

1. Singly Circular Linked List
o Each node points to the next node.
o The last node’s next pointer points back to the head node.
o Traversal can start at any node and continue until you reach that node again.
2. Doubly Circular Linked List
o Each node has pointers to both next and previous nodes.
o The last node’s next points to the head, and the head’s previous points to the
last node.
o Allows traversal in both directions in a circular manner.

RepresentatION
Head -> Node1 -> Node2 -> Node3 --\
^ |
|------------------------------|Advantages of Circularly Linked List

● Efficient for applications requiring cyclic traversal, like:

o Round-robin scheduling
o Multiplayer games where players take turns in cycles
o Buffer management
● Can easily start traversal at any node, not necessarily the head.
● No special case needed for the end of the list.
Operations

Operation Description Time Complexity

Traversal Visit nodes until back to the start node O(n)
Insertion Add node at beginning, end, or any position O(1) to O(n)
Deletion Remove node by value or position O(n)
Searching Find a node with a given value O(n)

Summary

● Circularly linked lists form a continuous loop.

● Useful where wrap-around or repeated cycling through elements is needed.
● Slightly more complex than linear lists but very powerful in certain contexts.

Doubly Linked List

A Doubly Linked List is a type of linked list where each node contains:
● Data: The value stored in the node.
● Next Pointer: A reference to the next node in the sequence.
● Previous Pointer: A reference to the previous node.
This allows traversal of the list in both directions — forward and backward.

Node Structure:
+---------+---------+---------+
| Previous| Data | Next |

● Previous points to the previous node.

● Next points to the next node.
● The head node’s previous pointer is NULL.
● The tail node’s next pointer is NULL.

Advantages of Doubly Linked List

● Two-way traversal: Can easily move forwards and backwards.

● Easier deletion: Can delete a node without traversing from the head (if you have a
pointer to the node).
● More flexible insertion: Insertions before or after a node are straightforward.
Operations on Doubly Linked List
Operation Description Time Complexity

Traversal Visit nodes forward or backward O(n)

O(1) if position known;

Insertion Add a new node at beginning, end, or middle
O(n) otherwise

Deletion Remove a node by value or position O(1) if node known; O(n) to

search

Searching Find a node with a given value O(n)