Algorithms Examination Review

UNIT – I: Divide and Conquer, Sorting, and Complexity

Analysis
1 (a) Explain Binary Search algorithm with example [5, 10, 15, 20, 25,
30, 35, 40] and analyze its time complexity.
The Binary Search algorithm is an efficient search algorithm used to find an element in a
sorted array. It works by repeatedly dividing the search interval in half.
●​ Algorithm Steps (Iterative):
1.​ Start with low pointing to the first element and high pointing to the last element.
2.​ While low is less than or equal to high, calculate the mid index: \text{mid} = \lfloor
(\text{low} + \text{high}) / 2 \rfloor.
3.​ If the element at mid is equal to the search key x, return mid.
4.​ If x is less than A[\text{mid}], the element must be in the lower half, so set
\text{high} = \text{mid} - 1.
5.​ If x is greater than A[\text{mid}], the element must be in the upper half, so set
\text{low} = \text{mid} + 1.
6.​ If the loop finishes without finding the element, return 0 (or not found).
●​ Example Array: A = [5, 10, 15, 20, 25, 30, 35, 40]. Search key x = 30.
○​ Step 1: \text{low} = 1, \text{high} = 8. \text{mid} = 4. A[4] = 20. Since 30 > 20, set
\text{low} = 5.
○​ Step 2: \text{low} = 5, \text{high} = 8. \text{mid} = 6. A[6] = 30.
○​ Result: A[6] matches x=30. Return 6.
●​ Time Complexity Analysis: The search space is halved in each step.

1 (b) Discuss about bubble sort with example [5, 1, 4, 2, 8] and analyze
its time complexity.
Bubble Sort is a comparison-based sorting algorithm where adjacent elements are repeatedly
compared and swapped if they are in the wrong order. This process ensures the largest
unsorted element "bubbles up" to its correct position in each pass.
●​ Example Array: A = [5, 1, 4, 2, 8]
Pass Comparison and Swap Array State After Pass Notes
(if needed)
Pass 1 (5, 1) \rightarrow swap [1, 4, 2, 5, 8] Largest element 8 is in
\rightarrow [1, 5, 4, 2, 8] place.
(5, 4) \rightarrow swap
\rightarrow [1, 4, 5, 2, 8]
(5, 2) \rightarrow swap
\rightarrow [1, 4, 2, 5, 8]
(5, 8) \rightarrow no
swap \rightarrow [1, 4,
Pass Comparison and Swap Array State After Pass Notes
(if needed)
2, 5, 8]
Pass 2 (1, 4) \rightarrow no [1, 2, 4, 5, 8] Second largest element
swap \rightarrow [1, 4, 5 is in place.
2, 5, 8]
(4, 2) \rightarrow swap
\rightarrow [1, 2, 4, 5, 8]
(4, 5) \rightarrow no
swap \rightarrow [1, 2,
4, 5, 8]
Pass 3 (1, 2) \rightarrow no [1, 2, 4, 5, 8] Array is sorted;
swap \rightarrow [1, 2, algorithm can stop
4, 5, 8] early.
●​ Time Complexity Analysis:
○​ Worst/Average Case (e.g., reverse sorted array): \mathbf{O(n^2)}.
○​ Best Case (already sorted): \mathbf{O(n)} (due to an optimization flag to stop early).

2 (a) Explain insertion sort with example [9, 5, 1, 4, 3] and analyze its
time complexity.
Insertion Sort builds the final sorted array one item at a time by taking elements from the input
data and inserting them into the correct position in a growing sorted sublist.
●​ Algorithm Steps:
1.​ Start with the second element as the key.
2.​ Compare the key with elements in the sorted sublist (left of the key).
3.​ Shift elements in the sorted sublist that are greater than the key to the right.
4.​ Insert the key into the correct position.
5.​ Repeat until the entire array is sorted.
●​ Example Array: A = [9, 5, 1, 4, 3]
Iteration Sorted Sublist Key Action Array State
Initial [9] - - [9, 5, 1, 4, 3]
1 [9] 5 Shift 9 right, Insert [5, 9, 1, 4, 3]
5
2 [5, 9] 1 Shift 9, 5 right, [1, 5, 9, 4, 3]
Insert 1
3 [1, 5, 9] 4 Shift 9, 5 right, [1, 4, 5, 9, 3]
Insert 4
4 [1, 4, 5, 9] 3 Shift 9, 5, 4 right, [1, 3, 4, 5, 9]
Insert 3
●​ Time Complexity Analysis:
○​ Worst Case (reverse sorted array): \mathbf{O(n^2)}.
○​ Best Case (already sorted): \mathbf{O(n)} (only n comparisons are needed).

2 (b) Explain merge sort with example [70, 20, 30, 50, 60, 10, 40] and
analysis its time complexity.
Merge Sort is an efficient, stable, comparison-based sorting algorithm that uses the Divide and
Conquer paradigm.
●​ Idea:
1.​ Divide: The array is split into two halves recursively until the subarrays contain only
one element (which is trivially sorted).
2.​ Conquer (Merge): The sorted subarrays are merged back together to produce
larger sorted arrays. The merging step is the key operation.
●​ Example Array: A = [70, 20, 30, 50, 60, 10, 40]
○​ Divide: \rightarrow [70, 20, 30], [50, 60, 10, 40] \rightarrow [70], [20, 30], [50, 60],
[10, 40] (and further down to single elements).
○​ Merge (Conquer):
■​ [20, 30] and [70] combine to [20, 30, 70].
■​ [10, 40] and [50, 60] combine to [10, 40, 50, 60].
■​ Finally, [20, 30, 70] and [10, 40, 50, 60] merge:
●​ Time Complexity Analysis:
○​ The total work done at each level of recursion (merging) is O(n).
○​ There are \log n levels of recursion.
○​

3 (a) Explain how the Divide and Conquer approach can be used to
find the median of two sorted arrays A = [1, 3, 5], B = [2, 4, 6] and
define the Inversion Counting problem and implement the following
example: A = [2, 4, 1, 3, 5].
Median of Two Sorted Arrays (Divide and Conquer)

The median of two sorted arrays of equal size can be found efficiently by comparing their
medians (m_1 and m_2) and recursively eliminating the parts of the arrays that cannot contain
the overall median.
●​ Example: A = [1, 3, 5], B = [2, 4, 6].
○​ Median m_1 (A) = 3. Median m_2 (B) = 4.
○​ Since m_1 < m_2 (3 < 4), the overall median cannot be in the lower half of A (i.e.,
[1]) or the upper half of B (i.e., [6]).
○​ The problem is reduced to finding the median of the remaining elements: A' = [3, 5],
B' = [2, 4].
○​ The median of the combined list (which is [1, 2, 3, 4, 5, 6]) is between 3 and 4, or
\mathbf{3.5}.
●​ Time Complexity: \mathbf{O(\log n)}.

Inversion Counting Problem

●​ Definition: An inversion in an array A is a pair of indices (i, j) such that i < j but A[i] > A[j].
●​ Efficient Solution: A modification of the Merge Sort algorithm is used to count inversions
in \mathbf{O(n \log n)} time.
●​ Example: A = [2, 4, 1, 3, 5]
 ○​ Inversions are:
■​ (2, 1) \rightarrow A[2] > A[3] (4 > 1)
■​ (4, 1) \rightarrow A[2] > A[3] (4 > 1) - This appears to be a typo in the source
material's reasoning. The pairs are index-based (i, j) such that A[i] > A[j].
■​ (2, 1) at indices (1, 3) \rightarrow A[1]=2, A[3]=1.
■​ (4, 1) at indices (2, 3) \rightarrow A[2]=4, A[3]=1.
■​ (4, 3) at indices (2, 4) \rightarrow A[2]=4, A[4]=3.
○​ Correct Inversions: (4, 1), (2, 1), and (4, 3).
○​ Total Inversions = 3.

3 (b) Describe one efficient algorithm for integer multiplication using

Divide and Conquer and Discrete Ham-Sandwich Theorem.
Efficient Algorithm for Integer Multiplication (Karatsuba)

The Karatsuba Algorithm is a recursive, Divide and Conquer algorithm for multiplying large
n-digit numbers. It performs fewer single-digit multiplications than the traditional method.
●​ Traditional Multiplication: \mathbf{O(n^2)}.
●​ Karatsuba's Time Complexity: \mathbf{O(n^{1.58})}.

Discrete Ham-Sandwich Theorem

●​ Statement: Given d finite sets of points in d-dimensional space, there exists a single
hyperplane (a line in 2D) that simultaneously bisects (cuts into two equal halves) all d
sets.
●​ Application: It is used in computational geometry for fair division problems. In 2D, you
can always draw a single line to split a set of red points and a set of blue points such that
half of the red points and half of the blue points are on each side of the line.

UNIT – II: Dynamic Programming and Backtracking

1 (a) Explain the construction of an Optimal Binary Search Tree
(OBST) with example: Keys A, B, C, D, Probability 0.1, 0.2, 0.4, 0.3.
An Optimal Binary Search Tree (OBST) is a BST constructed for a set of keys with known
search probabilities such that the expected search cost is minimized. It is solved using
Dynamic Programming.
●​ Dynamic Programming Approach:
1.​ The problem is solved for subproblems of increasing size (number of keys).
2.​ A cost matrix C[i][j] is computed, representing the minimum cost of searching
keys in the range i to j.
3.​ The final cost for the entire set of n keys is found at C[1][n].
4.​ Recurrence: For a subproblem C[i][j], the algorithm tries every key k between i and
j as the root. The optimal cost is: where \text{Weight}[i..j] is the sum of probabilities
of all keys from i to j.
●​ Example (Keys A, B, C, D with probabilities 0.1, 0.2, 0.4, 0.3): The DP approach
systematically calculates the minimum cost for subproblems (e.g., A-B, B-C, C-D) and
 uses those results to find the minimum cost for the full set A-D. The root k chosen at the
A-D step is the key that minimizes the expected search cost.

1 (b) Explain the Floyd-Warshall algorithm for finding shortest paths

in a weighted graph.
The Floyd-Warshall algorithm is a Dynamic Programming algorithm for finding the shortest
paths between all pairs of vertices in a weighted graph. It can handle graphs with negative
edge weights but fails if there is a negative weight cycle.
●​ Core Idea: It iteratively updates the shortest path estimate between every pair (i, j) by
considering all vertices k as potential intermediate stops.
●​ Recurrence Relation: The shortest path from i to j using only intermediate vertices
\{1..k\} is: The base case D[0][i][j] is the direct edge weight (or \infty if no direct edge
exists).
●​ Time Complexity: \mathbf{O(V^3)} where V is the number of vertices.

2 (a) Solve the 4-Queens problem using backtracking. Show the steps
and final solutions.
The 4-Queens problem requires placing four queens on a 4 \times 4 board so that no two
queens attack each other. Backtracking is used to systematically explore the solution space.
●​ Backtracking Strategy: Place queens row by row. If a position is safe (no conflict in
column or diagonal), proceed to the next row. If no safe column is found, revert to the
previous row and try the next column (backtrack).
●​ Steps (Finding Solution 1):
1.​ Row 1: Place Q at (1, 2).
2.​ Row 2: Try (2, 1), (2, 2 - conflict), (2, 3 - conflict). Place Q at (2, 4).
3.​ Row 3: Try (3, 1), (3, 2 - conflict), (3, 3 - conflict), (3, 4 - conflict). Backtrack to
Row 2.
4.​ Row 2: Move Q from (2, 4) to next column (none available). Backtrack to Row 1.
5.​ Row 1: Move Q from (1, 2) to (1, 3).
6.​ Row 2: Place Q at (2, 1).
7.​ Row 3: Place Q at (3, 4).
8.​ Row 4: Place Q at (4, 2).
9.​ Solution Found 1: Columns per row = [3, 1, 4, 2].
●​ Final Solutions (Columns per Row):
1.​ [2, 4, 1, 3]
2.​ [3, 1, 4, 2]

2 (b) Explain how Graph Coloring can be solved using backtracking.

Illustrate with a 3-coloring example for a simple graph.
Graph Coloring is the problem of assigning colors to a graph's vertices such that no two
adjacent vertices have the same color.
●​ Backtracking Approach:
1.​ The algorithm processes vertices one by one.
2.​ For a given vertex, it tries assigning colors sequentially from the available set \{1, 2,
 \dots, k\}.
3.​ A color is assigned if it does not conflict with any already colored neighbor.
4.​ If a vertex cannot be legally colored, the algorithm backtracks to the previous
vertex and tries its next color.
●​ Example (3-coloring a Triangle Graph V_1 - V_2 - V_3 - V_1):
○​ Vertex V_1: Assign Color 1.
○​ Vertex V_2: Must be different from V_1. Assign Color 2.
○​ Vertex V_3: Must be different from V_1 (Color 1) and V_2 (Color 2). Assign Color
3.
○​ Result: A valid 3-coloring is V_1=1, V_2=2, V_3=3.

3 (a) Describe the backtracking approach to find a Hamiltonian Cycle

in a graph. Write the general recursive algorithm.
A Hamiltonian Cycle is a cycle that visits every vertex in a graph exactly once and returns to
the starting vertex.
●​ Backtracking Approach:
1.​ Start at a fixed initial vertex (e.g., v_1).
2.​ Build the path recursively by trying adjacent, unvisited vertices.
3.​ If all vertices have been visited, check if the last vertex is adjacent to the starting
vertex to complete the cycle.
4.​ If a dead end is reached (no unvisited neighbor or cycle completion is impossible),
backtrack to the previous vertex and try another neighbor.
●​ General Recursive Algorithm (Conceptual):​
HamiltonianCycle(path[], position):​
// Base case: All V vertices included in the path​
if position == V:​
// Check if the last vertex connects back to the start
(v0)​
if edge(path[position-1], path[0]) exists:​
return true // Cycle found​
else:​
return false​
​
// Try all unvisited vertices 'v' as the next step​
for v in all_vertices:​
if isSafe(v, path, position): // Safe: v is adjacent &
unvisited​
path[position] = v​
if HamiltonianCycle(path, position + 1):​
return true​
​
path[position] = -1 // BACKTRACK: Remove v from path​
​
return false // No vertex leads to a solution from this
position​
3 (b) Describe how Dynamic Programming can be applied to solve the
Job Scheduling problem with deadlines and profits. Give an example.
The Job Scheduling problem with deadlines and profits seeks to select a subset of jobs,
maximizing total profit, where each job must be completed by its specific deadline.
●​ Dynamic Programming (DP) Approach:
1.​ The jobs are typically sorted by their deadlines.
2.​ A 2D DP table, dp[i][t], is used to store the maximum profit achievable using the first
i jobs within a time slot t.
3.​ Recurrence Relation: For the i-th job with profit p_i and processing time t_i:
■​ Include Job i (if t \geq t_i): dp[i][t] = p_i + dp[i-1][t - t_i]
■​ Exclude Job i: dp[i][t] = dp[i-1][t]
■​ Optimal Choice:
●​ Greedy Approach for Unit-Time Jobs (Simpler Case): A simpler, more common
approach for unit-time jobs is a Greedy method: sort jobs by profit and select the ones
that fit within their deadline.
○​ Example (Greedy for Unit-Time Jobs):
■​ Jobs: J1(Profit 100, Deadline 2), J3(27, 2), J5(15, 3).
■​ Sorted by Profit: J1(100), J3(27), J5(15).
■​ Time Slot 1: Take J1 (fits deadline 2).
■​ Time Slot 2: Take J3 (fits deadline 2, is not J1).
■​ Time Slot 3: Take J5 (fits deadline 3).
■​ Total Profit: 100 + 27 + 15 = \mathbf{142}.

UNIT – III: Greedy Algorithms and Search Strategies

1 (a) Explain how Prim’s algorithm constructs a Minimum Spanning
Tree (MST). Illustrate with an example graph.
Prim’s algorithm is a Greedy algorithm that constructs a Minimum Spanning Tree (MST),
which is a subset of the edges of a connected, weighted graph that connects all the vertices
together, without any cycles and with the minimum possible total edge weight.
●​ Construction Process:
1.​ Initialize the MST with an arbitrary starting vertex.
2.​ In a loop, repeatedly select the minimum-weight edge that connects a vertex in
the MST to a vertex outside the MST.
3.​ Add this minimum-weight edge and the new vertex to the MST.
4.​ Repeat until all vertices are included.
●​ Example (Graph Edges): A-B(1), A-C(3), B-C(1), B-D(4), C-D(2).
○​ Start: \{A\}.
○​ Step 1: Choose A-B (weight 1). MST: \{A, B\}.
○​ Step 2: Edges connecting \{A, B\} to outside: B-C(1), A-C(3), B-D(4). Choose
B-C(1). MST: \{A, B, C\}.
○​ Step 3: Edges connecting \{A, B, C\} to outside: C-D(2), B-D(4). Choose C-D(2).
MST: \{A, B, C, D\}.
○​ Result: MST Edges: \{A-B, B-C, C-D\}, Total Weight = \mathbf{4}.
1 (b) Compare Dijkstra’s algorithm and Bellman-Ford algorithm for
shortest paths. When is Bellman-Ford preferable?
Feature Dijkstra’s Algorithm Bellman-Ford Algorithm
Approach Greedy Dynamic Programming
Time Complexity O(E + V \log V) or O(V^2) \mathbf{O(V \cdot E)}
Edge Weights Works only with non-negative Handles negative edge
weights weights
Cycle Detection Cannot detect negative weight Detects negative weight
cycles cycles
●​ Bellman-Ford is Preferable:
○​ When the graph is known or suspected to contain negative edge weights.
○​ When the primary goal is to detect the presence of negative weight cycles.

2 (b) Explain the general strategy of branch and bound. How does it
differ from backtracking?
Branch and Bound (B&B) Strategy

Branch and Bound (B&B) is a systematic search strategy used to find the optimal solution for
optimization problems.
●​ Strategy:
1.​ Branch: The solution space is systematically partitioned into subproblems, forming
a state-space tree.
2.​ Bound: A lower bound (for minimization) or upper bound (for maximization) on
the value of the optimal solution is calculated for each subproblem (node).
3.​ Prune: Any node whose bound proves that it cannot possibly lead to a solution
better than the current best known solution is pruned (eliminated from further
searching).

Difference from Backtracking

Strategy Backtracking Branch and Bound

Goal Find feasible solutions (satisfy Find the optimal solution (best
constraints) value)
Pruning Prunes only infeasible Prunes suboptimal branches
branches (violating constraints) (cannot beat the best current
solution)
3 (a) Describe how the Traveling Salesperson Problem (TSP) can be
solved using branch and bound. Write the bounding function used.
The Traveling Salesperson Problem (TSP) seeks the shortest possible tour that visits every
city exactly once and returns to the starting city. B&B is used to find the minimum-cost tour
efficiently.
●​ B&B Approach for TSP:
 1.​ Nodes in the state-space tree represent partial tours (paths).
2.​ The B&B process calculates a lower bound (LB) on the cost of any complete tour
that passes through the current partial tour.
3.​ If LB is greater than or equal to the cost of the best full tour found so far, the node is
pruned.
●​ Bounding Function (Example using Reduced Cost Matrix): A common bounding
function uses the reduced cost matrix. A simpler bound, often used in introductory
examples, is:

3 (b) What is the Optimal Storage Problem? Show how a greedy

method minimizes average retrieval time.
Optimal Storage Problem

The Optimal Storage Problem involves arranging a set of data items (e.g., files on a sequential
storage device like a tape) to minimize the average retrieval time. The time required to
retrieve an item is dependent on its position in the sequence.

Greedy Method to Minimize Average Retrieval Time

The total retrieval time is the sum of the time taken to reach each file. To minimize this total time,
the most frequently or shortest-length files should be accessed first (i.e., placed at the
beginning).
●​ Greedy Strategy: Arrange the files in non-increasing (decreasing) order of their
access frequency (or non-decreasing order of their processing time/length).
●​ Rationale: By placing the most frequently accessed files first, their high access
frequencies are multiplied by the smallest positions (smallest access times), minimizing
the overall weighted average time.

UNIT – IV: Complexity Theory (P, NP, EXP, PSPACE)

1 (a) Differentiate between deterministic and nondeterministic
algorithms with suitable examples.
Feature Deterministic Algorithm Nondeterministic Algorithm
Execution Follows a single, predictableCan make arbitrary "guesses"
sequence of steps (e.g., or multiple choices
standard computers) simultaneously (conceptual
model)
Output Produces the same output for Can explore all possible paths
the same input every time simultaneously (conceptually)
Example Merge Sort, Dijkstra's Nondeterministic algorithm
algorithm for SAT (it guesses an
assignment and verifies it)
1 (b) Define the PSPACE class. Give an example of a problem in
PSPACE.
The PSPACE (Polynomial Space) class is the set of decision problems that can be solved by
a deterministic Turing machine using only an amount of memory (space) that is polynomial
in the size of the input.
●​ Focus: Space efficiency, not time efficiency.
●​ Example Problem: The Quantified Boolean Formula (QBF) problem, which determines
the truth of a fully quantified Boolean expression (e.g., \exists x \forall y, (x \vee y) \wedge
(\neg x \vee \neg y)). This problem is PSPACE-complete.

2 (a) What is the difference between NP-hard and NP-complete

problems? Give one example of each.
Feature NP-hard Problems NP-complete Problems
Definition A problem H is NP-hard if every A problem C is NP-complete if
problem in NP can be C is in NP and C is NP-hard.
polynomial-time reduced to H.
Membership in NP May not belong to NP. Must belong to NP (verifiable in
polynomial time).
Example Halting Problem (undecidable, 3-Satisfiability (3-SAT)
therefore not in NP, but
NP-hard)
2 (b) State and explain Cook’s Theorem. What is its implication for the
P vs NP?
Cook's Theorem

Cook's Theorem states that the Boolean Satisfiability Problem (SAT) is NP-complete.
●​ Explanation: The theorem proves that every problem in the complexity class \mathbf{NP}
can be transformed (reduced) into an instance of SAT in polynomial time. Therefore, SAT
is the "hardest" problem in NP.

Implication for P vs NP

●​ Cook's Theorem established the concept of NP-completeness.

●​ Implication: If a deterministic algorithm that runs in polynomial time (\mathbf{P}) could be
found for SAT, then, by the reduction property, all problems in NP could be solved in
polynomial time, which would prove that \mathbf{P = NP}.

3 (a) What is the EXP complexity class? How does it relate to P and
NP?
The EXP (Exponential Time) complexity class is the set of decision problems that can be
solved by a deterministic Turing machine in exponential time (\mathbf{O(2^{p(n)})}), where
p(n) is a polynomial in the input size n.
●​ Relation to P and NP: The relationship between the complexity classes is a known
 hierarchy: It is widely believed, though unproven, that \mathbf{P} \neq \mathbf{EXP} and
\mathbf{NP} \neq \mathbf{EXP}.

UNIT – V: Randomized and Approximation Algorithms

1 (a) Differentiate between Las Vegas and Monte Carlo algorithms with
suitable examples.
Feature Las Vegas Algorithm Monte Carlo Algorithm
Result Accuracy Always produces the correct May produce an incorrect
result. result with some probability
\epsilon.
Running Time The running time is random Runs in fixed, polynomial
(though the expected running time.
time is typically polynomial).
Focus Guaranteed correctness, Guaranteed time, probabilistic
probabilistic time. correctness.
Example Randomized QuickSort Miller–Rabin primality test
(always sorts correctly) (may output composite when it
is prime with small probability
\epsilon)
2 (b) Discuss the factor-2 approximation algorithm for the Vertex
Cover problem with an example, and briefly mention its time
complexity.
The Vertex Cover Problem is an NP-hard optimization problem: Given a graph G(V, E), find the
smallest subset of vertices (V' \subseteq V) such that every edge in E has at least one endpoint
in V'.

Factor-2 Approximation Algorithm

1.​ Initialize the vertex cover set V' = \emptyset.

2.​ Initialize the set of edges E' = E.
3.​ While E' is not empty: a. Arbitrarily pick an edge (u, v) from E'. b. Add both endpoints, u
and v, to V'. c. Remove all edges in E' that are incident to u or v.
4.​ Return V'.
<!-- end list -->
●​ Approximation Ratio: The size of the resulting vertex cover |V'| is guaranteed to be no
more than twice the size of the optimal vertex cover |OPT|. The approximation ratio is 2.
●​ Time Complexity: The algorithm iterates at most O(E) times (once per edge picked), and
each step is efficient. The time complexity is dominated by iterating over the edges,
resulting in \mathbf{O(V + E)}.

3 (a) What is the approximation ratio in approximation algorithms?

Give an example.
The approximation ratio (\rho(n)) of an approximation algorithm measures how close the
algorithm's solution is to the optimal solution for a given problem instance.
●​ Definition: For a minimization problem, the ratio is: The ratio is always \geq 1.
●​ Example (Vertex Cover): As discussed in 2(b), the simple greedy algorithm for the
Vertex Cover problem guarantees that its solution is at most twice the size of the optimal
solution.
○​ Approximation Ratio: \mathbf{2}.

3 (b) Elaborately describe the Online algorithms with a simple

example.
An Online algorithm is an algorithm that makes decisions (produces output) step by step as
the input arrives, without knowing the entire input sequence in advance. The decisions
made are based only on the past input, not the future.
●​ Contrast: An Offline algorithm (like Merge Sort) requires the entire input sequence
before it can begin processing.
●​ Simple Example (Paging/Caching Problem):
○​ Problem: When a cache is full and a request for a new page arrives, the system
must decide which page to evict to make space.
○​ Online Nature: The decision must be made immediately, without knowing which
pages the CPU will request next.
○​ Online Algorithm Example: The Least Recently Used (LRU) algorithm. It evicts
the page that was accessed furthest in the past. This is an online decision because
it only uses historical data, not future requests.