ADVANCED ALGORITHMS

UNIT-1
PART A
Q1. What is topological sorting?
A topological sort is a linear ordering of vertices in a Directed Acyclic Graph
(DAG) such that for every directed edge from node u to node v, u comes before
v in the ordering.

It is commonly used for scheduling jobs or tasks where certain activities must
precede others (resolving dependencies).

Key Points:

• It is only possible if the graph has no cycles (Acyclic) and is directed.

• A graph can have multiple valid topological sorts.

• Time Complexity: O(V + E), where V is vertices and E is edges.

Q2. What is the difference between BFS and DFS?

Feature Breadth-First Search (BFS) Depth-First Search (DFS)

Explores the graph level by Explores as deep as possible

Approach level (visiting all neighbors of along each branch before
a node first). backtracking.

Data Uses a Queue (FIFO - First In Uses a Stack (LIFO - Last In

Structure First Out). First Out) or Recursion.

Guaranteed to find the

Shortest Not guaranteed to find the
shortest path in unweighted
Path shortest path.
graphs.

[Link] is topological ordering in a DAG?

Yes, topological ordering is exclusively done in a Directed Acyclic Graph
(DAG).

Why?

1. Directed: Edges must have a specific direction to represent

dependencies (e.g., u \rightarrow v means u must come before v).

2. Acyclic: If the graph contains a cycle (e.g., A depends on B, and B

depends on A), a circular dependency occurs, making it impossible to
determine which node comes first.

Therefore, a graph must be both directed and acyclic for a valid topological
ordering to exist.

Q4. What is amortized analysis?

Amortized analysis is a method used to find the average time taken per
operation over a sequence of operations, rather than looking at the worst-
case time of a single isolated operation.

It guarantees that while an occasional operation might be highly expensive,

the average cost per operation over a long sequence remains low (typically
O(1)).

Key Example:

In a Dynamic Array (like a Vector or ArrayList), inserting an element is

usually O(1). However, when the array gets full, it copies all elements to a
new, larger array, which takes O(n) time. Amortized analysis proves that
because this expensive resizing happens so rarely, the average cost of each
insertion is still O(1).

PART B
[Link] different sorting algorithms and compare their
time complexity
1. Overview of Sorting Algorithms

Sorting algorithms are methods used to rearrange a collection of items (like

elements in an array or list) into a specific order, typically numerical or
alphabetical. They are broadly categorized into comparison-based (e.g.,
Bubble, Merge) and non-comparison-based (e.g., Radix, Counting)
algorithms.

2. Common Sorting Algorithms Explained

 • Bubble Sort: A simple, iterative algorithm that repeatedly steps through
the list, compares adjacent elements, and swaps them if they are in the
wrong order. This process repeats until the list is sorted.

• Insertion Sort: Builds the final sorted array one item at a time. It takes
each element from the unsorted portion and inserts it into its correct
position within the already sorted portion.

• Merge Sort: A Divide and Conquer algorithm. It recursively divides the

array into halves until each subarray has one element, sorts them, and
then merges the sorted subarrays back together.

• Quick Sort: Another Divide and Conquer algorithm. It picks an

element as a "pivot" and partitions the array around the pivot, such that
elements smaller than the pivot go to the left, and larger ones go to the
right. It then recursively sorts the sub-arrays.

3. Time Complexity Comparison Table

To evaluate their performance, we use Big O notation across three cases: Best
(ideal input), Average (random input), and Worst (least ideal input, like a
reverse-sorted array).

Average- Worst-
Best-Case Space
Algorith Case Case Stabilit
Complexit Complexit
m Complexit Complexit y
y y
y y

O(n) (with
Bubble flag
O(n2) O(n2) O(1) Yes
Sort optimization
)

Insertion
O(n) O(n2) O(n2) O(1) Yes
Sort

Merge
O(nlogn) O(nlogn) O(nlogn) O(n) Yes
Sort
 Average- Worst-
Best-Case Space
Algorith Case Case Stabilit
Complexit Complexit
m Complexit Complexit y
y y
y y

O(n2) (poor
Quick
O(nlogn) O(nlogn) pivot O(log n) No
Sort
choice)

4. Key Takeaways for Analysis

• Efficiency: Merge Sort and Quick Sort are highly efficient for large
datasets with an average time complexity of O(nlogn), whereas Bubble
and Insertion sort become highly inefficient at O(n2).

• Space Trade-off: While Merge Sort guarantees O(nlogn) even in the

worst case, it requires extra memory (O(n) space complexity) to merge
the arrays. Quick Sort is typically preferred in practice because it sorts
"in-place" (O(log n) auxiliary space).

• Stability: Bubble, Insertion, and Merge sorts are stable (they preserve
the relative order of equal elements), whereas Quick Sort is unstable.

Q2. Describe BFS and explain how it is used to find the

shortest path.
1. What is Breadth-First Search (BFS)?
Breadth-First Search (BFS) is a graph traversal algorithm used to
explore vertices and edges of a graph or tree. It starts at a
designated source node and explores all of its neighboring nodes
at the current depth level before moving on to nodes at the next
depth level.
• Data Structure: It utilizes a Queue (First-In, First-Out or
FIFO) to keep track of nodes to visit next.
• Tracking: A visited array/set is maintained to prevent
processing the same node multiple times, avoiding infinite
loops in cyclic graphs.
2. Step-by-Step BFS Algorithm
1. Initialize: Enqueue the starting/source node and mark it as
visited.
2. Loop: While the queue is not empty:
o Dequeue the front node from the queue.
o Process this node.
o Get all unvisited neighbors of the dequeued node, mark
them as visited, and insert (enqueue) them into the
queue.
3. Terminate: Repeat until the queue becomes empty.
3. How BFS Finds the Shortest Path
BFS is uniquely suited for finding the shortest path in an
unweighted graph (where every edge has an equal cost/weight of
1).
Because BFS explores a graph level-by-level, it radiates outward
from the source node like ripples in water. The first time BFS
encounters a destination node, it is guaranteed to have reached it
via the fewest number of edges possible.
Implementation Steps for Shortest Path:
To track and extract the actual path, two modifications are made
to the standard BFS:
• Distance Array: An array dist[] initialized to infinity (\infty),
with dist[source] = 0. When moving from node u to an
unvisited neighbor v, we update:
dist[v] = dist[u] + 1
• Parent Array: An array parent[] where parent[v] = u keeps
track of the immediate predecessor. Once the destination is
reached, the shortest path is reconstructed by backtracking
from the destination to the source using this array.
4. Complexity Analysis
 • Time Complexity: O(V + E), where V is the number of vertices
(nodes) and E is the number of edges. Every vertex and edge
is explored at most once.
• Space Complexity: O(V), required for the queue and the
visited/distance tracking arrays.
Q3. Explain Dijkstra’s algorithm with an example
1. Introduction to Dijkstra's Algorithm

Dijkstra’s algorithm is a greedy algorithm used to find the single-source

shortest path from a starting node to all other nodes in a weighted graph.

• Constraint: It only works for graphs with non-negative edge weights.

• Data Structure: It utilizes a Min-Priority Queue (or Min-Heap) to

efficiently select the unvisited node with the smallest tentative distance.

2. Step-by-Step Algorithm

1. Initialization: Set the distance to the source node to 0 and to all other
nodes to infinity (\infty). Mark all nodes as unvisited.

2. Select: Choose the unvisited node with the smallest tentative distance.
Let this be the current node, u.

3. Relaxation: For the current node u, consider all of its unvisited

neighbors v. Calculate their tentative distance through u:

If dist[u] + weight(u, v) < dist[v]

Update dist[v] = dist[u] + weight(u, v)

4. Repeat: Mark the current node u as visited (it will not be checked
again). Repeat steps 2 and 3 until all nodes are visited.

3. Illustrative Example

Consider a weighted graph with 4 nodes: A, B, C, D.

• Source Node: A

• Edges and Weights: (A to B) = 4, (A to C) = 1, (C to B) = 2, (B to D) = 3,

(C to D) = 6.

Trace Table Execution:

 Distance
Current Visited
Step Array [A, B, C, Notes
Node Set
D]

Source A is 0, rest are

Initial — [0, ∞, ∞, ∞] {}
\infty.

Step Relaxes B (0+4) and C

A [0, 4, 1, ∞] {A}
1 (0+1).

Smallest is C. Relaxes B
Step
C [0, 3, 1, 7] {A, C} (1+2=3 < 4, updated) and
2
D (1+6=7).

Smallest unvisited is B.
Step
B [0, 3, 1, 6] {A, C, B} Relaxes D (3+3=6 < 7,
3
updated).

Step {A, C, B,
D [0, 3, 1, 6] Final node visited.
4 D}

Final Shortest Paths from A:

• To B: 3 (via A -> C -> B)

• To C: 1 (via A-> C)

• To D: 6 (via A -> C -> B -> D)

4. Complexity Analysis

• Time Complexity: O((V + E)log V) when implemented using a binary

min-heap, where V is vertices and E is edges.

• Space Complexity: O(V) to store the distance array, visited set, and
priority queue data tracking structures.

Q4. Discuss strongly connected components and their

computation
1. What is a Strongly Connected Component (SCC)?

A Strongly Connected Component of a directed graph is a maximal

subgraph where every vertex is reachable from every other vertex within
that subgraph.

• In simpler terms, for any pair of vertices u and v in an SCC, there exists
a directed path from u to v and a directed path from v to u.

• If you contract each SCC into a single node, the resulting graph
becomes a Directed Acyclic Graph (DAG).

2. Algorithms for Computing SCCs

There are two primary, highly efficient algorithms used to find SCCs, both
based on Depth-First Search (DFS):

1. Kosaraju’s Algorithm: Linear time, easier to conceptualize, relies on

graph transposition (reversing edges).

2. Tarjan’s Algorithm: Linear time, uses a single DFS tracking discovery

times and low-link values using a stack.

For exams, Kosaraju’s Algorithm is the standard benchmark implementation

to demonstrate.

3. Computation using Kosaraju’s Algorithm (Step-by-Step)

Kosaraju's algorithm finds all SCCs in three distinct stages:

• Step 1: Order Vertices by Finish Time

Perform a standard DFS traversal on the original graph G. As vertices finish

processing (i.e., all their neighbors are explored), push them onto a Stack.
The node at the top of the stack will be the one that finishes last.

• Step 2: Transpose the Graph (G^T)

Create a reversed copy of the graph where the direction of every single edge is
inverted. Reversing the edges preserves the internal reachability of individual
SCCs but prevents leakage between distinct components.

• Step 3: Collect Components via DFS

Pop vertices one by one from the stack. If the popped vertex has not been
visited yet, start a fresh DFS traversal on the transposed graph G^T using
this vertex as the source. All nodes reachable during this specific traversal
form a single Strongly Connected Component. Repeat until the stack is
empty.

4. Complexity Analysis
 • Time Complexity: Theta(V + E)

o Step 1 (First DFS): O(V + E)

o Step 2 (Graph Transposition): O(V + E)

o Step 3 (Second DFS): O(V + E)

o Total Time is strictly linear relative to vertices (V) and edges (E).

• Space Complexity: O(V)

Required for the explicit tracking stack, the visited array, and the storage
allocated for the transposed graph representation.

UNIT-2
PART-A
Q1. Define greedy algorithm.
A Greedy Algorithm is an algorithmic paradigm that builds a solution step-
by-step by always making the choice that looks best at the immediate
moment. It selects the locally optimal choice at each stage with the intent
that it will lead to a globally optimal solution.

Key Properties

• No Backtracking: Once a decision is made, it cannot be changed or

undone.

• Examples: Dijkstra’s Algorithm, Prim’s/Kruskal’s Algorithms (MST),

and Fractional Knapsack.

Q2. What is a maximum matching in a graph?

A matching in a graph is a set of independent edges such that no two edges
share a common vertex. A maximum matching is a matching that contains
the largest possible number of edges.

Key Characteristic

• Size: It maximizes the cardinality (total count) of edges in the matching

set.

• Unlike a maximal matching (which cannot be expanded further simply

by adding an edge), a maximum matching represents the absolute global
maximum for the entire graph.

Q3. What is an independent set in a graph.

An independent set (or stable set) in a graph is a set of vertices such that no
two vertices in the set are adjacent. In other words, there is no edge
connecting any pair of vertices within an independent set.

Key Properties

• Maximum Independent Set: An independent set that contains the

largest possible number of vertices for a given graph.

• Relationship to Vertex Cover: A set of vertices I is independent if and

only if its complement (all remaining vertices in the graph) forms a
vertex cover.

Q4. Define augmenting path?

An augmenting path is a specific type of alternating path used in graph
matching and network flow algorithms. It is a path that starts and ends at
unmatched (free) vertices, and strictly alternates between edges that are not
in the current matching and edges that are in the current matching.

Key Significance

• Berge's Lemma: A matching in a graph is maximum if and only if it

contains no augmenting paths.

• By inverting the matching status of the edges along an augmenting path

(swapping matched edges for unmatched ones), the total number of
edges in the matching automatically increases by exactly one.

PART-B
Q1. Explain the greedy paradigm with suitable examples.
1. Introduction to the Greedy Paradigm

The Greedy Paradigm is an algorithmic design strategy used to solve

optimization problems. It builds a solution step-by-step, making the choice
that looks best at the immediate moment (locally optimal choice) without
looking ahead or considering future consequences. The fundamental hope is
that a sequence of local optimums will lead to a globally optimal solution.

2. Core Properties for Success

A problem can be solved optimally using the greedy paradigm if it satisfies

two main properties:

1. Greedy Choice Property: A global optimum can be arrived at by

making a locally optimal choice at each step.
 2. Optimal Substructure: The optimal solution to the overall problem
contains optimal solutions to its sub-problems.

3. Standard Examples (Where Greedy Works Perfectly)

Example 1: Fractional Knapsack Problem

• Problem: Given items with specific weights and values, fill a knapsack
of capacity W to maximize total value. Items can be broken into smaller
fractions.

• Greedy Strategy: Calculate the value-to-weight ratio (value weight)

for each item. Sort items in descending order of this ratio and strictly
take the highest ratio items first. If an item doesn't fit entirely, take a
fraction of it to fill the remaining capacity.

Example 2: Kruskal’s / Prim’s Algorithm for Minimum Spanning Tree

(MST)

• Problem: Connect all vertices in a weighted graph with the minimum

total edge weight without forming cycles.

• Greedy Strategy (Kruskal's): Sort all edges in ascending order of their

weights. Step through the list and greedily add the cheapest edge to the
tree, provided it does not form a cycle.

4. Limitations (Where Greedy Fails)

The greedy approach does not always guarantee an optimal solution because
it refuses to backtrack.

• Example (0/1 Knapsack): If items cannot be split into fractions,

picking the highest ratio item first can leave empty space that wastes
capacity, leading to a suboptimal total value.

• Example (Coin Change Problem): Given coin denominations of {1, 3,

4} and a target of 6. A greedy approach picks 4, leaving 2 (requiring two
1s), resulting in 3 coins (4+1+1). However, the optimal solution is 2
coins (3+3).

5. Complexity Analysis

• Time Complexity: Generally highly efficient, often dominated by

sorting the input data (O(nlogn)) or traversing structures (O(V + E)).

• Space Complexity: Typically O(1) or O(n) to store structural data,

making it very memory efficient.

Q2. Describe the algorithm for maximum weight independent

set.
1. Introduction to the Problem

The Maximum Weight Independent Set (MWIS) problem looks for a set of
vertices in a graph where no two vertices are adjacent, and the sum of their
weights is maximized.

• Complexity: For general graphs, finding the MWIS is an NP-hard

problem.

• Optimal Solution: However, for a Path Graph (a sequence of vertices

connected linearly) or trees, the problem can be solved efficiently in
polynomial time using Dynamic Programming (DP).

2. Dynamic Programming Formulations (Path Graph)

Let the vertices of a path graph be V={v1,v2,……vn} in order, with corresponding

positive weights w1,w2,…..wn. Let MWIS(i) be the maximum weight
independent set achievable using only the first i vertices.

The Deciding Substructure:

When evaluating the i-th vertex (v_i), we have exactly two mutually exclusive
choices:

1. Exclude v_i: If we do not include v_i, the max weight is simply the
optimal solution for the first i-1 vertices -> MWIS(i-1).

2. Include v_i: If we include v_i, we cannot include its immediate

neighbor v_{i-1}. Therefore, the max weight is v_i's weight plus the
optimal solution for the first i-2 vertices -> w_i + MWIS(i-2).

Recurrence Relation:

MWIS(i) = ( MWIS(i-1), wi + MWIS(i-2) )

Base Cases:

• MWIS(0) = 0 (No vertices)

• MWIS(1) = w_1 (Only the first vertex)

3. Step-by-Step Algorithm

The algorithm is split into two phases: computing the max weight (Forward
Phase) and reconstructing the actual set of vertices (Backtracking Phase).

Phase 1: Compute Maximum Weight

1. Create a 1D array DP of size n+1.

2. Initialize base cases: DP[0] = 0 and DP[1] = w[1].

3. For i from 2 to n:
 DP}[i] = \max(DP}[i-1], w[i] + DP}[i-2])

4. The value in DP[n] will hold the absolute maximum weight.

Phase 2: Reconstruction (Backtracking)

To find which vertices made the cut, trace backward from n:

1. Initialize an empty set S. Set i = n.

2. While i <= 1:

o If DP[i-1] <=w[i] + DP[i-2], then v_i was excluded. Set i = i - 1.

o Else, v_i was included. Add v_i to S, and set i = i - 2 (skipping its
neighbor).

3. Return set S.

4. Complexity Analysis

• Time Complexity: O(n). The forward loop runs n times, and the
backtracking loop processes at most n elements, making it strictly
linear time.

• Space Complexity: O(n) to store the dynamic programming array table.

(Can be optimized to O(1) if only tracking values, though O(n) is required
to reconstruct the path).

Q3. Explain minimum spanning tree and its applications.

1. Definition of a Minimum Spanning Tree (MST)
Given a connected and undirected graph G = (V, E) with weighted
edges, a Spanning Tree is a subgraph that connects all the
vertices (V) together using the minimum possible number of edges
(V - 1), without forming any cycles.
A Minimum Spanning Tree (MST) is the spanning tree that
minimizes the total sum of the edge weights among all possible
spanning trees of that graph.
Key Properties:
• Vertices and Edges: If a graph has V vertices, its MST will
have exactly V - 1 edges.
• Acyclic: Removing any edge from an MST disconnects the
graph; adding any edge creates a cycle.
A Minimum Spanning T ree (MST ) is a subset of edges from a connected, undirected, weighted graph that

connects all vertices without cycles and with the smallest possible total edge weight. MSTs are widely used in

network design, clustering, and routing.

T wo popular algorithms to find MSTs are Kruskal’s and Prim’s

 • Uniqueness: If all edge weights in the graph are unique, the
graph has exactly one unique MST.
2. Algorithms to Find an MST
Two classic greedy algorithms are used to compute the MST of a
graph in O(ElogV) time:
1. Kruskal’s Algorithm: An edge-centric approach. It sorts all
edges by weight in ascending order and greedily adds the
smallest edge, provided it doesn't form a cycle (managed
using a Disjoint-Set Data Structure).
2. Prim’s Algorithm: A vertex-centric approach. It starts from
an arbitrary seed vertex and grows the tree one vertex at a
time by greedily choosing the cheapest outgoing edge
connecting a visited vertex to an unvisited vertex.
3. Real-World Applications of MST
MSTs are fundamental to optimizing network layouts where
physical deployment costs must be minimized. Major applications
include:
• Infrastructure Network Design:
o Telecommunications: Laying down fiber-optic cables
or telephone wires to connect a set of cities with the
minimum length of cable.
o Utility Piping: Designing efficient layouts for electrical
grids, water supply pipelines, or gas networks across
neighborhoods.
• Approximation of NP-Hard Problems:
o The MST is used as a foundational step to build
approximation algorithms for highly complex problems
like the Traveling Salesperson Problem (TSP) (e.g.,
Christofides' algorithm).
• Cluster Analysis in Data Mining:
 o In unsupervised machine learning, an MST can be used
to construct a single-linkage hierarchical clustering
tree. Erasing the heaviest edges splits the dataset into
distinct, natural clusters.
• Computer Vision and Image Segmentation:
o Images can be modeled as graphs where pixels are
vertices and edge weights represent differences in pixel
intensity. Building an MST helps isolate structural
boundaries and segment objects out of the background
image.
4. Complexity Summary

Kruskal's Prim's Algorithm (using

Metric
Algorithm Binary Heap)

Time O(ElogE) or
O(ElogV)
Complexity O(ElogV)

Space
O(V + E) O(V)
Complexity

Q4. Describe maximum matching and augmenting paths.

1. What is a Maximum Matching?

In graph theory, a matching (or independent edge set) is a set of edges

selected such that no two edges share a common vertex. A vertex is considered
matched if it is an endpoint of an edge in the matching; otherwise, it is free or
unmatched.

• Maximum Matching: This represents a matching that contains the

largest possible number of edges for a given graph. It achieves the
absolute global maximum cardinality.
 • Distinct from Maximal Matching: A maximal matching is simply a
state where you cannot add any more edges without breaking the rules.
Every maximum matching is maximal, but not every maximal matching
is a maximum matching.

2. What is an Augmenting Path?

To understand an augmenting path, we must first define an alternating path.

An alternating path is a path whose edges strictly alternate between edges not
in the matching and edges in the matching.

An augmenting path is a special type of alternating path that:

1. Starts at an unmatched (free) vertex.

2. Alternates its edges between unmatched and matched states.

3. Ends at a different unmatched (free) vertex.

Because it begins and ends with an unmatched edge, an augmenting path

will always contain exactly one more unmatched edge than matched edges.

3. The Relationship: Berge’s Lemma

The core connection between these two concepts is defined by Berge’s

Lemma, which states:

"A matching M in a graph G is a maximum matching if and only if there is no

augmenting path relative to M."

If an augmenting path is found, the current matching is guaranteed not to be

maximum.

4. How Augmenting Paths are Used to Find Maximum Matching

Augmenting paths serve as the primary mechanism for driving optimization

algorithms (like the Hopcroft-Karp algorithm for bipartite graphs or
Edmonds' Blossom algorithm for general graphs).

The Augmentation Process:

1. Discover: Search the graph to locate an augmenting path.

2. Invert (Augment): Flip the status of all edges along that path. Change
all unmatched edges to matched, and all matched edges to unmatched.

3. Result: Because the path had one extra unmatched edge, this inversion
flip systematically increases the total edge count of the overall matching
by exactly 1, while keeping all vertex constraints valid.

4. Loop: Repeat the process until no more augmenting paths can be

found.
5. Complexity Summary

In a bipartite graph G = (V, E), finding maximum matching via augmenting

paths using the Hopcroft-Karp algorithm yields:

• Time Complexity: O(|E| \sqrt{|V|})

• Space Complexity: O(|V|) to track the matching states and paths.

UNIT-3
PART-A
Q1. State the max-flow min-cut the
The Max-Flow Min-Cut Theorem states that in a flow network, the maximum
amount of flow passing from the source to the sink is equal to the total weight
(capacity) of the edges in a minimum cut.

Maximum Flow Value} = Capacity of Minimum Cut}

Key Concepts

• Max-Flow: The highest possible rate at which fluid/data can safely be

routed from the start (source) to the end (sink) without exceeding edge
limits.

• Min-Cut: The specific set of edges with the smallest combined capacity
whose removal completely disconnects the source from the sink,
forming a system bottleneck.

Q2. What is Strassen’s matrix multiplication?

Strassen’s Matrix Multiplication is a divide-and-conquer algorithm used to
multiply two square matrices. It improves upon the standard row-by-column
multiplication approach by reducing the total number of required scalar
multiplications for 2 \times 2 submatrices from 8 down to 7.

Key Property

• Time Complexity: By minimizing multiplications, it reduces the

algorithmic runtime from the standard O(n^3) down to approximately
O(n^{2.81}) (specifically O(n^{\log_2 7})), making it significantly faster
for large datasets.

Q3. What is residual graph in flow networks?

A residual graph (or residual network) is an auxiliary graph G_f used in
network flow algorithms (like Ford-Fulkerson) to track the remaining capacity
available along edges in a flow network. It indicates how much additional flow
can be pushed through the network based on the current flow assignment.

Key Properties

• Forward Edges: Represent the remaining capacity available to push

more flow forward (Capacity - Current Flow).

• Backward Edges: Represent the amount of existing flow that can be

pushed backward or "undone" (Current Flow), allowing the algorithm to
reverse suboptimal routing decisions.

Q4. What is triangular matrix?

A triangular matrix is a special type of square matrix where all the entries
either above or below the main diagonal are equal to zero.

Types

• Upper Triangular Matrix: A matrix where all entries below the main
diagonal are zero.

• Lower Triangular Matrix: A matrix where all entries above the main
diagonal are zero.

Example (Upper Triangular):

PART-B
[Link] Ford-Fulkerson method for maximum flow.
1. Introduction to the Ford-Fulkerson Method

The Ford-Fulkerson method is an iterative algorithm used to calculate the

maximum flow in a flow network. It operates on a directed graph containing
a designated source (s) node and a sink (t) node, where each edge has a
specified maximum capacity.

It is referred to as a "method" rather than an algorithm because it does not

define a specific way to find the paths, allowing for multiple implementations
(such as the Edmonds-Karp algorithm, which uses BFS).

2. Key Underlying Concepts

To understand the method, three core concepts must be defined:

The Ford-Fulkerson method finds the maximum flow in a network by iteratively augmenting paths

from source to sink until no more flow can be pushed

 • Residual Capacity: The remaining capacity of an edge after some flow
has been directed through it. For a forward edge, it is (Capacity - Flow}).

• Residual Graph (Gf): An auxiliary graph that shows the current state
of available capacities. It includes both forward edges (remaining
capacity to push flow) and backward edges (current flow that can be
cancelled or redirected).

• Augmenting Path: A simple path from the source s to the sink t in the
residual graph along which additional flow can be pushed.

3. Step-by-Step Algorithm

The method works by continually pushing flow through valid paths until no
more paths exist:

1. Initialization: Initialize the flow on all edges in the network to 0.

2. Find Path: Search the residual graph Gf to find an augmenting path

from source s to sink t.

3. Determine Bottleneck: Find the minimum residual capacity along the

chosen augmenting path. Let this bottleneck value be cf(P).

4. Update Flow: Augment the network flow by updating the edges along
the path:

o For each forward edge, add the bottleneck value: flow = flow +
cf(P).

o For each backward edge, subtract the bottleneck value: flow =

flow– cf(P).

5. Loop & Terminate: Reconstruct the residual graph Gf based on the

new flows and repeat from Step 2. If no augmenting path can be found,
the loop terminates, and the current flow is the maximum flow.

4. Illustrative Execution Diagram

5. Complexity Analysis

• Time Complexity: O(E . f*), where E is the number of edges and f* is

the maximum flow value. In worst-case scenarios with integer
capacities, the algorithm might increase the flow by only 1 unit per
iteration.

• Space Complexity: O(V + E) to maintain the data structures for the

residual graph and graph traversal tracking (such as a queue or stack)
Applications

The Ford-Fulkerson method is widely used in:

Network traffic optimization

Transportation and logistics

Supply chain management

Water distribution and pipeline systems

Airline scheduling and resource allocation

Q2. Discuss Edmonds-Karp algorithm with complexity
analysis.
1. Introduction to the Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is a specific, highly efficient implementation

of the Ford-Fulkerson method used to compute the maximum flow in a flow
network.

While the general Ford-Fulkerson method leaves the choice of finding an

augmenting path open (which can lead to poor performance), Edmonds-Karp
explicitly dictates that Breadth-First Search (BFS) must be used to select the
path. It always chooses the shortest augmenting path from the source (s) to
the sink (t) in terms of the number of edges, regardless of capacity.

2. Step-by-Step Algorithm

1. Initialize: Set the initial flow on all edges to 0. Construct the initial
residual graph (Gf).

2. BFS Traversal: Run a BFS on the residual graph Gf starting from the
source s to find the shortest path to the sink t.

3. Check Termination: If no augmenting path is found by the BFS,

terminate. The current flow is the maximum flow.

4. Identify Bottleneck: Find the minimum residual capacity (bottleneck,

cf) among the edges along the path found by BFS.

5. Augment Flow: Update the flow network along the path:

o Add the bottleneck value to the forward edges.

o Subtract the bottleneck value from the backward edges (to allow
for flow redirection).

6. Repeat: Reconstruct the updated residual graph and loop back to Step
2.

3. Why BFS is Used (The Core Improvement)

Using BFS provides a crucial algorithmic guarantee: the distance to any

vertex in the residual graph increases monotonically (never decreases)
across iterations.

By picking the shortest path in terms of edge count, the algorithm prevents
the "ping-pong" behavior seen in standard Ford-Fulkerson (where flow can
bounce back and forth along a bottleneck edge indefinitely). This removes
dependency on the actual capacity values, ensuring the algorithm terminates
efficiently even with massive edge capacities.
4. Complexity Analysis

Time Complexity: O(V.E2)

• Cost of an Iteration: Each path discovery step uses BFS, which takes
O(V + E) = O(E) time for a connected flow network.

• Number of Augmentations: An edge is called "critical" if it is the

bottleneck on an augmenting path. An edge can become critical at most
O(V) times because each time it disappears and reappears, the shortest
path length from s to t must increase. Since there are E edges, the total
number of augmenting paths discovered is bounded by O(V.E).

• Total Time:Number of paths X BFS Cost = O(V.E) X O(E) = O(V.E2)}.

Space Complexity: O(V + E)

• Required to maintain the capacity tables, current flow tracking, and the
FIFO queue structure used by the BFS traversal.

5. Comparison Summary

General Ford-
Metric Edmonds-Karp
Fulkerson

Path Selection Any arbitrary path Strictly BFS (Shortest edge-

Strategy (DFS/BFS) count path)

Termination Depends on edge Independent of capacities;

Dependency capacities (f*) strictly structural

O(E.f*) (Can loop O(V.E2) (Guaranteed upper

Worst-Case Time
heavily) bound)

Q3. Explain Strassen’s algorithm for matrix multiplication.

1. Introduction to Strassen's Algorithm

Strassen’s Algorithm is a divide-and-conquer algorithm designed by Volker

Strassen in 1969 to multiply two square matrices of size n \times n.
 • The Standard Approach: The traditional row-by-column method
requires 8 scalar multiplications and 4 additions for a 2 \times 2
submatrix matrix block, resulting in a time complexity of O(n^3).

• The Strassen Improvement: Strassen observed that scalar

multiplication is computationally more expensive than addition. His
algorithm algebraically rearranges the terms to perform the
multiplication using only 7 scalar multiplications and 18 additions,
optimizing the overall runtime.

2. Core Mathematical Working (For a 2 x 2 Matrix)

Consider multiplying two 2 x 2 matrices, A and B, to produce matrix C:

Strassen’s algorithm computes 7 specific formulas (P_1 to P_7) using a single

multiplication each:

The final submatrices of C are then calculated using only additions and
subtractions of these intermediate values:

3. Step-by-Step Divide and Conquer Algorithm

For large matrices of size n \times n, the process is implemented recursively:

 1. Divide: Split the input matrices A and B into 4 submatrices of size n/2
\times n/2 each.

2. Compute Additions: Calculate the 14 linear additions/subtractions of

the submatrices needed for the formulas.

3. Conquer (Multiply Recursively): Recursively compute the 7 matrix

products (P_1 to P_7) using Strassen’s equations.

4. Combine: Add and subtract the products to construct the 4 quadrants

of the final product matrix C.

4. Complexity Analysis

Time Complexity: nlogba = nlog27 = n2.81

The recurrence relation for Strassen’s algorithm is:

T(n)=aT(n/b)+f(n)

Applying Case 1 of the Master Theorem:

• a = 7, b = 2, and f(n) = O(n2)

• Compare nlogba = nlog27 ≈ n2.81 with f(n) = n2.

• Since n2.81 dominates, the final time complexity is O(n2.81). This is

asymptotically faster than the standard O(n3) approach for large values
of n.

Space Complexity: O(n2)

Requires extra auxiliary memory at each recursive tier to store the submatrix
combinations and intermediate products (P1 to P7).

5. Limitations of Strassen’s Algorithm

• Overhead: For smaller matrices (typically n < 32 or 64), the high

number of additions (18 vs 4) introduces structural overhead that
makes it slower than traditional multiplication.

• Numerical Stability: It is less numerically stable than the standard

method due to the accumulation of rounding errors during aggressive
component cross-subtractions.

Q4. Describe LUP decomposition and its applications.

1. What is LUP Decomposition?

LUP Decomposition (or LU decomposition with partial pivoting) is an

algorithm that factors any non-singular square matrix A into the product of
three specific matrices:
PA = LU

• L (Lower Triangular Matrix): A matrix where all entries above the main
diagonal are zero, and the diagonal entries are typically equal to 1 (unit
lower triangular).

• U (Upper Triangular Matrix): A matrix where all entries below the main
diagonal are zero.

• P (Permutation Matrix): A row-switching matrix consisting of 0s and

1s. Multiplying A by P rearranges the rows of A to ensure numerical
stability during computation.

2. Why the Permutation Matrix (P) is Necessary

In standard LU decomposition (A = LU), the algorithm can fail completely if a

diagonal element (pivot) becomes zero during computation, as it leads to a
division-by-zero error.

LUP decomposition solves this through partial pivoting. At each step, it

identifies the largest absolute value in the current column and swaps that
row to the pivot position. The permutation matrix P keeps a strict
mathematical record of these row swaps, which minimizes round-off errors
and prevents algorithmic failure.

3. How to Solve Linear Systems Using LUP

Once a matrix A is decomposed into P, L, and U, solving a system of linear

equations Ax = b becomes highly efficient and can be completed in two simple
steps:

1. Forward Substitution: Substitute PA = LU into the equation to get LUx

= Pb. Let Ux = y. Now, solve the lower triangular system Ly = Pb for y.

2. Back Substitution: Once y is found, solve the upper triangular system

Ux = y to find the final variable vector x.

4. Key Real-World Applications

• Solving Systems of Linear Equations: It is the standard industry

method for solving Ax = b when the same coefficient matrix A must be
evaluated against multiple different output vectors b.

• Computing the Matrix Inverse (A^{-1}): The inverse of a matrix can be

calculated column-by-column by solving the LUP equation Ax = b_i,
where b_i represents successive columns of the Identity matrix (I).

• Calculating Determinants Efficiently: Computing the determinant of

a large matrix directly is computationally expensive. With LUP, because
 the determinant of a triangular matrix is simply the product of its
diagonal elements, it simplifies to:

• Geodesic and Structural Engineering: Used in computer-aided

engineering software to calculate stress, strain, and load distributions
across complex infrastructure frameworks.

5. Complexity Analysis

• Decomposition Phase (PA = LU): Requires O(n^3) time complexity to

compute the initial matrix factorization.

• Substitution Phase (Forward/Back): Requires only O(n^2) time

complexity to solve for x.

UNIT-4
PART-A
Q1. What is dynamic programming?
Dynamic Programming (DP) is an algorithmic design paradigm used to solve
complex optimization problems by breaking them down into simpler,
overlapping subproblems. It solves each subproblem exactly once and stores
its result in a table (like an array or hash map) to avoid redundant
computations.

Key Properties

To apply dynamic programming, a problem must exhibit two core properties:

1. Optimal Substructure: The optimal solution to the overall problem can

be constructed from the optimal solutions of its subproblems.

2. Overlapping Subproblems: The problem recursively reuses the same

subproblems multiple times rather than generating brand-new ones.

Q2. Define Chinese Remainder Theorem.

The Chinese Remainder Theorem (CRT) is a fundamental theorem in
number theory and cryptography. It states that if a set of positive integers m1,
m2,…. Mk are pairwise coprime (meaning gcd(mi, mj) = 1 for all i != j), then
any system of simultaneous linear congruences:
If you have an unknown number, and you only know its remainders when divided by several different

numbers (which must be pairwise coprime, meaning they share no common factors other than 1), CRT

guarantees that a unique solution exists within a certain range

Key Application

• It is widely used to speed up modular arithmetic and big-integer

computations in cryptography (such as optimizing RSA decryption).

Q3. What is Floyd-Warshall algorithm used for?

Purpose
The Floyd-Warshall algorithm is a dynamic programming algorithm used to
find the all-pairs shortest paths in a weighted, directed graph. This means it
computes the absolute shortest distance between every single pair of vertices
in the graph simultaneously.

Key Features

• Negative Weights: It can handle graphs with negative edge weights,

unlike Dijkstra's algorithm.

• Negative Cycle Detection: It can be used to detect the presence of

negative weight cycles (if the distance from any vertex to itself becomes
negative, a negative cycle exists).

• Complexity: It operates with a time complexity of O(V3) and a space

complexity of O(V2), where V is the number of vertices.

Q4. Define Discrete Fourier Transform (DFT).

The Discrete Fourier Transform (DFT) is a mathematical transform that
converts a discrete sequence of data sampled over time or space into its
constituent frequencies in the frequency domain.

For a sequence of N complex numbers xn, the DFT is defined by the formula:
Key Application

• It is the foundation of digital signal processing (DSP), used extensively

for filtering, audio processing, image compression (like JPEG), and
spectral analysis.

PART-B
Q1. Explain Floyd-Warshall algorithm with an example
1. Introduction to the Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming algorithm used

to solve the all-pairs shortest path problem in a weighted, directed graph. It
computes the shortest paths between every pair of vertices simultaneously.

• Capabilities: It can handle graphs with negative edge weights.

• Constraint: It cannot function if the graph contains a negative weight

cycle, but it can be used to detect them (if any diagonal element A[i][i]
becomes negative).

2. Core Working Principle

The algorithm works by incrementally considering each vertex k in the graph

as a potential intermediate node on a path between two other vertices, i and
j.

For every pair of vertices (i, j), the algorithm checks if passing through k offers
a shorter path than the currently recorded distance.
The Recurrence Relation:

3. Illustrative Example

Consider a weighted, directed graph with 3 vertices (1, 2, 3):

• Edges and Weights: (1 -> 3) = 11, (2 -> 1) = 4, (2 -> 3) = 2, (3 ->1) = 3.

• Note: Direct paths to self are 0, and missing direct paths are set to infinity
(\infty).
4. Complexity Analysis

• Time Complexity: \Theta(V^3). The algorithm uses three nested loops

(each running V times) to update the matrix, making its performance
independent of the number of edges.

• Space Complexity: \Theta(V^2) to store the 2D distance matrix.

Q2. Discuss dynamic programming paradigm with examples.

1. Introduction to Dynamic Programming

Dynamic Programming (DP) is an algorithmic design paradigm used to solve

complex optimization problems by breaking them down into simpler, smaller
subproblems.

Instead of recomputing the answers to these subproblems repeatedly, DP

solves each subproblem exactly once and stores the results in a lookup table
(an array, matrix, or hash map). This core technique of reusing previously
computed values is what differentiates DP from basic recursion.

2. Core Properties for Success

A problem can be solved using the dynamic programming paradigm if and

only if it exhibits two fundamental properties:

1. Overlapping Subproblems: The recursive solution to the problem

involves solving the exact same subproblems multiple times.

2. Optimal Substructure: The optimal solution to the overall, larger

problem can be constructed efficiently from the optimal solutions of its
smaller subproblems.

3. Implementation Approaches

Dynamic Programming can be implemented using two distinct strategies:

• Top-Down Approach (Memoization): This is an extension of standard

recursion. The algorithm solves the problem recursively but checks the
lookup table first. If the subproblem has already been solved, it returns
the cached result; otherwise, it computes it and saves it.
recursion means calling the function itself while caching means storing the intermediate results
 avoids recursions there is no stack overflow issue and no overhead of the recursive functions

• Bottom-Up Approach (Tabulation): This is an iterative approach. It

avoids recursion entirely by solving the smallest possible subproblems
first, filling a table (typically a 1D or 2D array) from the bottom up, and
using those values to solve progressively larger subproblems.

4. Standard Examples

Example 1: The Fibonacci Sequence

• Problem: Find the n-th Fibonacci number, where F(n) = F(n-1) + F(n-
2).

• Why Naive Recursion Fails: A simple recursive approach takes

exponential time (O(2^n)) because it recalculates branches like F(n-2)
multiple times.

• DP Solution: Using a 1D array of size n+1, we initialize base cases DP[0]

= 0 and DP[1] = 1. We then iteratively compute values using a simple
loop up to n. This transitions the execution runtime down to a highly
efficient linear time (O(n)).

Example 2: The 0/1 Knapsack Problem

• Problem: Given n items, each with a specific weight and value, choose
a subset of items to maximize total value without exceeding a maximum
knapsack weight capacity W. Items cannot be divided.

• DP Solution: This utilizes a 2D table DP[i][w], representing the

maximum value achievable using the first i items with a temporary
weight limit w. The recurrence relation builds the table by making a
choice for each item:

DP[i][w] =max(DP[i-1][w], vi + DP[i-1][w – wi])

5. Complexity Summary

• Time Complexity: Drastically reduced compared to naive recursion.

For instance, Fibonacci drops from O(2^n) to O(n), and 0/1 Knapsack
runs in O(n.W) time.

• Space Complexity: Typically O(n) or O(n. m) due to the allocation of

auxiliary memory required for the memoization table or tabulation grid.

[Link] Chinese Remainder Theorem and its applications.

1. Introduction to the Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a fundamental theorem in

number theory and abstract algebra. It states that if a set of positive integers
3. Real-World and Algorithmic Applications

The CRT allows large, computationally heavy calculations to be broken down

into smaller, independent parallel components. Its primary applications
include:

• RSA Decryption Optimization: In cryptography, the RSA decryption

process requires computing massive modular exponentiations

(Cd (mod N), where N = p.q). Using CRT, this single operation is split
into two much smaller, faster operations modulo p and modulo q,
reducing computation time by nearly 75%.

• Big Integer Arithmetic: Computers can process numbers up to 32 or

64 bits natively. For arithmetic involving massive integers, numbers can
be represented by their remainders relative to a set of small coprime
moduli. Calculations (addition, multiplication) are performed quickly on
these smaller remainders, and the final giant result is reconstructed via
CRT.

• Secret Sharing Schemes: Used in cybersecurity protocols (like

Shamir's Secret Sharing threshold schemes). A sensitive cryptographic
key can be split into multiple pieces (congruences) distributed to
different individuals. The master key can only be recovered when a
required number of individuals combine their remainders to solve the
CRT system.

• Digital Signal Processing (DSP): Used to optimize fast convolution

algorithms and the Fast Fourier Transform (FFT) by breaking down a
large multi-dimensional signal array into smaller, independent array
dimensions based on coprime index lengths.
4. Complexity & Advantage

• Time Complexity: Reconstructing the solution x takes O(k \log M) time

using the Extended Euclidean Algorithm to calculate the modular
inverses.

• Key Advantage: It completely eliminates the need to work directly with

dangerously large numbers during intermediate processing stages,
making systems significantly faster and preventing memory overflow.

[Link] Fast Fourier Transform (FFT) and its significance.

Here is a structured, 5-mark exam-style answer describing the Fast Fourier
Transform (FFT) and its significance.

1. What is the Fast Fourier Transform (FFT)?

The Fast Fourier Transform (FFT) is not a new transform itself, but rather a
highly efficient, optimized algorithm used to compute the Discrete Fourier
Transform (DFT) and its inverse.

While the DFT mathematically converts a signal sampled over time or space
into its constituent components in the frequency domain, a direct calculation
is computationally heavy. The FFT optimizes this process by exploiting the
mathematical symmetries and periodicity of the complex exponential terms
(roots of unity, denoted as W_N^{kn}).

2. Core Working Principle (Cooley-Tukey Algorithm)

The most common FFT implementation is the Cooley-Tukey algorithm,

which utilizes a Divide and Conquer paradigm.

Assuming the number of data samples N is a power of 2 (known as Radix-2

FFT), the algorithm works as follows:

1. Divide: It splits the original N-point time-domain sequence into two

smaller subsequences of size N/2: one consisting of the even-indexed
samples and the other of the odd-indexed samples.

2. Conquer: It recursively computes the DFTs of these smaller N/2 sub-

sequences.

3. Combine: It merges the results back together using a strict

mathematical structure called a "Butterfly Diagram", which reuses
calculated intermediate values to generate the final frequency
spectrum.
3. Computational Complexity Comparison

The true brilliance of the FFT lies in its dramatic reduction of computational
overhead:

• Direct DFT Complexity: A standard DFT requires nested loops where

every single output point relies on every single input point. This
demands O(N2) complex multiplications and additions.

• FFT Complexity: By breaking down the problem recursively, the FFT

reduces the number of operations to O(N log2 N).

Impact of the Optimization:

If you process a relatively standard signal containing N = 1,024 samples:

• Direct DFT requires: 10242 =1048576 operations.

• FFT requires: 1024 x log2(1024)+ 1024 x 10 = 10240 operations

• Result: The FFT is roughly 100 times faster for this small sample size,
and this performance gap widens exponentially as N grows.

4. Engineering & Real-World Significance

The introduction of the FFT is widely considered one of the most important
algorithmic breakthroughs of the 20th century because it made real-time
digital signal processing practically possible. Its core areas of significance
include:

• Audio and Video Compression: Modern multimedia formats like MP3,

AAC, and JPEG rely heavily on frequency domain manipulation. The
FFT enables these algorithms to rapidly isolate and remove
imperceptible high-frequency data to shrink file sizes.

• Telecommunications (OFDM & 5G): High-speed wireless networks

use Orthogonal Frequency Division Multiplexing (OFDM). The FFT is
embedded directly into hardware chipsets to modulate and demodulate
digital data across thousands of parallel sub-carrier frequencies
simultaneously.

• Medical Imaging (MRI and CT Scans): Medical scanners capture raw

spatial frequency data. The FFT is used to reconstruct these complex
mathematical signals into clear, recognizable 2D and 3D visual images
of human anatomy.
 • Fast Polynomial Multiplication: In computer algebra systems,
multiplying two polynomials of degree n traditionally takes O(n^2) time.
By converting the coefficients to the frequency domain using FFT,
multiplying them, and converting back, the complexity drops to O(n
\log n).

5. Summary Table

Discrete Fourier Fast Fourier Transform

Metric
Transform (DFT) (FFT)

Nature Mathematical Definition Algorithmic Optimization

Divide-and-Conquer
Approach Brute-force row-by-column
Recursion

Time O(N2) (Infeasible for real- O(N log N) (Highly viable for
Complexity time systems) real-time)