Approximation Method for NP-Hard Problems
NP-Hard problems are computationally intractable problems for which no polynomial-time exact algorithm is known. For
👉
large inputs, finding the exact optimal solution is impractical.
Approximation methods are used to obtain near-optimal solutions in reasonable time.
What is an Approximation Algorithm?
An approximation algorithm is a polynomial-time algorithm that produces a solution close to the optimal solution for an
NP-Hard problem.
● It does not guarantee an exact solution
● It guarantees a solution within a known bound of the optimal solution
Approximation Ratio
The approximation ratio measures how close the solution is to the optimal one.
For a minimization problem:
[
\text{Approximation Ratio} = \frac{\text{Approximate Solution}}{\text{Optimal Solution}}
]
For a maximization problem:
[
\text{Approximation Ratio} = \frac{\text{Optimal Solution}}{\text{Approximate Solution}}
]
Example:
● A 2-approximation algorithm guarantees that the solution is at most twice the optimal value.
Common Approximation Methods
1. Greedy Approximation
● Makes the locally optimal choice at each step
● Simple and fast
● May not give the best global solution
Example:
● Vertex Cover
● Set Cover
2. Local Search
● Starts with an initial solution
● Improves the solution by making small local changes
Example:
● Traveling Salesman Problem (TSP)
3. Rounding Techniques
● Solve a relaxed version of the problem (e.g., Linear Programming)
● Convert fractional solutions into integer solutions
Example:
● Scheduling problems
● Set Cover
4. Primal-Dual Method
● Solves primal and dual problems together
● Used mainly in network design problems
Example:
● Facility Location Problem
5. Randomized Approximation
● Uses randomness to obtain a good expected solution
● Often simple and effective
Example:
● MAX-CUT problem
Examples of Approximation Algorithms
NP-Hard Problem Approximation Approach Ratio
Vertex Cover Greedy 2-approximation
TSP (Metric) Christofides Algorithm 1.5-approximation
Set Cover Greedy ln(n) approximation
Knapsack Greedy + DP Fully Polynomial Time Approximation
Scheme (FPTAS)
Advantages
● Runs in polynomial time
● Suitable for large input sizes
● Provides performance guarantees
Limitations
● Does not give exact solution
● Quality depends on approximation ratio
● Some NP-Hard problems cannot be approximated within any constant factor
Role of Temperature Schedule in Simulated Annealing
Simulated Annealing (SA) is a probabilistic optimization technique used to find near-optimal solutions for NP-hard problems
by avoiding local minima.
The temperature schedule is a key component that controls how the algorithm explores the search space.
What is a Temperature Schedule?
A temperature schedule defines how the temperature T changes during the execution of the simulated annealing algorithm.
It consists of:
1. Initial temperature (T₀)
2. Cooling strategy
3. Final temperature (Tₓ)
Role of Temperature in Simulated Annealing
1. Controls Acceptance of Worse Solutions
● At high temperature, the algorithm accepts worse solutions with high probability
● At low temperature, it becomes selective and mostly accepts better solutions
Acceptance probability:
[
P = e^{-\Delta E / T}
]
where
ΔE = increase in cost
T = temperature
2. Avoids Local Minima
● High temperature allows the algorithm to escape local optima
● Enables wide exploration of the solution space in early stages
3. Gradual Transition from Exploration to Exploitation
● High T → Exploration (random behavior)
● Low T → Exploitation (greedy behavior)
Components of Temperature Schedule
1. Initial Temperature
● Should be sufficiently high
● Allows acceptance of most moves initially
● Poor choice may trap the algorithm early
2. Cooling Schedule (Cooling Rate)
Determines how temperature decreases over time.
Common cooling schedules:
Schedule Type Formula
Linear T = T₀ − k
Geometric (most used) T = αT (0.8 ≤ α ≤ 0.99)
Logarithmic T = T₀ / log(1 + k)
3. Final Temperature
● Stops the algorithm when temperature is very low
● System “freezes” into a near-optimal solution
Importance of Proper Temperature Schedule
● Too fast cooling → poor solution (local optimum)
● Too slow cooling → high computation time
● Balanced schedule gives better solution quality
Conclusion
The temperature schedule governs the behavior and performance of simulated annealing. It controls solution acceptance,
ensures global exploration initially, and enables convergence to a near-optimal solution gradually.
Exam-oriented short answer (5 marks)
The temperature schedule in simulated annealing determines how the control parameter temperature decreases during
execution. At high temperatures, the algorithm accepts worse solutions to escape local minima. As temperature decreases, the
probability of accepting worse solutions reduces, guiding the algorithm toward convergence. An effective temperature schedule
balances exploration and exploitation, significantly affecting solution quality and convergence speed.
Strassen’s Matrix Multiplication (in Data Structures)
Strassen’s Matrix Multiplication is a divide-and-conquer algorithm used to multiply two square matrices faster than the
conventional method.
Conventional Matrix Multiplication
● Time complexity: O(n³)
● Uses 8 multiplications for two 2×2 matrices
Strassen’s Idea
Strassen reduced the number of multiplications from 8 to 7, which significantly improves performance for large matrices.
Basic Concept
Given two matrices A and B of size n × n:
1. Divide each matrix into four submatrices of size (n/2 × n/2)
2. Compute 7 matrix products instead of 8
3. Combine the results to get the final matrix
Matrix Partitioning
[
A =
\begin{bmatrix}
A_{11} & A_{12} \
A_{21} & A_{22}
\end{bmatrix}
\quad
B =
\begin{bmatrix}
B_{11} & B_{12} \
B_{21} & B_{22}
\end{bmatrix}
]
Strassen’s 7 Multiplications
[
\begin{aligned}
M_1 &= (A_{11} + A_{22})(B_{11} + B_{22}) \
M_2 &= (A_{21} + A_{22})B_{11} \
M_3 &= A_{11}(B_{12} - B_{22}) \
M_4 &= A_{22}(B_{21} - B_{11}) \
M_5 &= (A_{11} + A_{12})B_{22} \
M_6 &= (A_{21} - A_{11})(B_{11} + B_{12}) \
M_7 &= (A_{12} - A_{22})(B_{21} + B_{22})
\end{aligned}
]
Resultant Matrix Computation
[
\begin{aligned}
C_{11} &= M_1 + M_4 - M_5 + M_7 \
C_{12} &= M_3 + M_5 \
C_{21} &= M_2 + M_4 \
C_{22} &= M_1 - M_2 + M_3 + M_6
\end{aligned}
]
Time Complexity
Using recurrence relation:
[
T(n) = 7T(n/2) + O(n^2)
]
Applying Master Theorem:
[
T(n) = O(n^{\log_2 7}) \approx O(n^{2.81})
]
Advantages
● Faster than conventional method for large matrices
● Reduces number of costly multiplications
Disadvantages
● More addition and subtraction operations
● Not efficient for small matrices
● Implementation is complex
Applications
● Scientific computing
● Computer graphics
● Large-scale matrix operations
Exam-Oriented Short Answer (5 Marks)
Strassen’s matrix multiplication is a divide-and-conquer algorithm that multiplies matrices in O(n^{2.81}) time. It partitions
matrices into submatrices and uses seven recursive multiplications instead of eight, reducing computational complexity
compared to the conventional O(n³) method.
Matrix Chain Multiplication – Breaking into Subproblems using Dynamic Programming
Matrix Chain Multiplication (MCM) is a classic dynamic programming problem.
The goal is not to multiply matrices, but to find the most efficient way (minimum cost) to multiply a sequence of matrices.
Problem Statement
Given a sequence of matrices
[
A_1, A_2, A_3, \dots, A_n
]
with dimensions:
[
A_i = p_{i-1} \times p_i
]
Find the optimal parenthesization that minimizes the number of scalar multiplications.
Why Dynamic Programming?
● The problem has optimal substructure
● It has overlapping subproblems
Hence, it is solved efficiently using dynamic programming.
Breaking into Subproblems
Step 1: Define Subproblem
Let:
[
m[i][j] = \text{minimum number of scalar multiplications needed to compute } A_i \dots A_j
]
Step 2: Base Case
If there is only one matrix, no multiplication is needed:
[
m[i][i] = 0
]
Step 3: Recursive Relation (Subproblem Division)
To compute ( m[i][j] ), split the product between matrix ( k ):
[
(A_i \dots A_k)(A_{k+1} \dots A_j)
]
Cost:
[
m[i][j] = \min_{i \le k < j}
\Big( m[i][k] + m[k+1][j] + p_{i-1} \times p_k \times p_j \Big)
]
Each choice of k creates two smaller subproblems:
● ( m[i][k] )
● ( m[k+1][j] )
Step 4: Order of Computation
● Solve subproblems of length 1
● Then length 2, 3, … up to n
● This is called bottom-up DP
Example of Subproblem Breakdown
For matrices:
A₁(10×30), A₂(30×5), A₃(5×60)
Possible subproblems:
● m[1][1], m[2][2], m[3][3]
● m[1][2], m[2][3]
● m[1][3]
DP Table Representation
i\j 1 2 3
1 0 m[1][2] m[1][3]
2 0 m[2][3]
3 0
Algorithm Outline
1. Initialize ( m[i][i] = 0 )
2. For chain length = 2 to n
3. For all valid i and j
4. Try all splits k
5. Choose minimum cost
Time and Space Complexity
● Time Complexity: ( O(n^3) )
● Space Complexity: ( O(n^2) )
Exam-Oriented Answer (5 Marks)
Matrix chain multiplication is divided into subproblems using dynamic programming by defining ( m[i][j] ) as the minimum cost of
multiplying matrices from ( A_i ) to ( A_j ). The problem is broken by choosing a split position ( k ), forming two subproblems (
m[i][k] ) and ( m[k+1][j] ). The optimal solution is obtained by minimizing the total cost over all possible k values.
Skip List – Use of Multiple Forward Lists in Data Structures
A Skip List is a probabilistic data structure that improves the performance of searching in a sorted linked list by using
multiple forward lists (levels).
Basic Idea
Instead of maintaining one single forward list, a skip list maintains multiple forward pointers at different levels.
● Lower levels → contain all elements (like a normal linked list)
● Higher levels → contain fewer elements and allow “skipping” over many nodes
This structure enables fast search, insertion, and deletion.
Structure of a Skip List
Each node contains:
● A key/value
● An array of forward pointers:
[
forward[1], forward[2], \dots, forward[level]
]
Multiple Forward Lists (Levels)
Level 0 (Bottom Level)
● Contains all elements
● Acts like a standard sorted linked list
Higher Levels (Level 1, 2, 3, …)
● Each higher level skips more nodes
● Nodes appear at higher levels randomly
● Used for faster traversal
Example Structure (Conceptual)
Level 3: HEAD --------> 20 ------------> 60
Level 2: HEAD ----> 10 ----> 30 ----> 60
Level 1: HEAD -> 10 -> 20 -> 30 -> 40 -> 60
Level 0: HEAD -> 5 -> 10 -> 20 -> 30 -> 40 -> 50 -> 60
How Multiple Forward Lists Improve Efficiency
Search Operation
1. Start at the highest level
2. Move forward while the next key is smaller
3. Drop down one level when no further move is possible
4. Repeat until level 0 is reached
➡ This allows skipping many elements at once.
Insertion Operation
● Find correct position at each level
● Randomly decide how many levels the new node will have
● Update forward pointers at all chosen levels
Deletion Operation
● Remove node references from all its forward lists
● Simple pointer updates
Time Complexity
Because of multiple forward lists:
Operation Average Case
Search O(log n)
Insert O(log n)
Delete O(log n)
Worst case: O(n) (rare)
Advantages of Using Multiple Forward Lists
● Faster than linked lists
● Simpler than balanced trees
● No complex rebalancing required
● Efficient for dynamic data
Disadvantages
● Extra memory for multiple pointers
● Performance depends on randomization
Exam-Oriented Short Answer (5 Marks)
A skip list uses multiple forward lists arranged in levels to improve search efficiency. The bottom level contains all elements,
while higher levels contain a subset of elements, allowing the algorithm to skip several nodes during traversal. These multiple
forward pointers reduce the average time complexity of search, insertion, and deletion operations to O(log n).
PRAM or Parallel Random Access Machines
Parallel Random Access Machine, also called PRAM is a model considered for most of the parallel algorithms. It helps to
write a precursor parallel algorithm without any architecture constraints and also allows parallel-algorithm designers to treat
processing power as unlimited. It ignores the complexity of inter-process communication. PRAM algorithms are mostly
theoretical but can be used as a basis for developing an efficient parallel algorithm for practical machines and can also motivate
building specialized machines.
PRAM Architecture Model
The following are the modules of which a PRAM consists of:
1. It consists of a control unit, global memory, and an unbounded set of similar processors, each with its own
private memory.
2. An active processor reads from global memory, performs required computation, and then writes to global
memory.
3. Therefore, if there are N processors in a PRAM, then N number of independent operations can be performed in
a particular unit of time.
Models of PRAM
While accessing the shared memory, there can be conflicts while performing the read and write operation (i.e.), a
processor can access a memory block that is already being accessed by another processor. Therefore, there are
various constraints on a PRAM model which handles the read or write conflicts. They are:
● EREW: also called Exclusive Read Exclusive Write is a constraint that doesn't allow two processors to read or
write from the same memory location at the same instance.
● CREW: also called Concurrent Read Exclusive Write is a constraint that allows all the processors to read from
the same memory location but are not allowed to write into the same memory location at the same time.
● ERCW: also called Exclusive Read Concurrent Write is a constraint that allows all the processors to write to the
same memory location but are now allowed to read the same memory location at the same time.
● CRCW: also called Concurrent Read Concurrent Write is a constraint that allows all the processors to read from
and write to the same memory location parallelly.
Example: Suppose we wish to add an array consisting of N numbers. We generally iterate through the array and use N steps to
find the sum of the array. So, if the size of the array is N and for each step, let's assume the time taken to be 1 second.
Therefore, it takes N seconds to complete the iteration. The same operation can be performed more efficiently using a CRCW
model of a PRAM. Let there be N/2 parallel processors for an array of size N, then the time taken for the execution is 4 which is
less than N = 6 seconds in the following illustration.
Streaming Algorithm – Idea (2 Marks)
A streaming algorithm processes data sequentially in a single or few passes using very limited memory, without storing
the entire dataset.
It is designed for very large or continuous data streams, where only approximate results are often computed efficiently.
Randomized Algorithm – (2 Marks)
A randomized algorithm is an algorithm that uses random numbers during its execution to make decisions, which may lead
to different outcomes or running times for the same input.
It often provides efficient average performance and is useful for solving complex problems.
Cuckoo Hashing – Definition
Cuckoo hashing is a hashing technique that uses two (or more) hash functions and two hash tables, where each key can
be stored in one of multiple possible positions.
If a collision occurs, the existing key is evicted (kicked out) and reinserted using its alternate hash position, ensuring O(1)
worst-case lookup time.
Suffix Tree Index for Pattern Matching in DNA Sequence Analysis
A suffix tree is a powerful string indexing data structure used for fast pattern matching, especially useful in DNA sequence
analysis, where large genomic strings must be searched efficiently.
What is a Suffix Tree?
A suffix tree is a compressed trie that contains all suffixes of a given string as its paths.
● Each edge is labeled with a substring
● Each leaf represents a suffix starting position
● Built in O(n) time and space (e.g., Ukkonen’s algorithm)
DNA Sequence Representation
A DNA sequence is a string over a small alphabet:
[
\Sigma = {A, C, G, T}
]
Example DNA string:
S = ACGTACGT$
($ is a unique terminal symbol)
Indexing DNA Using a Suffix Tree
● Construct a suffix tree for the DNA sequence
● This tree acts as an index
● Allows fast queries for any DNA pattern
Pattern Matching Using Suffix Tree
Steps:
1. Start at the root of the suffix tree
2. Match the pattern characters along the edges
3. If the pattern is fully matched:
○ All leaves under the current node give starting positions of the pattern
4. If a mismatch occurs:
○ Pattern does not exist in the DNA sequence
Time Complexity
● Suffix tree construction: O(n)
● Pattern search: O(m), where m is the pattern length
● Independent of DNA length — very efficient
Example
DNA Sequence:
S = ATCGATCGA$
Pattern:
P = ATC
Search follows the path A → T → C in the suffix tree.
All leaf nodes below indicate positions where ATC occurs in the DNA.
Advantages for DNA Sequence Matching
● Extremely fast pattern matching
● Suitable for large genome databases
● Finds all occurrences of a pattern
● Efficient even with repeated patterns
Applications in Bioinformatics
● DNA motif searching
● Gene identification
● Sequence alignment
● Repeated substring detection
Exam-Oriented Short Note (5 Marks)
A suffix tree is an efficient indexing structure for pattern matching in DNA sequences. By storing all suffixes of a DNA string, it
allows pattern searches in O(m) time, where m is the pattern length. This makes suffix trees suitable for large-scale genome
analysis and fast identification of DNA subsequences.