ADVANCED ALGORITHMS

Unit-Wise Breakdown

UNIT I – Basic Algorithms

 Sorting: Review of sorting and topological sorting.
 Graph Algorithms: BFS, Dijkstra’s, DFS, Strongly Connected
Components, time/space analysis, amortized analysis.

UNIT II – Matroid’s & Matching

 Matroids: Greedy algorithms, max-weight independent set, MST
applications.
 Graph Matching: Max matching, augmenting path, Edmond’s Blossom
Algorithm.

UNIT III – Flow and Matrix

 Flow Networks: Maxflow-MinCut, Ford-Fulkerson, Edmond-Karp
algorithms.
 Matrix Computations: Strassen’s algorithm, divide-and-conquer, matrix
inverse, triangular matrix, LUP decomposition.
UNIT IV – Advanced Topics

 Shortest Path: Floyd-Warshall, dynamic programming examples.

 Modulo Representations: Chinese Remainder Theorem, base/modulo
conversion, polynomial applications.
 DFT: DFT in complex/modulo ring, FFT, Schönhage–Strassen algorithm.

UNIT V – LP & Complexity

 Linear Programming: Feasibility region, Simplex algorithm.
 NP-Completeness: NP-hardness proofs and examples.
UNIT I – Basic Algorithms
Sorting Algorithms Review
🔹 Common Sorting Algorithms:
1. Bubble Sort
 Repeatedly swaps adjacent elements if they are in the wrong order.
 Time Complexity: O(n²)
 Best Use: Educational purposes; not used in practice.
2. Insertion Sort
 Builds sorted list one item at a time, like sorting playing cards.
 Time Complexity: O(n²), but O(n) if the list is nearly sorted.
3. Selection Sort
 Finds the minimum and swaps it to the front repeatedly.
 Time Complexity: O(n²)
4. Merge Sort
 Divide-and-conquer technique. Recursively splits the list and merges them in
sorted order.
 Time Complexity: O(n log n)
 Space Complexity: O(n)
 Stable? Yes
5. Quick Sort
 Picks a pivot, partitions the list around the pivot, and sorts recursively.
 Time Complexity: O(n log n) average, O(n²) worst-case
 In-place? Yes
 Stable? No
6. Heap Sort
 Uses binary heap to sort elements.
 Time Complexity: O(n log n)
 Space Complexity: O(1)
 Stable? No
7. Counting Sort
 Non-comparison-based sort for integers.
 Time Complexity: O(n + k) where k is the range of input.
 Stable? Yes
 Efficient for: Small range of integers
🔹 Topological Sorting
 Used for: Directed Acyclic Graphs (DAGs)
 Definition: A linear ordering of vertices such that for every directed edge u → v,
vertex u appears before v.
 Applications: Task scheduling, dependency resolution
 Algorithms:
 Kahn’s Algorithm (BFS-based)
 DFS-based (Post-order, reverse of finishing time)
Graph Algorithms

1. Breadth-First Search (BFS)

 Explores graph level by level.

 Uses: Shortest path in unweighted graphs, connectivity, bipartiteness.
 Time Complexity: O(V + E)

2. Depth-First Search (DFS)

 Explores as deep as possible before backtracking.

 Uses: Detect cycles, connected components, topological sort.
 Time Complexity: O(V + E)

3. Dijkstra’s Algorithm

 Finds the shortest path from a source vertex to all others in a weighted graph with non-
negative weights.
 Data Structures: Priority Queue / Min-Heap
 Time Complexity:
 O((V + E) log V) with binary heap
 O(V²) with simple arrays

Strongly Connected Components (SCCs)

 A Strongly Connected Component of a directed graph is a maximal set of vertices such

that each vertex is reachable from every other vertex in the same component.
 Algorithms:
 Kosaraju’s Algorithm (Two DFS passes)
 Tarjan’s Algorithm (Single DFS with low-link values)

Analysis Techniques

Time and Space Complexity

 Analyze algorithms using Big O notation.

 Helps compare and choose efficient algorithms.
Amortized Analysis
 Averages the time over a sequence of operations.
 Techniques:
 Aggregate Method
 Accounting Method
 Potential Method
 Example:
 Dynamic array resizing: Insertion is O(1) amortized even though occasional
resizing is O(n).

📌 Summary Table:
Best Worst Average Stable
Algorithm Case Case Case Space ?

Bubble Sort O(n) O(n²) O(n²) O(1) Yes

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

Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes

O(log
Quick Sort O(n log n) O(n²) O(n log n) n) No

Heap Sort O(n log n) O(n log n) O(n log n) O(1) No

Counting
Sort O(n + k) O(n + k) O(n + k) O(k) Yes
PART A: Sorting Algorithms – Diagrams
1. Merge Sort
Diagram:
Original: [38, 27, 43, 3, 9, 82, 10]

Divide:
[38, 27, 43, 3] [9, 82, 10]
[38, 27] [43, 3] [9, 82] [10]
[38] [27] [43] [3] [9] [82] [10]

Merge:
[27, 38] [3, 43] [9, 82] [10]
[3, 27, 38, 43] [9, 10, 82]

Final: [3, 9, 10, 27, 38, 43, 82]

2. Quick Sort
Example with Pivot = 33
[33, 15, 10, 45, 20]

Partition:
Left of pivot: [15, 10, 20]
Pivot: 33
Right of pivot: [45]

Recursively sort left and right parts

3. Topological Sort
Graph:
A → C → D
B → D
Topological Order: A, B, C, D or B, A, C, D

PART B: Graph Algorithms – Diagrams

1. BFS Example
Graph:
A -- B
| |
C -- D
BFS (starting from A): A → B → C → D
2. DFS Example
Graph:
1 → 2 → 3 → 4
↑ ↓
6 ← 5
DFS (from 1): 1 → 2 → 3 → 4 → 5 → 6
3. Dijkstra’s Algorithm
Graph:
(2)
A ------- B
\ /
(1) \ / (3)
\ /
C
From A to all nodes:
 A: 0
 B: 2
 C: 1

UNIT II – Matroids & Graph Matching

PART A: Matroids

What is a Matroid?
 A matroid is a combinatorial structure that generalizes the notion of independence in
vector spaces and graphs.

Matroid Definition:
A matroid is a pair M = (E, ℐ) where:
  E is a finite set (called the ground set)
 ℐ is a collection of subsets of E (called independent sets) satisfying:
1. Hereditary Property: Every subset of an independent set is independent.
2. Non-empty Property: The empty set is independent.
3. Exchange Property: If A and B are independent and |A| > |B|, there exists an
element in A that can be added to B while still being independent.

Greedy Algorithm and Matroids:

Matroids are special because greedy algorithms give optimal solutions for some optimization
problems (e.g., finding maximum weight independent sets).
Greedy Property of Matroids:
If you have a matroid and assign weights to the elements, then a greedy algorithm that repeatedly
selects the highest-weight element that maintains independence gives the optimal solution.

Example 1: Graphic Matroid

 E: Edges of a graph
 ℐ: A subset of edges that form a forest (no cycles)
 The greedy algorithm here is Kruskal’s Algorithm for Minimum Spanning Tree
(MST).
Kruskal’s = Greedy Algorithm for Graphic Matroid

Example 2: Uniform Matroid

 Any subset of up to k elements from a set of n items.
 Useful in selection problems where size is restricted.

Max-Weight Independent Set in Matroids

Problem: Given a matroid and weights on elements, find an independent set of maximum total
weight.
Greedy Algorithm:

Start with empty set S = ∅.

1. Sort elements in decreasing order of weight.
2.
3. Add each element if it doesn’t violate independence.
4. Return S.
Diagram – Kruskal's Algorithm (Graphic Matroid)
Graph:
A---(1)---B
| / |
(3) (2) |
| / |
C---(4)---D

Sorted edges: (1), (2), (3), (4)

Pick edges (1), (2), (3) → MST

PART B: Graph Matching

📌 What is Matching?
In a graph, a matching is a set of edges without common vertices.
 Maximum Matching: Largest possible matching
 Perfect Matching: Every vertex is matched
 Maximum Weight Matching: Maximize sum of weights (weighted graph)

Augmenting Path Algorithm

Step-by-step:
1. Start with an empty matching.
2. Look for augmenting paths (alternating unmatched and matched edges).
3. Flip the edges (augment) to increase the size of the matching.
4. Repeat until no more augmenting paths exist.
Bipartite Graphs:

Use the Hungarian Algorithm or Hopcroft-Karp Algorithm for maximum matching.

Edmonds’ Blossom Algorithm

Used for finding maximum matching in general (non-bipartite) graphs.

Idea:
 Handles odd-length cycles (blossoms) that cause issues in finding augmenting paths.
  Contracts blossoms into a single node, simplifies the graph, finds augmenting path, and
expands the blossom back.

📈 Blossom Diagram:
Odd Cycle:
A---B
\ /
C
/ \
D---E

Contracted to supernode for finding augmenting paths

1. U = {A, B, C}, V = {X, Y, Z}
2. Edges: (A-X), (B-Y), (C-X), (C-Z)
3. For a general graph with an odd cycle, explain how Blossom Algorithm would detect and
contract it.
4. Implement augmenting path matching in Python for a bipartite graph.

UNIT III – Flow Networks & Matrix Computations

PART A: Flow Networks

What is a Flow Network?

A flow network is a directed graph where:
 Each edge (u → v) has a capacity c(u, v) ≥ 0
 There is a source (s) and a sink (t)
 A flow is a function f(u, v) satisfying:
 Capacity Constraint: f(u, v) ≤ c(u, v)
 Skew Symmetry: f(u, v) = -f(v, u)
 Flow Conservation: For all v ≠ s, t, ∑inflow = ∑outflow

Ford-Fulkerson Method

Repeatedly find augmenting paths from s to t and add flow until no more paths exist.
 Uses: Residual graph Gf
 Augmenting Path: A path with available capacity > 0
 Flow Update: Increase flow along forward edges, decrease along backward edges
Time Complexity: O(max flow × E)
Edmonds-Karp Algorithm
An implementation of Ford-Fulkerson using BFS to find the shortest augmenting path (in terms
of number of edges).
 Improves time complexity:
O(V × E²)
 Always finds shortest augmenting path → fewer iterations

Max-Flow Min-Cut Theorem

 A cut divides vertices into two disjoint sets {S, T} such that s ∈ S, t ∈ T
The maximum value of flow from s to t is equal to the minimum capacity of an s–t cut.

 Cut capacity: Sum of capacities of edges from S to T

Diagram – Ford-Fulkerson Example

10 10
s -----> a -----> t
\ | ^
\ 4| |10
\ v |
---> b ----->

Capacities:
s→a:10, s→b:10, a→b:4, a→t:10, b→t:10

Initial flow: 0
Residual graph updated after each augmenting path

PART B: Matrix Computations

Strassen’s Algorithm
A divide-and-conquer algorithm that multiplies two n×n matrices faster than classical O(n³).

Classic Multiplication:
 Time Complexity: O(n³)

Strassen’s Algorithm:
 Reduces 8 multiplications to 7 per recursion level
  Time Complexity: O(n^log₂7) ≈ O(n^2.81)

Divide-and-Conquer Matrix Multiplication

Break matrices into 4 submatrices:

A = |A11 A12| B = |B11 B12|

|A21 A22| |B21 B22|

C = A × B computed using smaller subproblems

Used in Strassen’s method and recursive algorithms.

Matrix Inverse

For matrix A:

 A⁻¹ is such that A × A⁻¹ = I

 For small matrices, compute using Gaussian elimination or adjoint/cofactor method
 For large matrices: Use LU or LUP decomposition

Triangular Matrices

 Upper Triangular: All entries below main diagonal are 0

 Lower Triangular: All entries above main diagonal are 0

Multiplication and solving systems are easier with these forms.

LUP Decomposition

Decomposes a matrix A into:

 L: Lower triangular matrix
 U: Upper triangular matrix
 P: Permutation matrix
Used to solve Ax = b, compute determinants, and inverse.
Steps:
1. Find pivot (max element in column)
2. Swap rows (P)
3. Factor into L and U
Diagram – LUP Decomposition
Given A:
|2 0 2|
|1 1 1|
|3 2 1|

Decomposed into:
P * A = L * U

UNIT IV – Advanced Topics

PART A: Shortest Path – Floyd–Warshall Algorithm

Floyd–Warshall Algorithm
 Solves All-Pairs Shortest Path (APSP) problem.
 Works on both directed/undirected graphs (no negative cycles).
 Dynamic Programming approach.

Idea:
Let dist[i][j] be the shortest path from i to j.
At each step k, update:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

🔹 Time Complexity: O(V³)

🔹 Space Complexity: O(V²)

Example:
Graph:
0 → 1 (3)
0 → 2 (8)
1 → 2 (2)
2 → 0 (1)
Initial Matrix:
[0 3 8]
[INF 0 2]
[1 INF 0]
After applying Floyd–Warshall: shortest distances between all node pairs.
Other Dynamic Programming Examples
1. Matrix Chain Multiplication
2. Longest Common Subsequence (LCS)
3. Knapsack Problem
4. Edit Distance

PART B: Modulo Representations

1. Chinese Remainder Theorem (CRT)

Solves system of congruences with pairwise coprime moduli.

🔹 Statement:

If

x ≡ a₁ mod m₁
x ≡ a₂ mod m₂
...
and gcd(mᵢ, mⱼ) = 1, then there exists a unique solution modulo M = m₁·m₂·...·mₙ

🔹 Example:

Solve:

x ≡ 2 mod 3
x ≡ 3 mod 4
x ≡ 2 mod 5
Solution: x = 47 mod 60

2. Base & Modulo Conversion

 Convert a number from base b to decimal and back.
 Modulo Arithmetic: Used for efficient polynomial multiplication and hashing.

🔹 Application:
Fast modulo exponentiation:
Compute a^b mod m in O(log b)
 3. Polynomial Applications
 Use polynomials over finite fields (mod p).
 Applications in:
 Coding theory
 Cryptography (RSA, ECC)
 FFT over finite fields

PART C: Discrete Fourier Transform (DFT), FFT

1. DFT (Discrete Fourier Transform)

Converts a sequence of numbers into frequency domain.

Ak=∑j=0n−1aj⋅ωnjkAk=j=0∑n−1aj⋅ωnjk
For sequence a0,a1,...,an−1a0,a1,...,an−1, DFT produces:

Where ωn=e2πi/nωn=e2πi/n (primitive nth root of unity)

🔹 Complexity: O(n²)

2. FFT (Fast Fourier Transform)

Efficient algorithm to compute DFT in O(n log n) time.

🔹 Applications:
 Polynomial multiplication
 Convolution
 Signal processing

🔹 Divide-and-Conquer Idea:

Split polynomial into even and odd terms:

A(x) = A_even(x²) + x·A_odd(x²)

3. Schönhage–Strassen Algorithm
Fastest known integer multiplication for large inputs (better than FFT for huge n).
  Uses FFT over modulo rings

O(n⋅log⁡n⋅log⁡log⁡n)O(n⋅logn⋅loglogn)
 Time complexity:

📈 Diagrams

📊 Floyd-Warshall DP Table:
Before:
0 3 ∞
∞ 0 2
1 ∞ 0

After:
0 3 5
3 0 2
1 4 0

📊 FFT Tree (n = 4):

a(x) = a0 + a1·x + a2·x² + a3·x³

Divide:
Even: a0, a2
Odd: a1, a3

Recursive FFT calls on both

UNIT V – LP & Complexity

🔷 PART A: Linear Programming (LP)

📌 What is Linear Programming?

Linear Programming is the process of maximizing or minimizing a linear objective function,
subject to a set of linear constraints (equalities or inequalities).
🧮 General Form:
Maximize: Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
Subject to: a₁₁x₁ + a₁₂x₂ + ... ≤ b₁
a₂₁x₁ + a₂₂x₂ + ... ≤ b₂
...
x₁, x₂, ..., xₙ ≥ 0

1. Feasibility Region
 The feasible region is the set of all points that satisfy the constraints.
 Graphically, it's a convex polygon or polyhedron.
 The optimal solution lies at a vertex (corner point) of this region.

📈 Diagram:
x + y ≤ 4
x ≥ 0, y ≥ 0

Feasible region is a triangle bounded by axes and line x + y = 4.

2. Simplex Algorithm
A step-by-step iterative method to find the optimal value at a vertex of the feasible region.

Steps:
1. Convert constraints to equalities using slack variables.
2. Form the initial tableau.
3. Use pivoting to move from one vertex to another with improved objective value.
4. Stop when no further improvement is possible.

⏱ Time Complexity:
 Worst case: Exponential
 Practical performance: Very efficient for most real-world problems

📌 Applications of LP:
 Resource allocation
 Production planning
 Transportation and scheduling
 Network flow optimization
PART B: NP-Completeness

📌 What is NP?
 NP (Nondeterministic Polynomial time): Set of decision problems for which a solution
can be verified in polynomial time.

📌 What is NP-Complete?
A problem is NP-Complete if:
1. It is in NP.
2. Every NP problem can be reduced to it in polynomial time.
These are the “hardest” problems in NP. If any one NP-complete problem can be solved in
polynomial time, then P = NP.

📌 What is NP-Hard?
 A problem is NP-Hard if every problem in NP can be reduced to it.
 NP-Hard ≠ in NP necessarily (may not be decision problems).

🔹 Proving NP-Completeness

Steps:

1. Show the problem is in NP.

2. Reduce a known NP-complete problem (e.g., SAT, 3-SAT, CLIQUE, etc.) to your
problem in polynomial time.
📚 Examples of NP-Complete Problems:
Problem Description

SAT Boolean satisfiability

3-SAT Each clause has exactly 3 literals

Given a graph and number k, is there a clique of

CLIQUE size ≥ k?

Vertex Cover Smallest set of vertices covering all edges

Subset Sum Is there a subset that sums to a target value?

Hamiltonian
Cycle Cycle that visits each vertex exactly once

📈 Diagram – NP Relationships
P ⊆ NP
⎤
⎢ NP-Complete
NP-Hard ⊇ NP-Complete

📌 Summary Table
Concept Key Idea Complexity Use

Pseudo-
LP (Simplex) Iterative improvement polynomial Optimization
 Concept Key Idea Complexity Use

Verifiable in polynomial
NP time - SAT, CLIQUE

NP- Decision
Complete Hardest in NP - problems

May not be
NP-Hard As hard as NP-Complete - decision

UNIT -1

Sorting Algorithms – Detailed Review

🔷 What is Sorting?
Sorting is the process of arranging elements (usually numbers or strings) in a particular order —
typically ascending or descending.

Sorting algorithms are broadly categorized into:

 Comparison-based sorts: Rely on comparisons between elements (e.g., Quick Sort,

Merge Sort).
 Non-comparison sorts: Use properties like counting or digits (e.g., Counting Sort, Radix
Sort).
🔢 1. Bubble Sort

🔹 Description:

Repeatedly swap adjacent elements if they are in the wrong order.

🔹 Algorithm:
for i from 0 to n-1: for j from 0 to n-i-1: if A[j] > A[j+1]: swap A[j],
A[j+1]

🔹 Complexity:
 Best: O(n) (already sorted)
 Worst: O(n²)
 Stable: ✅
 In-place: ✅

🔹 Use: Educational, rarely used in practice.

🔢 2. Selection Sort

🔹 Description:

Select the minimum element and place it at the correct position in each pass.

🔹 Algorithm:
for i in 0 to n-1: min_idx = i for j in i+1 to n: if A[j] < A[min_idx]:
min_idx = j swap A[i] with A[min_idx]

🔹 Complexity:
 Best/Worst/Average: O(n²)
 Stable: ❌
 In-place: ✅
🔢 3. Insertion Sort

🔹 Description:

Builds sorted array one element at a time, similar to sorting playing cards.

🔹 Algorithm:
for i from 1 to n-1: key = A[i] j = i - 1 while j >= 0 and A[j] > key: A[j+1]
= A[j] j -= 1 A[j+1] = key

🔹 Complexity:
 Best: O(n)
 Worst: O(n²)
 Stable: ✅
 In-place: ✅

🔢 4. Merge Sort

🔹 Description:
A divide-and-conquer algorithm that splits the array into halves, sorts, and merges.

🔹 Algorithm:
MergeSort(A): if len(A) > 1: mid = len(A)//2 L = A[:mid] R = A[mid:]
MergeSort(L) MergeSort(R) Merge L and R into A

🔹 Complexity:
 Best/Worst/Average: O(n log n)
 Space: O(n)
 Stable: ✅
 In-place: ❌

🔹 Diagram:
[38, 27, 43, 3]
→ [38, 27] [43, 3]
→ [27, 38] [3, 43]
→ [3, 27, 38, 43]
🔢 5. Quick Sort

🔹 Description:
Choose a pivot, partition the array, and recursively sort left and right subarrays.

🔹 Algorithm (Lomuto partition):

QuickSort(A, low, high): if low < high: pi = partition(A, low, high)
QuickSort(A, low, pi-1) QuickSort(A, pi+1, high)

🔹 Complexity:
 Best/Average: O(n log n)
 Worst: O(n²) (bad pivot)
 In-place: ✅
 Stable: ❌

🔢 6. Heap Sort

🔹 Description:
Build a max heap, then extract max repeatedly and heapify.

🔹 Algorithm:
HeapSort(A): BuildMaxHeap(A) for i = n to 1: swap A[0] with A[i] Heapify(A,
0)

🔹 Complexity:
 All cases: O(n log n)
 In-place: ✅
 Stable: ❌
🔢 7. Counting Sort (Non-comparison)

🔹 Description:

Count the occurrences of each value (assumes integers in a range).

🔹 Algorithm:
count = [0]*(max+1) for i in A: count[i] += 1 for i from 1 to max: count[i]
+= count[i-1] Place elements in output array based on count[]

🔹 Complexity:
 O(n + k), where k is the range of numbers
 Stable: ✅
 In-place: ❌

📊 Summary Table:
Stabl
Algorithm Best Average Worst Space e Type

Compariso
Bubble Sort O(n) O(n²) O(n²) O(1) ✅ n

Insertion Compariso
Sort O(n) O(n²) O(n²) O(1) ✅ n

Selection Compariso
Sort O(n²) O(n²) O(n²) O(1) ❌ n

O(n log O(n log O(n log Compariso

Merge Sort n) n) n) O(n) ✅ n

O(n log O(n log O(log Compariso

Quick Sort n) n) O(n²) n) ❌ n

O(n log O(n log O(n log Compariso

Heap Sort n) n) n) O(1) ❌ n
 Stabl
Algorithm Best Average Worst Space e Type

Counting
Sort O(n + k) O(n + k) O(n + k) O(k) ✅ Non-comp.

Graph Algorithms – Detailed Review

🔷 1. Breadth-First Search (BFS)

📌 Description:
BFS explores all neighbors at the current depth before moving to the next level. It’s useful
for unweighted shortest path and level-order traversal.

🧠 Algorithm:
 Use a queue
 Mark nodes as visited
 Explore neighbors

🧮 Pseudocode:
BFS(graph, start): visited = set() queue = [start] while queue: node =
[Link](0) if node not in visited: visit(node) [Link](node)
[Link](all unvisited neighbors of node)

📈 Example:

Graph:

A → B → D
↓ ↓
C E
BFS(A): A → B → C → D → E

⏱ Complexity:
 Time: O(V + E)
 Space: O(V)
🔷 2. Depth-First Search (DFS)

📌 Description:
DFS explores as far as possible along a branch before backtracking. Useful for topological
sort, cycle detection, and SCCs.

🧮 Pseudocode (Recursive):
DFS(node): mark node visited for each neighbor: if not visited: DFS(neighbor)

📈 Example:

Graph:

1 → 2 → 3
↓ ↑
4 → 5 → 6
DFS(1): 1 → 2 → 3 → 6 → 5 → 4

⏱ Complexity:
 Time: O(V + E)
 Space: O(V)

🔷 3. Dijkstra’s Algorithm

📌 Description:
Finds shortest path from source to all nodes in a weighted graph with non-negative edges.

🔧 Data Structures:
 Priority Queue (Min Heap)
 Distance array

🧮 Pseudocode:
Initialize dist[] = ∞, dist[src] = 0 PQ = [(0, src)] while PQ is not empty:
(d, u) = [Link]() for each neighbor v: if dist[v] > dist[u] + weight(u,v):
dist[v] = dist[u] + weight(u,v) [Link]((dist[v], v))
📈 Example:

Graph:

A → B (4)
A → C (1)
C → B (2)
B → D (1)
C → D (5)
Dijkstra(A):
 A: 0
 B: 3
 C: 1
 D: 4

⏱ Time Complexity:
 With priority queue: O((V + E) log V)

🔷 4. Strongly Connected Components (SCC)

📌 Description:
In a directed graph, a strongly connected component is a maximal subset of vertices such
that each vertex is reachable from every other.

🔹 Kosaraju's Algorithm (2-pass DFS):

1. Do DFS and store finish times.
2. Reverse the graph.
3. DFS on the reversed graph in order of decreasing finish time.

🔹 Tarjan’s Algorithm (Single-pass):

Uses DFS with a stack and low-link values to find SCCs in O(V + E).

📈 Example:

Graph:

1 → 2 → 3 → 1
4 → 5

SCCs:
  [1, 2, 3]
 [4]
 [5]

📊 Summary Table
Directe Weighte Time
Algorithm Purpose d? d? Complexity

Shortest path (unweighted),

BFS reachability ✅ ❌ O(V + E)

DFS Reachability, SCC, Topo sort ✅ ❌ O(V + E)

O((V + E) log
Dijkstra Shortest path (weighted) ✅ ✅ V)

Kosaraju/ Strongly Connected

Tarjan Components ✅ ❌ O(V + E)

Analysis Techniques – Time, Space & Amortized

Analysis

🔷 1. Time Complexity

📌 Definition:
Time complexity describes how the runtime of an algorithm grows with the size of the input.
🔹 Asymptotic Notations:
Notatio Exampl
n Meaning e

Upper bound (worst-

O(f(n)) case) O(n²)

Ω(f(n)) Lower bound (best-case) Ω(n)

Tight bound (average- Θ(n log

Θ(f(n)) case) n)

🔹 Examples:
 Linear Search: O(n)
 Binary Search: O(log n)
 Merge Sort: O(n log n)

🔷 2. Space Complexity

📌 Definition:
Space complexity refers to the total memory space required by an algorithm, including input,
output, and auxiliary space.

🔹 Examples:
 Merge Sort: O(n) extra space
 Quick Sort: O(log n) (recursive stack)
 Bubble Sort: O(1) in-place
🔷 3. Worst, Best, and Average Case

Example (Insertion
Case Meaning Sort)

Worst
Case Longest execution time O(n²) (reverse sorted)
 Example (Insertion
Case Meaning Sort)

Best Case Fastest execution time O(n) (already sorted)

Expected time over all

Average inputs O(n²)

🔷 4. Amortized Analysis

📌 Purpose:
To find average time per operation over a sequence, even when a single operation may be
expensive.
Amortized time ≠ Average-case.
It's a guaranteed bound on sequence cost, not probabilistic.

✅ Useful when:
 Most operations are cheap, a few are costly
 Examples:
 Dynamic Array Resizing
 Incrementing Binary Counters
 Union-Find (Disjoint Set)

🔹 Methods of Amortized Analysis:

🟢 a. Aggregate Method

 Total cost for n operations is T(n)

 Amortized cost = T(n) / n
Example: Stack operations (push, pop, multi-pop)

🟢 b. Accounting Method

 Assign amortized cost per operation

 Overcharge cheap operations to pay for expensive ones
Example: Dynamic Array Resize
 Push cost:
 Normal push: Actual = 1, Amortized = 3
 Resize (double): Actual = n, Amortized = still ≤ 3 per op

🟢 c. Potential Method
 Use a potential function Φ(state) to measure "stored work"
 Amortized Cost = Actual Cost + Change in Potential
c^i=ci+Φ(Di)−Φ(Di−1)c^i=ci+Φ(Di)−Φ(Di−1)

Example:
Binary Counter increment
Potential = number of 1s in binary

📈 Binary Counter Example (Amortized)

 Increment a binary counter from 0 to n
 Some bits flip more than others
Total flips ≤ 2n → amortized O(1) per increment

📊 Summary Table
Technique Purpose Used For

Measure runtime
Time Complexity growth Sorting, searching

Space Complexity Measure memory use Recursion, arrays

Worst/Best/ Input-dependent
Average analysis Algorithm tuning
 Technique Purpose Used For

Amortized Avg. over sequence of Stacks, Hashing, Union-

Analysis ops Find

UNIT II – Matroids & Matching

🔷 Part A: Matroids

📌 What is a Matroid?
A matroid is a mathematical structure that generalizes the idea of linear independence in vector
spaces to more abstract settings (e.g., graphs, sets).

🧠 Formal Definition:
A matroid is a pair M = (E, I) where:
 E is a finite set (called the ground set)
 I is a collection of subsets of E (called independent sets)

1. Non-emptiness: ∅ ∈ I
I must satisfy:

2. Hereditary: If A ∈ I and B ⊆ A ⇒ B ∈ I
3. Exchange Property: If A, B ∈ I and |A| < |B|, then ∃ b ∈ B \ A such that A ∪ {b} ∈ I

📌 Examples of Matroids
1. Graphic Matroid
 E: Edges of a graph
 I: Sets of edges that form forests (acyclic subgraphs)
2. Uniform Matroid
 E: Any set
 I: All subsets of E of size ≤ k
3. Linear Matroid
 E: Vectors
 I: Linearly independent sets
🔹 Greedy Algorithm & Matroids

If a problem forms a matroid, the greedy algorithm gives the optimal solution.

✅ Greedy Strategy:
 Sort elements by weight/priority
 Add to solution if it remains independent

📌 Applications:
 Maximum weight independent set in matroids
 Minimum Spanning Tree is a greedy algorithm over graphic matroids

🔹 MST & Matroids

Kruskal's Algorithm = Greedy on Graphic Matroid

 Always safe to add the smallest edge that doesn’t form a cycle
 This is valid because forests satisfy matroid properties

🔷 Part B: Graph Matching

📌 What is Matching?
In an undirected graph G(V, E), a matching is a subset of edges M ⊆ E such that:
 No two edges in M share a common vertex

🔹 Types of Matchings
Type Description

Matchin
g Set of pairwise non-adjacent edges

Maximal Cannot add more edges without violating

 Type Description

matching

Maximu
m Matching with maximum number of edges

Perfect Every vertex is matched

🔹 Augmenting Path

If it starts and ends with unmatched vertices ⇒ augmenting path

 An alternating path between matched and unmatched edges

Berge’s Theorem: A matching is maximum ⇔ no augmenting path exists




🔹 Algorithm: Greedy + Augmentation

✅ Basic Augmentation:
1. Start with empty matching 2. While an augmenting path exists: Augment the
matching

🔷 Edmonds' Blossom Algorithm

📌 Purpose:
Find maximum matching in general (non-bipartite) graphs.

🔹 Key Idea:
 Standard matching fails in odd cycles ("blossoms")
 Algorithm contracts blossoms into pseudo-vertices
 Recursively finds augmenting paths
📈 Diagram:
Odd cycle: 1–2–3–4–5–1 (blossom)
Contract → single node
Find augmenting path
Expand → recover actual matching

🔹 Time Complexity:
 O(V³)

📊 Summary Table
Complexi
Topic Description Key Algorithm ty

Abstract independence
Matroid structure Greedy O(n log n)

Graphic Matroid Cycles in graphs Kruskal’s O(E log V)

Matching Pairwise disjoint edges Augmenting Path O(EV)

Blossom Edmonds'
Algorithm Matching with odd cycles Algorithm O(V³)

Matroids: Greedy Algorithms, Max-Weight

Independent Set, and MST Applications

🔷 1. What is a Matroid?
A matroid is a combinatorial structure that generalizes the notion of linear independence in
vector spaces and acyclicity in graphs. It helps determine whether a greedy algorithm can find
an optimal solution.
📌 Formal Definition:
A matroid is a pair M=(E,I)M=(E,I), where:
 EE is a finite ground set
 I⊆2EI⊆2E is a family of independent subsets
✅ The family II must satisfy:
1. Non-empty: ∅ ∈ II
2. Hereditary property: If A ∈ II, and B ⊆ A, then B ∈ II
3. Exchange property: If A, B ∈ II and |A| < |B|, then ∃ b ∈ B \ A such that A ∪ {b} ∈ II

🔷 2. Greedy Algorithm in Matroids

📌 Greedy Strategy:
 Sort elements by weight (descending for max-weight)
 Initialize solution set S=∅S=∅
 For each element e∈Ee∈E:
 If S∪{e}∈IS∪{e}∈I, add ee to SS

✅ Theorem:
If a problem can be modeled as a matroid, then the greedy algorithm always produces an
optimal solution.

📌 Example: Max-Weight Independent Set in a Matroid

Problem:
Given a matroid (E,I)(E,I) and a weight function w:E→R+w:E→R+, find the independent
set of maximum weight.
Solution: Use the greedy algorithm:
1. Sort EE by decreasing weight
2. Add elements one by one to the set if they maintain independence
🔷 3. Examples of Matroids
🔹 a. Graphic Matroid
 EE: Edges of a graph
 II: Acyclic subsets of edges (i.e., forests)
Application: Kruskal’s algorithm for Minimum Spanning Tree (MST)

🔹 b. Uniform Matroid
 EE: Any finite set
 II: All subsets of size ≤ k

🔹 c. Linear Matroid
 EE: Set of vectors
 II: Sets of linearly independent vectors

🔷 4. Minimum Spanning Tree (MST) and Matroids

📌 Kruskal’s Algorithm
Kruskal’s algorithm is a greedy algorithm that works because the MST problem is a graphic
matroid.

✅ Graphic Matroid:
 Ground set: Edges
 Independent sets: Any acyclic subset of edges
 Max-size independent set = Spanning tree
 Weight = Sum of edge weights

📌 How Greedy (Kruskal) Works:

1. Sort edges by weight
2. Add edge if it does not form a cycle (i.e., remains independent)
3. Stop when the tree spans all vertices
✔️The matroid exchange property ensures that Kruskal's choices lead to an optimal MST.

📈 Diagram: Graphic Matroid & Kruskal's

Graph:
A---(2)---B
| |
(3) (1)
| |
C---(4)---D

MST: edges with weights 1, 2, 3 → Total weight = 6

📌 Summary Table
Concept Key Properties

Matroid Generalizes independence

Independent Sets Hereditary + Exchange

Greedy Algorithm on
Matroids Always gives optimal solution

Graphic Matroid Forests (acyclic edge sets)

Greedy on Graphic Matroid for

Kruskal's Algorithm MST

Graph Matching: Max Matching, Augmenting Path,

and Edmond’s Blossom Algorithm
(From UNIT II – Advanced Algorithms (PC – III), JNTUH R22)

🔷 1. What is Graph Matching?

In a graph G=(V,E)G=(V,E), a matching is a subset of edges M⊆EM⊆E such that no two
edges share a common vertex.

🔹 Key Definitions
Term Meaning

Matching Set of edges with no common vertices

 Term Meaning

Maximal Matching that cannot be extended (not necessarily

Matching largest)

Maximum
Matching Matching with the maximum number of edges

Perfect
Matching All vertices are matched (i.e.,

Edge Cover Every vertex is incident to at least one edge

🔷 2. Maximum Matching
A maximum matching is a matching that contains the largest possible number of edges.

✅ Applications:
 Job assignment (bipartite graphs)
 Stable marriage problem
 Network scheduling
 Resource allocation

🔷 3. Augmenting Paths

📌 Definition:
An augmenting path is a path that:
 Starts and ends at free (unmatched) vertices
 Alternates between edges not in the matching and edges in the matching

✅ Berge’s Theorem:
A matching is maximum if and only if there is no augmenting path.
🔹 Augmentation Process:
1. Start with a matching MM
2. Find an augmenting path PP
3. Flip the matched and unmatched edges along PP:
 Add unmatched edges to MM
 Remove matched edges from MM
4. Result: Matching size increases by 1

🔷 4. Edmonds' Blossom Algorithm

📌 Problem:
In non-bipartite graphs, augmenting path search can fail due to odd-length cycles (blossoms).

✅ Edmonds’ Algorithm:
Finds maximum matching in general graphs using augmenting paths and blossom
contraction.

🔹 Key Ideas:
1. Odd cycles (blossoms) may block augmenting paths
2. Contract blossoms into a single pseudo-node
3. Continue BFS on contracted graph
4. Once path is found, expand blossoms and update matching

📈 Example:
Odd cycle: 1–2–3–4–5–1
Matching: 1-2, 3-4
No augmenting path unless cycle is contracted

🧮 Time Complexity:
 O(V³) for general graphs
🔷 5. Algorithms for Matching
Graph Time
Type Best Algorithm Complexity

Bipartite Hopcroft–Karp O(√V * E)

Edmonds’ Blossom
General Algorithm O(V³)

📊 Summary Table
Concept Description

Matching No shared vertices

Maximum
Matching Largest possible matching

Alternating path from unmatched to

Augmenting Path unmatched

Odd-length cycle obstructing

Blossom augmentation

Edmonds’
Algorithm Handles blossoms to find max matching

Flow Networks: Max-Flow Min-Cut, Ford-Fulkerson, and

Edmond-Karp Algorithms
(From UNIT III – Advanced Algorithms (PC – III), JNTUH R22)

🔷 1. What is a Flow Network?

A flow network is a directed graph G=(V,E)G=(V,E) with:
  A source vertex ss
 A sink vertex tt
 Capacity function c(u,v)c(u,v): maximum flow allowed on edge (u,v)(u,v)
Each edge carries a flow f(u,v)f(u,v), subject to:

✅ Constraints:
1. Capacity constraint: 0≤f(u,v)≤c(u,v)0≤f(u,v)≤c(u,v)
2. Flow conservation: ∑f(u,v)=∑f(v,w)∑f(u,v)=∑f(v,w) for all v≠s,tv=s,t

🔷 2. Max-Flow Problem
Find the maximum amount of flow from source ss to sink tt without violating constraints.

🔷 3. Ford–Fulkerson Algorithm

📌 Key Idea:
 Repeatedly find augmenting paths using DFS/BFS
 Push as much flow as possible through each path
 Update the residual graph

🧮 Steps:
1. Initialize flow f(u,v)=0f(u,v)=0
2. While there exists a path s→ts→t in residual graph:
 Find minimum residual capacity cfcf on the path
 For each edge (u,v)(u,v) in path:
 Increase f(u,v)f(u,v) by cfcf
 Decrease f(v,u)f(v,u) (reverse edge) by cfcf
3. Repeat until no more augmenting paths

🔁 Residual Graph:
For each edge (u,v)(u,v), define residual capacity:
cf(u,v)=c(u,v)−f(u,v)cf(u,v)=c(u,v)−f(u,v)

⚠ Limitation:
 May not terminate for irrational capacities (infinite loop)
🔷 4. Edmonds-Karp Algorithm (Improved Ford–
Fulkerson)
Uses Breadth-First Search (BFS) to find shortest augmenting paths (minimum number of
edges)

🔹 Time Complexity:
 Ford-Fulkerson: O(E * max flow) — depends on flow values
 Edmonds-Karp: O(VE²)

📈 Example:

Graph:

s --(10)--> a --(4)--> t
s --(10)--> b --(6)--> t
a --(2)--> b
Max flow = ?

Augmenting path examples:

 s → a → t (flow 4)
 s → b → t (flow 6)
 s → a → b → t (flow 2)
Total max flow = 4 + 6 + 2 = 12

🔷 5. Max-Flow Min-Cut Theorem

📌 Theorem:
The maximum flow from ss to tt is equal to the minimum capacity that, when removed,
disconnects ss from tt.

🔹 Cut:
A cut is a partition (S,T)(S,T) of vertices such that s∈Ss∈S and t∈Tt∈T.
The capacity of the cut is the sum of edge capacities from SS to TT.

✅ Max-Flow = Min-Cut:
 When no more augmenting paths exist
  Residual graph has no s→ts→t path ⇒ saturated cut

📊 Summary Table
Search Time
Algorithm Method Complexity Notes

Ford-Fulkerson DFS O(E * f*max)

Edmonds-Karp BFS O(VE²) Guaranteed to terminate

Max-Flow Min- Max flow = Min cut

Cut – – capacity

Matrix Computations: Strassen’s Algorithm, Divide-

and-Conquer, Matrix Inverse, Triangular Matrix,
LUP Decomposition
(From UNIT III – Advanced Algorithms (PC – III), JNTUH R22)

🔷 1. Divide-and-Conquer for Matrix Multiplication

📌 Problem:
Multiply two n×nn×n matrices AA and BB.

🔹 Naive Algorithm:
Cij=∑k=1nAik⋅BkjCij=k=1∑nAik⋅Bkj
 Time complexity: O(n³)
🔹 Divide-and-Conquer Idea:
1. Split matrices into 4 n/2×n/2n/2×n/2 submatrices
2. Perform 8 multiplications recursively
3. Combine the results
Still takes O(n³) — no improvement.

🔷 2. Strassen’s Algorithm

📌 Goal:
Reduce number of multiplications from 8 to 7 using clever combinations.

🔹 Divide matrices as:

Let

A=[A11A12A21A22],B=[B11B12B21B22]A=[A11A21A12A22],B=[B11B21B12
B22]

🔹 Compute 7 products:
M1=(A11+A22)
(B11+B22)M2=(A21+A22)B11M3=A11(B12−B22)M4=A22(B21−B11)M5=(A
11+A12)B22M6=(A21−A11)(B11+B12)M7=(A12−A22)(B21+B22)M1M2M3M4
M5M6M7=(A11+A22)(B11+B22)=(A21+A22)B11=A11(B12−B22)=A22(B21−B11)=(A11
+A12)B22=(A21−A11)(B11+B12)=(A12−A22)(B21+B22)

🔹 Combine:
C11=M1+M4−M5+M7C12=M3+M5C21=M2+M4C22=M1−M2+
M3+M6C11C12C21C22=M1+M4−M5+M7=M3+M5=M2+M4=M1−M2
+M3+M6

✅ Time Complexity:
T(n)=7T(n/
2)+O(n2)⇒T(n)=O(nlog⁡27)≈O(n2.81)T(n)=7T(n/
2)+O(n2)⇒T(n)=O(nlog27)≈O(n2.81)
Much faster than naive O(n³) for large matrices.

🔷 3. Matrix Inverse

📌 Definition:
For a matrix AA, the inverse A−1A−1 satisfies:
A⋅A−1=IA⋅A−1=I

🔹 Inversion Method (using Gauss-Jordan elimination):

1. Augment matrix AA with identity matrix II
2. Perform row operations to convert A→IA→I
3. The augmented part becomes A−1A−1

✅ Conditions:
 AA must be square
 det⁡(A)≠0det(A)=0 (non-singular)

🔷 4. Triangular Matrices

📌 Types:
Type Structure

Upper All entries below main

Triangular diagonal = 0

Lower All entries above main

Triangular diagonal = 0
✅ Properties:
 Fast multiplication: O(n²)
 Fast forward/backward substitution
 Determinant = product of diagonal entries
 Used in matrix decompositions

🔷 5. LUP Decomposition

📌 Goal:
Factor a matrix AA into:
P⋅A=L⋅UP⋅A=L⋅U

Where:

 LL = Lower triangular matrix

 UU = Upper triangular matrix
 PP = Permutation matrix (for row swaps)

🔹 Uses:
 Solving linear systems Ax=bAx=b
 Matrix inversion
 Determinant calculation

✅ Algorithm Steps:
1. Apply Gaussian elimination with row swaps
2. Track row swaps in permutation matrix PP
3. Store multipliers in LL, result in UU

🧮 Solving Ax = b Using LUP:

1. PAx=PbPAx=Pb
2. LUx=PbLUx=Pb
3. Solve Ly=PbLy=Pb (forward substitution)
4. Solve Ux=yUx=y (backward substitution)
📊 Summary Table
Time
Topic Use Case Complexity

Naive Matrix Mult. Standard multiplication O(n³)

Strassen’s
Algorithm Fast matrix multiplication O(n^2.81)

Matrix Inverse Solve systems, invert A O(n³)

Triangular
Matrices Efficient substitutions O(n²)

LUP Solving Ax = b, inverse,

Decomposition det(A) O(n³)

UNIT - IV

Shortest Path: Floyd–Warshall & Dynamic

Programming

🔷 1. Floyd–Warshall Algorithm

📌 Purpose:
Find all-pairs shortest paths in a weighted directed graph, even with negative edge weights,
as long as there are no negative cycles.
🧠 Key Idea:
Use dynamic programming to incrementally improve the shortest paths between all pairs of
vertices by considering each vertex as an intermediate step.

🔹 Input:
A graph with nn vertices and edge weights w(u,v)w(u,v)
Let the matrix D represent distances between nodes.

🧮 Algorithm Steps:
Let D(k)[i][j]D(k)[i][j] be the shortest distance from ii to jj using only nodes {1,2,...,k}
{1,2,...,k} as intermediates.
Recurrence:

D(k)[i][j]=min⁡(D(k−1)[i][j], D(k−1)[i][k]+D(k−1)[k][j])D(k)[i]
[j]=min(D(k−1)[i][j], D(k−1)[i][k]+D(k−1)[k][j])

🔁 Pseudocode:
for k in range(n): for i in range(n): for j in range(n): D[i][j] = min(D[i]
[j], D[i][k] + D[k][j])

⚠ Handling Negative Cycles:

If D[i][i]<0D[i][i]<0 for any ii, a negative cycle exists.

⏱ Time Complexity:
 O(n³) for n vertices

✅ Example:

Graph:

A → B (3), A → C (∞)
B → C (1), C → A (-2)

Initial distance matrix (D):

A B C
A 0 3 ∞
B ∞ 0 1
C -2 ∞ 0

After applying Floyd–Warshall:

A B C
A 0 3 4
B -1 0 1
C -2 1 0

🔷 2. Dynamic Programming Examples in Shortest

Paths

🔹 a. Bellman-Ford Algorithm (Single-Source)

 Solves for negative weights
 Dynamic programming over edge relaxations

Recurrence:

dist[v]=min⁡(dist[v], dist[u]+w(u,v)) for all (u,v

)dist[v]=min(dist[v], dist[u]+w(u,v)) for all (u,v)

⏱ Time: O(VE)

🔹 b. Matrix Chain Multiplication (related DP problem)

Given matrices A1,A2,...,AnA1,A2,...,An with dimensions p0×p1,p1×p2,...,pn−1×pnp0
×p1,p1×p2,...,pn−1×pn, find minimum multiplication cost.
DP Recurrence:

M[i][j]=min⁡i≤k<j(M[i][k]+M[k+1][j]+pi−1pkpj)M[i][j]=i≤k<jmin
(M[i][k]+M[k+1][j]+pi−1pkpj)

⏱ Time: O(n³)

🔹 c. Optimal BST (Binary Search Tree)

Given probabilities p1,...,pnp1,...,pn, compute tree with minimum expected search cost.

DP recurrence:
cost[i][j]=min⁡i≤r≤j(cost[i][r−1]+cost[r+1][j]+∑k=ijpk)cost[i]
[j]=i≤r≤jmin(cost[i][r−1]+cost[r+1][j]+k=i∑jpk)

⏱ Time: O(n³)

📊 Summary Table
Handles Negative Time
Algorithm Problem Type Edges Complexity

Floyd–Warshall All-pairs shortest path ✅ Yes (no cycles) O(n³)

Single-source shortest
Bellman-Ford path ✅ Yes O(VE)

Matrix Chain Optimal cost of

Mult. parenthesis ❌ (no edges) O(n³)

Modulo Representations: Chinese Remainder

Theorem, Base/Modulo Conversion, Polynomial
Applications
(From UNIT IV – Advanced Algorithms (PC – III), JNTUH R22)

🔷 1. Chinese Remainder Theorem (CRT)

📌 Problem:

Given several congruences:

modm2⋮x≡akmodmk
{x≡a1mod m1x≡a2mod m2⋮x≡akmod mk⎩⎨⎧x≡a1modm1x≡a2

Find a unique solution xmod MxmodM, where M=m1⋅m2⋯mkM=m1⋅m2⋯mk

✅ Conditions:
 Moduli m1,m2,...,mkm1,m2,...,mk are pairwise
coprime (i.e., gcd⁡(mi,mj)=1gcd(mi,mj)=1 for i≠ji=j)

🧮 Solution Steps:
1. Compute M=m1⋅m2⋯mkM=m1⋅m2⋯mk
2. For each ii, compute:
 Mi=M/miMi=M/mi
 yi=Mi−1mod miyi=Mi−1modmi (modular inverse of MiMi mod mimi)

x=∑i=1kai⋅Mi⋅yimod Mx=i=1∑kai⋅Mi⋅yimodM
3. Then:

✅ Example:

Solve:

{x≡2mod 3x≡3mod 5x≡2mod 7⎩⎨⎧

x≡2mod3x≡3mod5x≡2mod7
1. M=3⋅5⋅7=105M=3⋅5⋅7=105
2. M1=35, M2=21, M3=15M1=35, M2=21, M3=15
3. Inverses:
35−1mod 3=235−1mod3=2

 21−1mod 5=121−1mod5=1
 15−1mod 7=115−1mod7=1

⋅15⋅1=140+63+30=233x≡233mod
x=2⋅35⋅2+3⋅21⋅1+2⋅15⋅1=140+63+30=233x=2⋅35⋅2+3⋅21⋅1+2

105⇒x=23x≡233mod105⇒x=23

🔷 2. Base/Modulo Conversion

🔹 a. Base Conversion:
Convert number from base b1b1 to base b2b2:
1. Convert base b1b1 to decimal
2. Convert decimal to base b2b2
🔹 b. Modulo Arithmetic Conversion:

Convert large number into residue form using moduli:

xmod m1, xmod m2, ...,xmod mkxmodm1, xmodm2, ...,xmodmk

✅ Useful in:
 Parallel arithmetic
 Avoiding large number overflow
 Fast polynomial multiplication (NTT, FFT mod pp)

🔸 Example:
Convert 123123 to base 5:
123÷5=24 R3123÷5=24 R3

 24÷5=4 R424÷5=4 R4
 4÷5=0 R44÷5=0 R4
So: 12310=443512310=4435

🔷 3. Polynomial Applications of Modulo Arithmetic

📌 a. Polynomial Modulo a Prime:

Polynomials with coefficients in ZpZp, i.e., f(x)mod pf(x)modp
Used in:

 Finite fields
 Coding theory
 Cryptography

📌 b. Fast Polynomial Multiplication:

Use Number Theoretic Transform (NTT) or FFT over modulo rings to multiply polynomials
efficiently.

🔹 CRT in Polynomials:

If:
P(x)≡A(x)mod m1(x),P(x)≡B(x)mod m2(x)P(x)≡A(x)modm1
(x),P(x)≡B(x)modm2(x)
Then use polynomial CRT to reconstruct P(x)mod m1(x)⋅m2(x)P(x)modm1(x)⋅m2(x)

✅ Applications:
 Cryptographic schemes (RSA, ElGamal)
 Error correcting codes (Reed–Solomon)
 Modular exponentiation
 Polynomial multiplication modulo large prime

📊 Summary Table
Concept Description Applications

Chinese Remainder Reconstruct from multiple Parallel arithmetic, CRT-

Theorem moduli RSA

Between different numeral Computing, number

Base Conversion systems theory

Modulo Arithmetic Arithmetic under finite rings Cryptography, hashing

Computation with mod p

Polynomial Modulo Rings polynomials FFT/NTT, error correction

DFT: Complex/Modulo Ring, FFT, and Schönhage–

Strassen Algorithm
(From UNIT IV – Advanced Algorithms (PC – III), JNTUH R22)
🔷 1. Discrete Fourier Transform (DFT)

📌 Purpose:
The DFT transforms a sequence of values (usually coefficients of a polynomial) from the time
domain to the frequency domain.

Ak=∑j=0n−1aj⋅ωjk,0≤k<nAk=j=0∑n−1aj⋅ωjk,0≤k<n
Given a sequence a0,a1,...,an−1a0,a1,...,an−1, the DFT is:

Where:

 ω=e2πi/nω=e2πi/n is a primitive n-th root of unity in the complex plane.

✅ Applications:
 Fast polynomial multiplication
 Signal processing
 Number-theoretic algorithms

🔷 2. FFT – Fast Fourier Transform

📌 Purpose:
Efficiently compute the DFT in O(n log n) time instead of O(n²).

🔹 Divide and Conquer Idea:

Split input into even and odd indices recursively:

+ωk⋅DFT(aodd)
DFT(a)=DFT(aeven)+ωk⋅DFT(aodd)DFT(a)=DFT(aeven)

✅ Steps:
1. Pad the input to the nearest power of 2
2. Recursively compute DFTs of halves
3. Combine using complex roots of unity

🧠 Time Complexity:
T(n)=2T(n/
2)+O(n)⇒T(n)=O(nlog⁡n)T(n)=2T(n/2)+O(n)⇒T(n)=O(nlogn)
🔷 3. DFT in Modulo Rings (Number Theoretic Transform –
NTT)

📌 Motivation:

Complex FFT has floating-point errors → Use modular arithmetic

🔹 Use Prime Modulus:

 Pick a large prime pp where:
 p=c⋅2k+1p=c⋅2k+1 (for FFT to work in modulo)
 Find primitive root gg such that g(p−1)/ng(p−1)/n is an n-th root of unity

✅ Benefits:
 Exact arithmetic over ZpZp
 Avoids rounding errors

🔹 Example:
Modulus p=998244353p=998244353
998244353=119⋅223+1998244353=119⋅223+1
Primitive root g=3g=3
Used for FFT in competitive programming

🔷 4. Schönhage–Strassen Algorithm

📌 Purpose:
Fast multiplication of very large integers using FFT over modular rings

✅ Key Idea:
1. Represent integers as polynomials in base BB
2. Multiply polynomials using FFT over modular ring
3. Reconstruct product from coefficients

🔹 Time Complexity:
O(n⋅log⁡n⋅log⁡log⁡n)O(n⋅logn⋅loglogn)
Faster than Karatsuba (O(n^1.58)) and classical O(n²) for large n.

✅ Steps:
1. Break numbers into chunks:
A=a0+a1B+a2B2+...A=a0+a1B+a2B2+...
2. Apply NTT-based convolution (modular FFT)
3. Carry correction and combine result

🔹 Applications:
 Big integer multiplication in cryptography (RSA, ECC)
 Multiplication in arbitrary-precision libraries (like GMP)
 Efficient computation in symbolic algebra

📊 Summary Table
Algorithm / Time
Concept Purpose Complexity Domain

Time → Frequency Complex / Modulo

DFT domain O(n²) ring

FFT Fast DFT O(n log n) Complex numbers

NTT (Modular DFT over integers mod

FFT) prime O(n log n) ZpZp

Schönhage– Large integer O(n log n log log Modular

Strassen multiplication n) convolution

LP & Complexity: Linear Programming – Feasibility

Region and Simplex Algorithm
(From UNIT V – Advanced Algorithms (PC – III), JNTUH R22)
🔷 1. Linear Programming (LP)

📌 Definition:
A Linear Programming Problem is to:
 Maximize or minimize a linear objective function
 Subject to a set of linear constraints

🔹 General Form:
Maximize or Minimize:
Z=c1x1+c2x2+⋯+cnxnZ=c1x1+c2x2+⋯+cnxn
Subject to constraints:
{a11x1+a12x2+⋯+a1nxn≤b1a21x1+a22x2+⋯

+a1nxn≤b1a21x1+a22x2+⋯+a2nxn≤b2⋮xi≥0(Non-negativity constr
+a2nxn≤b2⋮xi≥0(Non-negativity constraints)⎩⎨⎧a11x1+a12x2+⋯

aints)

🔷 2. Feasibility Region

📌 Definition:
The feasibility region is the set of all points (x1,x2,...,xn)(x1,x2,...,xn) that satisfy all
constraints.

🔹 Properties:
 It is a convex polyhedron
 Optimal solutions lie on the vertices (corners) of this region
 There may be:
 Unique solution
 Multiple optimal solutions
 No solution (infeasible)
 Unbounded solution (value tends to ∞)

✅ Geometrical View (2D):

Example constraints:

x + y ≤ 6
x ≥ 0
y ≥ 0
The feasible region is a triangle bounded by x- and y-axes and the line x+y=6x+y=6

🔷 3. Simplex Algorithm

📌 Purpose:
Efficiently find the optimal value of a linear program by moving along vertices (corners) of the
feasible region.

✅ Key Idea:
 Start at a basic feasible solution (corner)
 Move to an adjacent vertex that improves the objective function
 Repeat until no improvement is possible

🔹 Terminology:
 Basic variable: Currently in the solution
 Non-basic variable: Set to zero
 Pivoting: Switching a basic ↔ non-basic variable

🔁 Simplex Steps:
1. Convert to standard form (equality + slack variables)
2. Create initial tableau
3. Repeat:
 Identify entering variable (improves objective)
 Identify leaving variable (to maintain feasibility)
 Pivot to update the tableau
4. Stop when no positive coefficients remain in the objective row (for maximization)

✅ Example:

Maximize:

Z=3x+5yZ=3x+5y

Subject to:

{x+y≤4x+3y≤6x,y≥0⎩⎨⎧x+y≤4x+3y≤6x,y≥0
Add slack variables, convert to tableau, apply pivoting steps.

🔷 4. Time Complexity
Worst Case
Method Complexity Notes

Exponential (worst-
Simplex case) Very fast in practice

Ellipsoid Polynomial Theoretical importance

Interior Practical + polynomial

Point Polynomial bounds

📊 Summary Table
Concept Meaning / Role

Linear Optimization over linear

Programming constraints

Feasible Region Set of all valid (legal) solutions

Simplex Algorithm Efficient vertex-to-vertex search

Solution with n variables, n

Basic Solution constraints

Slack Variables Convert inequalities to equalities

✅ NP-Completeness: NP-Hardness
Proofs and Examples

🔷 1. What is NP?

📌 NP (Nondeterministic Polynomial time):

 Class of decision problems where solutions can be verified in polynomial time.
 “Guess → Verify quickly”

🔷 2. Complexity Classes Overview

Class Description

P Problems solvable in polynomial time

NP Problems verifiable in polynomial time

NP-
Complete Hardest problems in NP

At least as hard as NP problems (not in

NP-Hard NP)
🔷 3. NP-Complete Problems

📌 Definition:
A problem LL is NP-complete if:

2. Every L′∈NPL′∈NP can be reduced to LL in polynomial time

1. L∈NPL∈NP

i.e., If we solve LL, we can solve any NP problem.

🔷 4. NP-Hard Problems

📌 Definition:
A problem is NP-Hard if every NP problem reduces to it, but it may not be in NP (e.g.,
optimization problems).
 May not be decision problems
 Verification might not be polynomial

🔷 5. Polynomial Time Reduction

To prove a problem AA is NP-Complete:
1. Prove A∈NPA∈NP
2. Choose a known NP-complete problem BB
3. Reduce B≤pAB≤pA (i.e., reduce BB to AA in polynomial time)
🔷 6. Famous NP-Complete Problems
Problem Description

SAT Boolean formula satisfiability

SAT where each clause has exactly 3

3-SAT literals

Find k-size complete subgraph in a

CLIQUE graph

Select minimum vertices to cover all

VERTEX COVER edges

HAMILTONIAN
CYCLE Visit all vertices exactly once

SUBSET SUM Does a subset sum to a target value?

TSP (decision) Is there a tour ≤ k? (not optimization)

🔷 7. Cook–Levin Theorem
First NP-complete problem: SAT
(1971 by Stephen Cook)
All NP problems can be reduced to SAT in polynomial time.
🔷 8. Example: Proving 3-SAT is NP-Complete
1. In NP: Given a truth assignment, we can verify it satisfies formula in polynomial time.
2. Reduction: SAT ≤p≤p 3-SAT
 Convert any SAT instance to 3-SAT using dummy variables/padding.

🔷 9. Optimization vs Decision Problems

Optimization
Problem Decision Version

TSP: Find shortest route TSP: Is there a route with cost ≤ K?

Knapsack: Maximize Knapsack: Is there value ≥ V with weight

value ≤ W?

Decision versions are often NP-complete, used in reductions.

🔷 10. NP-Hard but Not in NP

 Problems with infinite answers, no yes/no form
 Examples:
 Halting Problem
 Optimizing TSP (find actual shortest tour)
 Scheduling with penalties
📊 Summary Table
Can be verified in Can be solved in
Class Example P? P?

P Sorting, BFS ✅ Yes ✅ Yes

NP SAT, 3-SAT ✅ Yes ❌ Unknown

NP-
Complete SAT, CLIQUE ✅ Yes ❌ Unless P = NP

TSP (opt),
NP-Hard Halting ❌ Not always ❌ Not always

🧠 Practice Problems
1. Show that the CLIQUE problem is NP-complete by reduction from 3-SAT.
2. Is the Partition problem NP-complete?
3. Reduce 3-SAT to Vertex Cover.
4. Prove that TSP (decision) is NP-complete.

Would you like:

 🧠 A full NP-completeness proof (e.g., 3-SAT → CLIQUE)?

 📈 Diagrams for reductions?
 📥 PDF of UNIT V full notes?

Let me know!

ChatGPT can make mistakes. Check important info. See Cookie Preferences.