CP25C01 Advanced Data Structures and Algorithms

Data Structure
The data structure can be defined as the collection of elements and all the possible operations
which are required for those set of elements.
Data Structure and Algorithm
Data structures manage how data is stored and accessed, while Algorithms focus on processing
this data. Examples of data structures are Array, Linked List, Tree and Heap, and examples of
algorithms are Binary Search, Quick Sort and Merge Sort.

UNIT -1
Linear Data Structures and Memory Optimization
 Array
An array is a linear data structure and it is a collection of element of same data type stored
at contiguous memory locations.

Key Features

1. Fixed size (cannot be changed after declaration in static arrays).

2. Elements stored in continuous memory blocks.
3. Efficient access using index (O(1) time).
4. Supports traversal, insertion (at index), deletion (shifting elements).

Types of Arrays

 One-Dimensional Array → Linear collection (like a list).

 Two-Dimensional Array → Matrix form (rows and columns).
 Multi-Dimensional Array → More than two dimensions (e.g., 3D arrays).

1
 Sparse arrays
 A sparse array or sparse matrix is an array in which most of the elements are zero.
 A Sparse Array is an optimized way of storing large arrays with many zero values by
saving only non-zero values and their positions.
Characteristics of Sparse array
 Sparse matrices are those array that has the majority of their elements equal to zero.
 A sparse array is an array in which elements do not have contiguous indexes starting
at zero.
 Sparse arrays are used over arrays when there are lesser non-zero elements
Representation of Sparse Array
Sparse arrays can be represented in two ways:
a) Array Representation
b) Linked List Representation
1. Array Representation
To represent a sparse array 2-D array is used with three rows namely: Row, Column, and
Value.
Row: Index of the row where non-zero elements are present.
Column: Index of the column where the non-zero element is present.
Value: The non-zero value which is present in (Row, Column) index.

2. Linked List Representation

To represent a sparse array using linked lists, each node has four fields namely: Row,
Column, Value, and Next node.
Row: Index of the row where non-zero elements are present.
Column: Index of the column where the non-zero element is present.
Value: The non-zero value which is present in (Row, Column) index.
Next node: It stores the address of the next node.

Advantages

1. Memory Efficient
2. Faster Access for Non-Zero Elements

2
 3. Useful in matrices with lots of zeros

Disadvantages

1. Overhead for Index Storage

2. Not good for Dense Arrays

Applications

 Graph Representations
 Image Compression
 Machine Learning
 Scientific Computation

 Dynamic arrays

A Dynamic Array is a resizable array that can grow or shrink in size during runtime, unlike
a static array (fixed size). Dynamic Arrays = Resizable arrays that maintain random access
while supporting automatic expansion/shrinking.

 It provides random access like normal arrays.

 The array automatically resizes itself when capacity is exceeded.

Operation Complexity
Access (indexing) O(1)
Insertion (end) Amortized O(1)
Insertion (middle) O(n)
Deletion (end) O(1)
Deletion (middle) O(n)

Key Characteristics
 Resizable Capacity
 Random Access

3
  Contiguous Memory Management
 Memory Management

Advantages

 Flexible size (no need to know array size beforehand).

 Efficient for random access.
 Useful for implementing higher-level structures.

Disadvantages

 Resizing requires copying elements (can be costly).

 Memory overhead (extra allocated space).
 Not cache-friendly when resized frequently.

Example

 Java
 C++
 Python
 Java Script

 Cache-aware structures

 Modern CPUs have cache memory (L1, L2, and L3) between the processor and
main memory (RAM).
 A Cache-Aware data structure is designed to take advantage of cache locality
(how data is laid out in memory) to reduce cache misses and improve performance.
 Cache memory is small, high-speed memory that stores frequently used data and
instructions for quick retrieval by the CPU, significantly improving system
performance by reducing the need to access slower RAM.

Key Concepts

1. Spatial Locality
2. Temporal Locality
3. Cache Line

Levels of Cache Memory

 L1 Cache: The smallest and fastest cache, located directly on the CPU core.

 L2 Cache: Larger and slightly slower than L1, it can be integrated into the
CPU or sit close to it.

 L3 Cache: The largest and slowest of the CPU caches, shared across multiple
4
 processor cores.

Key Characteristics

 Speed: Significantly faster than main memory (RAM).

 Size: Much smaller than RAM due to its higher cost.

 Volatility: Like RAM, cache memory is volatile, meaning it loses its contents
when the power is turned off.

 Technology: It is typically built using Static Random Access Memory (SRAM).

Techniques for creating cache-aware structures

 Contiguous memory allocation

 Field reordering
 Structure splitting (Hot/Cold splitting)
 Clustering
 Loop blocking
 Cache-conscious allocation
 Space-filling curves

Examples of Cache-Aware Data Structures

1. B-Trees (and Variants: B+ Trees, B Trees)*

2. Cache-Aware Arrays
3. Blocked / Tiled Matrices
4. Van Emde Boas (vEB) Layout for Trees

Advantages

 High performance due to reduced cache misses.

 Better use of CPU hierarchy.
 Essential in large-scale computing (databases, graphics, machine learning).

Disadvantages
5
  Implementation can be complex (requires tuning to cache line size).
 May be architecture-dependent (different CPUs have different cache sizes).

Applications

 Databases
 Operating Systems
 Scientific Computing
 Big Data / Machine Learning

 Linked lists

 A linked list is a linear data structure where elements, called nodes, are connected
using pointers. Each node contains:

 Data: The value stored in the node.

 Next (or Prev): A pointer/reference to the next node (or previous node in some
types).

 Unlike arrays, linked lists do not store elements in contiguous memory, which
allows dynamic memory allocation and easy insertion/deletion.

There are different types of linked lists. They are

1. Singly Linked List

2. Doubly Linked list

3. Circular Linked List

4. Circular Doubly Linked List

5. Skip List

6. Unrolled List

7. XOR linked List

6
Operation Description
Traversal Visit each node from head to tail.
Insertion Add a node at the beginning, end, or a specific position.
Deletion Remove a node from the beginning, end, or a specific position.
Search Find a node with a specific value.
Update Modify the value of a node.

Advantages

 Dynamic size (memory efficient).

 Easy insertion and deletion.
 No memory wastage (unlike arrays with unused space).

Disadvantages

 Extra memory for pointers.

 Random access is not allowed (must traverse from head).
 Slightly slower due to pointer traversal.

Applications of Linked List

 Polynomial ADT
 Radix Sort
 Multilist

 Skip lists

 A skip list is a probabilistic data structure that allows fast search, insertion, and
deletion operations, similar to a balanced binary search tree (BST), but easier to
implement.
 It is essentially a layered linked list where higher layers act as "express lanes" to skip
multiple elements, improving search efficiency.

Structure

 Consists of multiple levels of linked lists.

 Level 0 is the base linked list containing all elements in sorted order.
 Higher levels contain a subset of elements from lower levels, allowing faster
traversal.
 Each node has forward pointers for each level it participates in.

Operations

 Average Case
 Search-Insert-Delete – O(log n)
 Worst Case
7
  Search-Insert-Delete – O(n)

Advantages

 Simpler than balanced BSTs (like AVL or Red-Black trees).

 Efficient: O(log n) average time complexity.
 Supports dynamic data (insertion/deletion easy).

Disadvantages

 Extra memory for multiple pointers per node.

 Worst-case time complexity O(n) (though extremely rare).
 Performance depends on the randomness of level assignment.

Applications

 Databases (Redis)
 Concurrent data structure
 Memory Key Value Store
 Indexing system

 Unrolled linked lists

 An Unrolled Linked List (ULL) is a variation of a linked list where each node
stores an array of elements instead of a single element.
 This reduces pointer overhead and improves cache performance, making it more
efficient for large datasets.

Structure

 Each node contains:

1. An array of elements (say of size B).
2. Count of actual elements stored.
3. Pointer to the next node.
 Nodes are partially filled (usually between 50%-100% of capacity) to allow efficient
insertions/deletions.

Key Characteristics

 Node Structure
8
  Cache Performance
 Memory Overhead

Operations

 Insertion/Deletion
 Traversal
 Searching

Advantages

 Reduces memory overhead (fewer pointers).

 Better cache performance than standard linked lists.
 Efficient for large lists and sequential access.

Node structure example

Disadvantages

 Slightly more complex insertion/deletion logic.

 Fixed block size may waste memory if not well-tuned.
 Random access is still slower than arrays.

 XOR linked lists

 In an XOR linked list, each node stores only one pointer (npx) which is the
XOR (exclusive OR) of the addresses of the previous and next nodes.
 This saves memory since only one pointer is stored instead of two.

XOR List Representation of doubly linked list

9
Types of XOR Linked List
There are two main types of XOR Linked List:
 Singly Linked XOR List: A singly XOR linked list is a variation of the XOR linked
list that uses the XOR operation to store the memory address of the next node in a
singly linked list.
 Doubly Linked XOR List: A doubly XOR linked list is a variation of the XOR linked
list that uses the XOR operation to store the memory addresses of
the next and previous nodes in a doubly linked list.
Traversal in XOR linked list
Two types of traversal are possible in XOR linked list.
 Forward Traversal
 Backward Traversal:
Forward Traversal in XOR linked list
address of next Node = (address of prev Node) ^ (both)

Backward Traversal in XOR linked list

address of previous Node = (address of next Node) ^ (both)

Operations

 Insertion
 Deletion
 Traversal

Time complexity (similar to doubly linked list):

 Traversal: O(n)
 Insertion/Deletion: O(1)

10
Advantages

 Memory-efficient
 Saves space in memory-constrained environments.

Disadvantages

 Debugging is very hard

 Random access is difficult
 Not supported in high-level languages like Java/Python easily

 Stacks

 A stack in data structure is a linear data structure that follows the LIFO (Last In,
First Out) principle.
 This means the last element inserted (pushed) into the stack is the first one to be
removed (popped).
 In which both insertion and deletion occur at only one end of the list called the Top.

Key Features

1. Order: LIFO (Last In, First Out).

2. Operations:
o Push → Insert an element on top of the stack.
o top=top+1
o Pop → Remove the top element.
o top=top-1
o Peek/Top → View the top element without removing it.
o isEmpty() → Check if the stack is empty.
o isFull() (in fixed-size stacks) → Check if the stack is full.

IMPLEMENTATION OF STACK
 Array implementation of Stack
 Linked list implementation of Stack
Array implementation of Stack
Push Operation
 It adds a new element to the stack.
 When implementing the push operation, overflow condition of a stack is to be
checked.
E.g.

11
Routine to check stack is FULL
int isFull(stack s)
{
if(Top>=Arraysize-1)
return(1);
}
Routine to Push an element on to stack
Void push(int x, stack s)
{
if(isFull((s))
Error(“Full Stack”);
else{
top=top+1;
s[top]=x;
}
}
ROUTINE TO DISPLAY THE ELEMENT OF THE STACK
void display(int s[])
{
printf("Display the elements in the stack");
for(i=top;i>=0;i--)
{
printf(" \n %d",s[i]);
}}
Pop Operation
 A Pop operation deletes the topmost elements from the stack.
 Underflow condition of a stack is to be checked.
Example

Routine to pop an element from the stack

Void pop(stack s)
{
If(IsEmpty(s))
Error(“Empty stack”)
Else{
x=s[top];
Top=top-1;
}
}
Int Is empty(stack s)

12
{
If(top==-1)
Return(1);
}
Routine to return top element of the stack (Peek)
Int topelement (stack s)
{
If(!IsEmpty(s))
Return s[top];
Else
Error(“Empty stack”);
Return 0;
}
Linked list implementation of Stack
 Dynamically created
 The list is a collection of nodes. Each node consists of two fields, data and next
pointer.
DECLARATION FOR LINKED LIST IMPLEMENTATION
struct node
{
int data;
struct node *link;
}

Routine to push an element on to stack

Void push(int x, stack s)
{
Stack temp;
Temp=malloc(Size of (struct node));
If(temp==NULL)
Error(“Out of space”);
else {
temp ->data=x;
temp ->next=top;
top=temp;
}
}
Routine to Pop
Void pop(stack s)
{
If(IsEmpty(s))
Printf(“stack is Empty”);
else {
temp= top;

13
 top= top->next;
free(temp)
}
}
Routine to test whether a stack is empty
Int IsEmpty(stack s)
{
If(s->next== NULL);
Return(1);
}
Application of Stack
 Balancing Symbol
 Function call
 Postfix Expression evaluation
 Infix to Postfix Conversion
INFIX NOTATION
For example: A+B
POSTFIX NOTATION
For example: AB +
PREFIX NOTATION
For example: +AB

Infix to Postfix Conversion

 ()
 ^
 *, /, %
 +, -

14
15
Postfix Expression Evaluation

16
 Queue

 A Queue in data structure is a linear data structure that follows the FIFO (First In,
First Out) principle.
 This means the first element inserted (enqueued) is the first one to be removed
(dequeued).

Key Features

1. Order: FIFO (First In, First Out).

2. Operations:
o Enqueue(x) → Insert element x at the rear.
o Dequeue() → Remove element from the front.
o Peek/Front() → View the front element without removing it.
o isEmpty() → Check if the queue is empty.
o isFull() → (for fixed-size queues).

Representation

 Array-based Queue
 Linked List-based Queue
 Circular Queue

17
Variants of Queue

1. Linear Queue
2. Circular Queue
3. Deque (Double-Ended Queue)
4. Priority Queue

Applications of Queue

1. CPU Scheduling
2. I/O Buffers
3. Breadth-First Search (BFS)
4. Resource management
5. Simulation systems

Array Implementation of Queue

Enqueue operation

 It is used to add a new element into a queue at the rear end.

18
Linked List Implementation of Queue

 Enqueue operation is performed at the end of the list.

 Dequeue operation is performed at the front of the list.

DECLARATION FOR LINKED LIST IMPLEMENTATION OF QUEUE ADT

Struct node
{
Int data;
Struct node*next;
}
Else{
rear→next= temp;
rear= rear→next; }
Insertion
Q getnode(Q*temp)
{
Temp= malloc(Size of(Q));
Temp→ next= NULL:
Return temp;
}
Void insert()
{
Q*temp;
temp= getnode(temp);
if(front == NULL;)
{
Front= temp;
Rear= temp;
}}
Deletion

19
 Priority queues

 A Priority Queue is a special type of queue in which each element is associated

with a priority, and elements are served based on their priority, not just the order of
insertion (FIFO).
 If two elements have the same priority, they are served according to their order of
arrival (like a normal queue).

Types of Priority Queues

1. Ascending Priority Queue → Smallest priority element is served first.

2. Descending Priority Queue → Largest priority element is served first.
3. Min-Priority Queue → The element with the minimum priority value is dequeued
first.
4. Max-Priority Queue → The element with the maximum priority value is dequeued
first.

20
Operations

1. Insert (Enqueue with Priority) → Add an element with an assigned priority.

2. Delete (Dequeue) → Remove the element with the highest (or lowest) priority.
3. Peek() → View the element with the highest (or lowest) priority.

Key Characteristics

 Priority Assignment
 FIFO for identical Priorities
 Priority based Deletion

Implementation Methods

1. Using Arrays/Linked Lists

2. Using Heaps (Binary Heap, Fibonacci Heap, etc.)

Applications of Priority Queues

1. CPU Scheduling
2. Dijkstra’s Algorithm / A Search* (shortest path in graphs).
3. Huffman Coding
4. Network Routers
5. Event-Driven Simulations

 Double-ended queues (Deque)

 A Deque (pronounced “deck”) is a type of queue in which insertion and deletion

can be performed at both ends (front and rear).
 It is a generalization of queues, combining the features of stacks and queues.

Types of Deque

1. Input-Restricted Deque
2. Output-Restricted Deque

Example

Operations in Deque

1. InsertFront(x)
2. InsertRear(x)

21
 3. DeleteFront()
4. DeleteRear()
5. PeekFront() / PeekRear()
6. isEmpty(), isFull()

Routine to insert an element at rear end

Void insert_rear(int x, DQueue DQ)

{
If(rear== Arraysize-1)
{
printf(“Queue overflow”);
}
else {
if(front== -1)
front= 0; rear= 0;
else {
rear= rear +1;
DQ[rear]= x;
}

22
Applications of Deque

1. Palindrome checking
2. Sliding Window problems
3. Job/Task scheduling
4. Undo/Redo operations
5. Deque-based Queue/Stack implementations

23
 Circular buffers

 A Circular Buffer (also called Ring Buffer or Circular Queue) is a fixed-size

buffer that treats memory as if it were connected end-to-end.
When the buffer reaches the end, it wraps around to the beginning (like a circle).
 It is mainly used in queues, where the rear and front indices wrap around the
array.

Key Features

1. Fixed Size
2. Wrap-around
3. Efficient Memory Use

Operations

1. Enqueue(x) → Add an element at the rear.

2. Dequeue() → Remove an element from the front.
3. isEmpty() → True if front = -1.
4. isFull() → True if (rear + 1) % size == front.
5. Peek() → Check the front element.

Example

Applications of Circular Buffers

1. CPU Scheduling
2. Streaming Data
3. I/O Buffers in Operating Systems.
4. Embedded Systems

24
Advantages of circular queue

It overcomes the problem of unutilized space in linear queues, when it is implemented as

arrays.

 Hashing

 Hashing is a technique used to map data of arbitrary size to fixed-size

values (called hash values or hash codes) using a hash function.
 It is mainly used in fast data retrieval in hash tables, dictionaries, and sets.

Key Properties of Hash Functions

 Fixed Output Size

 Efficiency
 Uniformity
 Collision Resistance

Applications of Hashing

1. Databases
2. Symbol Tables
3. Cryptography
4. Caching
5. Hash Tables
6. Data Integrity
7. Data Structure
8. File Systems

25
26
27
28
29
30
 Perfect hashing

 Perfect Hashing is a special kind of hashing technique where no collisions occur.

 Each key is mapped to a unique slot in the hash table.
 It guarantees that no two keys will hash to the same value.

Key Features

1. No collisions → Every key has a unique index.

2. O(1) Search time (worst case) → Unlike standard hashing
3. Usually constructed when the set of keys is fixed and known in advance (static set).

Types of Perfect Hashing

1. Minimal Perfect Hashing

o Ensure that the range of the hash function is equal to the number of keys.
o Maps n keys to exactly n slots.
o No unused slots in the hash table.
2. Non-Minimal Perfect Hashing
o The range may be larger than the number of keys.
o May use extra slots, but still ensures no collisions.

Example

Suppose we have keys: {10, 22, 37}

If table size = 3, and hash function = h(x) = (x mod 3)

 h(10) = 1
 h(22) = 1 ❌ Collision
So this is not perfect hashing.

Instead, if we choose h(x) = (x mod 7)

 h(10) = 3
 h(22) = 1
 h(37) = 2
 No collisions → Perfect Hashing.

Implementation Approaches

1. Static Perfect Hashing (FKS scheme – Fredman, Komlós, Szemerédi)

o Two-level hashing:
 First level distributes keys into buckets.
 Second level uses another hash function inside each bucket ensuring
no collisions.
2. Mathematical Hash Functions
o Designed carefully for small fixed sets (e.g., keywords in a programming
language).

31
Here, R = 7 and N = 5. The universal hash has unused buckets and collisions. The perfect
hash has no collisions, and the MPH has neither collisions nor unused buckets.

Applications of Perfect Hashing

1. Compilers
2. Databases
3. Networking
4. Embedded Systems

Advantage

 No collisions

Disadvantage

 Complex to construct.

 Cuckoo hashing

 Cuckoo Hashing is a collision resolution technique in hashing that uses two (or more)
hash functions and ensures O(1) lookup time in the worst case.
 It is named after the cuckoo bird, which lays its eggs in another bird’s nest, often
displacing the existing eggs. Similarly, in Cuckoo Hashing, when a collision occurs, the
existing key is kicked out and reinserted into another position using a different hash
function.

Key Idea

 Use two hash functions: h1(x) and h2(x).

 Each key can be placed in one of two possible locations.
 If the slot is already occupied, the existing key is "kicked out" (like a cuckoo chick)
and reinserted at its alternative location.

Operations

1. Insertion

2. Search

32
3. Deletion

Example

Hash table size = 7

Hash functions:

 h1(x) = x % 7
 h2(x) = (x / 7) % 7

Insert keys: 10, 20, 30

 Insert 10 → h1(10) = 3 → place at index 3.

 Insert 20 → h1(20) = 6 → place at index 6.
 Insert 30 → h1(30) = 2 → place at index 2.
 Insert 37 → h1(37) = 2 (collision with 30).
o Kick out 30 → reinsert at h2(30).
o 37 takes index 2, 30 moves to new slot.

Properties

 Lookup time = O (1) worst case.

 Insertion = O (1) average case.
 Space efficiency is better than chaining or open addressing.

Applications

1. Networking
2. Databases
3. Memory Systems
4. Real-time Systems

 Extendible hashing

Extendible Hashing is a dynamic hashing technique used in databases and file systems.
It solves the problem of bucket overflows in static hashing by allowing the hash table to grow
or shrink dynamically.

Key Concepts

1. Hash Function (h)

2. Directory
3. Buckets
4. Splitting

Main Features

33
  Directories: The directories store addresses of the buckets in pointers.
 Buckets: The buckets are used to hash the actual data.

Basic Working of Extendible Hashing

34
Limitations
 Size of every bucket is fixed.
 Memory is wasted in pointers when the global depth and local depth difference
becomes drastic.
 This method is complicated to code.

Advantages

 Dynamic growth (no overflow chains like in linear hashing).

 Efficient for large databases.
 Lookup is still O (1) average.

Disadvantages

 Directory can become large.

 More memory overhead than static hashing.

UNIT- 2
Advanced Tree Data Structures

 Balanced Trees

A balanced tree is a binary tree where the height difference between the left and right sub
trees of any node is kept within certain limits. This ensures the tree remains shallow, so
operations are efficient.

Properties of Balanced Trees

1. Height-balanced: Difference between left and right sub tree heights is minimized.
2. Efficient operations:
o Searching: O(log n)
o Insertion: O(log n)
o Deletion: O(log n)
3. Avoids skewed trees (like linked lists).

Advantages of Balanced Trees

 Faster searching, insertion, and deletion.

 Prevents degeneration into linked lists.
 Used in databases, memory indexing, and compilers.

Diagram: Balanced vs. Unbalanced Tree

Unbalanced BST: Balanced BST:

10 20
\ / \

35
 20 10 30
\ \
30 40

 AVL

An AVL Tree (named after inventors Adelson-Velsky and Landis, 1962) is a self-
balancing Binary Search Tree (BST) where the height difference (balance factor)
between the left and right subtrees of any node is at most

BalanceFactor(node)=height(leftSubtree)−height(rightSubtree)BalanceFactor(node) =
height(leftSubtree) -
height(rightSubtree)BalanceFactor(node)=height(leftSubtree)−height(rightSubtree)

Properties of AVL Tree

1. Balanced Height: Always maintains log(n) height.

2. Operations Complexity:
o Search: O(log n)
o Insertion: O(log n)
o Deletion: O(log n)
3. Height Constraint: Maximum height ≈ 1.44 × log₂(n+2) - 0.328

36
37
38
39
40
Applications of AVL Trees

 Databases (indexing, searching)

 Memory management
 Compilers
 Routing tables in networks
 Anywhere efficient ordered data retrieval is needed

 Red-Black Trees

 Red-Black Tree is a type of self-balancing binary search tree (BST).

 It ensures the tree remains approximately balanced by coloring each node either Red
or Black and enforcing a set of rules.
 This allows search, insertion, and deletion to be performed in O(log n) time.

Operations

1. Search → Same as BST (O(log n)).

2. Insertion → Insert as in BST, color new node Red, then fix violations using
rotations & recoloring.
3. Deletion → Replace and remove like BST, then fix balance with rotations &
recoloring.

Balancing (Fixing Violations)

When inserting or deleting, violations of RBT properties can occur. They are fixed by:

 Recoloring (Red ↔ Black)

 Rotations:
o Left Rotation
o Right Rotation
o Sometimes a combination (Left-Right / Right-Left).

Applications

 Used in C++ STL (map, set, multimap, multiset)

 Used in Java’s TreeMap & TreeSet
 Linux kernel uses RBTs for process scheduling & memory management
 Database indexing

 Splay Trees

A Splay Tree is a type of self-adjusting binary search tree (BST) in which recently
accessed elements are moved closer to the root by a process called splaying.

Key Idea

41
  After search, insertion, or deletion, the accessed node is splayed (rotated) to the
root.
 This makes future access to that node faster.
 Over time, frequently used elements stay near the top.

Operations in Splay Trees

1. Search(x)
o Search like BST.
o If found (or last accessed node if not found), splay it to the root.
2. Insert(x)
o Insert as in BST.
o Then splay the inserted node to the root.
3. Delete(x)
o Search & splay x to the root.
o Remove root.
o Join left and right subtrees by splaying the largest node of the left subtree and
attaching the right subtree.

Splaying (Rotation Cases)

There are 3 main cases when bringing a node up:

1. Zig (Single Rotation)

o Node is child of root.
o Perform one rotation.
2. Zig-Zig (Double Rotation, Same Side)
o Node & parent are both left children or both right children.
o Perform two rotations in the same direction.
3. Zig-Zag (Double Rotation, Opposite Sides)
o Node is left child of a right parent or right child of a left parent.
o Perform two rotations in opposite directions.

Applications

 Cache implementations (recently used elements at top).

 Memory management (garbage collectors).
 Data compression (adaptive Huffman coding).
 Network routing (frequently accessed nodes kept near root).

 Treaps

A Treap is a randomized balanced binary search tree (BST).

It combines properties of:

 Binary Search Tree (BST) → ordered by keys.

 Heap (usually Max-Heap or Min-Heap) → ordered by priority.

42
Each node stores:

1. Key → follows BST property.

2. Priority (randomly assigned) → follows Heap property.

Properties

1. BST property (by key):

o Left child’s key < parent’s key < right child’s key.
2. Heap property (by priority):
o Parent’s priority > child’s priority (for max-heap).

Operations in Treap

1. Insertion(key, priority)
o Insert node as in BST (by key).
o Assign a random priority.
o If heap property is violated, rotate to fix.
2. Deletion(key)
o Search key like BST.
o Rotate down the node until it becomes a leaf (maintaining heap property).
o Delete it.
3. Search(key)
o Same as BST search.

Rotations in Treap

 Right Rotation (fix left child priority higher than parent).

 Left Rotation (fix right child priority higher than parent).

Applications

 Randomized BSTs in practice.

 Databases (indexing).
 Memory allocators.
 Probabilistic data structures.

 Multi-way Trees

Multi-way Tree (also called an m-ary tree) is a tree in which each node can have more
than two children (unlike a binary tree).

If each node can have at most m children, it is called an m-way tree.

 Binary Tree → Special case of m-way tree (m = 2).

 Used widely in databases and file systems for indexing and efficient searching.

43
 B-Trees

 B-Tree is a self-balancing multi-way search tree designed for disk-based storage

(like databases and file systems).
 It maintains data in sorted order and allows search, insertion, deletion, and
sequential access in O(log n) time.
 It generalizes binary search trees by allowing multiple keys per node and multiple
children.

Properties of B-Trees

1. A node can have many children (not just 2 like BST).

2. All leaf nodes are at the same level (balanced).
3. Each node contains multiple keys (sorted in ascending order).
4. If a node has k keys, it has k+1 children.
5. Every node (except root) must be at least half full.
6. Root can have a minimum of 2 children (unless it is a leaf).

Operations

1. Search(x) → Works like binary search within nodes.

2. Insert(x) → Insert in sorted order.
o If node overflows (> m–1 keys), split the node and promote the middle key.
3. Delete(x) → If removing causes underflow (< ⌈m/2⌉ keys), borrow from sibling or
merge nodes.

Complexity

 Height of B-Tree = O(logₘ n), where m = order (branching factor).

 Search, Insert, Delete = O(log n).
 Very efficient for disk access because one node can hold hundreds/thousands of keys
(reduces height).

Applications

 Databases (MySQL, Oracle, PostgreSQL use B-Trees for indexing).

 File Systems (NTFS, ext4, HFS+ use B+ Trees, a variant).
 Search Engines (for indexing documents).

Difference: B-Tree vs B+ Tree

 B-Tree → Data stored in both internal & leaf nodes.

 B+ Tree → Data only in leaf nodes; internal nodes store keys for indexing.
 B+ Tree is more efficient for range queries.

Advantages of B-Trees
 B-Trees are self-balancing.
 High-concurrency and high-throughput.
 Efficient storage utilization.

44
Disadvantages of B-Trees
 B-Trees are based on disk-based data structures and can have a high disk usage.
 Not the best for all cases.

 B+ Trees
B+ Tree is an advanced data structure used in database systems and file systems to
maintain sorted data for fast retrieval, especially from disk. It is an extended version of the B
Tree, where all actual data is stored only in the leaf nodes, while internal nodes contain only
keys for navigation.
Components of B+ Tree
 Leaf nodes store all the key values and pointers to the actual data.
 Internal nodes store only the keys that guide searches.
 All leaf nodes are linked together, supporting efficient sequential and range queries.
Features of B+ Trees
 Balanced
 Multi-level
 Ordered
 High Fan-out
 Cache-friendly
 Disk-efficient
Difference between B+ Tree and B Tree
Parameters B+ Tree B Tree

Separate leaf nodes for data

Nodes store both keys and data
Structure storage and internal nodes for
values
indexing

Leaf nodes form a linked list for Leaf nodes do not form a linked
Leaf Nodes
efficient range-based queries list

Order Higher order (more keys) Lower order (fewer keys)

Key Typically allows key duplication Usually does not allow key
Duplication in leaf nodes duplication

Better disk access due to

More disk I/O due to non-
Disk Access sequential reads in a linked list
sequential reads in internal nodes
structure

Database systems, file systems, In-memory data structures,

Applications
where range queries are common databases, general-purpose use

Better performance for range Balanced performance for search,

Performance
queries and bulk data retrieval insert, and delete operations

45
Parameters B+ Tree B Tree

Memory Requires more memory for Requires less memory as keys and
Usage internal nodes values are stored in the same node

Advantages of B+Trees
 Data stored in a B+ tree can be accessed both sequentially and directly.
 It takes an equal number of disk accesses to fetch records.
 B+trees have redundant search keys, and storing search keys repeatedly is not
possible.
Disadvantages of B+ Trees
 Slower exact match
 More disk access
 Complex updates
 Extra space

 R-Trees
 R-tree is a tree data structure used for storing spatial data indexes in an efficient
manner. R-trees are highly useful for spatial data queries and storage.
 An R-Tree (Rectangle Tree) is a balanced multi-way search tree designed for
indexing multi-dimensional data like:

 Geometric objects (points, rectangles, polygons)

 Spatial data (maps, GPS data, 3D models)

Key Idea

 Instead of single values, nodes in an R-Tree store bounding rectangles.

 Each bounding rectangle covers the spatial area of its children.
 Searching involves checking which rectangles overlap with the query region.

Properties of R-Trees

1. Balanced structure → all leaf nodes are at the same level.

2. Each node contains between m and M entries (like B-Trees).
o M = maximum number of entries.
o m = minimum number (usually M/2).
3. Internal nodes contain minimum bounding rectangles (MBRs) that enclose their
children.
4. Leaf nodes contain actual data entries or pointers to objects with their bounding
boxes.

Variants of R-Tree

 R+ Tree → avoids overlapping MBRs (by splitting).

 R Tree* → optimized insertion, reduces overlap, widely used in practice.

Applications of R-Trees

46
  Geographic Information Systems (GIS) 🌍 (maps, GPS, spatial queries).
 Databases (spatial indexes in PostgreSQL, Oracle Spatial).
 Computer Graphics & CAD (collision detection, object representation).
 Networking (location-based services, nearest server lookup).

 Segment Trees

 A Segment Tree is a binary tree data structure used for storing information about
intervals (segments) or ranges.
 It allows efficient range queries and range updates (like sum, minimum, maximum,
gcd, etc.) in O(log n) time.

Structure of Segment Tree

 Built as a binary tree where:

o Leaf nodes → individual elements of the array.
o Internal nodes → store results (sum/min/max) for the range covered by that
node. For an array of size n:

 Segment tree size ≈ 4n nodes.

 Height = O(log n).

Example

Array = [2, 5, 1, 4, 9, 3]

Segment Tree for sum queries:

[24]
/ \
[8] [16]
/ \ / \
[7] [1] [13] [3]
/ \ /\ / \ / \
[2] [5] [1] [4] [9] [4] [9] [3]

 Root [24] = sum(2+5+1+4+9+3).

 Left child [8] = sum(2+5+1).
 Right child [16] = sum(4+9+3).

Operations

1. Build Tree → O(n)

2. Query(l, r) → O(log n)
o Recursively check which nodes overlap with [l, r].
3. Update(index, value) → O(log n)
o Update leaf and recalculate ancestors.

Variants

47
  Lazy Propagation → Handles range updates efficiently.
 Dynamic Segment Tree → For large/unbounded ranges.
 2D Segment Trees → For queries on 2D grids (matrices).

Applications

 Range queries in arrays (sum, min, max).

 Competitive programming & coding interviews.
 Interval problems (overlapping intervals).
 Computational geometry (finding intersections, ranges).
 Image processing (histograms, segment stats).

Advantages
 Efficient querying
 Efficient updates
 Flexibility
Disadvantages
 Complexity
 Time complexity

 Fenwick Trees
A Fenwick Tree, also called a Binary Indexed Tree (BIT), is a data structure that
provides:

 Efficient prefix sum queries.

 Efficient updates to elements.

It is an alternative to Segment Trees but is often simpler and uses less memory (O(n)).

Key Idea

 Store cumulative sums of ranges of powers of two.

 Each index in the BIT array covers a certain range of the original array.
 Uses bit manipulation (i & -i) to navigate parent/child relationships.

Operations

For an array arr[1…n], Fenwick Tree supports:

1. Update(index, value) → Add value to arr[index].

o Propagates changes up the tree.
o Time: O(log n)
2. Prefix Sum(index) → Returns sum of arr[1] … arr[index].
o Traverse BIT by reducing index.
o Time: O(log n)
3. Range Sum(l, r) → PrefixSum(r) – PrefixSum(l-1)

Example

Array: [2, 1, 3, 2, 1, 4, 5]

48
Fenwick Tree Representation (BIT):

Index: 1 2 3 4 5 6 7
BIT[]: 2 3 3 8 1 5 5

 BIT[1] = arr[1] = 2
 BIT[2] = arr[1] + arr[2] = 3
 BIT[4] = arr[1] + arr[2] + arr[3] + arr[4] = 8
 And so on...

Complexity

 Build Tree → O(n log n) (or O(n) with optimization).

 Query → O(log n).
 Update → O(log n).
 Space → O(n).

Applications

 Range sum queries in arrays.

 Frequency counting (prefix counts).
 Inversion counting in an array.
 Competitive programming (BIT is often preferred over Segment Tree when memory
matters).
 Used in dynamic cumulative frequency tables.

Segment Tree vs Fenwick Tree

Feature Segment Tree Fenwick Tree
Memory O(4n) O(n)
Complexity O(log n) O(log n)
Implementation More complex Simple & compact
Operations More flexible (range updates, min, max, Mostly prefix sums & point
supported gcd) updates

 Suffix Trees and Tries for string processing

Tries (Prefix Trees)

 A Trie is a tree-like data structure that stores strings by their prefixes.

 Each edge represents a character, and a path from the root to a node represents a
prefix of one or more strings.

Structure

 Root node: Represents the empty string.

 Edges: Labeled with characters.
 Each path: Represents a prefix.
 End-of-word markers: Indicate complete words.

49
Operations

 Insert(word)
 Search (word)
 Prefix search

Applications

 Autocomplete systems.
 Spell checking.
 Prefix-based searching.
 IP routing (longest prefix match).
 Efficient dictionary representation.

Complexity

 Insertion: O (m) O (m) O (m) (where mmm = length of word).

 Search: O (m) O (m) O (m).
 Space: High (can be optimized with compressed tries or ternary search trees).

Suffix Trees

A Suffix Tree is a compressed trie that stores all suffixes of a string.

It provides efficient solutions for many string-processing problems.

Structure

 Built from all suffixes of a string.

 Each path from root to leaf represents a suffix.
 Compression: Consecutive edges with single-child are merged into one edge (labeled
with a substring instead of a single character).

Example for string "banana$" (with $ as unique terminator):

 Suffixes: "banana$", "anana$", "nana$", "ana$", "na$", "a$", "$".

 Suffix tree will contain all of them, but compressed to save space.

Applications

 Fast pattern matching: Check if a substring exists in O(m)O(m)O(m).

 Longest repeated substring.
 Longest common substring (between two strings).
 Substring frequency analysis.
 Plagiarism detection.
 Bioinformatics: DNA sequence analysis.

Complexity

 Construction (Ukkonen’s algorithm): O(n)O(n)O(n).

 Search: O(m)O(m)O(m).

50
  Space: O(n)O(n)O(n), but large constant factors (often 10–20× input size).

Key Differences: Trie vs. Suffix Tree

Feature Trie (Prefix Tree) Suffix Tree
Stores Words / prefixes All suffixes of a string
Usage Autocomplete, dictionaries Substring problems, pattern matching
Compression Not always (unless radix tree) Always compressed

Space Higher (but per inserted word) Higher (proportional to input string length)

Time complexity Insert/Search: O(m)O(m)O(m) Search substring: O(m)O(m)O(m)

Construction Simple More complex (e.g., Ukkonen’s algorithm)

 Applications in indexing
Indexing with Tries

A Trie is essentially a natural indexing structure for strings because it organizes data based
on prefixes.

Applications in Indexing

1. Dictionary / Word Indexing

o Stores words in a way that allows fast lookup.
o Example: Autocomplete in search engines.
2. Prefix Indexing
o Quickly retrieve all words starting with a given prefix.
o Example: Type "ban" → get "banana", "band", "bank".
3. IP Routing Indexing (Longest Prefix Match)
o Tries (Patricia tries, radix trees) are used to index IP addresses for efficient
routing.
4. Text Indexing
o Index words for fast search in documents.
o Each node can hold references to documents where the prefix appears.

Indexing with Suffix Trees

A Suffix Tree indexes all suffixes of a string, making it a powerful indexing tool for
substring problems.

Applications in Indexing

1. Full-text Indexing
o Allows substring queries in O(m)O(m)O(m) time (where mmm is query
length).
o Used in search engines and text editors.
2. Pattern Matching Index
o Efficiently checks if a pattern exists in the text.

51
 o Example: Find if "ana" occurs in "banana".
3. Substring Frequency Index
o Can count occurrences of a substring quickly.
o Useful in analytics (e.g., keyword frequency).
4. Bioinformatics Indexing
o DNA/protein sequences are long strings.
o Suffix trees help index them for fast pattern matching (e.g., finding gene
sequences).
5. Plagiarism Detection Index
o Detects longest common substrings across documents.

 Text retrieval

 Text retrieval is the process of storing, indexing, and searching text efficiently.
 It’s a core area of Information Retrieval (IR) – finding relevant documents/strings
based on queries.

Data Structures for Text Retrieval

1. Tries (Prefix Trees)

 Used for dictionary-style retrieval.

 Fast lookups of words and prefixes.
 Applications:
o Autocomplete
o Spell check
o Prefix-based document retrieval

2. Suffix Trees

 Index all suffixes of a string.

 Allow efficient substring queries.
 Applications:
o Substring search (find if "ana" is in "banana")
o Longest repeated substring
o Text analytics
o Bioinformatics sequence retrieval

3. Suffix Arrays

 Space-efficient alternative to suffix trees.

 Stores sorted suffixes of a string.
 Supports substring search with binary search.
 Applications:
o Full-text search engines
o Genome sequence indexing

4. Inverted Index

52
  Fundamental structure in search engines.
 Maps each word → list of documents containing it.
 Example:
 "banana" → [Doc1, Doc5]
 "apple" → [Doc2, Doc3, Doc4]
 Applications:
o Google search
o Document retrieval
o Keyword queries

5. B-Trees / B+ Trees

 Used in databases for indexing large text files.

 Balanced search tree structure ensures fast lookups.
 Applications:
o File systems
o Database text retrieval

6. Hashing

 Hash tables store words with their document references.

 Fast exact match retrieval, but not efficient for substring/prefix queries.
 Example: Dictionary lookups.

Applications of Text Retrieval

 Search Engines (Google, Bing) – inverted index + ranking.

 Plagiarism Detection – suffix trees/arrays.
 Bioinformatics – DNA/protein sequence matching.
 Databases – B-tree indexing for text fields.
 Natural Language Processing (NLP) – keyword extraction, corpus search.

 Computational geometry

 Computational Geometry is the study of algorithms and data structures for solving
geometric problems involving points, lines, polygons, and shapes.
 It’s widely used in graphics, robotics, GIS, CAD, gaming, and computer vision.

Key Problems in Computational Geometry

1. Point Location
2. Convex Hull
3. Range Searching
4. Nearest Neighbor Search
5. Intersection Problems
6. Triangulation

Data Structures Used in Computational Geometry

53
1. Segment Tree

 Stores intervals/segments.
 Used for:
o Line segment intersection detection.
o Range queries (e.g., how many lines overlap at a point).

2. Interval Tree

 Specialized for storing intervals.

 Queries: find all intervals overlapping with a point or another interval.
 Applications: scheduling, graphics clipping.

3. Range Trees

 Used for orthogonal range searching in 2D or higher.

 Example: Given points in a plane, find all points inside a rectangle.
 Applications: GIS (Geographic Information Systems).

4. k-d Tree (k-dimensional tree)

 Binary tree for points in k-dimensional space.

 Efficient for:
o Nearest neighbor search.
o Range searching.
 Applications: AI pathfinding, machine learning, graphics.

5. Quad Trees

 Recursive partitioning of 2D space into quadrants.

 Applications:
o Image representation.
o Spatial indexing (GIS, maps).
o Collision detection in games.

6. R-Trees

 Balanced tree for spatial indexing.

 Stores rectangles bounding geometric objects.
 Applications:
o Databases
o GIS systems
o Spatial queries (e.g., "find all restaurants within 5 km").

7. Voronoi Diagrams & Delaunay Triangulation

 Not exactly trees, but key computational geometry structures.

 Voronoi: partitions space into regions closest to a given set of points.
 Delaunay Triangulation: dual structure of Voronoi, used in mesh generation.

54
Applications of Computational Geometry

 Computer Graphics (rendering, mesh generation).

 Robotics (motion planning, collision detection).
 GIS & Mapping (nearest city, range queries).
 Gaming (spatial partitioning, physics engines).
 Machine Learning (clustering, nearest neighbor search).
 VLSI Design (circuit layout, intersection detection).

UNIT – 3
Graph Data Structures and Algorithms
 Representation: Adjacency list/matrix

Adjacency Matrix
An Adjacency Matrix is a 2D array (matrix) used to represent a graph.

 Size: V×VV \times VV×V, where VVV = number of vertices.

 Entry A[i][j]A[i][j]A[i][j]:
o 1 (or weight w) → if edge exists from vertex iii to jjj.
o 0 → if no edge exists.

Example (Undirected graph with vertices A, B, C, D)

Edges: A–B, A–C, B–D

A B C D
A[0 1 1 0]
B[1 0 0 1]
C[1 0 0 0]
D[0 1 0 0]

Best for

 Dense graphs (many edges).

 When quick edge existence queries are needed.
 Weighted graphs (matrix can store weights).

Adjacency List

An Adjacency List represents a graph as an array/list of lists.

 Each vertex stores a list of its neighbors.

 More space-efficient for sparse graphs.

Example (Same graph)

A → [B, C]

55
B → [A, D]
C → [A]
D → [B]

Best for

 Sparse graphs (few edges).

 When we need to traverse neighbors often (like in DFS/BFS).

In Algorithms

 BFS / DFS → usually use Adjacency List (efficient traversal).

 Dijkstra / Prim (with heaps) → works better with Adjacency List.
 Floyd–Warshall → needs Adjacency Matrix.
 Graph density check:
o If E≈V2E \approx V^2E≈V2 → Matrix is better.
o If E≪V2E \ll V^2E≪V2 → List is better.

 Incidence matrix
An Incidence Matrix is a way of representing a graph using a matrix of size V×EV \times
EV×E, where:

 VVV = number of vertices

 EEE = number of edges

Each row corresponds to a vertex and each column corresponds to an edge.

Rules

1. Undirected Graph:
o If edge eje_jej connects vertex viv_ivi, then:
 M[i][j]=1M[i][j] = 1M[i][j]=1 if viv_ivi is incident to eje_jej.
 Otherwise, M[i][j]=0M[i][j] = 0M[i][j]=0.
o Each column has exactly two 1’s (since each edge connects two vertices).
2. Directed Graph:
o If edge eje_jej goes from vertex viv_ivi: M[i][j]=−1M[i][j] = -1M[i][j]=−1.
o If edge eje_jej goes to vertex vkv_kvk: M[k][j]=+1M[k][j] = +1M[k][j]=+1.
o Otherwise: 000.
o Each column has one -1 and one +1.

Example 1: Undirected Graph

Vertices: A, B, C
Edges: e1 = (A, B), e2 = (B, C), e3 = (A, C)

Incidence Matrix:

e1 e2 e3
A →[1 0 1]

56
B →[1 1 0]
C →[0 1 1]
Example 2: Directed Graph

Vertices: A, B, C
Edges: e1 = A → B, e2 = B → C, e3 = C → A

Incidence Matrix:

e1 e2 e3
A → [ -1 0 1 ]
B → [ 1 -1 0 ]
C → [ 0 1 -1 ]
Properties

 Size: V×EV \times EV×E.

 Space: Larger than adjacency list, smaller than adjacency matrix in some cases.
 Edge existence: Easy (look at column).
 Vertex degree: Sum of row entries gives degree of a vertex.

Applications in Algorithms

 Graph theory proofs (algebraic graph theory).

 Network flow problems (incidence matrix helps in flow conservation equations).
 Cycle detection (linear algebra methods on incidence matrix).
 Electrical circuits (Kirchhoff’s laws use incidence matrices).
 Optimization problems (linear programming formulations for graphs).

 Compressed storage

 Compressed storage refers to representation techniques that reduce memory usage

while still supporting efficient algorithmic operations (like searching, traversal, or
processing).
 It is especially important for large datasets, graphs, matrices, and strings.

Compressed Storage in Common Data Structures

1. Compressed Sparse Row (CSR) / Compressed Sparse Column (CSC)

 Used in sparse matrices (where most elements are 0).

 Instead of storing all V2V^2V2 entries, only store nonzero values and their positions.

Example (CSR format):

 Arrays:
o val[] → stores nonzero values
o col[] → stores column indices
o row_ptr[] → marks starting index of each row

57
✅ Applications: Graph algorithms (adjacency matrix compression), scientific computing.

2. Compressed Tries (Radix Trees / Patricia Tries)

 Standard tries use a lot of memory for storing characters.

 Compressed tries merge chains of single-child nodes into one edge with a substring
label.

✅ Applications: String processing, IP routing, dictionaries.

3. Run-Length Encoding (RLE)

 Stores repeated sequences as (value, count).

 Example: aaaaabbbcc → (a,5)(b,3)(c,2).

✅ Applications: Image compression (TIFF, BMP), text compression.

4. Dictionary-based Compression (LZ77, LZW)

 Build a dictionary of repeated patterns.

 Store references instead of full text.

✅ Applications: File compression (ZIP, GIF, PNG).

5. Huffman Coding (Variable-Length Encoding)

 Assign shorter codes to frequent symbols, longer codes to rare ones.

 Reduces average storage size.

✅ Applications: JPEG, MP3, text compression.

6. Compressed Graph Representations

 Adjacency list is already compressed vs adjacency matrix.

 CSR/CSC formats used in graph algorithms.
 Web graphs & social networks → use compressed structures (like gap encoding,
Elias gamma coding).

✅ Applications: Web crawlers, social network analysis.

7. Suffix Arrays with Compression

 Suffix trees are large (10–20× input size).

 Compressed suffix arrays (CSA) and FM-index reduce space while supporting fast
substring queries.

✅ Applications: Text retrieval, bioinformatics (genome indexing).

Compressed Storage Matters

58
  Efficiency → Handles large-scale data within memory limits.
 Performance → Less I/O from disk.
 Scalability → Enables big-data processing (graphs, matrices, documents).

Summary
Technique Where Used
CSR / CSC Sparse matrices, graph algorithms
Compressed Tries String dictionaries, IP routing
RLE Text/images with repetition
Huffman Coding File formats, multimedia compression
Dictionary-based (LZW) ZIP, PNG, GIF
Compressed Suffix Arrays Text indexing, DNA sequences
Graph compression Social networks, web graphs

 Graph Traversals: DFS and BFS

Graphs (or trees as a special case) can be explored systematically using traversal algorithms.
The two fundamental ones are:

1. Depth First Search (DFS)

 Idea: Explore as far as possible along a branch before backtracking.

 Implementation:’
o Recursive (using function call stack)
o Iterative (using explicit stack)

Pseudocode (Recursive DFS)

DFS(node):
mark node as visited
for each neighbor of node:
if neighbor not visited:
DFS(neighbor)

Applications of DFS

1. Path Finding / Connectivity

o Check if a path exists between two nodes.
2. Topological Sorting
o In Directed Acyclic Graphs (DAGs).
3. Cycle Detection
o Detect back edges in directed/undirected graphs.
4. Solving Mazes & Puzzles
o Backtracking problems like Sudoku, N-Queens.
5. Strongly Connected Components (SCCs)
o Kosaraju’s / Tarjan’s algorithm.
6. Spanning Trees

59
 o Generate a DFS Tree.

2. Breadth First Search (BFS)

 Idea: Explore all neighbors level by level before moving deeper.

 Implementation:
o Uses a queue (FIFO).

Pseudocode (BFS)

BFS(start):
create a queue Q
mark start as visited
enqueue start
while Q not empty:
node = dequeue(Q)
for each neighbor of node:
if neighbor not visited:
mark visited
enqueue(neighbor)

Applications of BFS

1. Shortest Path in Unweighted Graphs

o Finds minimum number of edges.
2. Level Order Traversal in Trees
o Binary trees (used in many tree problems).
3. Web Crawlers
o Traverse web links layer by layer.
4. Network Broadcasting
o Sending messages to all nodes efficiently.
5. Bipartite Graph Checking
o Alternate coloring of levels.
6. Minimum Spanning Tree (Unweighted)
o Useful in connectivity checks.

Comparison: DFS vs BFS

Feature DFS BFS
Data Structure Stack (or recursion) Queue
Exploration Goes deep before backtracking Explores level by level
Path Finding May not find shortest path Always finds shortest path (unweighted)
Memory Usage O(V) in recursion/stack O(V) in queue
Best For Backtracking, puzzles, SCCs Shortest paths, level-wise problems

 Shortest Path Algorithms: Dijkstra

Algorithm (Steps)

60
Given a graph G(V, E) with edge weights w(u, v) ≥ 0:

1. Initialization
o Distance of source s = 0
o Distance of all other vertices = ∞
o Mark all vertices unvisited
2. Processing
o While there are unvisited vertices:
 Select vertex u with the minimum distance
 Mark u as visited
 For each neighbor v of u:
 If dist[u] + w(u, v) < dist[v]
→ Update dist[v] = dist[u] + w(u, v)
3. End
o Distances now represent shortest paths from s

Pseudocode
Dijkstra(Graph, source):
for each vertex v in Graph:
dist[v] = ∞
prev[v] = NIL
dist[source] = 0
create a priority queue Q
[Link](source, 0)
while Q is not empty:
u = Q.extract_min()
for each neighbor v of u:
alt = dist[u] + weight(u, v)
if alt < dist[v]:
dist[v] = alt
prev[v] = u
Q.decrease_key(v, alt)
return dist[], prev[]

Applications of Dijkstra’s Algorithm

1. Shortest Path in Maps

o GPS navigation, Google Maps.
2. Network Routing
o OSPF (Open Shortest Path First) protocol.
3. Resource Allocation
o Finding least-cost paths in logistics.
4. Game Development
o NPC pathfinding on weighted maps.
5. Social Networks
o Find degrees of separation.

Limitations
Does not work with negative weight edges (Bellman-Ford is needed instead).

61
 Bellman-Ford
Algorithm (Steps)

1. Initialization
o Distance to source = 0
o Distance to all other vertices = ∞
2. Relaxation (Repeat V – 1 times)
o For each edge (u, v) with weight w:
If dist[u] + w < dist[v] → update dist[v] = dist[u] + w
3. Negative Cycle Check
o Run one more relaxation:
 If any distance is updated → Negative cycle exists.

Pseudocode
BellmanFord(Graph, source):
for each vertex v in Graph:
dist[v] = ∞
dist[source] = 0
for i = 1 to V-1:
for each edge (u, v) with weight w in Graph:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for each edge (u, v) with weight w in Graph:
if dist[u] + w < dist[v]:
return "Negative weight cycle detected"

return dist[]
Applications of Bellman–Ford

1. Shortest Paths with Negative Edges

o Unlike Dijkstra, works in such cases.
2. Detect Negative Cycles
o Useful in financial arbitrage detection, currency exchange.
3. Routing Protocols
o Used in Distance Vector Routing Protocols (like RIP – Routing Information
Protocol).
4. Constraint Systems
o Solves problems where constraints are expressed as inequalities.

 Floyd-Warshall
Algorithm (Steps)

1. Initialization
o Construct a distance matrix dist[][] from the adjacency matrix.
o If no edge exists → ∞ (infinity).
o Distance of vertex to itself = 0.
2. Dynamic Programming Update
o For each vertex k (as intermediate):
 For each pair (i, j):

62
  Update:
 if dist[i][k] + dist[k][j] < dist[i][j]:
 dist[i][j] = dist[i][k] + dist[k][j]
3. Result
o Matrix dist[][] gives shortest distances between all vertex pairs.
o If dist[i][i] < 0 → Negative cycle exists.

Pseudocode
FloydWarshall(Graph):
let dist = adjacency matrix of Graph
for k = 1 to V:
for i = 1 to V:
for j = 1 to V:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]

return dist
Applications of Floyd–Warshall

1. All-Pairs Shortest Path

o Unlike Dijkstra (single source), computes all in one run.
2. Routing Algorithms
o Used in network routing (transitive closure, shortest delays).
3. Urban Planning / Traffic Systems
o Finding best routes between all city intersections.
4. Transitive Closure
o Check reachability of nodes.
5. Detecting Negative Cycles
o If dist[i][i] < 0 for any vertex.

Comparison with Dijkstra and Bellman–Ford

Feature Dijkstra Bellman–Ford Floyd–Warshall
Single-source shortest Single-source shortest All-pairs shortest
Type
path path path
✅ Allowed (no
Negative Weights ❌ Not allowed ✅ Allowed (no cycles)
cycles)
Negative Cycle
❌ ✅ ✅
Detet
Time Complexity O((V+E) log V) O(V·E) O(V³)
Graphs with negative Dense graphs, all-
Best For Large sparse graphs
edges pairs

 Johnson’s algorithm
 It finds the shortest paths between all pairs of vertices in a weighted directed graph. It
allows some of the edge weights to be negative numbers, but no negative-weight
cycles may exist.
 Use Floyd–Warshall for dense graphs.
 Use Johnson’s Algorithm for sparse graphs with possible negative weights.

63
 Steps of Johnson’s Algorithm

1. Add a New Vertex q

o Connect it to every other vertex with edge weight 0.
2. Run Bellman–Ford from q
o Compute shortest distances h(v) from q to every vertex v.
o If Bellman–Ford detects a negative cycle → Stop (no solution).
3. Reweight Edges
o For every edge (u, v) with weight w(u, v):
o w'(u, v) = w(u, v) + h(u) - h(v)
o This ensures all weights become non-negative.
4. Run Dijkstra for Each Vertex
o Use Dijkstra to compute shortest paths in the reweighted graph.
o Reconvert distances back to original weights:
o dist(u, v) = dist’(u, v) + h(v) - h(u)
Pseudocode
Johnson(Graph G):
add new node q
for each vertex v in G:
add edge (q, v) with weight 0
if BellmanFord(q) has negative cycle:
return "Negative cycle detected"
for each vertex v:
h[v] = dist(q, v) // from Bellman-Ford
for each edge (u, v) in G:
w'(u, v) = w(u, v) + h[u] - h[v]
for each vertex u in G:
run Dijkstra(u) using w'
for each vertex v:
dist[u][v] = dist’(u, v) + h[v] - h[u]
return dist[][]
Applications of Johnson’s Algorithm

1. All-Pairs Shortest Paths in Sparse Graphs

o Works even with negative edges.
2. Routing & Network Optimization
o Efficient when graphs have few edges compared to vertices.
3. Graph Analysis in AI & Robotics
o Finding multiple optimal routes quickly.
4. Economics / Finance
o Detecting arbitrage opportunities (negative cycles).

 Minimum Spanning Trees: Prim’s, Kruskal’s

Minimum Spanning Tree (MST)

 A spanning tree of a graph is a subset of edges that connects all vertices with no
cycles.

64
  A minimum spanning tree is a spanning tree with the minimum total edge weight.
 MST exists only for connected, undirected, weighted graphs.

1. Prim’s Algorithm

 Start from a node, grow the MST one edge at a time by always picking the
minimum edge that connects a vertex inside the tree to one outside.

Steps

1. Start with any vertex.

2. Choose the smallest edge connecting the tree to a new vertex.
3. Add that vertex and edge to the tree.
4. Repeat until all vertices are included.

Pseudocode
Prim(Graph, start):
Initialize MST = {}
dist[v] = ∞ for all vertices
dist[start] = 0
Q = priority queue of all vertices
while Q is not empty:
u = extract_min(Q)
for each neighbor v of u:
if v in Q and weight(u,v) < dist[v]:
dist[v] = weight(u,v)
parent[v] = u
return parent[]

2. Kruskal’s Algorithm

 Start with all vertices as separate components, then add edges in increasing weight
order, avoiding cycles.
 Uses Disjoint Set Union (DSU) / Union-Find to check cycles.

Steps

1. Sort all edges by weight.

2. Initialize MST = {}.
3. For each edge (u, v) in sorted order:
o If u and v are in different sets → add edge to MST.
o Union sets of u and v.
4. Stop when MST has (V – 1) edges.

Pseudocode
Kruskal(Graph):
MST = {}
sort edges by weight
for each edge (u, v) in sorted order:
if Find(u) != Find(v):

65
 [Link]((u, v))
Union(u, v)
return MST
Comparison: Prim’s vs Kruskal’s
Feature Prim’s Algorithm Kruskal’s Algorithm
Approach Grow MST from a start node Add edges by global min wt
Data Structure Priority Queue (Heap) Union-Find (Disjoint Set)
Best For Dense graphs (many edges) Sparse graphs (few edges)
Complexity O(E log V) O(E log E)
Cycle Check Implicit (via tree growth) Explicit (Union-Find)

Applications of MST

1. Network Design
o Laying cables, pipelines, roads (minimum cost).
2. Clustering in Machine Learning
o Single-link hierarchical clustering.
3. Approximation Algorithms
o Basis for TSP approximation.
4. Image Segmentation
o Region-based grouping in computer vision.

 Borůvka’s algorithm

 Borůvka’s Algorithm (1926) is one of the earliest MST algorithms.

 It repeatedly connects components of the graph by selecting the cheapest outgoing
edge from each component, until all vertices are in a single connected MST.
 It grows multiple components simultaneously by adding cheapest edges.

Algorithm (Steps)

1. Initialize MST as an empty set.

2. Treat each vertex as a separate component.
3. While more than one component exists:
o For each component, find the cheapest outgoing edge.
o Add all those cheapest edges to MST (this merges components).
4. When only one component remains → that’s the MST.

Pseudocode
Boruvka(Graph):
MST = {}
Components = {each vertex is a separate set}
while number_of_components > 1:
for each component C:
find the cheapest edge (u, v) leaving C
for each chosen edge (u, v):
if u and v are in different components:

66
 [Link]((u, v))
Union(u, v)
return MST
Applications

1. Network Design
o Constructing low-cost power or telecommunication networks.
2. Parallel & Distributed Computing
o Each component can independently find its cheapest edge (parallel-friendly).
3. Sparse Graph Optimization
o Especially useful in early MST computations before Kruskal/Prim
optimizations.

 Network Flow Algorithms: Ford-Fulkerson

Ford–Fulkerson Method

Algorithm (Steps)

1. Initialize flow f(u, v) = 0 for all edges.

2. While there exists a path P from s to t in the residual graph:
o Find bottleneck capacity = minimum residual capacity along P.
o Add bottleneck flow to all edges along P.
3. When no augmenting path exists, the current flow is maximum flow.

Pseudocode

FordFulkerson(Graph, s, t):
for each edge (u, v):
f[u][v] = 0
while there exists augmenting path P from s to t:
bottleneck = min(residual_capacity(u, v) for (u, v) in P)
for each edge (u, v) in P:
f[u][v] += bottleneck
f[v][u] -= bottleneck // reverse edge
return total flow from s

Applications of Ford–Fulkerson

1. Network Routing
2. Bipartite Matching
3. Circulation Problems
4. Image Segmentation
5. Project Scheduling

 Edmonds-Karp

67
  It is Ford–Fulkerson + BFS.
 Instead of choosing any augmenting path arbitrarily, Edmonds–Karp always chooses
the shortest augmenting path (in terms of number of edges) using Breadth-First
Search (BFS) in the residual graph.

Algorithm (Steps)

1. Initialize flow:
Set all edge flows f(u, v) = 0.
2. Build residual graph:
For each edge (u, v) with capacity c(u, v), maintain residual capacity:
o Forward: c(u, v) – f(u, v)
o Backward: f(u, v)
3. Find augmenting path (BFS):
o Run BFS from source s to sink t in residual graph.
o If no path exists → stop.
4. Augment flow:
o Find bottleneck capacity = min residual capacity along the BFS path.
o Increase flow along forward edges, decrease along reverse edges.
5. Repeat until no augmenting path exists.

Pseudocode
EdmondsKarp(Graph, s, t):
for each edge (u, v):
f[u][v] = 0

max_flow = 0
while BFS(s, t) finds augmenting path P:
bottleneck = min(residual_capacity(u, v) for (u, v) in P)
for each edge (u, v) in P:
f[u][v] += bottleneck
f[v][u] -= bottleneck
max_flow += bottleneck
return max_flow
Applications

1. Network Bandwidth Optimization

2. Bipartite Matching
3. Job Assignment Problems
4. Image Segmentation (Graph Cuts)
5. Sports Tournament Scheduling

 Push-Relabel

 It maintains a preflow: flow that may temporarily violate the conservation property (a
vertex can have more incoming flow than outgoing).
 Excess flow is gradually pushed "downhill" from source s toward sink t.

68
  A height function (label) guides flow direction: flow is only pushed from higher to
lower height nodes.

Algorithm (Steps)

1. Initialization
o Set flow f(u, v) = 0.
o Set h(s) = |V|, h(v) = 0 for others.
o Push maximum possible flow from source s to its neighbors.
2. While some vertex u (≠ s, t) has excess flow:
o If u can push flow to neighbor v: Push.
o Else: Relabel (increase h(u)).
3. Continue until no vertex (except sink) has excess flow.

Pseudocode
PushRelabel(Graph, s, t):
initialize preflow: f(u, v) = 0
h[s] = |V|, h[v] = 0 for all v ≠ s
for each neighbor v of s:
f(s, v) = c(s, v)
e(v) = c(s, v)
while there exists a vertex u ≠ s, t with e(u) > 0:
if exists v such that (u, v) has residual capacity and h(u) = h(v) + 1:
Push(u, v)
else:
Relabel(u)
return total flow out of s
Applications

1. Maximum Flow Problems

2. Bipartite Matching
3. Image Segmentation
4. Circulation & Supply Chain Optimization.

UNIT -4
Algorithm Design and Paradigms
Divide and Conquer: Karatsuba’s multiplication

69
The Karatsuba multiplication algorithm is a fast multiplication algorithm based on the
divide and conquer technique. It improves the multiplication of two nnn-digit numbers from
the classical complexity of

O(n2) to

O(nlog⁡23)≈O(n1.585)O(n^{\log_2 3}) \approx O(n^{1.585})O(nlog23)≈O(n1.585)

Karatsuba’s Trick

Karatsuba reduces the 4 multiplications to just 3:

1. Z2=X1⋅Y1Z_2 = X_1 \cdot Y_1Z2=X1⋅Y1

2. Z0=X0⋅Y0Z_0 = X_0 \cdot Y_0Z0=X0⋅Y0
3. Z1=(X1+X0)(Y1+Y0)−Z2−Z0Z_1 = (X_1 + X_0)(Y_1 + Y_0) - Z_2 - Z_0Z1=(X1
+X0)(Y1+Y0)−Z2−Z0

Then, the result is:

X⋅Y=Z2⋅102m+Z1⋅10m+Z0X \cdot Y = Z_2 \cdot 10^{2m} + Z_1 \cdot 10^m +

Z_0X⋅Y=Z2⋅102m+Z1⋅10m+Z0
Complexity

 Classical multiplication: O(n2)O(n^2)O(n2)

 Karatsuba: T(n)=3T(n/2)+O(n)T(n) = 3T(n/2) + O(n)T(n)=3T(n/2)+O(n)
→ By Master Theorem: O(nlog⁡23)≈O(n1.585)O(n^{\log_2 3}) \approx
O(n^{1.585})O(nlog23)≈O(n1.585).

Thus, it is asymptotically faster for large nnn.

 Strassen’s algorithm

 Problem: Matrix multiplication

 Naïve method: Multiplying two n×nn \times nn×n matrices takes

O(n3)O(n^3)O(n3)

operations.

 Strassen’s idea (1969): Use Divide and Conquer to reduce the number of
multiplications.
→ Achieves time complexity:

O(nlog⁡27)≈O(n2.81)O(n^{\log_2 7}) \approx O(n^{2.81})O(nlog27)≈O(n2.81)

which is faster than O(n3)O(n^3)O(n3).

Applications
70
  Useful in large matrix multiplications.
 Forms the basis of faster algorithms like Coppersmith-Winograd.
 Applied in computer graphics, scientific computing, and big data problems.

 Greedy Methods: Huffman coding

Huffman Coding
 Huffman coding is a lossless data compression technique.

 It assigns variable-length codes to input characters:

o Frequent characters → shorter codes
o Less frequent characters → longer codes
 Used in file compression (ZIP, GZIP), multimedia (JPEG, MP3), etc.

Greedy Strategy

Huffman coding follows a greedy approach:

1. Build the Huffman tree by repeatedly merging the two least-frequent nodes.
2. Assign 0 to one branch and 1 to the other.
3. Codes are obtained by traversing from the root to each leaf.

Algorithm Steps

Given a set of characters with frequencies:

1. Input: Characters + frequencies.

2. Build priority queue (min-heap) of all characters based on frequency.
3. Repeat until one node left:
o Extract 2 smallest frequency nodes.
o Create a new internal node with frequency = sum of two nodes.
o Insert back into min-heap.
4. The remaining node = root of Huffman Tree.
5. Assign codes by traversing:
o Left edge → 0
o Right edge → 1

Example

Characters: {A:5, B:9, C:12, D:13, E:16, F:45}

Step 1: Build heap with frequencies.

Step 2: Combine smallest pairs:

 A(5) + B(9) = 14
 Insert back → {C:12, D:13, (AB):14, E:16, F:45}

Step 3: Continue merging:

71
  C(12) + D(13) = 25
 (AB)(14) + E(16) = 30
 (CD)(25) + (AB,E)(30) = 55
 (55) + F(45) = 100

Step 4: Construct tree → generate codes:

 F=0
 C = 100
 D = 101
 A = 1100
 B = 1101
 E = 111

Result

Character Frequency Code

F 45 0
C 12 100
D 13 101
A 5 1100
B 9 1101
E 16 111

✅ Average code length is minimized.

Applications

 File compression: ZIP, GZIP

 Multimedia compression: JPEG, MP3
 Transmission of data in networks
 Used in compiler design for encoding tokens

 Interval scheduling

Problem Definition

 You are given n intervals/jobs, each with a start time and finish time.
 Goal: Select the maximum number of non-overlapping intervals.

This problem is also called Activity Selection Problem.

Greedy Algorithm

The greedy choice is:

Always pick the interval that finishes earliest among those that are still compatible.

72
Algorithm Steps

1. Sort intervals by finish time.

2. Select the first interval (earliest finish).
3. For each next interval:
o If its start time ≥ finish time of last selected interval → include it.
o Otherwise, skip.
4. Continue until all intervals are checked.

Example

Intervals (start, finish):

(1,3),(2,5),(4,6),(6,7),(5,9),(8,10)(1, 3), (2, 5), (4, 6), (6, 7), (5, 9), (8,
10)(1,3),(2,5),(4,6),(6,7),(5,9),(8,10)

Step 1: Sort by finish time:

(1,3),(4,6),(6,7),(2,5),(5,9),(8,10)(1, 3), (4, 6), (6, 7), (2, 5), (5, 9), (8,
10)(1,3),(4,6),(6,7),(2,5),(5,9),(8,10)

→ Actually: correct sorted order is

(1,3),(2,5),(4,6),(6,7),(5,9),(8,10)(1, 3), (2, 5), (4, 6), (6, 7), (5, 9), (8,
10)(1,3),(2,5),(4,6),(6,7),(5,9),(8,10)

Step 2: Select intervals greedily:

 Pick (1,3) → first job.

 Next (2,5): overlaps → skip.
 Next (4,6): start=4 ≥3 → select.
 Next (6,7): start=6 ≥6 → select.
 Next (5,9): overlaps → skip.
 Next (8,10): start=8 ≥7 → select.

✅ Optimal solution: (1,3), (4,6), (6,7), (8,10) → 4 jobs.

Applications

 CPU job scheduling

 Scheduling classes/exams in classrooms
 Resource allocation in cloud computing
 Project planning (choosing maximum tasks without overlap)

 Set cover approximation

Definition

 We are given:
73
 o A universe of elements U={1,2,...,n}U = \{1,2,...,n\}U={1,2,...,n}
o A collection of subsets S={S1,S2,...,Sm}S = \{S_1, S_2, ..., S_m\}S={S1,S2
,...,Sm}, each Si⊆US_i \subseteq USi⊆U.
 Goal: Select the minimum number of subsets from SSS whose union covers UUU.

Algorithm Steps

1. Input: Universe UUU, subsets SSS.

2. Initialize Cover C=∅C = \emptysetC=∅.
3. While U≠∅U \neq \emptysetU =∅:
o Choose Si∈SS_i \in SSi∈S that maximizes ∣Si∩U∣|S_i \cap U|∣Si∩U∣.
o Add SiS_iSi to CCC.
o Remove covered elements from UUU.
4. Return CCC.

Example

Universe:

U={1,2,3,4,5,6,7}U = \{1,2,3,4,5,6,7\}U={1,2,3,4,5,6,7}

Subsets:

 S1={1,2,3}S_1 = \{1,2,3\}S1={1,2,3}
 S2={2,4,5}S_2 = \{2,4,5\}S2={2,4,5}
 S3={3,6}S_3 = \{3,6\}S3={3,6}
 S4={4,5,6,7}S_4 = \{4,5,6,7\}S4={4,5,6,7}

Step 1: Pick S1={1,2,3}S_1 = \{1,2,3\}S1={1,2,3} (covers 3 elements).

Remaining U={4,5,6,7}U = \{4,5,6,7\}U={4,5,6,7}.

Step 2: Pick S4={4,5,6,7}S_4 = \{4,5,6,7\}S4={4,5,6,7} (covers 4 elements).

Remaining U=∅U = \emptysetU=∅.

✅ Final Cover = {S1,S4}\{S_1, S_4\}{S1,S4}.

Applications

 Resource allocation (minimum facilities covering all demands)

 Network design (minimum routers covering all users)
 Compiler optimization (minimum registers covering variable lifetimes)

74
  Test case reduction (cover all conditions with fewer test cases)

 Dynamic Programming: Matrix chain multiplication

 We are given a chain of matrices A1,A2,…,AnA_1, A_2, \dots, A_nA1,A2,…,An.

 Multiplying matrices is associative, but the cost differs based on parenthesization.
 Goal: Find the optimal way to parenthesize to minimize the total number of scalar
multiplications.

Example:

 (A1A2)A3(A_1A_2)A_3(A1A2)A3 may be cheaper than

A1(A2A3)A_1(A_2A_3)A1(A2A3).

Dynamic Programming Algorithm

1. Initialize diagonal entries: m[i,i]=0m[i,i] = 0m[i,i]=0.

2. For chain length L=2L = 2L=2 to nnn:
o For each iii, compute j=i+L−1j = i + L - 1j=i+L−1.
o Evaluate all possible splits kkk.
o Store the minimum cost in m[i,j]m[i,j]m[i,j].
3. Final answer = m[1,n]m[1,n]m[1,n].

Example

Given dimensions:

p=[10,20,30,40,30]p = [10, 20, 30, 40, 30]p=[10,20,30,40,30]

Matrices:

 A1(10×20)A_1 (10\times 20)A1(10×20),

 A2(20×30)A_2 (20\times 30)A2(20×30),
 A3(30×40)A_3 (30\times 40)A3(30×40),
 A4(40×30)A_4 (40\times 30)A4(40×30).
 Naive multiplication orders differ:
o ((A1A2)A3)A4((A_1A_2)A_3)A_4((A1A2)A3)A4 = 51000 multiplications.
o A1((A2A3)A4)A_1((A_2A_3)A_4)A1((A2A3)A4) = 36000 multiplications.

75
 o (A1A2)(A3A4)(A_1A_2)(A_3A_4)(A1A2)(A3A4) = 30000 multiplications
(optimal)

Applications

 Compiler design → optimal order for evaluating matrix expressions.

 Databases → optimal join order in queries.
 Computer graphics & scientific computing → efficient large matrix computations.

 Floyd Warshall

Problem Definition

 Input: A weighted directed graph G=(V,E)G = (V,E)G=(V,E) with weight function

w(u,v)w(u,v)w(u,v).
 Goal: Find shortest paths between all pairs of vertices.
 Works even with negative edge weights, but no negative cycles.

Algorithm

for k = 1 to n:
for i = 1 to n:
for j = 1 to n:
d[i][j] = min(d[i][j], d[i][k] + d[k][j])

Example

Graph with vertices {1,2,3}\{1,2,3\}{1,2,3}:

 Edge weights:
o 1→2=41 \to 2 = 41→2=4
o 2→3=52 \to 3 = 52→3=5
o 1→3=101 \to 3 = 101→3=10

Iteration process updates the distance matrix step by step.

✅ Final shortest path: 1→3=91 \to 3 = 91→3=9 (via 2).

76
Applications

 Routing protocols (network shortest paths).

 Social network analysis (closeness, betweenness).
 Preprocessing in AI pathfinding (game maps, robotics).
 Detecting negative weight cycles (if d[i][i]<0d[i][i] < 0d[i][i]<0).

 Knapsack variants

Classic Problem Definition

 We are given:
o A set of nnn items, each with:
 weight wiw_iwi
 value viv_ivi
o A knapsack of capacity WWW.
 Goal: Maximize the total value without exceeding the capacity.

Knapsack Variants
0/1 Knapsack

 Each item can be taken at most once.

 xi∈{0,1}x_i \in \{0,1\}xi∈{0,1}.

Fractional Knapsack

 Items can be broken into fractions.

 0≤xi≤10 \leq x_i \leq 10≤xi≤1.
 Solved with Greedy Algorithm: pick items with max value/weight ratio.
 Complexity: O(nlog⁡n)O(n \log n)O(nlogn).

Unbounded Knapsack

 Items can be taken any number of times.

 xi≥0x_i \geq 0xi≥0.
 DP formula:

dp[w]=max⁡i:wi≤w(dp[w−wi]+vi)dp[w] = \max_{i: w_i \leq w} (dp[w - w_i] +

v_i)dp[w]=i:wi≤wmax(dp[w−wi]+vi)

 Complexity: O(nW)O(nW)O(nW).

77
Bounded Knapsack

 Each item can be taken a limited number of times (given count cic_ici).
 Reduction to 0/1 knapsack using binary representation trick (e.g., item count 13 →
items of 1, 2, 4, 6).
 Complexity: O(nWlog⁡ci)O(nW \log c_i)O(nWlogci).

Multiple Knapsack Problem (MKP)

 Multiple knapsacks, each with its own capacity.

 Assign items optimally across knapsacks.
 Much harder → often solved with approximation/heuristics.

Multi-dimensional Knapsack (Multi-constraint Knapsack)

 Each item has multiple constraints (e.g., weight, volume, cost).

 Constraints:

∑wi,jxi≤Wj∀j\sum w_{i,j} x_i \leq W_j \quad \forall j∑wi,jxi≤Wj∀j

 More complex DP, often NP-hard in practice.

Applications

 Resource allocation (budget, storage, bandwidth).

 Investment decisions (maximize return with limited budget).
 Cutting stock problems (industry optimization).
 Cloud computing (task scheduling under resource constraints).


Backtracking

Backtracking is a general algorithmic technique for solving problems incrementally by

building candidates and abandoning them (“backtracking”) as soon as it determines that the
candidate cannot possibly lead to a valid solution.

 Approach: Depth-First Search (DFS) with pruning.

 Used for:
o N-Queens problem
o Hamiltonian cycle
o Sudoku solving
o Graph coloring

Steps

1. Construct a solution step by step.

2. Check feasibility at each step.
3. If infeasible → backtrack.
4. If feasible and complete → accept solution.

78
 Branch and Bound

Branch-and-Bound is an optimization technique used to solve combinatorial and

optimization problems more efficiently by systematically exploring and pruning search
space using bounds.

 Approach: Best-First Search (BFS or Priority Queue) with bounding function.

 Used for:
o 0/1 Knapsack Problem
o Travelling Salesman Problem (TSP)
o Job scheduling
o Integer programming

Steps

1. Start from the root (no items/choices yet).

2. Branch → generate subproblems.
3. Bound → calculate upper/lower bound of solution.
4. If bound worse than best solution → prune branch.
5. Continue until all branches are explored or pruned.

Comparison of Backtracking vs Branch-and-Bound

Feature Backtracking Branch-and-Bound
Nature Feasibility problem solving Optimization problem solving
Search BFS or Best-First Search with
DFS-based
strategy priority
Based on bounds (upper/lower
Pruning Based on feasibility
values)
Used for N-Queens, Sudoku, Graph coloring TSP, Knapsack, Job Scheduling
Find a feasible solution (may be
Goal Find optimal solution
multiple)

 Randomized Algorithms and Probabilistic Analysis

Randomized Algorithms

79
A randomized algorithm is an algorithm that uses random numbers during its execution to
make decisions. This introduces probabilistic behavior in the outcome, performance, or
both.

Types of Randomized Algorithms

1. Las Vegas Algorithms

o Always produce the correct result.
o Randomness only affects time/steps taken.
o Example: Randomized QuickSort (partition pivot chosen randomly).
2. Monte Carlo Algorithms
o May produce an incorrect result with some probability.
o Trade accuracy for efficiency.
o Example: Primality testing (Miller–Rabin test).

Examples in Data Structures & Algorithms

 Randomized QuickSort → reduces probability of worst-case O(n2)O(n^2)O(n2) to

negligible.
 Randomized QuickSelect → finds k-th smallest element in expected O(n)O(n)O(n).
 Randomized Hashing → reduces collisions in hash tables.
 Skip Lists → levels assigned using coin tosses for balanced search.
 Randomized Min-Cut Algorithm → finds min-cut in graphs with high probability.

Probabilistic Analysis

Probabilistic analysis evaluates the expected performance of an algorithm by considering all

possible inputs (or random choices) with certain probabilities.

Key Concepts

1. Worst-case analysis – Guarantees upper bound, no randomness.

2. Average-case analysis – Assumes input distribution is uniform.
3. Probabilistic analysis – Uses probability theory to analyze performance when
algorithms or inputs involve randomness.

Example

 Hashing with chaining:

80
 o
Expected chain length is small (O(1)O(1)O(1)) under random uniform
hashing.
 Randomized QuickSort:
o Expected runtime is O(nlog⁡n)O(n \log n)O(nlogn) even though worst case is
O(n2)O(n^2)O(n2).

Applications

 Cryptography (secure random key generation).

 Machine learning (random sampling, stochastic gradient descent).
 Approximation algorithms (e.g., Max-Cut).
 Data structures (Skip Lists, randomized treaps).
 Network algorithms (randomized routing, gossip protocols).

UNIT -5
Computational Complexity and Approximation Algorithms
 Complexity Classes: P
Definition

 P (Polynomial time) is the class of decision problems (yes/no problems) that can be
solved by a deterministic Turing machine in polynomial time.

Key Features

 Efficiently solvable problems.

 Running time is polynomial in input size (e.g., O(n),O(n2),O(n3)O(n), O(n^2),
O(n^3)O(n),O(n2),O(n3)).
 Considered tractable or feasible problems.

Examples of Problems in P

 Sorting (Merge Sort, QuickSort → O(nlog⁡n)O(n \log n)O(nlogn)).

 Searching (Binary Search → O(log⁡n)O(\log n)O(logn)).
 Graph algorithms:
o BFS/DFS → O(V+E)O(V+E)O(V+E)
o Dijkstra’s algorithm (with binary heap) → O(Elog⁡V)O(E \log V)O(ElogV)
o Minimum Spanning Tree (Prim’s/Kruskal’s).
 Matrix multiplication (Strassen’s → O(n2.81)O(n^{2.81})O(n2.81), classical →
O(n3)O(n^3)O(n3)).
 Maximum flow (Edmonds-Karp) → O(VE2)O(VE^2)O(VE2).

Important

 P is central in complexity theory:

o It defines problems we can solve efficiently.
o It is contained in NP (i.e., P⊆NPP \subseteq NPP⊆NP).
 Open Question: Is P=NPP = NPP=NP?
o One of the biggest unsolved problems in computer science.

81
Applications

 Designing efficient algorithms.

 Understanding computational limits.
 Benchmark for comparing harder classes (like NP, NP-complete, EXP).

 NP

 NP stands for Nondeterministic Polynomial time.

 So, in Data Structures & Algorithms, NP mainly comes under Computational
Complexity Theory, helping us classify problems by their difficulty.
 It is the class of decision problems for which:
o A given solution can be verified in polynomial time.
o Finding the solution might be hard, but checking if a given solution is correct
is easy (polynomial time).

Example

Subset Sum Problem

 Problem: Given a set of integers, is there a subset whose sum equals a target value?
 Hard to compute directly (may take exponential time).
 But if someone gives you a subset, you can quickly add the numbers and check if it
equals the target → verification is polynomial time.
Thus, it belongs to NP.

Relation with P

 P ⊆ NP
o Every problem in P (solvable in polynomial time) is also in NP (since we can
verify solutions easily).
 Open question:
Is P = NP? → Still unsolved in Computer Science.

NP-Complete & NP-Hard

 NP-Complete (NPC):
o Problems that are both in NP and as hard as any other problem in NP.
o If you solve one NP-Complete problem in polynomial time → all NP
problems can be solved in polynomial time.
o Examples: Traveling Salesman Problem (decision version), 3-SAT, Clique
problem.

82
  NP-Hard:
o At least as hard as NP problems but not necessarily in NP (may not even be
decision problems).
o Example: Optimization version of TSP.

Diagram (Hierarchy)
P ⊆ NP ⊆ NP-Complete ⊆ NP-Hard

 P: Problems solvable in polynomial time.

 NP: Problems verifiable in polynomial time.
 NP-Complete: Hardest problems in NP.
 NP-Hard: At least as hard as NP problems (includes optimization problems).

 NP-Complete

 A problem is NP-Complete if:

1. It is in NP → A given solution can be verified in polynomial time.
2. NP-hard → As hard as any problem in NP (every NP problem can be reduced
to it in polynomial time).

 NP-Complete problems are the hardest problems in NP.

 If we find a polynomial-time solution to any NP-Complete problem, then P = NP
(one of the biggest open questions in Computer Science).

Important in DSA

 NP-Complete problems help us classify inherently difficult problems where no

efficient algorithms are known.
 Instead of searching for exact solutions, we often use:
o Approximation algorithms
o Heuristics
o Randomized algorithms
o Backtracking / Branch-and-Bound

Examples of NP-Complete Problems

1. Traveling Salesman Problem (TSP, decision version)

o Given a graph and a cost limit k, is there a path visiting all nodes with total
cost ≤ k?
2. Subset Sum Problem
o Is there a subset of numbers that adds up to a target?
3. Knapsack Problem (0/1, decision version)
o Can we fill the knapsack to reach at least value V without exceeding capacity
W?
4. Graph Coloring Problem
o Can the vertices of a graph be colored with k colors so that no two adjacent
vertices share the same color?
5. Hamiltonian Cycle Problem

83
 o Does a cycle exist that visits every vertex exactly once?

Key Techniques in DSA

To handle NP-Complete problems, algorithms often use:

 Brute Force (exponential)

 Dynamic Programming (subset sum, knapsack)
 Backtracking (graph coloring, Hamiltonian cycle)
 Greedy + Approximation (TSP approximation, vertex cover)

 NP-Hard

 NP-Hard = “Non-deterministic Polynomial-time Hard”

 A problem is NP-Hard if every NP problem can be reduced to it in polynomial
time.
 Not required to be in NP (may not even be a decision problem).
 They are at least as hard as NP problems.
 NP-Complete ⊆ NP-Hard
 But NP-Hard problems may be harder and not even verifiable in polynomial time.

Key Difference from NP & NP-Complete

Class Definition Example
Problems where solutions can be verified in Subset Sum (decision
NP
polynomial time version)
NP-
In NP + as hard as any NP problem 3-SAT, Hamiltonian Cycle
Complete
As hard as NP, may not be in NP (verification not Optimization TSP, Halting
NP-Hard
always polynomial) Problem

Examples of NP-Hard Problems

1. Travelling Salesman Problem (Optimization version)

o Find the shortest path visiting all cities once (not just decision form).
2. Knapsack (Optimization version)
o Maximize value under weight limit (not just “≥ V” decision).
3. Job Scheduling Problem
o Minimize completion time with constraints.
4. Halting Problem
o Decide if a given program halts or runs forever (undecidable → NP-Hard).
5. Bin Packing Problem
o Pack items into the minimum number of bins.

Important in DSA

 Helps us understand problem hardness and computational limits.

 No polynomial-time algorithms are known for NP-Hard problems.
 Practical approaches in DSA:

84
 o Approximation algorithms (e.g., for TSP, Vertex Cover)
o Heuristics & Metaheuristics (e.g., Genetic algorithms, Simulated annealing)
o Branch-and-Bound / Backtracking

Relation (Hierarchy)
P ⊆ NP
⊆ NP-Complete
⊆ NP-Hard

 Every NP-Complete problem is NP-Hard,

 But not every NP-Hard problem is NP-Complete.

 Reductions: Polynomial-time reductions

 A reduction is a way to transform one problem into another.

 If problem A can be reduced to problem B, then solving B also gives us a way to
solve A.
 Reductions help us compare the relative difficulty of problems.

Polynomial-Time Reduction

 A polynomial-time reduction is a transformation from Problem A → Problem B

that:
1. Can be done in polynomial time.
2. Ensures that the answer to B corresponds to the answer to A.

Notation: A ≤p B

This means Problem A reduces to Problem B in polynomial time.

Why Important

1. Helps in classifying problems (P, NP, NP-Complete, NP-Hard).

2. Used to prove a problem is NP-Complete:
o Show that the problem is in NP.
o Reduce a known NP-Complete problem to it using polynomial-time reduction.

Example

Subset Sum ≤p Knapsack

 Subset Sum Problem: Does there exist a subset of numbers that adds to K?
 Knapsack Problem: Can items be chosen such that weight ≤ W and value ≥ V?

We can convert Subset Sum into a special case of Knapsack in polynomial time →
proving that if Knapsack can be solved efficiently, so can Subset Sum.

Real Examples in Complexity

85
 1. 3-SAT ≤p Clique
o SAT formulas can be reduced to graphs (clique problem).
2. Clique ≤p Vertex Cover
o Graph transformations map one to another.
3. Hamiltonian Cycle ≤p Traveling Salesman Problem (TSP)
o Special weights enforce equivalence.

 Cook-Levin theorem (overview)

 The Cook-Levin Theorem (also called Cook’s Theorem) is a foundational result

in complexity theory.
 It states: The Boolean Satisfiability Problem (SAT) is NP-Complete.
 The Cook-Levin theorem was the first NP-Completeness proof and the starting
point of reduction-based hardness proofs in Data Structures & Algorithms.

Key Concepts

 SAT (Boolean Satisfiability Problem):

o Given a Boolean formula (with AND, OR, NOT, variables), determine if there
exists an assignment of variables that makes the formula true.
o Example: (x ∨ y) ∧ (¬x ∨ z) → is there an assignment of x, y, z that satisfies
it?
 NP:
o Problems for which a given solution can be verified in polynomial time.
o SAT clearly belongs to NP (you can check a solution by plugging values into
the formula).
 NP-Complete:
o Problems that are in NP and are as hard as any problem in NP.

What the theorem proves

 SAT ∈ NP (trivial).
 Every NP problem can be reduced to SAT in polynomial time.
 This means SAT was the first problem proven NP-Complete.
 After this, to prove other problems NP-Complete, researchers reduce SAT to them.

Importance in DSA

 Cook-Levin theorem laid the foundation of NP-Completeness theory.

 In practice:
o Many DSA problems (e.g., Clique, Vertex Cover, Hamiltonian Cycle, TSP
decision version) are proven NP-Complete via reductions from SAT.
o It tells us why certain problems are inherently hard and why we rely on
heuristics/approximations in algorithms.

Simplified Proof Idea (Intuition)

1. Any problem in NP can be represented as a non-deterministic Turing machine

computation.

86
 2. The machine’s computation steps can be encoded into a Boolean formula.
3. The formula is satisfiable if and only if the machine accepts the input.
4. Thus, solving SAT is as powerful as solving any NP problem.

 Approximation Algorithms: Vertex cover

 Definition: Given a graph G=(V,E)G = (V, E)G=(V,E), a vertex cover is a subset of

vertices C⊆VC \subseteq VC⊆V such that every edge in EEE has at least one
endpoint in CCC.
 Goal (Optimization): Find the minimum vertex cover (smallest number of
vertices).
 This problem is NP-Hard → no known polynomial-time exact solution (unless
P=NP).

Approximation Algorithms

Since exact solutions are hard, we use approximation algorithms that guarantee a solution
close to optimal.

2-Approximation Algorithm (Greedy)

 One of the simplest and most famous.

Algorithm (Greedy Matching):

1. Start with an empty cover set CCC.

2. Pick an arbitrary edge (u, v) from the graph.
3. Add both uuu and vvv to CCC.
4. Remove all edges incident to uuu or vvv.
5. Repeat until no edges remain.

Guarantee:

 This algorithm gives a solution of size at most 2 × OPT (where OPT = size of
minimum vertex cover).
 Hence, it’s a 2-approximation.

Example

Graph edges:

E = {(a, b), (b, c), (c, d)}

 Pick edge (b, c) → Add {b, c} to cover.

 All edges are now covered → Vertex Cover = {b, c}.

✅ OPT = 2, Algorithm = 2 → Exact in this case.

But in worst cases, the algorithm may pick up to 2× OPT.
87
Why Important in DSA?

 Shows how approximation algorithms can give near-optimal solutions efficiently

for NP-Hard problems.
 Used in network security, facility location, resource allocation, etc.

 Set cover
Definition

 We are given:
o A universe U={e1,e2,…,en}U = \{e_1, e_2, …, e_n\}U={e1,e2,…,en} (a set
of elements).
o A collection of subsets S={S1,S2,…,Sm}S = \{S_1, S_2, …, S_m\}S={S1,S2
,…,Sm}, where each Si⊆US_i \subseteq USi⊆U.

Goal: Find the smallest number of subsets from SSS whose union equals UUU.

Example

Universe:

U = {1, 2, 3, 4, 5}

Subsets:

S1 = {1, 2, 3}
S2 = {2, 4}
S3 = {3, 4, 5}

 One cover is {S1, S3}, because {1, 2, 3, 4, 5} = U.

 Minimum set cover size = 2.

Complexity

 Set Cover is NP-Hard (optimization version).

 The decision version (“Can we cover U with ≤ k subsets?”) is NP-Complete.
 Exact solution requires exponential time in general.

Approximation Algorithm for Set Cover

Since Set Cover is NP-Hard, we use approximation algorithms.

Greedy Approximation Algorithm

1. Start with empty cover CCC.

2. While not all elements of UUU are covered:
o Pick the subset SiS_iSi that covers the largest number of uncovered
elements.
o Add SiS_iSi to CCC.

88
 3. Stop when all elements are covered.

Performance

 Approximation Ratio: O(log⁡n)O(\log n)O(logn), where n=∣U∣n = |U|n=∣U∣.

 Time Complexity: O(mn)O(mn)O(mn) (with efficient implementation).

Applications in DSA

 Resource allocation (minimum resources to cover requirements).

 Network design (minimum routers/links to cover connectivity).
 Database indexing (minimum indexes to cover queries).
 Facility location (minimum warehouses covering cities).

 TSP

 The Travelling Salesman Problem (TSP) is a classic optimization problem in

graph theory and algorithms.
 TSP is about finding the shortest possible route covering all nodes exactly once. It’s
NP-hard, solved by brute force (small nnn), DP Held-Karp (medium nnn), and
heuristics/metaheuristics (large nnn).

Problem Statement

A salesman wants to visit a set of cities exactly once and return to the starting city, traveling
the minimum possible cost (distance/time).

Formally:

 Given a complete weighted graph G=(V,E)G = (V, E)G=(V,E), where VVV is the
set of cities and EEE is the set of edges with weights (distances),
 Find the shortest Hamiltonian Cycle that visits each vertex once and returns to the
start.

Key Characteristics

1. Input:
o
Number of cities nnn
o
Cost matrix (distance between each pair of cities)
2. Output:
o The order of visiting cities that minimizes the total cost
o The minimum tour cost
3. Type:
o Combinatorial optimization
o NP-hard problem

Example

89
Suppose we have 4 cities and the cost matrix:

From/To A B C D
A 0 10 15 20
B 10 0 35 25
C 15 35 0 30
D 20 25 30 0

One possible tour:

A→B→C→D→A
Cost = 10 + 35 + 30 + 20 = 95

But the optimal tour may differ (we compute using algorithms).

Algorithms to Solve TSP

Since TSP is NP-hard, exact algorithms are expensive for large nnn.

1. Brute Force

 Generate all possible permutations of cities

 Compute cost of each tour
 Pick minimum
 Time Complexity: O(n!)O(n!)O(n!)

2. Dynamic Programming (Held-Karp Algorithm)

 Use bitmasking + DP
 Recurrence:

dp[S][i]=min⁡j∈S,j≠i(dp[S−{i}][j]+cost[j][i])dp[S][i] = \min_{j \in S, j \neq i}(dp[S

- \{i\}][j] + cost[j][i])dp[S][i]=j∈S,j =imin(dp[S−{i}][j]+cost[j][i])

 Time Complexity: O(n2⋅2n)O(n^2 \cdot 2^n)O(n2⋅2n)

 Space Complexity: O(n⋅2n)O(n \cdot 2^n)O(n⋅2n)

3. Approximation / Heuristics (for large nnn)

 Nearest Neighbor Algorithm

 Minimum Spanning Tree (MST) based approach
 Christofides Algorithm (gives at most 1.5 × optimal tour)
 Genetic Algorithms, Simulated Annealing, Ant Colony Optimization
(metaheuristics)

Applications of TSP

 Logistics & supply chain optimization

 Route planning (delivery services, airlines, ride-sharing)
 Microchip design (circuit routing)
90
  DNA sequencing in bioinformatics
 Robotics path planning

 k center problem

Problem Statement

Given:

 A set of n points (usually in a metric space with distances defined between every pair
of points).
 An integer k (the number of centers).

Goal:

 Choose k centers such that the maximum distance of any point to its nearest center
is minimized.

Example

Suppose you want to build k hospitals in a city to serve n localities.

You want to place the hospitals so that the farthest locality from its nearest hospital is as
close as possible.

Complexity

 The problem is NP-hard for general metric spaces.

 Exact solutions are computationally infeasible for large inputs.
 Therefore, approximation algorithms are typically used.

Approximation Algorithm (Greedy)

A well-known 2-approximation algorithm works as follows:

1. Pick an arbitrary point as the first center.

2. Repeatedly select the point that is farthest from the already chosen centers.
3. Stop when k centers are selected.

This guarantees that the maximum distance is at most 2 × OPT (where OPT is the optimal
solution).

Applications

 Clustering (machine learning, data mining).

 Facility location (warehouses, hospitals, schools, data centers).
 Network design (minimizing worst-case latency).

Related Problems

91
  k-means (minimizes average squared distance, not max distance).
 k-median (minimizes sum of distances, not max distance).
 Dominating set problem (special case of k-center).

 Heuristic Algorithms: Local search

 Local Search is a heuristic algorithmic technique used for solving optimization

problems.
 Instead of searching the entire solution space (which is often exponential), it starts
from an initial feasible solution and tries to improve it step by step.
 At each step, the algorithm explores the "neighborhood" of the current solution
(slightly modified versions of it) and moves to a better one, if found.

Key Features

1. Works well for large and complex problems

2. Does not guarantee optimal solution
3. Used in problems where exact algorithms are too slow.

General Steps of Local Search

1. Initialization
2. Neighborhood Generation
3. Evaluation
4. Move/Update
5. Termination

Example Problems in DSA

1. Traveling Salesman Problem (TSP)

2. Graph Coloring
3. Knapsack Problem

Common Local Search Variants

1. Hill Climbing
2. Simulated Annealing
3. Tabu Search
4. Genetic Algorithms (GA)

Advantages

 Simple and intuitive.

 Efficient for large-scale optimization.
 Provides near-optimal solutions in practice.

Disadvantages

92
  Can get stuck in local optima.
 Performance depends on the initial solution.
 No guarantee of global optimum.

 Simulated annealing

 Simulated Annealing (SA) is a probabilistic local search heuristic used to solve

optimization problems.
 It’s inspired by the annealing process in metallurgy (heating and controlled cooling
of metals to reach a low-energy stable state).
 Unlike greedy methods (e.g., hill climbing), SA sometimes accepts worse solutions
to escape local optima, giving it a better chance of finding the global optimum.

Key Idea

 Maintain a "temperature" parameter T that gradually decreases.

 At each step:
1. Pick a neighboring solution.
2. If it’s better → accept it.
3. If it’s worse → accept it with probability:

P=e−ΔE/TP = e^{-\Delta E / T}P=e−ΔE/T

where ΔE = (new_cost - current_cost)

 As T → 0, the algorithm behaves like hill climbing (accepting only better moves).

Algorithm Steps

1. Initialize a random solution and set a high temperature T.

2. Repeat until stopping condition:
o Generate a neighbor solution.
o Compute the cost difference (ΔE).
o If better → accept.
o If worse → accept with probability e−ΔE/Te^{-\Delta E / T}e−ΔE/T.
o Decrease temperature using a cooling schedule.

Example Applications in DSA

 Traveling Salesman Problem (TSP)

 Graph Coloring
 Knapsack Problem
 Scheduling Problems

Limitations of Simulated Annealing

 Parameter Sensitivity
 Computational Time
 Slow Convergence

93
Advantages

✅ escapes local optima by occasionally accepting worse solutions.

✅ Works well for NP-hard problems.
✅ Flexible and widely applicable.

Disadvantages

❌ Slower compared to greedy local search.

❌ Performance depends on cooling schedule and parameters.
❌ No guarantee of reaching the true global optimum.

 Genetic algorithms

 A Genetic Algorithm is a metaheuristic inspired by natural selection and evolutionary

biology.
 It is used to solve optimization and search problems.
 Works on a population of candidate solutions instead of just one solution.
 Uses concepts of selection, crossover, and mutation to evolve better solutions over
generations.

Key Concepts in GA

1. Population
2. Chromosome
3. Fitness Function
4. Selection
5. Crossover (Recombination)
6. Mutation
7. Generations

Steps of a Genetic Algorithm

1. Initialize Population
2. Evaluate Fitness
3. Selection
4. Crossover
5. Mutation
6. Replacement
7. Termination

Example Applications in DSA

 Traveling Salesman Problem (TSP)

 Knapsack Problem
 Job Scheduling
 Graph Partitioning

94
Advantages

✅ Works well for complex, NP-hard problems.

✅ does not require gradient or derivative information.
✅ Explores global search space effectively (avoids local minima).

Disadvantages

❌ can be computationally expensive.

❌ Performance depends on encoding, operators, and parameter tuning.
❌ May converge prematurely (stuck in suboptimal solution).

UNIT -6
Advanced Topics and Emerging Trends
 Randomized Algorithms

 A randomized algorithm uses random numbers (coin flips, random choices) during
execution to make decisions.
 Unlike deterministic algorithms, which always give the same result for the same
input, randomized algorithms may behave differently on different runs.

Types of Randomized Algorithms

1. Las Vegas Algorithm

o Always produces a correct result.
o Running time is a random variable (depends on random choices).
o Example: Randomized QuickSort → output is always sorted, but time
depends on pivot choices.
2. Monte Carlo Algorithm
o Runs in fixed time, but may produce an incorrect result with some small
probability.
o Often used in approximation or probabilistic decision-making.
o Example: Miller-Rabin primality test → may say a composite number is
prime with small probability.

Common Applications in DS

1. Randomized QuickSort
o Pivot chosen randomly to avoid worst-case (O(n^2)).
o Expected time: O(n log n).
2. Randomized Selection (QuickSelect)
o Finds k-th smallest element in expected O(n) time.
3. Randomized Hashing
o Hash functions with randomness reduce collision chances.
o Example: Universal hashing, Cuckoo hashing.
4. Randomized Primality Testing

95
 Miller-Rabin, Fermat’s test used in cryptography.
o
5. Randomized Graph Algorithms
o Minimum cut (Karger’s Algorithm).
o Randomized algorithms for matching, spanning trees, etc.
6. Approximation Algorithms
o Use randomness to find near-optimal solutions in NP-hard problems.
o Example: Randomized rounding.

Advantages

 Often simpler and faster than deterministic counterparts.

 Avoid worst-case scenarios by random choices.
 Useful for large inputs and NP-hard problems.

Disadvantages

 May produce incorrect answers (Monte Carlo).

 Performance is not guaranteed every single run.
 Harder to debug due to non-deterministic behavior.

Real-World Examples

 Google search (hashing + randomization).

 Cryptography (primality testing).
 Network routing.
 Machine learning (randomized optimization like stochastic gradient descent).

 Monte Carlo Algorithms

 Monte Carlo algorithms sacrifice certainty for speed — they always run fast, but may
be wrong with low probability. Repetition makes them highly reliable.

 Monte Carlo algorithms are a type of randomized algorithm that:

 Always terminate in bounded time (usually polynomial).

 May give an incorrect result with a small probability.
 Trade accuracy for efficiency.

Characteristics

 Deterministic time complexity

 Probabilistic correctness
 Useful when fast answers are more important than guaranteed correctness.

Example Applications in DSA

1. Primality Testing
o Miller-Rabin test → checks if a number is prime.

96
 o Runs in polynomial time, may wrongly classify a composite as prime with tiny
probability.
o Widely used in cryptography.
2. Minimum Cut Problem (Karger’s Algorithm)
o Uses random edge contractions to find graph minimum cut.
o Result may be wrong, but repeating increases correctness probability.
3. Polynomial Identity Testing
o Checks if two polynomials are identical by evaluating them at random points.
o Fast but has a chance of error.
4. Monte Carlo Integration (approximation)
o Used in approximation algorithms (e.g., estimating area, volume, or
probabilities).
5. Randomized Approximation Algorithms
o Many NP-hard problems (e.g., MAX-SAT, Vertex Cover) use Monte Carlo
approximation.

Complexity

 Time complexity: always bounded (e.g., polynomial).

 Error probability: can be reduced to ϵ\epsilonϵ by repetition.

Advantages

✔ Very fast and simple.

✔ Works well for large inputs where deterministic solutions are slow.
✔ Probability of error can be made negligible.

Disadvantages

✘ No guarantee of correctness in one run.

✘ May require multiple runs to reduce error.
✘ Harder to prove correctness compared to Las Vegas algorithms.

Real-World Usage

 Cryptography (RSA key generation using primality tests).

 Graph algorithms (network reliability, min-cuts).
 Numerical simulations (finance, physics).
 Machine learning (stochastic methods).

 Parallel and Distributed Algorithms

Parallel Algorithm

 Algorithms designed to run on multiple processors/cores simultaneously within the

same machine.
→ Focus: speedup by splitting a task into independent subtasks executed in parallel.

97
Distributed Algorithms

 Algorithms that run on a network of interconnected computers (nodes) that

communicate via messages.
→ Focus: coordination, fault tolerance, and scalability across multiple systems.

Parallel Algorithms in DSA

1. Parallel Sorting Algorithms

o Parallel Merge Sort, Parallel QuickSort.
o Divide data among processors, merge results.
2. Parallel Matrix Multiplication
o Divide rows/columns among processors.
o Time reduced from O(n3)O(n^3)O(n3) → O(n3/p)O(n^3/p)O(n3/p) with ppp
processors.
3. Prefix Sum / Scan
o Used in parallel computing for cumulative sums.
4. Graph Algorithms
o Parallel BFS, DFS.
o Parallel shortest path algorithms (Dijkstra, Bellman-Ford).

Distributed Algorithms in DSA

1. Leader Election
o Nodes elect a coordinator in distributed systems (e.g., Bully Algorithm, Ring
Algorithm).
2. Consensus Algorithms
o Ensures all nodes agree on a value.
o Examples: Paxos, Raft, Byzantine Agreement.
3. Distributed Mutual Exclusion
o Algorithms to avoid race conditions (Ricart–Agrawala, Token-based
methods).
4. Spanning Tree Construction
o Distributed Minimum Spanning Tree (Gallager-Humblet-Spira algorithm).
5. Distributed Shortest Paths
o Bellman-Ford and Dijkstra adapted for networks.

Advantages

Parallel Algorithms

 Faster execution.
 Efficient use of multi-core systems.
98
Distributed Algorithms

 High scalability.
 Fault tolerance (system continues despite failures).
 Essential for cloud computing, blockchain, and distributed databases.

Challenges

Parallel Algorithms

 Synchronization overhead.
 Load balancing across processors.

Distributed Algorithms

 Message delays and failures.

 Consensus under unreliable networks is difficult.

Real-World Application

 Parallel: Image processing, scientific simulations, machine learning training.

 Distributed: Google File System, Blockchain, Distributed databases (e.g., Cassandra,
MongoDB).

 PRAM Model

 PRAM stands for Parallel Random Access Machine.

 It is a theoretical model used to design and analyze parallel algorithms.
 PRAM is a theoretical parallel model with processors + shared memory. It has
variations (EREW, CREW, CRCW) that define rules for memory access. Though
unrealistic in hardware, it’s powerful for teaching and analyzing parallel algorithms.
 PRAM assumes:
o Multiple processors (P₁, P₂, P₃, …, Pn).
o All processors share a single global memory.
o Each processor can access any memory cell in unit time (O(1)).
o Processors operate in lockstep (synchronous execution).

 PRAM is used to study how parallelism improves efficiency before implementing on

real hardware.

Components of PRAM

1. Processors (P₁, P₂, …, Pn) → perform computations.

2. Shared Memory → global memory accessible by all processors.
3. Interconnection Network → not modeled in detail (assumed free).
4. Clock → synchronizes execution of all processors.

Types of PRAM Modls (based on memory access conflicts)

99
 1. EREW PRAM (Exclusive Read, Exclusive Write)
o No two processors can read or write the same memory location
simultaneously.
o Most restrictive, easiest to implement.
2. CREW PRAM (Concurrent Read, Exclusive Write)
o Multiple processors can read the same memory cell at the same time.
o Only one processor can write at a time.
3. CRCW PRAM (Concurrent Read, Concurrent Write)
o Multiple processors can read and write the same memory cell simultaneously.
o Variants:
 Common CRCW: All processors writing must write the same value.
 Arbitrary CRCW: One arbitrary processor’s value is written.
 Priority CRCW: The processor with highest priority writes.

Applications of PAM

 Designing parallel algorithms for:

o Prefix sum computation.
o Parallel searching & sorting.
o Matrix operations.
o Graph algorithms (e.g., BFS, shortest paths).

Advantage

✔ Simplifies analysis of parallel algorithms.

✔ Helps in understanding speedup & efficiency.
✔ provides a foundation for real-world multi-core and parallel computing.

Limitations

✘ Unrealistic assumption of unit-time global memory access.

✘ Ignores communication overhead.
✘ Real hardware uses more complex models (e.g., mesh, hypercube).

 Divide and Conquer in Parallel

Divide and Conquer algorithms are naturally suited for parallel execution since independent
sub problems can run simultaneously. Classic examples include Parallel Merge Sort, Matrix
Multiplication, FFT, and Graph algorithms.

 Divide: Break the problem into smaller independent subproblems.

 Conquer: Solve each subproblem (recursively).
 Combine: Merge the results to get the final solution.

Example: Merge Sort, QuickSort, Binary Search.

Parallelize Divide and Conquer

100
  Many subproblems are independent → can be solved simultaneously by different
processors.
 Parallelization reduces execution time by distributing work.
 Works well with PRAM model or multi-core processors.

Parallel Divide and Conquer Strategy

1. Divide step:
o Assign different subproblems to different processors.
o Example: Splitting an array into two halves → each processor handles one
half.
2. Conquer step:
o Each processor solves its subproblem in parallel.
o If still large, subproblem is again split among processors (recursive
parallelism).
3. Combine step:
o Merge results (may need synchronization).
o Example: Merging sorted subarrays in Parallel Merge Sort.

Examples in DSA

1. Parallel Merge Sort

2. Parallel Matrix Multiplication
3. Parallel Binary Search
4. Parallel FFT (Fast Fourier Transform)

Complexity

 Sequential Divide & Conquer:

T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)T(n)=aT(n/b)+f(n) (Master Theorem).
 Parallel Divide & Conquer:
Work and depth analysis:
o Work (W): total operations = same as sequential.
o Depth (D): critical path length = reduced due to parallelism.
o Parallel time (Tₚ): Tp=O(W/p+D)Tₚ = O(W/p + D)Tp=O(W/p+D).

Advantages

✔ exploits independent sub problems efficiently.

✔ significant speedup on multi-core/parallel systems.
✔ Fits naturally with recursive algorithms.

Challenges

⚠ Load balancing → processors may get uneven work.

⚠ Synchronization overhead in combine step.
⚠ Limited parallelism if subproblems are not independent.

Load Balancing

101
  Load Balancing is the process of distributing tasks/workload evenly across
processors or resources so that no single processor is overloaded while others
remain idle.
 It is crucial in parallel and distributed algorithms, where multiple
processors/cores/computers cooperate to solve a problem.

Goal: maximize throughput, minimize execution time, and improve resource utilization.

Load Balancing Important in DSA

 Many DSA algorithms (sorting, searching, graph processing, matrix operations) are
implemented in parallel/distributed systems.
 Unequal task distribution → idle processors → reduced efficiency.
 Example: In Parallel Merge Sort, if one processor handles a huge subarray and others
get small chunks, performance suffers.

Types of Load Balancing

1. Static Load Balancing

o Tasks are assigned before execution begins.
o Simple but may not adapt to runtime changes.
o Example: Equal partitioning of an array for parallel sorting.
2. Dynamic Load Balancing
o Tasks are distributed at runtime depending on processor load.
o Processors can "steal work" from overloaded processors.
o Example: Work-stealing in parallel DFS or task scheduling systems.

Load Balancing Strategies in Algorithms

1. Divide and Conquer Strategy

o Split problem into equal-sized independent subproblems.
o Example: Parallel Merge Sort → split array into balanced halves.
2. Work Stealing
o Idle processors take tasks from busy processors.
o Used in task schedulers and libraries like OpenMP, Cilk.
3. Round Robin Assignment
o Tasks distributed cyclically across processors.
4. Randomized Load Balancing
o Assign tasks randomly → probabilistically balances load.
o Example: Balls into Bins problem in probability.
5. Graph Partitioning
o For graph algorithms (BFS, shortest paths), divide graph nodes/edges evenly
among processors.

Applications in DSA

 Parallel Sorting
 Matrix Multiplication
 Graph Algorithms
 Hashing & Data Structures

102
  Distributed Systems

Challenges

⚠ Overhead of task redistribution.

⚠ Communication cost in distributed systems.
⚠ Hard to balance when tasks are unpredictable in execution time.

 Streaming Algorithms

 Streaming algorithms are designed to process large data streams where the input
is:
o Too large to store entirely in memory.
o Arrives sequentially and must be processed in one pass (or few passes).
 They use small memory (sublinear in input size) and often produce approximate
answers instead of exact results.

Useful for Big Data, real-time analytics, and network monitoring.

Key Characteristics

 Single pass (or few passes) over the data.

 Sub linear memory usage (much smaller than data size).
 Approximate answers with probabilistic guarantees.
 Must handle continuous, high-speed data efficiently.

Techniques in Streaming Algorithms

1. Sampling
o Keep a random subset of data to approximate results.
o Example: Reservoir Sampling.
2. Sketching
o Maintain a compact summary (sketch) of data.
o Example: Count-Min Sketch for frequency estimation.
3. Sliding Window Models
o Process only the most recent data.
o Example: Network traffic monitoring over the last 10 minutes.
4. Hashing & Randomization
o Use hash functions for approximate counting.
o Example: Flajolet-Martin algorithm for distinct elements.

Classic Streaming Algorithms in DSA

1. Reservoir Sampling
o Selects a random sample of k items from a stream of unknown length.
2. Morris Algorithm
o Probabilistic counting algorithm (logarithmic space for counters).
3. Flajolet-Martin Algorithm

103
 oEstimates the number of distinct elements in a stream.
4. Count-Min Sketch
o Estimates the frequency of elements with limited memory.
5. Bloom Filters
o Probabilistic data structure to test set membership with false positives allowed.

Applications

 Network traffic analysis

 Search engines
 Databases
 Recommendation systems
 IoT & real-time systems

Advantages

✔ Handles huge data efficiently.

✔ Requires very little memory.
✔ Suitable for real-time processing.

Limitations

✘ Produces approximate answers.

✘ Works best with probabilistic guarantees, not exact results.
✘ Algorithm design is non-trivial.

 Data Stream Models

 A Data Stream Model is a computational model where data arrives as a continuous

stream, often too large to store entirely.
 Algorithms must process input sequentially, using sub linear memory and often in one
pass.
 Instead of exact results, algorithms provide approximate answers with high
probability.

This model is widely used in streaming algorithms for handling Big Data, IoT, and network
analytics.

Key Assumptions in Data Stream Models

 Input is massive and cannot be stored in full.

 Limited memory (polylogarithmic in input size).
 Algorithms should be fast (near real-time).
 Multiple types of queries: frequencies, distinct elements, top-k, etc.

Types of Data Stream Models

104
 1. Insertion-only Model
o Stream contains only insertions (new data items).
o Example: Counting website visitors, accumulating transaction records.
2. Cash Register Model
o Generalization of insertion-only.
o Each item has an associated positive weight.
o Example: Monitoring sales revenue, packet sizes in a network.
3. Turnstile Model
o Stream allows both insertions and deletions.
o Each update modifies the frequency of an item (can increase or decrease).
o Example: Tracking active users (login = +1, logout = –1).
4. Sliding Window Model
o Only the most recent W elements of the stream are considered.
o Useful when recent data is more relevant than old data.
o Example: Monitoring website hits in the last 10 minutes.

Applications of Data Stream Models

 Search Engines
 Network Security
 Social Media Analytics
 Financial Systems
 IoT & Sensors

Techniques Used in Stream Models

 Sampling → Reservoir Sampling.

 Sketching → Count-Min Sketch, HyperLogLog.
 Probabilistic Counting → Morris algorithm, Flajolet-Martin.
 Approximate Structures → Bloom filters.

Advantages

✔ Can process huge, continuous data efficiently.

✔ Uses small memory compared to input size.
✔ Works in real-time with low latency.

Limitations

✘ Cannot always provide exact answers.

✘ Complexity in designing efficient streaming algorithms.
✘ Handling deletions and updates is harder.

 Sketching and Sampling

 Sampling chooses a subset of data for approximation.

 Sketching builds a summary structure (like Count-Min Sketch, Bloom Filter, FM
Sketch).

105
 Both are key techniques in streaming algorithms for handling massive, real-time data
efficiently.w
 When dealing with large data streams (Big Data, real-time analytics), storing and
processing the entire dataset is impossible.

 Sampling → pick a representative subset.

 Sketching → maintain a compact summary.

Both are widely used in streaming algorithms for approximation with limited memory.

Sampling in DSA

Definition: Sampling selects a small subset of items from a stream or dataset while
preserving statistical properties.

Techniques

1. Reservoir Sampling
o Randomly selects kkk items from a stream of unknown length.
o Guarantees uniform probability for each item.
2. Random Sampling with Replacement
o Each item has equal chance of being chosen, independent of previous
selections.
3. Priority Sampling / Weighted Sampling
o Items with higher weights are more likely to be chosen.

Applications

 Estimating averages, sums, and distributions.

 Query optimization in databases.
 Approximate statistics in real-time monitoring.
 Machine learning: training models with sampled data.

Sketching in DSA

Definition: Sketching creates a compact summary (sketch) of a stream that allows

approximate query answers with high probability.

Common Sketching Techniques

1. Count-Min Sketch
o Approximates frequency of items in a stream.
o Uses hash functions + counters.
o Example: Finding most frequent queries in Google search logs.
2. Bloom Filters
o Probabilistic data structure to test set membership.
o May give false positives but never false negatives.
o Example: Checking if an element has appeared before in a stream.
3. Flajolet-Martin Algorithm (FM Sketch)
o Estimates number of distinct elements.

106
 o
Uses hashing and position of least significant 1-bit.
4. HyperLogLog
o Improved distinct element counting.
o Used in databases and analytics engines.

Applications

 Network monitoring
 Search engines
 Big data analytics
 Distributed systems

Comparison: Sampling vs Sketching

Feature Sampling Sketching
Method Keeps a subset of items Builds a compressed summary
Accuracy Exact for sample, approximate for dataset Approximate, probabilistic
Memory Depends on sample size Very small, polylogarithmic in data size
Example Reservoir Sampling Count-Min Sketch, Bloom Filter

Advantages

✔ Enables real-time processing.

✔ Low memory requirement.
✔ Probabilistic guarantees → high accuracy with small space.

Limitations

✘ Not always exact.

✘ Careful design required to avoid bias.
✘ Trade-off between accuracy, memory, and speed

Frequency Moments

Definition: Given a data stream of elements a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an

from a universe of size mmm, let fif_ifi denote the frequency (number of occurrences) of
the element iii in the stream.

The k-th frequency moment, denoted FkF_kFk, is defined as:

Fk=∑i=1mfikF_k = \sum_{i=1}^{m} f_i^kFk=i=1∑mfik

Examples of Frequency Moments

 F₀ (Zero-th moment): Number of distinct elements in the stream.

F0=∑i=1m[fi>0]F_0 = \sum_{i=1}^{m} [f_i > 0] F0=i=1∑m[fi>0]

107
 (Here, we count each element that appears at least once.)

 F₁ (First moment): Total number of elements in the stream.

F1=∑i=1mfi=nF_1 = \sum_{i=1}^{m} f_i = nF1=i=1∑mfi=n

 F₂ (Second moment): Sum of squares of frequencies, which captures the skewness

or concentration of elements.

F2=∑i=1mfi2F_2 = \sum_{i=1}^{m} f_i^2F2=i=1∑mfi2

 F∞ (Infinite moment): Maximum frequency of any element.

F∞=max⁡(f1,f2,…,fm)F_\infty = \max(f_1, f_2, \dots, f_m)F∞=max(f1,f2,…,fm)

Applications

Frequency moments are used in:

1. Data Streams / Big Data

o Estimating distinct elements in a massive dataset (F₀).
o Detecting heavy hitters (elements with very high frequency) using F₂ or F∞.
2. Network Traffic Analysis
o Finding frequent IP addresses, detecting DDoS attacks.
3. Database Queries
o Fast approximate counting of duplicates or common items.
4. Randomized Algorithms
o Many streaming algorithms use sketching and sampling techniques to
approximate frequency moments.

Computing Frequency Moments

 Exact computation: Use a hash table to store frequencies → O(n) time, O(m) space.
But this is impractical for large streams (big data) due to memory limits.
 Approximate computation (popular in streaming algorithms):
o F₀: HyperLogLog algorithm, Flajolet-Martin algorithm
o F₂: Alon-Matias-Szegedy (AMS) algorithm
o Heavy hitters / F∞: Count-Min Sketch

These algorithms use sublinear space and probabilistic guarantees to estimate frequency
moments.

Summary Table
Moment Formula Meaning Example
∑i=1m[fi>0]\sum_{i=1}^{m} [f_i > Distinct Stream: [a, b, a, c] → F₀ =
F₀
0]∑i=1m[fi>0] elements 3
Total Stream: [a, b, a, c] → F₁ =
F₁ ∑i=1mfi\sum_{i=1}^{m} f_i∑i=1mfi
elements 4
F₂ ∑i=1mfi2\sum_{i=1}^{m} f_i^2∑i=1m Measure of Stream: [a, b, a, c] → F₂ =

108
Moment Formula Meaning Example
fi2 skew 2² + 1² + 1² = 6
Most Stream: [a, b, a, c] → F∞
F∞ max(f_i)
frequent =2

 Advanced String Matching

Problem Definition

String Matching / Pattern Matching:

Given a text TTT of length nnn and a pattern PPP of length mmm, find all occurrences of
PPP in TTT.

 Naive solution: Compare PPP at every position in TTT → O(n × m) time.

 Advanced algorithms reduce this to linear or near-linear time using clever
preprocessing.

Key Advanced String Matching Algorithms

Knuth-Morris-Pratt (KMP) Algorithm

 Idea: Avoid redundant comparisons by preprocessing the pattern.

 Preprocessing: Compute the Longest Prefix Suffix (LPS) array for the pattern.
 Time Complexity: O(n + m)

Use Case: Exact pattern search in large texts.

Boyer-Moore Algorithm

 Idea: Compare from right to left and skip sections of text intelligently.
 Heuristics:
1. Bad Character Rule: Shift pattern past the mismatched character.
2. Good Suffix Rule: Shift pattern based on matched suffix.
 Time Complexity: O(n) on average; O(n × m) worst case.
 Use Case: Fast searching in English text, DNA sequences.

Rabin-Karp Algorithm

 Idea: Use hashing to compare substrings quickly.

 Compute hash of pattern PPP and sliding window hashes of text.
 If hash matches, then compare strings to avoid collisions.
 Time Complexity:
o Average: O(n + m)
o Worst case: O(n × m) (rare)
 Use Case: Detect multiple pattern matches, plagiarism detection.

Aho-Corasick Algorithm

 Idea: Efficient multi-pattern matching using a trie + failure links.

109
  Builds an automaton for all patterns → scans text in O(n + total pattern length +
output size)
 Use Case: Spam filtering, DNA motif search, dictionary matching.

Suffix Trees & Suffix Arrays

 Suffix Tree: A compressed trie of all suffixes of text TTT.

o Find patterns in O(m) time (after O(n) construction).
 Suffix Array + LCP Array: Space-efficient alternative to suffix trees.
 Use Case: Substring search, longest repeated substring, genome analysis.

Knuth-Morris-Pratt Variants

 Z-Algorithm: Computes Z-array (length of longest prefix matching) → useful for

pattern matching.
 Time Complexity: O(n + m)

Applications

 Text editors (search/replace)

 Bioinformatics (DNA/RNA sequence search)
 Plagiarism detection
 Spam filtering and intrusion detection
 Data compression (LZ77, LZ78)

 Suffix Trees

A suffix tree is a compressed trie of all suffixes of a string SSS of length nnn.

 Each edge represents a substring of SSS.

 Each leaf represents a suffix of SSS.
 Used for fast substring queries and other string problems.

Example:
Let S="banana$"S = "banana\$"S="banana$" (we append $ to mark the end).
Suffixes of SSS:

banana$
anana$
nana$
ana$
na$
a$
$

A suffix tree organizes all these suffixes in a trie, compressing common prefixes.

Key Features

110
  Search for a pattern PPP: O(m), where m = length of P
 Longest repeated substring: O(n)
 Longest common substring between two strings: O(n + m) with generalized suffix
tree
 Space: O(n) with Ukkonen’s online construction algorithm

Structure of a Suffix Tree

1. Nodes:
o Internal nodes: represent branching points of common prefixes.
o Leaf nodes: represent suffix indices.
2. Edges:
oLabeled with substrings of S.
oCompressed: instead of one character per edge, edges can represent multiple
characters.
3. Suffix Links (used in construction):
o Link from a node representing string xαx\alphaxα to a node representing
α\alphaα
o Crucial for Ukkonen’s linear-time construction.

Construction of Suffix Trees

 Naive Approach: Insert all suffixes into a trie → O(n²) time, O(n²) space.
 Ukkonen’s Algorithm (online construction):
o Builds suffix tree in O(n) time and O(n) space.
o Uses suffix links and implicit suffix trees.

Applications
Application How Suffix Tree Helps
Substring search Check if P exists in T in O(m)
Longest repeated substring Find the deepest internal node
Longest common substring Build generalized suffix tree for two strings
String compression Detect repeated patterns
DNA sequence analysis Search patterns in genomes efficiently

Example

Text: banana$

Suffixes:

banana$, anana$, nana$, ana$, na$, a$, $

Pattern search: Check if ana exists:

 Start at root → follow edges labeled a → n → a → success, found at positions 1 and

3.

Longest repeated substring:

111
  Internal node ana is repeated → answer: "ana"

Comparison: Suffix Tree vs Suffix Array

Feature Suffix Tree Suffix Array
Search O(m) O(m log n)
Space O(n) O(n) (more compact)
Construction O(n) O(n)
Use Case Complex string queries Memory-efficient searches

 Suffix Arrays

A suffix array is a sorted array of all suffixes of a string SSS.

 Each entry stores the starting index of a suffix in lexicographical order.

 Unlike suffix trees, it doesn’t store the actual tree structure, making it more
memory-efficient.

Example:
Let S = "banana$". Suffixes:

0: banana$
1: anana$
2: nana$
3: ana$
4: na$
5: a$
6: $

Sort them lexicographically:

Suffix Index
$ 6
a$ 5
ana$ 3
anana$ 1
banana$ 0
na$ 4
nana$ 2

Suffix Array (SA) = [6, 5, 3, 1, 0, 4, 2]

Key Properties

 Sorted lexicographically → Binary search can be used for pattern search.

 Space-efficient → Only an array of size nnn (no tree nodes).
 Can be combined with LCP (Longest Common Prefix) array for fast queries.

112
Construction of Suffix Arrays

A. Naive Approach

 Generate all suffixes, sort them → O(n² log n) (because comparing strings is O(n)).

B. Efficient Algorithms

1. Prefix Doubling / Sorting by 2k prefixes → O(n log² n)

2. Kärkkäinen-Sanders / DC3 algorithm → O(n)
3. Use of radix sort / counting sort → O(n log n)

Tip: For competitive programming, O(n log n) methods are standard.

Pattern Matching using Suffix Arrays

To find a pattern PPP of length mmm in text TTT using a suffix array:

1. Perform binary search on SA.

2. Compare PPP with suffix starting at SA[mid].
3. If matched → pattern exists; else adjust search.

Time Complexity:

 O(m log n) for each search (O(m) to compare + O(log n) for binary search)

LCP (Longest Common Prefix) Array

 Definition: LCP[i] = length of longest common prefix between suffixes SA[i] and
SA[i-1].
 Use: Helps in finding repeated substrings, longest common substring, etc.
 Construction: Kasai’s algorithm → O(n) time.

Applications
Application How Suffix Array Helps
Pattern search Binary search in O(m log n)
Longest repeated substring Use LCP array
Longest common substring Compare LCPs in generalized SA for two strings
Data compression Detect repeated substrings
Genome analysis Efficient substring queries in DNA sequences

 Pattern Matching in Linear Time

Knuth-Morris-Pratt (KMP) Algorithm

Idea

 Avoid re-checking characters in the text when a mismatch occurs.

 Use preprocessing on the pattern to build the Longest Prefix Suffix (LPS) array.
113
Steps

1. Preprocess Pattern:
o LPS[i] = length of the longest proper prefix which is also a suffix for
pattern[0..i].
2. Search in Text:
o Compare pattern and text character by character.
o If mismatch occurs, use LPS to skip ahead in pattern.

Time Complexity

 O(n + m)
 O(m) to build LPS, O(n) to search.

Z-Algorithm

Idea

 Compute Z-array for string S=P+$+TS = P + \$ + TS=P+$+T.

 Z[i] = length of the longest prefix starting at i that matches the prefix of S.
 If Z[i] = m → pattern occurs at that position.

Steps

1. Concatenate: S = P + $ + T (where $ is a unique delimiter).

2. Compute Z-array in O(n + m).
3. Check Z[i] = m → match found.

Time Complexity

 O(n + m)

Rabin-Karp Algorithm (Using Rolling Hash)

Idea

 Use hashing to compare pattern with substrings of text.

 Hashes can be compared in O(1) using rolling hash.

Steps

1. Compute hash of pattern PPP.

2. Compute rolling hash of all substrings of T of length m.
3. If hashes match → check characters to avoid collision.

Time Complexity

 Average: O(n + m)
 Worst case: O(n × m) (rare, depends on collisions)

114
Suffix Tree / Suffix Array Based Matching

 Suffix Tree: O(m) search after O(n) construction.

 Suffix Array + LCP: O(m log n) search, can be improved using enhanced suffix
arrays.

Applications

 Searching for substrings in large texts (e.g., text editors, IDEs)

 DNA / genome sequence matching
 Plagiarism detection
 Spam filtering / intrusion detection

115