DDA

UNIT 1

0/1 knapsack problem-Dynamic Programming | Data structures and algorithms

✅ (A) Short Theory: Job Scheduling Using Greedy
What is Job Scheduling?
Job Scheduling is a problem where we have a set of jobs, each with:
 a deadline, and
  a profit.
Each job takes 1 unit of time, and we must schedule jobs such that:
 All jobs finish before their deadline
 Total profit is maximized

✅ How Greedy Algorithm Solves Job Scheduling?

The greedy method selects jobs in descending order of profit, because choosing higher-profit jobs
first gives maximum overall profit.

✅ Principle of Greedy Method

The Greedy choice property states:
At every step, choose the job with the highest profit that can still be completed before its deadline.

✅ Control Abstraction (Generic Greedy Routine)

1. Sort all jobs in decreasing profit
2. For each job in sorted order:
o Schedule it in the latest available slot before its deadline
o If slot free → place job
o Else → skip job
3. Return final job sequence and maximum profit

Greedy-Job-Scheduling(Jobs)
{
// Jobs are sorted according to some greedy criterion
sort(Jobs according to finish time)

S = {} // S = selected jobs set

last_finish = 0 // finish time of last selected job

for each job j in Jobs do

{
if (start_time(j) ≥ last_finish)

S = S ∪ {j}
{
// select the job
last_finish = finish_time(j)
}
}

return S // S is the optimal set of non-overlapping jobs

}

✅ Time Complexity
 Sorting jobs → O(n log n)
 Placing each job → O(n)
Total = O(n²)
What is the Greedy Approach?
The Greedy Approach is a method of solving optimization problems by making the locally optimal
choice at each stage with the hope of finding a global optimum.
 In simple terms: At every step, pick the best available option right now without worrying too
much about the future steps.
 For Job Scheduling, the "greedy choice" is to always pick the highest paying job first and try
to fit it into the schedule.

Job Scheduling Problem:

We have jobs, each with a deadline and profit. Each job takes 1 unit time. We must schedule jobs so
that total profit is maximized.
Greedy Strategy:
1. Sort jobs in decreasing order of profit.
2. Maintain a time slot array (slot[ ]) of size = max deadline.
 3. For each job in sorted order, place it in the latest free slot before its deadline.
4. If free slot available → schedule it. If not → skip.
This gives the maximum total profit.
Clarify rule: In the standard job sequencing with deadlines (each job takes 1 time unit), a job with
deadline d must be scheduled no later than time slot d, but it may be scheduled earlier (in any slot ≤
d). So a job with deadline 2 can be placed in slot 1 or 2. That is allowed.

Write High-level description of job sequencing algorithm. Let number of jobs (n)=5; Profit vector
P={20, 15, 10, 5, 1); Deadline vector D={2, 2, 1, 3, 3) Find the feasible solutions. What is the optimal
solution and maximum profit?

High-Level Description of Job Sequencing Algorithm

The Job Sequencing algorithm with deadlines is a Greedy Algorithm designed to maximize total
profit. The core principle is to always prioritize the highest-paying jobs while ensuring they can be
completed within their deadlines.
Algorithm Steps:
1. Sort: Arrange all jobs in descending order based on their Profit
2. Initialize: Create a time slot array (or schedule) up to the maximum deadline found in the
job list. Initially, all time slots are empty (0)
3. Iterate and Schedule: For each job in the sorted list:
o Check the time slot corresponding to its deadline
o If slot $d$ is empty, assign the job to that slot.
o If slot $d$ is occupied, look backward (checking slots $d-1, d-2, \dots, 1$) for the
latest available empty slot.
o If a free slot is found, assign the job. If no slots are free up to the deadline, ignore
the job 33.
4. Output: The filled slots represent the optimal sequence of jobs that yields the maximum
profit.
Write a control abstraction for greedy method. Comment on the time complexity of this
abstraction?

Control Abstraction for Greedy Method (Exam-Ready)

⭐ Explanation of the Control Abstraction
 sort(A): Items are arranged using the greedy rule (e.g., highest profit first).
 select(A, i): Picks the i-th element from the already sorted list.
 feasible(x): Checks whether adding the selected element keeps the partial solution valid
(e.g., in job scheduling → deadline condition).
 include(x): Permanently adds the chosen item to the growing solution.
 solution: After the loop finishes, the built set is returned as the final greedy solution.

⭐ Time Complexity
 Sorting step: O(n log n)
 Selection + Feasibility checks: O(n) (each element checked once)
 Total Time Complexity:
T (n)=O(n log ⁡n)+O(n)=O(n log ⁡n)
This is the standard time complexity for all classic greedy problems such as Job Scheduling, Activity
Selection, Huffman coding, Fractional Knapsack, etc.

Comment on the statement “Problem which does not satisfy the principle of optimality cannot be
solved by dynamic programming”.

Comment on the statement:

“Problems which do not satisfy the principle of optimality cannot be solved by dynamic
programming.”**
This statement is true, and here’s why:
Dynamic Programming (DP) works only when a problem satisfies the Principle of Optimality, which
states:
An optimal solution to a problem must contain optimal solutions to its subproblems.
If this condition is not satisfied, DP breaks down.
DP builds solutions bottom-up, storing results of subproblems and combining them.
But if the subproblem solutions are not part of the final optimal solution, then:
 Reusing subproblem results becomes impossible
 Storing intermediate results becomes meaningless
 Optimal global solution cannot be constructed from optimal partial solutions

Example of a problem that violates optimality principle:

 Longest simple path in a graph
  0/1 Knapsack with fractional restriction removed
 Traveling Salesman Problem (TSP)
In these problems, a locally optimal choice (or optimal sub-solution) may lead to a globally non-
optimal result, so DP cannot be applied.

Conclusion
If a problem fails the principle of optimality:
 DP cannot guarantee correctness
 Subproblem reuse becomes invalid
 DP is not a suitable approach
Therefore, the statement is correct and foundational to DP.

Write a control abstraction for dynamic programming strategy. Comment on the time complexity
of this abstraction?

⭐ Control Abstraction for Dynamic Programming

⭐ Explanation (simple and clear)

1. Define subproblems: Break the problem into smaller overlapping subproblems.
2. Order subproblems: Arrange them so that every subproblem needed for computing another
is solved earlier (topological or natural order).
3. Apply recurrence: Use the DP formula to fill a table bottom-up.
4. Final answer: The last cell of the table gives the optimal solution.

⭐ Time Complexity of DP Control Abstraction

If:
 number of subproblems = N
 time to solve each subproblem = M
Then the total time is:
T (N )=O(N ⋅ M )
For most classical DP problems:
 computing each subproblem is constant time (M = 1)
2
 number of subproblems is polynomial, often O(n )or O(nW )
So overall time is:
O(N )or in general O(NM )
Typical results:
 0/1 Knapsack DP: O(nW )
3
 Matrix Chain Multiplication: O(n )
 Floyd–Warshall: O(n 3)

⭐ Exam-Ready Short Conclusion

Dynamic Programming analyzes all subproblems and stores their solutions, so the time complexity is
the number of subproblems multiplied by the time needed to compute each, making DP typically
polynomial time.

Explain Greedy strategy: Principle, control abstraction, time analysis of control abstraction with
suitable example.

⭐ 1. Greedy Strategy – Principle

The Greedy strategy solves problems by making a sequence of choices, where each choice is the
best local or immediate choice at that moment.
The key idea is:
Greedy Choice Property:
A locally optimal choice leads to a globally optimal solution.
Greedy method does not reconsider earlier decisions.
It works only for problems that satisfy:
 Greedy-choice property
 Optimal substructure
Examples: Activity selection, Job sequencing, Huffman coding, Fractional knapsack.

⭐ 2. Control Abstraction of Greedy Method

Meaning:
 sort(A) → Arrange items by profit, weight, finish time, etc.
 select(A,i) → Picks the next best item after sorting.
 feasible(x) → Tests if including x violates constraints.
 include(x) → Adds x permanently to solution.

⭐ 3. Time Analysis of Greedy Control Abstraction

 Sorting step: O(n log n)
 Loop runs n times: O(n)
  Feasibility check: Usually O(1) or O(log n) depending on data structure.
Therefore,
T (n)=O(n log ⁡n)
This is the standard time complexity for most greedy algorithms.

⭐ 4. Suitable Example – Job Sequencing with Deadlines

Jobs:
Job Deadlin Profit
e
J1 2 20
J2 1 10
J3 1 40
J4 1 30
Step 1: Sort by profit:
J3(40), J4(30), J1(20), J2(10)
Step 2: Schedule each job in the latest free slot:
 J3 → deadline 1 → place in slot 1
 J4 → deadline 1 → slot occupied → skip
 J1 → deadline 2 → place in slot 2
 J2 → deadline 1 → full → skip
Final schedule:
J3, J1
Maximum profit:
40+ 20=60

⭐ Final Short Summary (Exam-Ready)

 Greedy method makes locally best choices hoping to reach global optimum.
 Works only if problem has greedy choice property and optimal substructure.
 Uses a simple control abstraction involving sorting, selecting, feasibility checking, and
including candidates.
 Time complexity is generally O(n log n).
 Example: Job Sequencing where selecting jobs by highest profit first gives maximum total
profit.

Explain Dynamic programming: Principle, control abstraction, time analysis of control abstraction
with suitable example.

⭐ 1. Principle of Dynamic Programming

Dynamic Programming (DP) is a technique for solving optimization problems by breaking them into
overlapping subproblems and solving each subproblem only once.
Its correctness relies on:
(a) Optimal Substructure
The optimal solution of the whole problem is built from optimal solutions to subproblems.
(b) Overlapping Subproblems
Subproblems recur many times, so storing (memoizing) their results avoids recomputation.
DP typically uses a table-filling (bottom-up) or memoized (top-down) approach.
⭐ 2. Control Abstraction of Dynamic Programming

Explanation:
 Identify subproblem structure
 Set up a DP table
 Fill entries using recurrence relation
 Last entry gives optimal solution

⭐ 3. Time Analysis of the DP Control Abstraction

Let:
 N = number of subproblems
 M = time to compute each subproblem
Then total time:
T (N )=O(N × M )
Usually:
 For many DP problems, M is constant or small → complexity becomes polynomial.
Examples:
 0/1 Knapsack DP: O(nW )
 Matrix Chain Multiplication: O(n 3)
 Floyd–Warshall: O(n 3)
DP is efficient because it avoids exponential recomputation.

⭐ 4. Suitable Example – Fibonacci Using DP

Recurrence:
F (n)=F (n−1)+ F (n−2)
DP Table:
n 0 1 2 3 4 5
F 0 1 1 2 3 5
Bottom-up algorithm:
F[0] = 0
F[1] = 1
for i = 2 to n:
F[i] = F[i-1] + F[i-2]
return F[n]
Time:
O(n)

⭐ Short Exam-Ready Summary

 DP is used for optimization problems with optimal substructure and overlapping
subproblems.
 It stores solutions to subproblems in a table, building solutions bottom-up.
 Control abstraction computes each subproblem once, using values of smaller subproblems.
 Time complexity is generally O(N × M) where N = number of subproblems.
 Example: Fibonacci (O(n)) or 0/1 Knapsack (O(nW)).

Write steps for Greedy approach for Job sequencing.

Steps for Greedy Approach for Job Sequencing

1. Sort all jobs in descending order of profit.
The idea: pick the most profitable job first.
2. Find the maximum deadline among all jobs.
This tells you how many time slots you need.
3. Create an empty schedule of size = max deadline.
Initially, all slots are free.
4. For each job (in sorted order):
Try to place it in the latest possible free slot before its deadline.
5. If the slot is free, schedule the job there.
If not free, try earlier slots.
6. If no slot is available, skip the job.
7. Finally, the filled schedule gives the feasible solution,
and the sum of included job profits gives the maximum profit.
8.
When we do A1A2 we remove common element and when we do A1 x A2 we take common element
Doubts:
UNIT 2

⭐ Branch and Bound – Short Theory

Branch and Bound is a problem-solving technique used for optimization problems. The idea is to
represent the solution space as a state-space tree and explore it using branching (splitting into
subproblems) and bounding (computing the maximum possible value from that node).
Any branch whose bound is worse than the current best solution is pruned, so we avoid unnecessary
exploration. Thus, Branch and Bound searches only promising nodes and eliminates the rest.

⭐ Algorithm for 0/1 Knapsack – Short Version

1. Sort items in decreasing order of profit/weight ratio.
2. Create a root node with:
profit = 0, weight = 0, level = –1, and compute its bound.
3. Insert the root into a priority queue (highest bound first).
4. While queue is not empty:
o Remove the node with the highest bound.
o If its bound is less than the current best profit → skip.
o Create left child → include next item
 If weight ≤ capacity, update best profit
 Compute bound and insert if bound is promising
o Create right child → exclude next item
 Compute bound and insert if promising
5. When all nodes are processed, the best profit obtained is the optimal answer.
Explain with suitable example Backtracking: Principle, control abstraction, time analysis of control
abstraction.

✅ BACKTRACKING
1. Principle of Backtracking
Backtracking is a general problem-solving strategy used when the solution to a problem can be built
step-by-step, and at each step we must check whether the partial solution is still valid.
The principle is:
1. Build a solution incrementally.
2. At every step, check feasibility (whether this step can lead to a valid solution).
3. If it is not feasible, backtrack:
o Undo the previous step.
o Try a different choice.
 4. Continue this process until:
o A solution is found, OR
o All possibilities are exhausted.
Backtracking is basically a depth-first search through the solution space, where invalid paths are
pruned early.
Keyword to remember:
👉 “Make a choice → Check → If wrong, undo → Try next choice.”

2. Control Abstraction for Backtracking

A control abstraction is a general template that all backtracking algorithms follow.
General Backtracking Control Abstraction

Explanation:
 k → current step or level.
 C(k) → list of all possible choices at level k.
 is_feasible() → checks whether adding the choice still keeps the partial solution valid.
 BACKTRACK(k+1) → recursively tries to build the remaining solution.
 remove x from solution → undoes the choice (backtracking).

3. Time Analysis of Backtracking

Backtracking explores the search space in the worst case completely, therefore:
Worst-Case Time Complexity
If each level has b choices and depth is n, then:
n
T (n)=O(b )
This is exponential time, because:
 Backtracking tries all combinations when no pruning is possible.
Best Case
If many paths are rejected early due to feasibility checks, time reduces drastically.
Key Point
Backtracking is efficient only when pruning is strong.

✅ 4. Suitable Example: N-Queens Problem (4-Queens example)

Problem:
Place 4 queens on a 4×4 chessboard so that no two queens attack each other.
How backtracking works:
1. Place queen in row 1 → try columns 1,2,3,4.
2. If safe, go to row 2; if not safe, try next column.
 3. If row 2 cannot place a queen, backtrack to row 1.
4. Continue until all queens are placed.
Tree Sketch (simple):
Row1: Try C1 → conflict later → backtrack
Row1: Try C2 → works → go to Row2
Row2: Try C1…C4 → if conflict, backtrack
...
Continue until all 4 queens placed
Final Solution Example:
.Q..
...Q
Q...
..Q.
Backtracking tries multiple arrangements and prunes invalid ones immediately.

Compare between greedy method and dynamic programming with respect to. i) ii) iii) iv) v)
Feasibility. Optimality. Recursion. Memorization. Time complexity

Point Greedy Method Dynamic Programming (DP)

i) Feasibility Always produces a feasible solution, but Ensures feasibility by exploring all
it may not consider all possibilities subproblems and combining them to
because it makes decisions step-by- form valid overall solutions.
step.
ii) Optimality Does not always guarantee an optimal Always produces optimal solution if
solution. Works only when the problem the problem satisfies principle of
satisfies greedy-choice property. optimality.
iii) Recursion Usually non-recursive. Decisions are Str
made once in each step. ongly based on recursion or
recurrence relations to define
subproblems.
iv) No memorization; does not store past Uses memoization / tabulation to
Memorization results. Only current decision matters. store intermediate subproblem
results and avoid recomputation.
v) Time Generally lower time complexity (O(n Generally higher time complexity
Complexity log n), O(n), etc.) because it performs (O(n²), O(n³), etc.) because it solves
only one pass of decisions. all subproblems and stores them.

What is sum of subset problem? Solve sum of subset problem for following instance using
backtracking approach. Input : set [] = {2, 3, 5, 6, 8, 10}, sum = 10
What is Branch and Bound method? Write control abstraction for Least cost search?

Branch and Bound Method

Branch and Bound (B&B) is a general problem-solving technique used for solving combinatorial
optimization problems such as
– 0/1 Knapsack
– Job assignment
– Travelling Salesman Problem
– Sum of subsets
– Scheduling problems
Principle
1. Branching:
Break the main problem into smaller subproblems (branches).
2. Bounding:
For each subproblem, compute a bound (lower bound or upper bound) on the optimal
solution that can be obtained from that subproblem.
3. Pruning:
If a subproblem cannot yield a better solution than the best known solution, it is discarded
(pruned).
4. Search Strategy:
Usually best-first search or least-cost node is selected first.
Key idea:
Avoid exploring all subproblems; explore only promising ones.

Control Abstraction for Least-Cost Search (Branch and Bound)

Branch and Bound:
 Uses branching to create subproblems.
 Uses bounding to eliminate subproblems that cannot lead to the optimal solution.
 Explores only promising nodes.
 Uses priority queue for selecting the next node (usually least-cost node).
Least-Cost Search:
 Always expands the node with the minimum bound first.
 Guarantees finding the optimal solution when a solution is removed from the queue.

Assume that a graph with n vertices is represented by an adjacency matrix G. Let there be “m”
number of colours available. Write a recursive backtracking algorithm to colour all the vertices of
the graph. What is the time complexity of this algorithm?

Graph Coloring Using Backtracking

Q. Assume that a graph with n vertices is represented by an adjacency matrix G, and we have m
colors.
Write a recursive backtracking algorithm to color all vertices of the graph.
What is the time complexity?

✅ 1. What is the Graph Coloring Problem?

Graph coloring means assigning a color to every vertex of a graph such that:
 No two adjacent (connected) vertices have the same color.
 Only m colors are available.
This is a classical constraint satisfaction problem solved using backtracking.

✅ 2. Principle of Backtracking (Very Simple Explanation)

Backtracking tries to build the solution step by step:
1. Assign a color to vertex 1.
2. Move to vertex 2 and assign a color that doesn’t clash with vertex 1.
3. Continue for all vertices.
4. If at any vertex no color is possible, backtrack:
o Undo the previous color assignment.
o Try the next color.
Backtracking = Try → Check → Continue → Otherwise Backtrack

✅ 3. Control Abstraction (Recursive Algorithm)

This is EXACTLY how you write it in your exam.

Algorithm: GraphColoring(G, m, n)

Function IsSafe(v, c):

✅ 4. Very Short Explanation of the Algorithm
 We try to color each vertex starting from 1 to n.
 For every vertex, we try all m colors.
 A color is valid only if no neighbor uses that same color.
 If stuck, we backtrack and try another color.

✅ 5. Time Complexity
Backtracking tries m colors at each of n vertices.
Worst-case time complexity:
O(mⁿ)

 n = number of vertices in the graph

 m = number of colors available

Because for every vertex we try all m colors recursively.

This is exponential because graph coloring is NP-Complete.
Doubt :
Doubt :
Based on the provided image and the Branch and Bound theory from your notes, here is the
explanation and the step-by-step solution.
1. What is Branch and Bound Algorithmic Strategy?
Branch and Bound is a general algorithm used to find the optimal solution for problems where you
need to minimize a cost or maximize a profit (like the Traveling Salesman Problem).
 Branching: It solves the problem by breaking it into smaller sub-problems (building a tree of
decisions). For TSP, this means "If I start at City A, which city do I go to next?"
 Bounding: For every decision (node in the tree), it calculates a Lower Bound (Cost). This is
an estimate of the minimum possible cost if we continue down that path.
 Pruning: If a path's Lower Bound is already higher than a solution we have found, we kill
(prune) that path. This saves time by not exploring bad options 1.

2. Solving the Traveling Salesman Problem (TSP)

Goal: Find the cheapest tour that visits every city exactly once and returns to the start.
Step 1: Create the Cost Matrix
From the image, we have 4 nodes (0, 1, 2, 3). We construct the matrix using the edge weights.
(infinity means no self-loop).
Doubt :
Doubt :
Doubt :
UNIT 5

What is amortized analysis? Explain the aggregate method with example

✅ Amortized Analysis
Amortized analysis is a method used to determine the average running time per operation over a
worst-case sequence of operations.
 It does not take a simple average using probability.
 Instead, it spreads the high cost of a few expensive operations over many cheap
operations.
 This gives a more realistic running time than worst-case per operation.
Used when:
 Some operations are expensive, but do not happen every time.
 Examples: dynamic array resizing, union-find, splay trees.

✅ Aggregate Method (Type of Amortized Analysis)

Definition
In the aggregate method, we analyze a sequence of n operations and compute:
Total worst-case cost of all operations
Amortized cost per operation=
n
 Every operation is assigned equal amortized cost.
 Simple to use and perfect for exam answers.

📌 Example: Dynamic Array Expansion

(VERY common exam example – easy to write)
Consider a dynamic array that:
 Doubles in size when it becomes full.
 Inserting an element normally costs 1 unit.
 But when the array is full, resizing and copying costs more.
➤ Example Insert Sequence
Suppose we insert n = 8 elements one by one.
Actual Costs
Operation Cost
Insert 1 1
Insert 2 1
Insert 3 1
Insert 4 1
Insert 5 → resize 4→8 4 (copy) + 1
Insert 6 1
Insert 7 1
 Insert 8 1
Total Cost
1+1+1+1+( 4+1)+1+1+1=12
Amortized Cost
12
=1.5≈ O(1)
8
✔ Even though occasional operations are costly (resizing),
✔ the amortized time per insertion = O(1).

What is Potential function method of amortized analysis? To illustrate Potential method, find
amortized cost of PUSH, POP and MULTIPOP stack operations

⭐ What is the Potential Function Method in Amortized Analysis?

The Potential Method is a technique used in amortized analysis to find the average cost per
operation in a sequence of operations.

✔ Idea
We imagine the data structure stores some “potential energy”.
 When the structure becomes more expensive to maintain later, potential increases.
 When the structure becomes cheaper, potential decreases.
This stored potential helps us distribute the cost of expensive operations across cheaper ones.

⭐ Steps of Potential Method

1. Choose a potential function Φ(S):
o A non-negative function based on the current state of the data structure.
2. Compute amortized cost:
c^i=ci +Φ (S i )−Φ(S i−1)
where
o c i= actual cost of i-th operation
o Φ (S i) = potential after operation
o Φ (S i−1)= potential before operation
3. Ensure Φ(S) ≥ 0 for all states.

⭐ Example Using Stack Operations (PUSH, POP, MULTIPOP)

🎯 Operations and Real Costs
 PUSH(x) → cost = 1
 POP() → cost = 1
 MULTIPOP(k) → cost = min(k, current stack size)

⭐ Choosing Potential Function

We choose:
Φ (S )=number of elements in the stack
Why?
 PUSH increases stack size → increases potential
 POP decreases stack size → reduces potential
This makes amortized cost simple.
⭐ Amortized Cost Calculations
✔ 1. PUSH(x)
Actual cost:
c i=1
Potential change:
Φ (S i)−Φ( S i−1 )=(n+1)−n=1
Amortized cost:
c^i=1+1=2
👉 Amortized cost of PUSH = 2 (O(1))

✔ 2. POP()
Actual cost:
c i=1
Potential change:
Φ (S i)−Φ( S i−1 )=(n−1)−n=−1
Amortized cost:
c^i=1−1=0
👉 Amortized cost of POP = 0 (O(1))
Note: 0 is allowed in amortized analysis.

✔ 3. MULTIPOP(k)
Actual cost:
c i=min ⁡(k , n)
If we remove m elements:
c i=m
Potential change:
Φ (S i)−Φ( S i−1 )=(n−m)−n=−m
Amortized cost:
c^i=m−m=0
👉 Amortized cost of MULTIPOP = 0 (O(1))

⭐ Final Amortized Costs

Operation Actual Cost Amortized Cost
PUSH 1 2 (O(1))
POP 1 0 (O(1))
MULTIPOP(k) ≤ k 0 (O(1))

⭐ Why does this make sense?

 PUSH stores potential (extra cost).
 POP & MULTIPOP use that stored potential.
 Total amortized cost across any sequence of n operations = O(n).

What are special needs of embedded algorithm? Which sorting algorithm is best for embedded
systems? Why?

1. Special Needs of Embedded Algorithms

Embedded systems run on small hardware, have limited memory, and often work in real-time.
Therefore, algorithms designed for embedded systems must satisfy the following requirements:
(i) Low Memory Usage
 Embedded devices usually have very small RAM and ROM.
 Algorithms must not use heavy data structures or large temporary arrays.
(ii) Low Power Consumption
 Algorithms must finish work quickly so the processor can go to a low-power state.
 More computation → more power consumption → not suitable.
(iii) Deterministic and Predictable Running Time
 Embedded systems often perform real-time tasks.
 The algorithm’s worst-case time must be predictable.
 No sudden long delays; consistent performance is required.
(iv) Low Code Size
 Firmware has limited storage.
 Smaller algorithms are preferred because they reduce flash memory usage.
(v) Reliability and Simplicity
 Embedded systems run for years without failure.
 Simple algorithms reduce the risk of bugs and make debugging easier.
(vi) No Dynamic Memory Allocation
 Embedded systems often avoid malloc() or dynamic memory due to fragmentation issues.
 Algorithms should work with fixed, static buffers.

✅ Which sorting algorithm is best for embedded systems? Why?

Best Choice: Insertion Sort
Insertion sort is usually considered the best sorting algorithm for embedded systems.

✔ Reasons why Insertion Sort is best

1. Very Low Memory Usage
 Works in-place.
 Requires only O(1) extra space.
 Perfect for small-memory microcontrollers.
2. Predictable Performance
 Worst case = O(n²), but for small n (small datasets) it is extremely fast.
 No deep recursion, no heap allocation.
3. Great for Almost-Sorted Data
 Many embedded systems handle data that is almost sorted already (sensor readings, logs,
event queues).
 Insertion sort becomes nearly O(n) for almost-sorted arrays.
4. Simple and Reliable
 Very small code size.
 Extremely easy to implement and debug.
 Less risk of logical errors → more reliable firmware.
5. No Recursion
 Recursion is expensive on embedded systems.
 Algorithms like QuickSort use recursion and require stack space, making them risky.

Explain Randomized and Approximate algorithms.

Randomized Algorithms
Definition
A randomized algorithm is an algorithm that uses random numbers during its execution.
The behaviour (running time or output) depends partly on random choices.
Principle
 Randomization is used to make decisions (e.g., choose pivot randomly, pick random
element).
 Helps avoid worst-case input patterns.
 Expected performance is often better than deterministic algorithms.
Types
1. Las Vegas Algorithm
o Always gives correct result.
o Running time is random.
o Example: Randomized QuickSort.
2. Monte Carlo Algorithm
o Runs in fixed time.
o Output may be incorrect with small probability.
o Example: Randomized primality test (Miller–Rabin).
Advantages
 Simple to design.
 Faster on average.
 Avoids worst-case behaviour.
Disadvantages
 Not always predictable.
 In some cases, small probability of incorrect result.

Example (Easy): Randomized QuickSort

Instead of picking the first element as pivot, choose a random pivot.
This avoids worst-case (sorted input).
Expected time: O(n log n).

Approximate Algorithms
Definition
An approximation algorithm is an algorithm used to solve NP-Hard problems, where finding the
exact optimal solution is too slow.
It returns a solution that is close to the optimal within a guaranteed bound.
Principle
 Produce solutions that are good enough, not perfect.
 Use heuristics, greedy choices, or relaxation techniques.
 Guarantee an approximation ratio:
Approx solution
≤ρ
Optimal solution
Why needed?
NP-hard problems like TSP, Vertex Cover, Knapsack take exponential time exactly.
Approx algorithms give quick solutions with guaranteed quality.

Example (Easy): Vertex Cover Approximation

Algorithm:
 1. Choose an edge (u,v).
2. Add both u and v into the solution.
3. Remove all edges incident to u or v.
4. Repeat.
Guarantee: solution is at most 2 × optimal.
Time complexity: O(V + E).

Randomized vs Approximate (Quick Comparison)

Feature Randomized Algorithm Approximate Algorithm
Purpose Improve average performance using Solve NP-hard problems with near-
randomness optimal solution
Correctness Sometimes always correct; sometimes Always correct but may not be optimal
probabilistic
Output May vary due to random choices Deterministically near-optimal
Used For Sorting, searching, primality tests TSP, Vertex Cover, Knapsack

What is randomized algorithm? Give any example of randomized algorithm? Also explain Random
variable, Binomial random variable and-Mathematics for Randomized algorithm.

1. What is a Randomized Algorithm?

A randomized algorithm is an algorithm that uses random numbers (like coin flips) during its
execution to make decisions.
 The algorithm’s behavior changes each time you run it because its choices depend on
random values.
 It does not always produce the same output or take the same time.
 Randomization helps:
o simplify complex problems,
o avoid worst-case inputs,
o improve average performance.

2. Types of Randomized Algorithms

There are two main types:
i) Las Vegas Algorithm
 Always gives the correct answer
 Running time is random (not fixed).
 Example: Randomized QuickSort
(pivot is chosen randomly → guarantees expected O(n log n) time)
ii) Monte Carlo Algorithm
 Running time is fixed.
 Output may be incorrect with small probability.
 Example: Primality Testing (Miller–Rabin)

3. Example of a Randomized Algorithm

Randomized QuickSort (very easy to explain in exam)
Idea:
Choose a random pivot instead of a fixed pivot.
Steps:
 1. Pick a pivot element randomly.
2. Partition the array around the pivot.
3. Recursively sort left and right parts.
Why random?
 Avoids worst-case (when pivot is always smallest/largest)
 Expected time becomes O(n log n)

4. Random Variable (basic definition for exams)

A random variable is a variable whose value is determined by the outcome of a random
experiment.
Examples:
 Number of heads in 10 coin flips
 Number of comparisons in randomized quicksort
 Whether pivot lands in good position or bad position

5. Binomial Random Variable

A binomial random variable counts the number of successes in n independent Bernoulli trials.
 Each trial has 2 outcomes: success (1) or failure (0).
 Probability of success = p
 Probability of failure = 1 – p
Example:
If you flip a fair coin 10 times:
 X = number of heads
 X follows Binomial(n = 10, p = 0.5)

6. Mathematics for Randomized Algorithms (in simple words)

Randomized algorithms commonly use:
i) Expectation (Expected Value E[X])
 Average value of a random variable over many runs
 Used to analyze expected running time
Example:
Expected number of comparisons in Randomized QuickSort is O(n log n).
ii) Probability
 Used to measure:
o Chance of success
o Chance of failure
o Running time guarantees
iii) Indicator Random Variables
Used to simplify expected value calculations.
Example:
Let Xi =
1 if ith element participates in comparison
0 otherwise.
Then total comparisons = Σ Xi.

What is amortized analysis? Explain aggregate and potential function methods used for amortized
analysis with respect to stack operations?
✅ What is Amortized Analysis?
Amortized analysis is a method used to determine the average running time per operation over a
sequence of operations, even if some individual operations are expensive.
 It does not take the average over randomness (that is probabilistic analysis).
 It takes the average over a sequence of operations, assuming the worst case for each.
👉 It ensures that the total cost of n operations is bounded, so each operation has small
“amortized” cost.

⭐1) Aggregate Method (Very Simple Explanation)

Definition
In the aggregate method, we calculate:
 Total cost of n operations,
 Divide by n,
 The result is the amortized cost per operation.
Stack Operations Example (PUSH, POP, MULTIPOP)
Operations:
 PUSH(x) → store element
 POP() → remove top element
 MULTIPOP(k) → pop up to k elements or until stack becomes empty
Key Idea
An element can be pushed once and popped once.
Cost Calculation
 Cost of PUSH = 1
 Cost of POP = 1
 Cost of MULTIPOP(k) = min(k, current stack size)
For n operations:
 Maximum number of PUSH operations = n
 Maximum number of POP operations (including all MULTIPOPs) = n
(because POP cannot happen more times than pushes)
So total cost:
Total Cost ≤ n PUSH + n POP = 2n
⭐ Amortized Cost
Amortized Cost = Total Cost / n = 2n / n = 2 = O(1)
Final Result
All stack operations (PUSH, POP, MULTIPOP) have O(1) amortized time using the aggregate method.

⭐2) Potential Function Method

Definition
In this method:
 We assign a potential energy Φ to the data structure.
 Potential increases when the structure becomes “more expensive to operate on later”.
 Amortized cost = Actual cost + Change in Potential.
Potential Function for Stack
Use this simple potential function:
Φ(stack) = number of elements in the stack
Now calculate amortized cost:

✔ PUSH(x)
  Actual cost = 1
 Potential increases by 1 (because stack size +1)
Amortized cost:
ĉ = actual cost + ΔΦ = 1 + (1) = 2 = O(1)

✔ POP()
 Actual cost = 1
 Potential decreases by 1 (stack size –1)
Amortized cost:
ĉ = 1 + (-1) = 0 = O(1)

✔ MULTIPOP(k)
Actual cost = t pops performed (t ≤ k)
Potential decreases by t:
ĉ = t + (-t) = 0 = O(1)
Final Result
Using the potential method, all operations also have O(1) amortized time.

🎯 Final Exam-Ready Summary

Method Idea Result for Stack Operations
Aggregate Method Total cost of n ops ÷ Amortized cost = O(1)
n
Potential Function Use Φ = size of stack PUSH → 2, POP → 0, MULTIPOP → 0 →
Method O(1)

Write short notes on the following. i) ii) iii) iv) Aggregate analysis. Accounting Analysis. Potential
function method. Tractable and Non-tractable problems.

(i) Aggregate Analysis – Short Note

Definition:
Aggregate analysis is an amortized analysis method where we calculate the total actual cost of
performing n operations and then compute the amortized cost = (total cost / n).
Key Points:
 We do not assign different costs to different operations.
 We assume each operation costs the same on average.
 Very easy to apply.
 Used when operations may have occasional expensive steps but overall cost is manageable.
Example:
For a stack, n operations (PUSH, POP, MULTIPOP) take at most O(n) total time.
So amortized cost = O(1) per operation.

(ii) Accounting (Banker's) Method – Short Note

Definition:
In the accounting method, we assign an amortized cost to each operation (may be higher than
actual cost). Extra cost is saved as a credit to pay for future expensive operations.
Key Points:
 Each operation has a “bank account”.
  Extra charges from cheap operations pay for costly ones.
 Ensures the total amortized cost ≥ total actual cost.
 Useful when future expensive operations depend on earlier cheap operations.
Example:
For a stack:
 PUSH: amortized cost = 2 (1 actual + 1 credit saved)
 POP: actual cost paid by stored credits
All operations still amortize to O(1).

(iii) Potential Function Method – Short Note

Definition:
This method uses a mathematical potential function Φ (phi) that represents the “stored energy” or
“future work saved” in the data structure.
Amortized cost = Actual cost + Change in potential.
Key Points:
 Potential increases during cheap operations and decreases during expensive ones.
 More formal than accounting method.
 Guarantees that total amortized cost bounds actual cost.
Example with Stack:
Let Φ = number of items in stack.
Then amortized cost of PUSH, POP, MULTIPOP becomes O(1).

(iv) Tractable and Non-tractable Problems – Short Note

Tractable Problems:
 Problems that can be solved in polynomial time (O(n), O(n²), O(n³)…).
 Considered efficient and feasible to compute.
 Example: Sorting, shortest path (Dijkstra).
Non-tractable Problems:
 Problems that require exponential or factorial time (O(2ⁿ), O(n!)).
 Not feasible for large inputs.
 Many are NP-hard / NP-complete.
 Example: Traveling Salesman Problem (TSP), Subset Sum, Graph Coloring.

Write short notes on with suitable example of each. i) ii) Randomized algorithm. Approximation
algorithm

i) Randomized Algorithm
A randomized algorithm is an algorithm that uses random numbers or random choices during its
execution to make decisions. This randomness can help the algorithm achieve faster average
performance, avoid worst-case scenarios, or simplify the logic. Even though the algorithm may
behave differently on different runs (because of random choices), it usually provides good expected
performance.
Types of randomized algorithms
1. Las Vegas algorithms — always produce the correct answer, but running time varies.
2. Monte Carlo algorithms — running time is fixed, but answer may be incorrect with a very
small probability.
Example: Randomized QuickSort
In normal QuickSort, choosing a bad pivot (e.g., smallest or largest element) gives worst-case
performance O(n²).
In Randomized QuickSort, the pivot is chosen randomly.
 This avoids the bad-case pattern.
 Expected time becomes O(n log n).
Steps:
1. Pick a random element as pivot.
2. Partition array.
3. Recursively sort.
Because the pivot is random, the probability of hitting a bad pivot repeatedly is very low.

ii) Approximation Algorithm

An approximation algorithm is an algorithm used for hard (NP-hard) optimization problems, where
finding an exact optimal solution is extremely expensive. Instead, the algorithm returns a solution
that is close to optimal within a guaranteed ratio, in polynomial time. They are mainly used for
problems like scheduling, traveling salesman, vertex cover, knapsack, etc.
Approximation Ratio
If the optimal solution value is OPT and the algorithm’s solution value is A, then:
 For minimization: A / OPT ≤ α
 For maximization: OPT / A ≤ α
where α is called the approximation factor.
A smaller α means a better approximation.
Example: Vertex Cover Approximation (2-approx)
Given a graph, find the smallest set of vertices that cover all edges.
Approximation algorithm steps:
1. Pick any edge (u, v).
2. Add both u and v to the vertex cover.
3. Remove all edges touching u or v.
4. Repeat until no edges remain.
This algorithm always produces a vertex cover of size at most twice the optimal size, hence a 2-
approximation.

Explain the methods of amortized analysis. Give suitable example.

1. Aggregate Method
Idea
In the aggregate method, we calculate the total cost of n operations, and divide it by n to get the
amortized cost per operation.
All operations get the same amortized cost.
Example: Dynamic Array Expansion
Suppose we maintain an array that doubles its size whenever it becomes full.
Operation costs:
 Inserting normally = 1 unit
 Doubling the array + copying elements = expensive (k copies)
Total cost for n insertions
When we insert elements, resizing happens at sizes:
1, 2, 4, 8, …, n
Total copying = 1 + 2 + 4 + … + n/2 = 2n − 1 = O(n)
Thus:
 Total work for n insertions = O(n)
 Amortized cost per insertion = O(1)
Even though some insertions take O(n), the average per operation is still O(1).

2. Accounting (Banker’s) Method

Idea
Assign an artificial cost (amortized cost) to each operation.
Each operation pays extra “credit,” which is saved to pay for future expensive operations.
We store this credit on specific objects (like array slots).
Example: Dynamic Array (Again)
Let actual costs be:
 Simple insertion = 1
 Resize cost (copying k elements) = k
We assign an amortized cost:
→ Charge 3 units per insertion.
Usage of the 3 units:
 1 unit pays for the actual insertion
 1 unit is saved as credit on the new element
 1 unit goes toward future copying
When resizing happens, each element has saved 1 credit, which is used to pay the copying cost.
Thus every operation costs constant amortized time = O(1).

3. Potential Method
Idea
This method uses a potential function Φ, which stores “energy” in the data structure.
If the data structure becomes more “complicated,” the potential increases.
The amortized cost is:
Amortized Cost=Actual Cost + ΔΦ
Where:
ΔΦ=Φafter −Φ before
Example: Stack with Multipop Operation
Operations:
 PUSH(x): push element
 POP(): remove top
 MULTIPOP(k): pop up to k elements or until empty
Worst case cost of MULTIPOP = O(n)
But amortized cost will be O(1).
Potential Function
Let Φ = number of items in the stack.
PUSH
Actual cost = 1
Potential increases by +1
Amortized cost = 1 + 1 = 2
POP
Actual cost = 1
Potential decreases by −1
Amortized cost = 1 − 1 = 0
MULTIPOP(k)
At most s items removed, where s ≤ current stack size
Actual cost = s
Potential decreases by s
Amortized cost = s − s = 0
Thus every operation, including MULTIPOP, has O(1) amortized time.

Suppose you are working on an embedded system for a medical device that monitors patient vital
signs. The device continuously collects data from various sensors and needs to process and display
this information in real-time. The data includes timestamps, temperature readings, heart rate, and
blood pressure measurements. Suggest suitable sorting algorithm for this scenario. Clearly justify
your answer with respect to key factors

Suitable Sorting Algorithm: Heap Sort (or Priority Queue–based Sorting)

For a real-time embedded medical device that continuously processes sensor data such as
timestamps, temperature, heart rate, and blood pressure, the most suitable sorting algorithm is
Heap Sort (or maintaining a Binary Min-Heap / Max-Heap for real-time ordered data processing).

Justification with Respect to Key Factors

1. Real-Time Guarantees (Predictable Worst-Case Time)
Embedded medical systems must be deterministic, because unpredictable delays can affect patient
safety.
 Heap Sort has a guaranteed worst-case time of O(n log n).
 Algorithms like QuickSort have O(n²) worst-case, which is unsafe for real-time systems.
 Real-time systems must avoid variable execution times.
Thus, Heap Sort is preferred because of its predictable upper bound.

2. Low Memory Usage (Important for Embedded Systems)

Embedded medical devices often have very limited RAM.
 Heap Sort uses O(1) extra memory (in-place).
 Merge Sort requires O(n) additional memory → not suitable for small embedded systems.
Therefore, Heap Sort fits memory-constrained devices.

3. Continuous Streaming Data Handling

Sensor data arrives continuously, often in small increments.
A Heap allows:
 Efficient insertion in O(log n)
 Efficient retrieval of the minimum/maximum in O(log n)
 Maintaining a live sorted stream
This is ideal for tasks such as:
 Ordering readings by timestamp
 Triggering alerts when heart rate or temperature exceed limits
 Maintaining sliding windows of recent data

4. Stability Not Critical

Medical sensor data does not require stable sorting because:
 Timestamps make entries unique
 Sorting by reading values does not need to preserve earlier equal-value order
So the fact that Heap Sort is not stable is not a problem.

5. Real-Time Display Requirements

Heap-based sorting ensures:
 Timely processing
 No long pauses
 Smooth real-time display of vital sign graphs
This supports the continuous, safe functioning of the medical device.

Why Not Other Algorithms?

QuickSort
 Fast on average, but O(n²) worst-case → unacceptable for real-time medical safety.
Merge Sort
 Stable and predictable, but needs large extra memory → bad for embedded systems.
Insertion Sort
 Works well on very small or nearly sorted datasets but too slow for large continuous
streams.

Conclusion
Heap Sort (or a real-time heap-based priority queue) is the most suitable sorting method for an
embedded medical device because it provides:
 Predictable worst-case performance (real-time safety)
 Low memory usage (embedded constraints)
 Efficient handling of continuous sensor data
 Fast insertion and retrieval

What are randomized algorithms? Enlist and explain in brief the primary reasons for using
randomized algorithms.

What Are Randomized Algorithms?

A randomized algorithm is an algorithm that uses random numbers or random choices during its
execution to influence the outcome or the sequence of operations.
Because of these random decisions, the algorithm may produce different results or take different
amounts of time when run multiple times on the same input.
Randomness helps the algorithm avoid worst-case situations and improves expected performance,
simplicity, and robustness.
Examples include Randomized QuickSort, Randomized Prim’s algorithm, and Monte Carlo/Las
Vegas algorithms.

Primary Reasons for Using Randomized Algorithms

1. Better Expected Performance
Randomized algorithms often have faster expected running time compared to their deterministic
counterparts.
Example:
Randomized QuickSort avoids the worst-case O(n²) by choosing a random pivot and achieves
expected O(n log n).

2. Avoiding Worst-Case Inputs

Randomization helps the algorithm avoid specially crafted worst-case inputs.
For example:
In deterministic algorithms, an adversary can choose inputs that force worst-case behavior.
Randomness makes this extremely difficult.

3. Simplicity and Elegance

Randomized algorithms are often simpler and easier to implement than complicated deterministic
algorithms that achieve similar performance.
Example:
Randomized selection and randomized minimum cut algorithms are much simpler than
corresponding deterministic versions.

4. Better Performance in Big Data and Parallel Computing

Randomized algorithms are often more suitable for:
 large datasets
 distributed systems
 parallel processing
Random sampling makes computations faster and reduces overhead.

5. Breaking Symmetry in Distributed Systems

In distributed computing (such as networks or sensor systems), random choices help processes avoid
conflicts and deadlocks.
Example:
Random back-off in network routing avoids repeated collisions.

6. Useful When Deterministic Solutions Are Too Slow or Complex

For many NP-hard or very large problems, a randomized approximation algorithm can provide a
good, fast solution even when exact deterministic methods are impractical.

What are approximation algorithms? Based on the approximation ratio, classify the approximation
algorithms

What Are Approximation Algorithms?

An approximation algorithm is an algorithm designed to find a solution that is close to the optimal
solution for computationally hard optimization problems (usually NP-hard problems).
Since finding an exact solution is extremely time-consuming, approximation algorithms provide a
near-optimal solution in polynomial time with a mathematically guaranteed performance bound.
Examples include algorithms for Vertex Cover, Traveling Salesman Problem (TSP), Knapsack, Set
Cover, etc.

Approximation Ratio (Performance Guarantee)

For an optimization problem, let:
 OPT = optimal solution value
 A = value returned by approximation algorithm
The approximation ratio (α) measures how close A is to OPT.
For Minimization Problems
A
≤α
OPT
For Maximization Problems
OPT
≤α
A
If α = 1 → exact optimal solution
Larger α → worse approximation

Classification of Approximation Algorithms Based on Approximation Ratio

1. Polynomial-Time Approximation Scheme (PTAS)
 For any ε > 0, algorithm gives a solution within (1 + ε) of optimum (minimization)
 Runs in polynomial time for fixed ε
 Time grows quickly as ε becomes smaller
 Very accurate but may be slow
Example: PTAS for Knapsack Problem.

2. Fully Polynomial-Time Approximation Scheme (FPTAS)

 More efficient than PTAS
 Runs in polynomial time in both n and 1/ε
 Produces solution within (1 + ε) of OPT
 Most powerful type of approximation scheme
Example: FPTAS for Fractional Knapsack using scaling.

3. Constant-Factor Approximation Algorithms

These algorithms guarantee that the solution is within a fixed constant factor α of the optimal.
Examples:
 Vertex Cover – 2-approximation
 Metric TSP – 1.5-approximation (Christofides algorithm)

4. Logarithmic or Polynomial-Factor Approximations

Some problems are too hard to approximate closely, so only weaker guarantees exist.
Examples:
 Set Cover – O(log n) approximation
 Certain scheduling problems – O(n^c) approximation for some constant c

5. Asymptotic Approximation Algorithms

Algorithms whose performance ratio approaches 1 as the input size grows.
Example:
 Bin Packing First-Fit Decreasing has approximation ratio close to 1.22 and improves
asymptotically.

Exam-Ready Summary
Approximation algorithms provide near-optimal solutions to NP-hard problems in polynomial time
with a guaranteed approximation ratio.
Based on approximation ratio, they are classified into:
1. PTAS – (1 + ε) approximation, polynomial time for fixed ε
2. FPTAS – (1 + ε) approximation, polynomial in both n and 1/ε
3. Constant-factor approximation – α-approximation (α is constant, e.g., 2-approx)
4. Logarithmic/polynomial-factor approximations – O(log n) or polynomial factor
5. Asymptotic approximations – ratio approaches 1 for large input
What is embedded algorithm? Explain Embedded system scheduling using power optimized
scheduling algorithm.

What Is an Embedded Algorithm?

An embedded algorithm is an algorithm specifically designed to run on an embedded system, which
is a small, specialized computing device integrated into a larger machine (e.g., medical monitors,
washing machines, automotive systems).
An embedded algorithm is optimized for:
 Low power consumption
 Limited memory and processing capacity
 Real-time performance
 Reliability and safety
Examples include control algorithms, sensor data filtering, signal processing, and task scheduling
algorithms used in real-time embedded systems.

Embedded System Scheduling

Embedded system scheduling refers to the method of deciding which tasks run, when they run, and
how processor time is shared, so that the system meets real-time deadlines, power constraints,
and reliability goals.
Types of tasks:
 Periodic tasks (fixed intervals → sensor sampling)
 Aperiodic tasks (user interaction → button press)
 Sporadic tasks (unpredictable events → alarm)
Common scheduling algorithms include Rate Monotonic Scheduling (RMS), Earliest Deadline First
(EDF), priority scheduling, and power-optimized scheduling.

Power-Optimized Scheduling Algorithm (Explanation)

Power-optimized scheduling aims to complete all tasks before their deadlines while minimizing
energy usage.
In embedded systems (like medical devices, wearables, IoT sensors), power efficiency is crucial
because they run on limited battery power.
Key Idea
The processor should:
1. Run tasks at the lowest possible speed,
2. Enter low-power sleep modes when idle,
3. Use dynamic voltage and frequency scaling (DVFS) to reduce energy consumption.

How Power-Optimized Scheduling Works

1. Dynamic Voltage and Frequency Scaling (DVFS)
 CPU lowers its frequency when workload is low

 Power ∝ Voltage² × Frequency

 Lower frequency → lower voltage → large power savings

Thus reducing frequency/voltage drastically reduces energy consumption.

Example:
Running a task at 50% frequency may reduce power usage by nearly 70%.

2. Slack Time Utilization

Slack = extra idle time between task deadlines.
Power-optimized scheduler:
 Detects slack
 Slows down the CPU proportionally
 Executes tasks at a lower speed while still finishing them before deadlines
This avoids running at full speed unnecessarily.

3. Putting CPU into Sleep Mode

When tasks finish early:
 CPU enters sleep or low-power mode
 Wakes up only when the next task is ready
This is essential for battery-powered embedded systems.

4. Priority-Based Power Scheduling

Higher-priority tasks are run first, but scheduler adjusts CPU frequency depending on:
 Task urgency
 Remaining time until deadline
 Required computational load
This ensures deadlines are met with minimum energy use.

Example Scenario (Simple and Exam-Friendly)

Consider an embedded medical device with 3 periodic tasks:
Tas Execution Time Deadline Type
k
T1 2 ms 10 ms Heart rate sampling
T2 1 ms 6 ms Temperature sensor
T3 1.5 ms 15 ms Blood pressure processing
Using power-optimized scheduling:
1. Scheduler calculates slack between deadlines.
2. CPU frequency is reduced so that tasks finish just before their deadlines.
3. Idle gaps are used to put CPU in sleep mode.
4. Energy consumption drops significantly without missing any deadlines.

What are the advantages and disadvantages of : i) ii) Aggregate Analysis Accounting Method

i) Aggregate Analysis
Advantages
1. Simple and easy to apply
Total cost is calculated for n operations, and dividing by n gives amortized cost.
2. Provides uniform amortized cost
Every operation gets the same amortized cost, making analysis straightforward.
3. Useful for many common data structures
Works well for dynamic arrays, stacks, queues, etc.
4. Gives a clear total worst-case bound
Ensures performance guarantee over the entire sequence of operations.
Disadvantages
1. Cannot differentiate between expensive and cheap operations
All operations get the same amortized cost even when their actual costs differ widely.
 2. Not suitable for complex or irregular data structures
Hard to use when cost patterns vary non-uniformly.
3. Does not show how individual operations contribute to total cost
It hides the detailed behavior of specific operations.
4. Less flexible
Cannot assign different costs or credits to different operations like the Accounting method
can.

ii) Accounting Method (Banker’s Method)

Advantages
1. Can assign different amortized costs to different operations
Useful when some operations need to store “credit” for future expensive operations.
2. More flexible than aggregate analysis
Helps analyze complex data structures like splay trees or dynamic tables.
3. Gives more insight into how costs accumulate
Shows exactly how credits are saved and spent over operations.
4. Better for systems with occasional expensive operations
Random expensive operations are balanced by cheap ones.
Disadvantages
1. Choosing amortized cost values (credits) can be difficult
Requires experience to assign the right number of credits to each operation.
2. More complex to understand and apply
Not as straightforward as aggregate analysis for beginners.
3. If credit values are chosen incorrectly, analysis becomes incorrect
Requires careful planning to ensure correctness.
4. Possibility of confusion with real monetary cost
Students sometimes confuse “credits” with actual cost instead of conceptual tokens.

Why potential function method cannot be used for analysing binary counter? Explain

1. The Potential Function Does Not Capture Flip Patterns Correctly

In a binary counter:
 Incrementing may cause many bits to flip from 1 → 0, and
 Only one bit flips from 0 → 1.
The potential function method requires a potential that:
 Increases or decreases smoothly
 Matches the future cost of operations
But binary counters have irregular flipping patterns:
 Sometimes only 1 bit flips
 Sometimes log n bits flip
 Sometimes all bits flip
The potential function cannot consistently predict these patterns.

2. Potential Cannot Be Defined to Accurately Represent “Stored Work”

The potential function should represent saved work for future operations.
For dynamic arrays or stacks → this is possible.
For binary counters → no meaningful potential can be stored, because:
 A long chain of zeroes suddenly flips to ones.
  A long chain of ones suddenly flips to zeroes.
Thus, the system has no gradual buildup of potential, making it difficult to define a valid Φ(state).

3. Potential Becomes Negative or Unbounded

A valid potential function must always be:
 Non-negative, and
 Polynomially bounded
For binary counters, any potential function tied to:
 Number of 1s
 Number of 0s
 Position of least significant 0
…eventually becomes negative or grows beyond limits because bit flips occur unpredictably and in
large clusters.
Thus, the method cannot maintain a proper balance of potential.

4. Aggregate and Accounting Methods Work Perfectly → Potential Is Unnecessary

Binary counters are easily analyzed using:
 Aggregate method → Total flips = O(n)
 Accounting method → Pay 2 credits per bit flip
These approaches successfully give amortized O(1) time per increment.
But the potential method:
 Requires a stable potential change per operation
 Cannot establish one because bit flips are not stable or gradual
Hence, this method offers no advantage and fails to cleanly model cost.

5. Potential Method Cannot Track Carry Propagation

Binary counters use carry propagation.
Example:
Incrementing 011111 → 100000 (6 bits flipped at once)
Carry propagation is:
 Sudden
 Non-linear
 Unpredictable in amount
The potential function struggles because it cannot accumulate enough “credit” for such bursts of
expensive operations.

Comment on the following statements :

i)
ii)
“The knapsack problem is NP-hard”
“Boolean Satisfiability Problem (SAT) is NP-complete”
iii)
“Minimum spanning tree is tractable problem”

i) “The knapsack problem is NP-hard” — Comment

The Knapsack Problem is considered NP-hard because there is no known polynomial-time
algorithm that can solve all its instances optimally.
The core difficulty comes from the fact that the problem requires selecting the “best combination”
of items under weight constraints, and this selection process grows exponentially with the number
of items.
In the 0/1 knapsack variant, every item can either be included or excluded, leading to 2npossible
subsets, and checking each one becomes computationally infeasible for large input sizes.
Therefore, the knapsack problem is NP-hard because it belongs to a class of optimization problems
that cannot be solved efficiently using deterministic polynomial-time algorithms unless P = NP.

ii) “Boolean Satisfiability Problem (SAT) is NP-complete” — Comment

The Boolean Satisfiability Problem (SAT) is the first problem that was proven to be NP-complete
(Cook’s Theorem).
SAT is NP-complete because:
1. It is in NP:
Given a truth assignment, you can check in polynomial time whether it satisfies the Boolean
formula.
2. It is NP-hard:
Every problem in NP can be reduced to SAT in polynomial time. This means that SAT is at
least as hard as any other NP problem.
Since SAT meets both conditions—being in NP and being NP-hard—it is classified as NP-complete.
This classification implies that SAT is one of the most computationally difficult decision problems,
and finding a polynomial-time algorithm for SAT would imply P = NP.

iii) “Minimum spanning tree is a tractable problem” — Comment

The Minimum Spanning Tree (MST) problem is considered tractable because it can be solved
efficiently in polynomial time.
There are well-known algorithms such as:
 Kruskal’s Algorithm — O(E log ⁡E)
 Prim’s Algorithm — O(E+V log ⁡V )
These algorithms allow us to find an MST even for large graphs without exponential time complexity.
A tractable problem means that practical, efficient solutions exist, and MST clearly falls under this
category.
Therefore, MST is classified as tractable because it belongs to the class P, where problems are
solvable in polynomial time.

UNIT 6
Doubt :
Explain an algorithm for Distributed Minimum Spanning Tree

Distributed Minimum Spanning Tree (DMST) – Explanation of Algorithm

In distributed systems, each computer (node) only knows about its neighbors and can communicate
only through message passing. To find an MST without a central controller, the GHS (Gallager–
Humblet–Spira) algorithm is used.
The GHS algorithm constructs an MST by growing and merging fragments (partial trees) until all
nodes become part of one final MST.
A Distributed Minimum Spanning Tree (DMST) finds the cheapest way to connect all nodes in a
network (like computers or routers) by having nodes communicate and build the tree
collaboratively, without a central controller, using message passing. Instead of classic Prim's or
Kruskal's, DMST algorithms (like GHS) grow tree fragments, finding the Minimum Weight Outgoing
Edge (MOE) to merge with others, efficiently reducing communication in large, dynamic systems for
things like cost-effective broadcast or network design.
Key Concepts
 Goal: Construct an MST where nodes (processes) identify their incident MST edges through
message exchange.
 Message Passing: Nodes send messages over network edges (with potential delays) to share
information.
 Fragments: Nodes start as single-node fragments, then combine using minimum-weight
edges to form larger fragments.
 MOE (Minimum Outgoing Edge): Each fragment finds the cheapest edge connecting it to
another fragment.
 Levels: Fragments increase in "level" as they merge, simplifying combination rules.

How it Works (Simplified GHS Example)

1. Initialization: Each node is a fragment (ID=Node ID, Level=0).
2. Find MOE: Each node identifies its cheapest link to another fragment.
3. Combine Fragments: Fragments with matching MOE weights merge, increasing their level.
4. Broadcast: The new combined fragment broadcasts its ID and level.
5. Repeat: Process continues until all nodes are in one large fragment (the MST).

Why it's Important

 Scalability: Handles vast networks where central algorithms fail.
 Fault Tolerance: More robust to node failures than centralized methods.
 Efficiency: Reduces total message costs for network-wide tasks like broadcasting.
 Applications: Network design, clustering, power grids, and optimizing communication in
distributed systems.

Key Concepts Before the Algorithm

1. Fragment
A fragment is a subset of nodes that currently form a partial MST.
Initially, every node is its own fragment.
2. Minimum Outgoing Edge (MOE)
For each fragment, the MOE is the lightest edge that connects it to a different fragment.
3. Fragment Levels
Each fragment maintains a “level” to control merging:
 Level 0: a fragment with a single node
 Level increases when two fragments of the same level merge

GHS Algorithm – Step-by-Step

Step 1: Initialization
 Every node begins as a separate fragment (Level 0).
 Each node finds the smallest-weight edge connected to any neighbor.
 That edge becomes the candidate for merging.
Step 2: Find Minimum Outgoing Edge (MOE)
Each fragment independently identifies its MOE by exchanging small messages with neighbors.
For example, if fragment F has edges:
3, 6, 8, 1 → MOE is edge weight 1.
Nodes send messages to:
 inquire about neighbors
 check whether an edge connects to another fragment
 compute the minimum edge

Step 3: Merge Fragments

Once MOE is chosen, the fragment requests merging with the fragment on the other side of the
MOE.
Rules of merging:
1. If two fragments of the same level merge → new level = old level + 1
2. If two fragments of different levels merge → the lower-level fragment joins the higher-
level fragment, level unchanged
During merging, nodes exchange:
 Connect messages (to join fragments)
 Initiate messages (to set new fragment identity)
 Test/Accept/Reject messages (to check MOE validity)

Step 4: Repeat Until One Fragment Remains

After merging, the new fragment again finds its MOE.
Fragments grow larger after each merge:
 From Level 0 → Level 1 → Level 2 → … until all nodes are in one fragment.
The algorithm stops when:
 All nodes belong to one final fragment
 No MOE is left
This final fragment is the Distributed Minimum Spanning Tree.

Example (Simplified)
Assume 4 nodes with edges:
A—B(2), B—C(3), C—D(1), A—D(4)
Round 1:
Each node selects its smallest local edge:
A→B(2), B→A(2), C→D(1), D→C(1)
Fragments:
 {A,B}
 {C,D}
Round 2:
Fragment {A,B} finds MOE = C edge (2 or 3)
Fragment {C,D} finds MOE = A or B
Merge fragments on the lightest edge: C—B (3)
Resulting MST edges: 2, 1, 3
Algorithm ends when one fragment remains.

Initial State
We start with a graph of 4 nodes (A, B, C, D) and their weighted edges:
 A—B (weight 2)
 B—C (weight 3)
 C—D (weight 1)
 A—D (weight 4)
Round 1: Fragment Formation
In the first round, each node independently selects its smallest incident edge.
 Node A selects A—B (2)
 Node B selects B—A (2)
 Node C selects C—D (1)
 Node D selects D—C (1)
This process forms two separate fragments, {A,B} and {C,D}, connected by their chosen edges.

Round 2: Merging Fragments

In the second round, each fragment finds its Minimum Outgoing Edge (MOE) - the lightest edge
connecting it to a different fragment.
 Fragment {A,B} identifies its outgoing edges as B—C (3) and A—D (4). Its MOE is B—C (3).
 Fragment {C,D} identifies its outgoing edges as C—B (3) and D—A (4). Its MOE is C—B (3).
Both fragments identify the same edge, C—B (3), as their MOE. They merge across this edge, forming
a single connected component. The algorithm terminates as there is only one fragment left.

Resulting MST Edges: 2, 1, 3

Why GHS Works Well in Distributed Systems

 No global controller required
 Only local information is used
 Scalable and efficient
 Low message complexity: O(E + N log N)
 Works well even with unreliable networks

Write and explain Rabin-Karp algorithm for string matching.

Rabin–Karp Algorithm for String Matching

The Rabin–Karp algorithm is a string-matching algorithm that uses hashing to efficiently find a
pattern inside a larger text.
Instead of comparing the pattern with every substring directly, it compares their hash values, which
makes the algorithm faster in practice.
Idea of the Algorithm
1. Compute the hash of the pattern.
2. Compute the hash of every substring of the text with the same length as the pattern.
3. If the hash values match, check the characters one by one to confirm.
4. Slide the window by one position and update the hash efficiently using a rolling hash.
This approach avoids repeated full comparisons and speeds up string matching.

Algorithm Steps (Rabin–Karp)

Let:
 T = text of length n
 P = pattern of length m
 d = number of possible characters (e.g., 256 for ASCII)
 q = a large prime number used for modulo operations
Step 1: Preprocessing
1. Compute hash of pattern HP
2. Compute hash of the first substring of text HT0
Step 2: Slide the window
For every shift s from 0 to n − m:
 Compare HP with current text hash HTs
 If hash matches → verify characters one by one
 Update hash using rolling hash formula:
H T s+1=[d (H T s −T [s]⋅h)+T [s+ m]]mod q
where:
m−1
h=d mod q
Step 3: If match is found
Return the index where pattern starts.

Example
Text (T): “ABCCDDAEF”
Pattern (P): “CCD”
Length of pattern = 3.
1. Compute hash of “CCD”.
Assume ASCII values and modulo q is used.
Let HP = hash(“CCD”)
2. Compute hash for first three letters of text: “ABC”
Compare HP with hash(ABC).
 Not equal → slide window.
3. Next substring: “BCC”
 Hash does not match → continue.
4. Next substring: “CCD”
 Hash matches → verify characters
 Characters match → pattern found at index 2.

Advantages of Rabin–Karp
 Efficient for multiple pattern searching
 Rolling hash reduces computation
 Average-case complexity is O(n + m)
 Disadvantages
 Worst-case complexity becomes O(nm) when many hash collisions occur
 Requires careful hash design to reduce collisions

With respect to Multithreaded Algorithms explain Analyzing multithreaded algorithms, Parallel

loops, Race conditions.

1. Analyzing Multithreaded Algorithms

Analyzing multithreaded algorithms involves measuring the performance, efficiency, and
correctness of algorithms that run across multiple threads. Because many operations execute
simultaneously, traditional single-thread metrics do not apply directly.
Instead, multithreaded algorithms are evaluated using two major concepts:
a) Work (T₁)
Work is the total number of operations executed by the algorithm if it were run on a single thread.
It is similar to the time complexity of a sequential algorithm.
b) Span (T∞)
Span (also called critical-path length or computational depth) is the minimum execution time
assuming infinite processors.
It represents the longest chain of dependent operations.
c) Parallelism
Parallelism = T₁ / T∞
It shows how much the algorithm can speed up by using parallel processors.
d) Speedup
Speedup = T₁ / Tₚ
Tₚ = running time on p processors.
e) Lower Bound
The performance is limited by the span:
Tₚ ≥ T∞
Thus, analyzing multithreaded algorithms means measuring:
 How much work they do
 How much of that work can be executed in parallel
 How dependencies affect total running time

2. Parallel Loops
Parallel loops are loops in which each iteration can execute independently and simultaneously using
multiple threads.
They are used when loop iterations do not depend on each other’s results.
Example of a parallelizable loop:
for i = 1 to n:
A[i] = B[i] + C[i]
Each iteration is independent, so the loop can be safely executed using multiple threads.
Benefits of Parallel Loops
 Significant reduction in execution time
 Simple way to introduce parallelism
 Easy to implement using constructs like:
o parallel for in OpenMP
o parfor in MATLAB
 o Thread pools in Java/Python
Constraints
A loop cannot be parallelized if:
 One iteration depends on results from previous iterations
 There is shared data without protection
 The order of execution matters

3. Race Conditions
A race condition occurs when multiple threads access and modify shared data at the same time, and
the final outcome depends on the unpredictable order of execution.
Example of Race Condition
Two threads executing:
x=x+1
If both threads read the same old value of x at the same time and write back independently, one
update is lost, resulting in incorrect output.
Why Race Conditions Occur?
 Threads are unsynchronized
 Memory updates are non-atomic
 Shared variables or shared memory is accessed without locks or barriers
Consequences
 Incorrect results
 Non-deterministic behavior (program works sometimes, fails sometimes)
 Hard-to-debug errors
Prevention
 Use mutex locks
 Use semaphores
 Use atomic operations
 Use thread synchronization techniques (barriers, monitors, etc.)

Write and explain pseudo code for Multi-threaded merge sort algorithm. How parallel merging
gives a significant parallelism advantage over Merge Sort?

Multithreaded Merge Sort Algorithm

Merge Sort is naturally recursive and divide-and-conquer based, making it suitable for parallel
execution.
In a multithreaded merge sort, the array is divided into two halves, and each half is sorted in
parallel using separate threads. After sorting, the two halves are merged.
This increases performance because the sorting of the left and right halves happens concurrently
instead of sequentially.

Pseudocode for Multithreaded Merge Sort

Below is simple exam-friendly pseudocode:
Algorithm: MULTITHREADED-MERGESORT(A, low, high)

MULTITHREADED-MERGESORT(A, low, high):

if low < high:

mid = (low + high) / 2

 # Create two threads for left and right parts
spawn MULTITHREADED-MERGESORT(A, low, mid)
spawn MULTITHREADED-MERGESORT(A, mid+1, high)

# Wait for both threads to finish

sync

MERGE(A, low, mid, high)

MERGE(A, low, mid, high)

MERGE(A, low, mid, high):
create temporary array temp[]
i = low
j = mid + 1
k=0

while i ≤ mid and j ≤ high:

if A[i] ≤ A[j]:
temp[k] = A[i]
i=i+1
else:
temp[k] = A[j]
j=j+1
k=k+1

# Copy remaining elements

while i ≤ mid:
temp[k] = A[i]
i=i+1
k=k+1

while j ≤ high:
temp[k] = A[j]
j=j+1
k=k+1

# Copy back to original array

for p = 0 to k-1:
A[low + p] = temp[p]

Explanation of the Algorithm

1. Divide
The array is recursively split into two halves.
2. Spawn Threads
Each half is sorted in parallel using the spawn keyword
(meaning a new thread or parallel task is created).
3. Sync
The sync statement ensures the algorithm waits for both child threads to finish sorting before
merging.
4. Merge
The two sorted halves are then merged as usual.

Why Parallel Merging Gives Significant Parallelism Advantage

1. Merge Sort has high parallelism potential
 The height of merge sort’s recursion tree is log n.
 At each level, the total work done is n.
 But the work at each level can be done in parallel, especially the divide step.
2. Parallel merging reduces span
In the basic Merge Sort:
 Sorting both halves takes T(n/2) + T(n/2) sequentially.
In multithreaded merge sort:
 Sorting both halves happens simultaneously → max(T(n/2), T(n/2)) = T(n/2).
This makes the recursion tree execute faster.
3. Span reduces from O(n log n) to O(n)
Work remains O(n log n), but span becomes almost O(log² n) or even O(log n) with optimized
merging.
This gives very high parallel speedup.
4. Parallel merging can be applied
Traditional merge takes O(n).
Parallel merging divides the merge step into smaller chunks that can be merged simultaneously.
For example:
 Divide the smaller half into √n blocks
 Binary search in the larger half
 Merge each block independently using multiple threads
This reduces merge span from O(n) → O(log n), creating a huge improvement.
5. More processors = more speedup
If enough processors are available:
 splitting is parallel
 sorting halves is parallel
 merging is parallel
This significantly improves execution over normal merge sort.

Write short notes on the following. i) ii) iii) iv) Multithreaded matrix multiplication. Multithreaded
merge sort. Distributed breadth first search. The Rabin-Karp algorithm.

i) Multithreaded Matrix Multiplication (Points)

 It performs matrix multiplication using multiple threads to speed up computation.
 Each thread is assigned a portion of the output matrix (rows, columns, or blocks).
 All matrix element calculations are independent, enabling high parallelism.
 Reduces execution time significantly on multicore processors.
 Requires minimal synchronization because threads write to separate output locations.
 Used in scientific computing, graphics, machine learning, and large numerical applications.
ii) Multithreaded Merge Sort (Points)
 It is a parallel version of merge sort using the divide-and-conquer strategy.
 The input array is split into two halves, and each half is sorted by separate threads.
 Threads run concurrently, reducing overall sorting time.
 After sorting, results are merged using the standard merge procedure.
 Provides good speedup on multicore systems due to parallel recursion.
 Requires careful thread management to avoid excessive overhead.

iii) Distributed Breadth-First Search (Distributed BFS) (Points)

 BFS is executed across multiple machines or processors in a distributed network.
 The graph is divided among nodes, each storing a portion of the vertices and edges.
 BFS proceeds level by level, with each machine computing its local frontier.
 Machines exchange frontier information to explore the next level collaboratively.
 Enables traversal of extremely large graphs that do not fit into one system’s memory.
  Used in large-scale graph analytics, social networks, and distributed systems.

iv) Rabin–Karp Algorithm (Points)

 A string-matching algorithm that uses hashing to find pattern occurrences in text.
 Computes a hash of the pattern and compares it with hashes of text substrings.
 Uses a rolling hash to update substring hashes efficiently while sliding the window.
 When hash values match, direct character comparison verifies the match.
 Very efficient for multiple pattern matching.
 Average time complexity is O(n + m), worst case O(nm) due to hash collisions.
Write a Rabin-Karp string matching algorithm. Input to the algorithm be: Original text “t” of length
n and pattern text being matched is “p” of length m. What is the expected runtime and worst-case
runtime of this algorithm?

✅ Rabin–Karp String Matching Algorithm

The Rabin–Karp algorithm finds all occurrences of a pattern p (length m) in a text t (length n) using
hashing.
It compares hash values instead of characters, making the algorithm efficient for multiple pattern
searches.

Pseudo Code for Rabin–Karp Algorithm

RABIN-KARP(t, p, n, m):

d = 256 # number of characters in input alphabet

q = large prime # modulus for hashing

# Step 1: Precompute hash of pattern and first window of text

pattern_hash = 0
text_hash = 0
h=1
 for i = 1 to m-1:
h = (h * d) % q

for i = 0 to m-1:
pattern_hash = (d * pattern_hash + p[i]) % q
text_hash = (d * text_hash + t[i]) % q

# Step 2: Slide pattern over text

for s = 0 to n - m:

# Step 3: Check if hash values match

if pattern_hash == text_hash:
# Verify characters one by one
if t[s .. s+m-1] == p[0 .. m-1]:
print "Pattern found at position", s

# Step 4: Compute next window hash

if s < n - m:
text_hash = (d * (text_hash - t[s] * h) + t[s + m]) % q

# Make hash positive

if text_hash < 0:
text_hash = text_hash + q

⭐ Explanation of the Algorithm

1. Compute the hash value of the pattern.
2. Compute the hash value of the first window of the text.
3. Slide the window over the text from position 0 to n–m.
4. For each shift:
o Compare pattern hash with text window hash.
o If equal, verify characters to avoid false positives (hash collisions).
5. Use rolling hash technique to update the text hash efficiently:
o Remove leftmost character
o Add new rightmost character

📌 Expected Runtime of Rabin–Karp

Expected / Average Case Time: O(n + m)
Reason:
 Hash comparison takes constant time per shift.
 Hash collisions are rare when a good hash function and large prime modulus are used.
 Character-by-character comparison occurs only occasionally.
Thus, the expected running time is linear in the size of the text.

📌 Worst-Case Runtime of Rabin–Karp

Worst Case Time: O(nm)
Worst-case happens when:
 Hash collisions occur at every shift.
 This forces the algorithm to compare m characters for each of the n-m+1 windows.
Example of worst case:
 All characters are identical
 Bad hash function that causes repeated collisions
Therefore, in the worst case, Rabin–Karp behaves like the naive string matching algorithm.

Write multi-threaded merge sort algorithm. Briefly discuss how does it differ from conventional
merge sort

✅ Multi-Threaded Merge Sort (Theory Only)

Multi-threaded merge sort is an extension of the standard merge sort algorithm where the sorting
of the left and right halves of the array is done in parallel using multiple threads. Instead of
performing the recursive calls one after another, the algorithm creates two independent threads so
that both halves can be processed simultaneously.

⭐ How Multi-Threaded Merge Sort Works (In Theory)

1. Divide Step (same as merge sort)
The array is divided into two equal halves.
2. Parallel Recursive Sorting
o In a normal merge sort, first the left half is sorted, then the right half.
o In multi-threaded merge sort, two separate threads are created:
 One thread sorts the left half
 Another thread sorts the right half
o These threads run simultaneously on different CPU cores, reducing total time.
3. Synchronization
Before merging, the main thread waits until both sorting threads finish their work (using
thread join or equivalent).
4. Merge Step (same as normal merge sort)
After both halves are sorted in parallel, they are merged into a final sorted array.
The merge step remains mostly sequential.

⭐ How It Differs from Conventional Merge Sort

1. Parallelism
 Conventional Merge Sort:
Executes left and right recursive calls one after the other (sequential).
 Multi-Threaded Merge Sort:
Executes both calls simultaneously using multiple threads (parallel).
2. Performance
 Conventional merge sort runs in:
O(n log ⁡n)
 Multi-threaded merge sort can reduce time by using multiple processors:
n log ⁡n
O( )
P
where P = number of cores/threads.
3. CPU Utilization
 Conventional: Uses only one CPU core.
 Multi-Threaded: Utilizes multiple cores, giving major speedup on multi-core systems.
4. Thread Overhead
 Multi-threaded merge sort creates many threads → higher overhead.
  Too many threads slow down performance, so practical implementations limit the number
of threads.
5. Memory Usage
 Merge sort already requires extra memory.
 Multi-threaded version requires additional memory for each thread’s stack and context.
6. Scalability
 Performance increases with number of cores.
 Ideal for large datasets and multi-core processors.

⭐ Why Parallel Merging Gives Advantage

Even though the merge step is mostly sequential, the main time consumption in merge sort is in the
recursive splitting and sorting, not merging.
Parallelizing these sorting tasks gives:
 Faster divide-and-sort operations
 Less waiting time
 Better use of CPU cores
 Up to near-linear speedup for large arrays
Thus, multi-threaded merge sort can be significantly faster than the conventional version on systems
with multiple CPU cores.

What do you understand by spawn and sync keywords used in multithreaded programming?
Explain with the help of suitable example.

Spawn and Sync in Multithreaded Programming

In multithreaded or parallel programming, spawn and sync are keywords used to express parallelism
in algorithms without directly dealing with low-level thread management.
⭐ 1. SPAWN Keyword
Meaning
The spawn keyword indicates that a function or procedure should be executed in parallel with the
current execution.
When a procedure is spawned, a new thread of execution begins, allowing two or more operations
to run simultaneously.
Key Idea
 It creates a parallel task.
 The parent thread continues without waiting.
 Used to express concurrency in divide-and-conquer algorithms.
Example (Conceptual)
spawn COMPUTE_LEFT()
COMPUTE_RIGHT()
sync
Explanation:
 COMPUTE_LEFT() is executed in a separate thread.
 COMPUTE_RIGHT() runs in the current thread.
 Both functions execute in parallel until sync forces them to join.

⭐ 2. SYNC Keyword
Meaning
The sync keyword forces the program to wait for all spawned tasks created by the current function
to finish before proceeding.
Key Idea
 Acts like a join point.
 Prevents race conditions or incomplete results.
 Ensures correctness when parallel tasks produce output required later.
Example
spawn processPartA()
spawn processPartB()
sync
combineResults()
Explanation:
 Both processPartA() and processPartB() run in parallel.
 The sync keyword waits until both tasks finish.
 Only then combineResults() is executed.

⭐ Simple Real-Life Analogy

Imagine you are cooking:
 You ask one person to chop vegetables → spawn task
 You boil water yourself → main thread
 Before mixing everything, you wait until chopping is done → sync

⭐ Where Spawn & Sync Are Commonly Used

 Multithreaded merge sort
 Multithreaded quicksort
 Parallel matrix operations
 Parallel BFS on graphs
 Divide-and-conquer parallel algorithms
⭐ Summary
Keywor Meaning Purpose
d
spawn Start a function in parallel as a new thread Introduce parallelism
sync Wait until all spawned tasks in current scope finish Synchronization
Write a pseudo code for naïve string matching algorithm and Rabin Karp algorithm for string
matching and analyze the same.

✅ 1. Naïve String Matching Algorithm

Pseudo Code

Time Complexity Analysis

Best Case:
 Pattern mismatches at the first character for every shift
 Only 1 comparison per shift
O(n)
Worst Case:
 Pattern matches for many characters but fails at last character
 Example:
o Text: aaaaaaaaab
o Pattern: aaaab
 For every shift, it compares m characters
O(nm)
Average Case:
O(nm)
Because it compares characters one by one at each shift.

✅ 2. Rabin–Karp String Matching Algorithm

Pseudo Code
Time Complexity Analysis
Expected / Average Case:
Hash comparisons take constant time, and collisions are rare.
O(n+ m)
Best Case:
No collisions occur → only hash comparison needed.
O(n+ m)
Worst Case:
Every hash collides → character-by-character comparison needed each shift.
O(nm)
Space Complexity:
O(1)
(Only hashes and a few integer variables)
🎯 Final Comparison Summary
Algorithm Best Average Worst Notes
Case Case Case
Naïve O(n) O(nm) O(nm) Simple but inefficient
Rabin– O(n + m) O(n + m) O(nm) Fast for multiple patterns; hashing improves
Karp speed

Briefly explain performance measures – speedup, efficiency, throughput, contention, and latency
of rnultithreaded algorithms

✅ Performance Measures in Multithreaded Algorithms

Multithreaded algorithms are evaluated using several performance metrics to understand how well
they utilize parallelism. The key measures are speedup, efficiency, throughput, contention, and
latency.
⭐ 1. Speedup
Definition:
Speedup measures how much faster a parallel (multithreaded) algorithm runs compared to its
sequential version.
Time taken by sequential algorithm
Speedup=
Time taken by parallel algorithm
Example:
 Sequential time = 10 seconds
 Parallel time = 2 seconds
Speedup = 10/2 = 5
Interpretation:
Higher speedup means better use of threads.

⭐ 2. Efficiency
Definition:
Efficiency shows how effectively the available threads (processors) are being used.
Speedup
Efficiency =
Number of threads
Example:
Speedup = 5, Threads = 10
Efficiency = 5/10 = 0.5 (50%)
Interpretation:
 Efficiency close to 1 (100%) means excellent parallel performance.
 Low efficiency means many threads are idle or overhead is high.

⭐ 3. Throughput
Definition:
Throughput is the number of tasks completed per unit time.
Example:
If 50 tasks are completed in 10 seconds → Throughput = 5 tasks/sec.
Interpretation:
Higher throughput means the system handles more work in parallel.

⭐ 4. Contention
Definition:
Contention refers to the conflict between threads when they try to access shared resources (e.g.,
memory, locks, shared variables) at the same time.
Effects of contention:
 Slows down execution
 Causes waiting or blocking
 Reduces speedup and efficiency
Example:
If many threads try to update the same global counter simultaneously, contention increases and
performance drops.

⭐ 5. Latency
Definition:
Latency is the time taken to complete a single task or operation from start to finish.
In multithreaded systems, latency increases due to:
 Context switching
 Synchronization delays
 Communication overhead
Example:
A database query takes 5 ms normally but takes 8 ms in a multithreaded setup due to locking →
increased latency.

🎯 Summary Table
Measure Meaning Good Why It Matters
Value?
Speedup Sequential vs parallel High Indicates parallel gain
improvement
Efficiency Speedup/threads usage Close to 1 Shows how well threads are
used
Throughpu Tasks completed per time High Represents system productivity
t
Contention Competition for shared Low Reduces delays and blocking
resources
Latency Time per task completion Low Faster response for individual
tasks

If we have two matrices of the order m x n and n x p then what will be the time complexity of
multiplying these matrices in conventional approach and in multithreaded approach. Discuss.

✅ Matrix Multiplication Time Complexity

We have two matrices:
 First matrix: A of size m × n
 Second matrix: B of size n × p
The result matrix C will be of size m × p.

⭐ 1. Conventional (Sequential) Matrix Multiplication

To compute each entry C[i][j], we do:
n
C [i][ j]=∑ ❑ A [i][k ]× B [k ][ j]
k=1
Number of operations:
 There are m × p elements in result matrix.
 Each element requires n multiplications and additions.
Total Time Complexity:
O(mnp)
This is the standard complexity taught for classical matrix multiplication.

⭐ 2. Multithreaded Matrix Multiplication

In a multithreaded approach, we try to compute different parts of the result matrix in parallel.
Common parallel strategies:
1. One thread per row
2. One thread per element (cell)
3. Block-level parallelism (divide matrix into blocks)

⭐ Best-Case Theoretical Complexity (Ideal Case)

If we have m × p threads, each computing one element of result matrix, then:
 Each thread performs O(n) work (to compute one output).
 All threads run in parallel.
So, the parallel time becomes:
O(n)
This is the minimum possible time if infinite processors are available.

⭐ Realistic Multithreaded Complexity

In practice, the number of CPU cores = T.
Only T threads can run truly in parallel; others must wait.
Parallel time becomes:
mnp
O( )
T
Where:
 mnp = total work
 T = number of available threads/cores

⭐ Comparison Table
Approach Time Explanation
Complexity
Conventional matrix O(mnp) One processor computes everything
multiplication sequentially
Multithreaded (ideal infinite O(n) Each output element computed in parallel
threads)
Multithreaded (realistic T O(mnp / T) Speed increases proportional to number of
threads) available cores
⭐ Discussion
Advantages of Multithreading
 Faster computation on multi-core processors
 Suitable for large matrices in scientific computing
 Allows parallelization row-wise, column-wise, or block-wise
Limitations
 Speedup is limited by number of cores
 Too many threads → overhead due to context switching
 Synchronization may cause contention