DAA ASSIGNMENT

TASK 1
Q1) Consider the following C function.
int check(int n) {
int i, j, k, count = 0;
for (i = n / 2; i <= n; i++) {
for (j = 1; j + n / 2 < n; j = j * 2) {
for (k = 0; k < n / 2; k++) {
count++;
}
}
}
return count; }
Represent the time complexity of check in terms of Omega notation.

Ans) Time complexity represents the amount of time an algorithm takes to execute as a function
of input size nnn. Omega notation Ω\OmegaΩ represents the best-case lower bound.

The function contains three nested loops:

 Outer loop:

for (i = n/2; i <= n; i++)

→ Runs approximately n/2 times → O(n)

 Middle loop:

for (j = 1; j <= n/2; j++)

 Runs n/2 times → O(n)

 Inner loop:

for (k = 0; k < n/2; k++)

 → Runs n/2 times → O(n)

Total Iterations

T(n)=(n/2)×(n/2)×(n/2)
T(n) = n3/8

Ignoring constants:

T(n)=O(n3)

Omega Notation (Best Case)

Since all loops execute fully regardless of input:

Best case = Worst case = Same execution

Ω(n3)\Omega(n^3)Ω(n3)

Q2) In this problem you are given a set of n points in a 2D plane. The goal is to find the two
points that are closest to each other based on the Euclidean distance. The distance between two
points P1(x1,y1)and P2(x2,y2) is defined as:

d(P1,P2)=sqrt{(x2 - x1)^2 + (y2 - y1)^2}

You are required to implement both a brute-force approach (for simplicity) and an optimized
divide-and-conquer approach to solve the problem. Compare the time complexity of both
approaches and determine the closest pair of points for the given set of points

Input: Consider the following set of points in a 2D plane: Points: P1(2,3) P2(12,30) P3(40,50)
P4(5,1) P5(12,10) P6(3,4) P7(7,8) P8(15,20)

Ans) The closest pair problem aims to find two points in a plane with the minimum Euclidean
distance.

d= root{(x2 - x1)^2 + (y2 - y1)^2}

Brute Force Approach

Steps

1. Compare every pair of points

2. Compute distance
3. Keep track of minimum
Time Complexity

O(n^2)

Divide and Conquer Approach

Steps

1. Sort points based on x-coordinate → O(nlog⁡n)O(n \log n)O(nlogn)

2. Divide into two halves
3. Recursively find minimum in each half
4. Check strip around midpoint

Time Complexity

O(nlogn)

Given Points

(2,3), (12,30), (40,50), (5,1), (12,10), (3,4), (7,8), (15,20)

Distance Calculation

Between (2,3) and (3,4):

D=root[(3-2)^2+(4-3)^2]

d=root(1+1)=root(2)

Q3)Find the City with the Smallest Number of Neighbors at a Threshold Distance.

There are n cities numbered from 0 to [Link] the array edges whrer edges[i]=[fromi, toi,
weighti ] represents a birectional edge between cities fromi and toi, and given the integer
distance Threshold. Return the city with the smallest number of cities that are reachable through
some path and whose distance is at most distance Threshold, If there are multiple such cities,
return the city with the greatest [Link] that the distance of a path connecting cities i and j
is equal to the sum of the edges' weights along that path.
Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4

Ans) We are given cities and weighted edges. The goal is to find the city with the fewest
reachable neighbors within a threshold distance.

Algorithm Used: Floyd–Warshall

dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

Steps

1. Create distance matrix

2. Initialize with edge weights
3. Apply Floyd–Warshall
4. Count reachable cities for each node
5. Choose:
o Minimum count
o If tie → greatest index

Given Input

n=4
edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
threshold = 4

Reachable Cities

 City 0 → 1,2 → count = 2

 City 1 → 0,2,3 → count = 3
 City 2 → 0,1,3 → count = 3
 City 3 → 1,2 → count = 2

Cities 0 and 3 have minimum neighbors.

Choose larger index → City 3

Q4) Apply heuristic algorithm on the nearest-neighbour and multifragment for TSP problem with
a example.

Ans) TSP finds the shortest route visiting all cities once and returning to start.

Nearest Neighbor is a greedy heuristic approach.

Algorithm Steps

1. Start from any node

2. Choose nearest unvisited node
3. Repeat until all nodes visited
4. Return to start

Example Explanation

Start at A:

A→C→E→D→B→A

Cost Calculation

A–C = 1
C–E = 2
E–D = 3
D–B = 7
B–A = 3

Total:

1+2+3+7+3=161 + 2 + 3 + 7 + 3 = 161+2+3+7+3=16

Time Complexity

O(n^2)

Nearest neighbor is simple but does not guarantee optimal solution.

Q5) Solve the following problem using Simplex method

MAX Z = 3x1 + 5x2 + 4x3

subject to

2x1 + 3x2 <= 8

2x2 + 5x3 <= 10

3x1 + 2x2 + 4x3 <= 15

and x1 , x2 , x3 >= 0

Ans)

Simplex Method
Problem

Maximize:

Z=3x1+5x2+4x3

Subject to:

2x1+3x2≤8

2x2+5x3≤10

3x1+2x2+4x3≤15

x1,x2,x3≥0

Convert inequalities into equations

Add slack variables s1,s2,s3

2x1+3x2+s1=8

2x2+5x3+s2=10

3x1+2x2+4x3+s3=15

Objective function:

Z−3x1−5x2−4x3=0
The largest positive value in Cj−Zj is 5, so x2 enters.

Ratio test

8/3,10/2,15/2

Smallest ratio is:

8/3

So s1 leaves.

x1=41/89

x2=41/50

x3=41/62

Now substitute in objective function:

Z=3x1+5x2+4x3

Z=3(89/41)+5(50/41)+4(62/41)

Z=267/41+250/41+248/41

Z=765/41

Z=18.65

Therefore the maximum value of gthe objective function is

Zmax=765/41=18.65

At

X1=89/41,x2=50/41,x3=62/41

Thus the given linear programing problem is solved using the Simplex Method
TASK 2:

Q1) Consider a sorting algorithm that has a time complexity of O(n2) in the worst-case
scenario and O(nlogn) in the best-case scenario. What would be its average-case time
complexity using Theta notation? You have an algorithm that computes the factorial of a
number using a divide-and-conquer approach, resulting in a time complexity of
O(nlogn). What would be its time complexity using Theta notation?

Ans) String matching is the process of finding a pattern string within a larger text string. The
time complexity of string matching depends on the algorithm used and the nature of the input.

In the best case, the pattern is found quickly without many comparisons. Efficient algorithms
like binary search-based or optimized methods can achieve a time complexity of:

O(nlogn)

This happens when comparisons are minimized and the pattern matches early.

In the worst case, the algorithm has to compare the pattern with almost every position in the
text. For example, when the text and pattern have repeated characters, many unnecessary
comparisons occur. In such cases, the time complexity becomes:

O(n^2)

This is common in basic or naive string matching algorithms.

Thus, the time complexity of string matching varies based on the input:

 Best case: (nlogn)

 Worst case: O(n^2)

Efficient algorithms reduce comparisons and improve performance.

Q2) Given a set of n points in a 2D plane, the goal is to find the convex hull of the points. The
convex hull must contain the outermost points, such that no point is inside the polygon formed
by the convex hull.

Input:

Consider the following set of points in a 2D plane: Points (x, y): P1(0,3) P2(2,2) P3(1,1)
P4(2,4) P5(3,1) P6(4,3) P7(3,5) P8(5,0) P9(0,0) P10(1,3)
You are required to implement algorithms to find the convex hull of this set of points. The
convex hull should be represented as a set of points that form the boundary of the convex
polygon.

Ans) The convex hull of a set of points is the smallest convex polygon that contains all the given
points. It is formed using only the outermost points, while the remaining points lie inside or on
the boundary of the polygon.

For the given points:

P1(0,3), P2(2,2), P3(1,1), P4(2,4), P5(3,1), P6(4,3), P7(3,5), P8(5,0), P9(0,0), P10(1,3)

We can use the Graham Scan Algorithm or Jarvis March Algorithm to find the convex hull.

Algorithm Steps

1. Select the lowest point as the starting point.

Here, the lowest-leftmost point is P9(0,0).
2. Sort the remaining points according to their polar angle with the starting point.
3. Check each point one by one and form a boundary.
4. If a point creates an inward turn, remove it.
5. Continue until the outer boundary polygon is formed.

Final Convex Hull Points

The points forming the convex hull are:

P9(0,0), P8(5,0), P6(4,3), P7(3,5), P1(0,3)

So, the convex hull boundary is:

(0,0)→(5,0)→(4,3)→(3,5)→(0,3)→(0,0)

Therefore, the convex hull consists of the outermost points:

P9, P8, P6, P7, P1

All other points lie inside this polygon. The time complexity of Graham Scan is:

O(nlogn)

Q3) Compute the transitive closure of a given directed graph using Warshall's algorithm
and for the same graph implement the all pairs shortest path problem using Floyd’s
Algorithm
Ans)Warshall’s algorithm is used to find the transitive closure of a directed graph. It tells
whether a path exists from one vertex to another. From the given graph, all vertices are reachable
from each other, so the transitive closure matrix is:

Floyd’s algorithm is used to find the shortest distance between every pair of vertices.
Given edges:

1→2=4
1 → 3 = 11
2→1=6
2→3=2
3→1=3

After applying Floyd’s algorithm, the shortest path matrix is:

Thus, Warshall gives reachability, while Floyd gives minimum distance between every pair.

Q4) Utilize backtracking, find the optimal solution to a knapsack problem for the knapsack
instance n=4,m=10,(p1…p7)=(4,7,5,2) and (w1….w7)=(40,42,25,12).

Ans) Given:

n=4, Capacity=10
Weights:

(4,7,5,2)

Profits:

(40,42,25,12)

In 0/1 knapsack, each item can either be selected or rejected. Using backtracking, we explore all
possible combinations and choose the one that gives maximum profit without exceeding
capacity.

Possible combinations:

Item 1 + Item 2:

4+7=11

Not allowed.

Item 1 + Item 3:

4+5=9

Profit:

40+25=65

Item 2 + Item 4:

7+2=9

Profit:

42+12=54

Item 3 + Item 4:

5+2=7

Profit:

25+12=37

Maximum profit is obtained by selecting Item 1 and Item 3.

Maximum Profit=65

Selected items : (1,3)

Q5) A factory manufactures two products A and B on three machines X, Y, and Z. Product A
requires 10 hours of machine X and 5 hours of machine Y a one our of machine Z. The
requirement of product B is 6 hours, 10 hours and 2 hours of machine X, Y and Z respectively.
The profit contribution of products A and B are Rs. 23/ per unit and Rs. 32 / per unit
respectively. In the coming planning period the available capacity of machines X, Y and Z are
2500 hours, 2000 hours and 500 hours respectively. Solve the optimal product mix for
maximizing the profit

Ans) Let:

x=number of Product A
y=number of Product B

Profit function:

Max Z=23x+32y

Subject to machine constraints:

Machine X:

10x+6y≤2500

Machine Y:

5x+10y≤2000

Machine Z:

2y≤500
x,y≥0x

Simplifying:

y≤250

Now checking corner points:

At (250,0)
Z=23(250)+32(0)=5750

At (0,200)

Z=23(0)+32(200)=6400

Intersection of:

10x+6y=2500
5x+10y=2000

Solving gives:

x=185.71, y=107.14

Profit:

Z=23(185.71)+32(107.14)
Z =7700

Therefore, the optimal production is:

x=185.71 , y=107.14

Maximum Profit

Rs. 7700
Task-3
[Link] the following C function. Represent the time complexity of check in terms of
omega, theta, Big-O notation. int check (int n) {
int i, j, k, count = 0;
for (i = n / 2; i <= n; i++) {
for (j = 1; j + n / 2 < n; j = j * 2) {
for (k = 0; k < n / 2; k++) {
count++;
}
}
}
return count;
}
Ans: Loop breakdown:
• Outer loop (i): runs from n/2 to n → exactly ⌊n/2⌋ + 1 iterations ⇒ Θ(n)
• Middle loop (j): condition j + n/2 < n ⇔ j < n/2; j doubles each time (j = 1, 2, 4, ..., <
n/2) ⇒ number of iterations = ⌊log₂(n/2)⌋ + 1 ⇒ Θ(log n)
• Inner loop (k): runs n/2 times ⇒ Θ(n)
Total operations:
Θ(𝑛) × Θ(log⁡ 𝑛) × Θ(𝑛) = Θ(𝑛2 log⁡ 𝑛)

Asymptotic bounds:
• Big-O: 𝑂(𝑛2 log⁡ 𝑛)
• Omega: Ω(𝑛2 log⁡ 𝑛)
• Theta: Θ(𝑛2 log⁡ 𝑛)

2. In this problem you are given a set of n items, where each item has a weight and a value.
Your task is to find the subset of items that maximizes the total value without exceeding a
given weight capacity. This is a classic 0/1 Knapsack Problem, and you will use the
Exhaustive Search technique to solve it.
Given:
• A set of items with their corresponding weights and values.
• A knapsack with a weight capacity.
You need to:
1. List all possible subsets of items.
2. Compute the total weight and total value for each subset.
3. Find the subset that has the maximum value without exceeding the weight capacity.
Input:
Consider the following set of items:
• Item 1: Weight = 2, Value = 3
• Item 2: Weight = 3, Value = 4
• Item 3: Weight = 4, Value = 5
• Item 4: Weight = 5, Value = 6
Ans:
Given:
Item Weight Value

1 2 3

2 3 4

3 4 5

4 5 6

Let the knapsack capacity = 5

Step 1: List All Possible Subsets

Total subsets = 24 = 16
Subset Items Included Total Weight Total Value

S0 {} 0 0

S1 {1} 2 3

S2 {2} 3 4

S3 {3} 4 5

S4 {4} 5 6

S5 {1,2} 5 7

S6 {1,3} 6 8

S7 {1,4} 7 9

S8 {2,3} 7 9

S9 {2,4} 8 10

S10 {3,4} 9 11

S11 {1,2,3} 9 12

S12 {1,2,4} 10 13

S13 {1,3,4} 11 14
Subset Items Included Total Weight Total Value

S14 {2,3,4} 12 15

S15 {1,2,3,4} 14 18

( = exceeds capacity)

Step 2: Valid Subsets (Weight ≤ 5)

• {} → Value = 0
• {1} → Value = 3
• {2} → Value = 4
• {3} → Value = 5
• {4} → Value = 6
• {1,2} → Value = 7

Step 3: Optimal Solution

Maximum value among valid subsets:
Subset {1,2} gives maximum value = 7

Final Answer:
• Selected Items: Item 1 and Item 2
• Total Weight: 5
• Total Value: 7

Conclusion:
Using Exhaustive Search, we checked all possible subsets and found that:
Optimal solution = {1,2}, Max Value = 7

3. Compute the transitive closure of a given directed graph using Warshall's algorithm and for
the same graph implement the all pairs shortest path problem using Floyd's algorithm.
Problem: City of Blinding Lights
Given a directed weighted graph where weight indicates distance, for each query, determine
the length of the shortest path between nodes. There may be many queries, so efficiency
counts. For example, your graph consists of 5 nodes as in the following:
A few queries are from node 4 to node3 ,node 2 to node5 , and node 5 to node3

Ans:
Step 1: Identify Edges from Graph
From the diagram:
• 1→2=8
• 1→4=1
• 4→2=2
• 4→3=9
• 2→3=1
• 3→1=4
Step 2: Initial Distance Matrix (D)
(∞ = no direct edge)
0 8 ∞ 1
∞ 0 1 ∞
𝐷=[ ]
4 ∞ 0 ∞
∞ 2 9 0
Part A: Warshall’s Algorithm (Transitive Closure)
Boolean Matrix (T)
1 1 0 1
0 1 1 0
𝑇=[ ]
1 0 1 0
0 1 1 1
Final Transitive Closure (After Warshall)
1 1 1 1
1 1 1 1
𝑇∗ = [ ]
1 1 1 1
1 1 1 1
Interpretation:
All nodes are reachable from each other.

Part B: Floyd’s Algorithm (Shortest Paths)

Apply:
𝐷[𝑖][𝑗] = min⁡(𝐷[𝑖][𝑗], 𝐷[𝑖][𝑘] + 𝐷[𝑘][𝑗])

Final Shortest Path Matrix

 0 3 4 1
5 0 1 6
𝐷∗ = [ ]
4 7 0 5
7 2 3 0

Step 3: Answer Queries

1→3
Shortest path = 4
2→4
Shortest path = 6
3→2
Shortest path = 7

Final Answer:
Query Shortest Distance

1→34

2→46

3→27

Conclusion
• Warshall: All nodes are reachable
• Floyd: Efficient shortest path for all pairs
• Time Complexity:
𝑂(𝑛3 )

4. Use Branch and Bound to solve the Knapsack problem with the following:
- Weights: [2, 3, 4]
- Values: [3, 4, 5]
- Knapsack Capacity: 5
Show the bounding steps and how the solution is found.
Ans:
Given:
• Weights = [2, 3, 4]
• Values = [3, 4, 5]
• Capacity W = 5
Step 1: Compute Value/Weight Ratio
Item Weight Value Ratio (v/w)

1 2 3 1.5

2 3 4 1.33
Item Weight Value Ratio (v/w)

3 4 5 1.25

Already in decreasing order → no sorting needed.

Step 2: Root Node (Level 0)
• Profit = 0, Weight = 0
• Compute Upper Bound (UB) using fractional knapsack:
Fill capacity 5:
• Take Item 1 → weight = 2, value = 3
• Take Item 2 → weight = 3, value = 4
Total = 7
UB = 7
Step 3: Branching
Level 1: Include Item 1
• Weight = 2, Profit = 3
Bound:
• Remaining capacity = 3
• Add Item 2 fully → +4
• UB = 7

Level 1: Exclude Item 1

• Weight = 0, Profit = 0
Bound:
• Take Item 2 → 4
• Remaining capacity = 2 → fraction of Item 3 → 2/4 × 5 = 2.5
• UB = 6.5
Step 4: Explore Best Node (Include Item 1)
Level 2: Include Item 2
• Weight = 5, Profit = 7
✔ Valid (fits capacity)
✔ This becomes current best solution
Level 2: Exclude Item 2
• Weight = 2, Profit = 3
Bound:
• Remaining capacity = 3
• Fraction of Item 3 → 3/4 × 5 = 3.75
• UB = 6.75

Since 6.75 < 7, prune this branch

Step 5: Explore Other Branch
Exclude Item 1 branch had:
UB = 6.5 < 7

→ Pruned
Final Solution
• Selected Items: Item 1 and Item 2
• Total Weight: 2 + 3 = 5
• Maximum Profit: 3 + 4 = 7
Conclusion
Using Branch and Bound, non-promising branches were pruned using upper bounds,
leading efficiently to:
Optimal Solution Profit = 7

5.

Ans:
Given Graph (Capacities)
From the diagram:
Source = 1, Sink = 8
Edges with capacities:
• 1 → 2 = 10
• 1→3=5
• 1 → 4 = 15
• 2→5=9
• 2 → 6 = 15
• 3→2=4
• 3→6=8
• 3→7=6
• 4→3=4
• 4 → 7 = 30
• 5 → 8 = 10
• 6 → 5 = 15
• 6 → 8 = 10
• 7 → 6 = 15
• 7 → 8 = 10

Step 1: Apply Ford-Fulkerson Method

Augmenting Paths
Path 1: 1 → 2 → 5 → 8
Flow = min(10, 9, 10) = 9
Path 2: 1 → 3 → 6 → 8
Flow = min(5, 8, 10) = 5
Path 3: 1 → 4 → 7 → 8
Flow = min(15, 30, 10) = 10
Path 4: 1 → 4 → 7 → 6 → 5 → 8
Remaining capacities:
• 1→4 = 5 left
• 7→6 = 15
• 6→5 = 15
• 5→8 = 1 left
Flow = 1
Total Max Flow
Max Flow = 9 + 5 + 10 + 1 = 25

Step 2: Minimum Cut

After max flow, separate nodes into:
• S (reachable from source): {1, 4, 7, 6}
• T (remaining nodes): {2, 3, 5, 8}
Cut Edges (S → T)
• 1 → 2 = 10
• 1→3=5
• 6 → 5 = 15
But considering flow saturation, effective cut:
Min Cut Capacity = 25
Final Answer
• Maximum Flow = 25
• Minimum Cut = 25
Conclusion
Max Flow = Min Cut = 25
Task-4
1. You're analyzing the time complexity of an algorithm that uses a divide-and-conquer
approach, and you've identified a recurrence relation of the form T(n)=aT(n/b) +f(n), where a
represents the number of subproblems, b is the factor by which the problem size is reduced,
and f(n) is the time taken to divide the problem, combine subproblem solutions, and perform
any additional work. Use master Theorem and infer the time complexity of the algorithm.

Ans:
Given recurrence:
𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑓(𝑛)
Where:
• 𝑎 = number of subproblems
• 𝑏 = size reduction factor
• 𝑓(𝑛) = extra work (divide + combine)
Step 1: Compute Critical Value
𝑛log⁡𝑏 𝑎
This is compared with 𝑓(𝑛).
Step 2: Apply Master Theorem Cases
Case 1:
If
𝑓(𝑛) = 𝑂(𝑛log⁡𝑏 𝑎−𝜖 )

Then:
𝑇(𝑛) = Θ(𝑛log⁡𝑏 𝑎 )
Case 2:
If
𝑓(𝑛) = Θ(𝑛log⁡𝑏 𝑎 )

Then:
𝑇(𝑛) = Θ(𝑛log⁡𝑏 𝑎 log⁡ 𝑛)
Case 3:
If
𝑓(𝑛) = Ω(𝑛log⁡𝑏 𝑎+𝜖 )

Then:
𝑇(𝑛) = Θ(𝑓(𝑛))
Final Inference
The time complexity depends on comparison between:
𝑓(𝑛)and𝑛log⁡𝑏 𝑎
 Θ(𝑛log⁡𝑏 𝑎 ) if 𝑓(𝑛) is smaller
log⁡ 𝑎
𝑇(𝑛) = {Θ(𝑛 𝑏 log⁡ 𝑛) if equal
Θ(𝑓(𝑛)) if larger
Example (for clarity):
If:
𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛

• 𝑎 = 2, 𝑏 = 2
• 𝑛log⁡2 2 = 𝑛
⇒ 𝑇(𝑛) = Θ(𝑛log⁡ 𝑛)
Conclusion:
Master Theorem provides a direct way to solve divide-and-conquer recurrences in:
𝑂(log⁡ 𝑛) time (analysis)

2. Given the array A = [12, 11, 13, 5, 6, 7] demonstrate how to sort it using the Heap Sort
algorithm. Show the steps for building the heap and sorting the array.
Ans:
Given Array:
𝐴 = [12,11,13,5,6,7]
Step 1: Build Max Heap
Convert array into a Max Heap (largest element at root).
Initial Array:
[12, 11, 13, 5, 6, 7]
Start heapify from last non-leaf node 𝑖 = 𝑛/2 − 1 = 2
Heapify at i = 2
• Element = 13, children = (none significant)
→ No change
Heapify at i = 1
• Element = 11, children = 5, 6
→ Already satisfies heap
→ No change
Heapify at i = 0
• Element = 12, children = 11, 13
→ Largest = 13 → swap
[13, 11, 12, 5, 6, 7]
Max Heap Formed:
[13, 11, 12, 5, 6, 7]
Step 2: Heap Sort (Extract Max)
Pass 1:
Swap root with last element
[7, 11, 12, 5, 6, 13]
Heapify:
 [12, 11, 7, 5, 6, 13]
Pass 2:
[6, 11, 7, 5, 12, 13]
Heapify:
[11, 6, 7, 5, 12, 13]
Pass 3:
[5, 6, 7, 11, 12, 13]
Heapify:
[7, 6, 5, 11, 12, 13]
Pass 4:
[5, 6, 7, 11, 12, 13]
Heapify:
[6, 5, 7, 11, 12, 13]
Pass 5:
[5, 6, 7, 11, 12, 13]
Final Sorted Array:
[5, 6, 7, 11, 12, 13]
Conclusion
• Heap Sort builds a Max Heap, then repeatedly extracts the maximum element.
• Time Complexity:
Best = Average = Worst = 𝑂(𝑛log⁡ 𝑛)

3. Given an integer array of coins[] of size n representing different types of denominations

and an integer sum, the task is to count all combinations of coins to make a given value
sum. Input: sum = 10, coins[] = [2, 5, 3, 6] Output: 5 Explanation: There are five
solutions: [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5] and [5, 5]
Ans:
Given:
• Coins = [2, 5, 3, 6]
• Sum = 10
Approach: Dynamic Programming
Let
𝑑𝑝[𝑖] = number of ways to make sum 𝑖
Step 1: Initialize
• 𝑑𝑝[0] = 1 (one way to make sum 0 — choose nothing)
• All other values = 0
𝑑𝑝 = [1,0,0,0,0,0,0,0,0,0,0]
Step 2: Process Each Coin
Using coin = 2
Update multiples of 2:
𝑑𝑝 = [1,0,1,0,1,0,1,0,1,0,1]
Using coin = 5
 𝑑𝑝 = [1,0,1,0,1,1,1,1,1,1,2]
Using coin = 3
𝑑𝑝 = [1,0,1,1,1,2,2,2,3,3,4]
Using coin = 6
𝑑𝑝 = [1,0,1,1,1,2,3,2,4,4,5]
Step 3: Final Answer
𝑑𝑝[10] = 5
All Possible Combinations
1. [2, 2, 2, 2, 2]
2. [2, 2, 3, 3]
3. [2, 2, 6]
4. [2, 3, 5]
5. [5, 5]
Conclusion
• Number of ways = 5
• Time Complexity: 𝑂(𝑛 × sum)
• Space Complexity: 𝑂(sum)

4. Solve the following cost matrix using Branch and Bound to minimize the total cost:
[5, 8, 6]
[7, 3, 2]
[9, 6, 4]
Write the step-by-step process, including how bounds are calculated.
Ans:
Problem: Minimize Cost (3 × 3 Matrix)
5 8 6
[7 3 2]
9 6 4
Goal: Assign each row to one column with minimum total cost.
Step 1: Row Reduction
Subtract minimum of each row:
• Row1 min = 5 → [0, 3, 1]
• Row2 min = 2 → [5, 1, 0]
• Row3 min = 4 → [5, 2, 0]
0 3 1
[5 1 0]
5 2 0
Row reduction cost = 5 + 2 + 4 = 11
Step 2: Column Reduction
Column mins:
• Col1 min = 0
• Col2 min = 1
• Col3 min = 0
After reduction:
 0 2 1
[5 0 0]
5 1 0
Column reduction cost = 1
Initial Lower Bound (LB)
𝐿𝐵 = 11 + 1 = 12
Step 3: Branching (State Space Tree)
We assign row by row.
Branch 1: Row1 → Col1
Remaining matrix:
0 0
[ ]
1 0
Possible assignments:
• Row2 → Col2 (3), Row3 → Col3 (4)
Total cost:
5 + 3 + 4 = 12
Branch 2: Row1 → Col2
Cost = 8
Remaining best:
• Row2 → Col3 (2), Row3 → Col1 (9)
Total:
8 + 2 + 9 = 19
Branch 3: Row1 → Col3
Cost = 6
Remaining:
• Row2 → Col2 (3), Row3 → Col1 (9)
Total:
6 + 3 + 9 = 18
Step 4: Choose Minimum
Best solution:
12
Final Assignment
Row Column Cost

1 1 5

2 2 3

3 3 4

Final Answer
• Minimum Cost = 12
Conclusion
Branch and Bound prunes higher-cost branches and finds optimal assignment efficiently.

5.

Ans:
Given Network
Edges with capacities:
• S →A=8
• S→D=3
• A→B=9
• D→B=7
• D→C=4
• B→T=2
• C→T=5
Solution
We use the Maximum Flow Method (Ford-Fulkerson Method) to calculate the maximum
amount of liquid that can flow from source S to sink T.
Step 1: Find Augmenting Path 1
Path:
𝑆→𝐴→𝐵→𝑇
Capacities:
• S →A=8
• A→B=9
• B→T=2
Minimum capacity:
min⁡(8,9,2) = 2
So, flow through this path = 2 units
Step 2: Find Augmenting Path 2
Path:
 𝑆→𝐷→𝐶→𝑇
Capacities:
• S→D=3
• D→C=4
• C→T=5
Minimum capacity:
min⁡(3,4,5) = 3
So, flow through this path = 3 units
Step 3: Calculate Total Maximum Flow
Maximum Flow = 2 + 3
Maximum Flow = 5
Result
Maximum liquid flow from source S to sink T is 5 units

Thus, the maximum amount of liquid that can be sent from the source to the sink at an
instance is 5 units.
TASK 5

Task 5 — Question 1: Big Omega Definition and Verification

Full Question:
Show the mathematical definition of Big Omega (Ω). For the functions defined by: f(n) = 3n³
+ 2n² + 1 and g(n) = 2n² + 3, verify that f(n) = Ω(g(n)).

Answer:
Mathematical Definition of Big Omega (Ω):
A function f(n) is said to be Ω(g(n)) (Big Omega of g(n)) if and only if there exist positive constants c and n₀ such
that:
f(n) ≥ c · g(n) for all n ≥ n₀
In formal notation: f(n) = Ω(g(n)) iff c > 0, n₀ > 0 such that f(n) ≥ c·g(n) n ≥ n₀∃ ∀ Big
Omega provides a LOWER BOUND on the growth rate of a function.

Verification that f(n) = Ω(g(n)):

Given: f(n) = 3n³ + 2n² + 1 and g(n) = 2n² + 3
We need to show: 3n³ + 2n² + 1 ≥ c · (2n² + 3) for some constants c > 0 and n₀ > 0

Step 1: Choose c = 1 (a simple positive constant)

Step 4: Choose n₀ = 1. For all n ≥ 1: 3n³ ≥ 3 ≥ 2, so the inequality holds.

Conclusion:
With c = 1 and n₀ = 1, we have proven that:
f(n) = 3n³ + 2n² + 1 ≥ 1 · (2n² + 3) = g(n) for all n ≥ 1
Therefore, f(n) = Ω(g(n)). ✓
This makes sense because f(n) is a cubic polynomial (degree 3) and g(n) is a quadratic polynomial (degree 2). A
cubic always dominates a quadratic for sufficiently large n, so it is clearly a lower bound of higher growth.
Task 5 — Question 2: Travelling Salesman Problem (Exhaustive Search)
Full Question:
You are required to use the Exhaustive Search method (brute-force) to find the optimal solution to the TSP for a
given set of cities and distances between them. Also analyze the time complexity of the brute-force approach.
Input: Consider a set of 4 cities labeled A, B, C, D with the following distances (in km):

From / To A B C D

A 0 10 15 20

B 10 0 35 25

C 15 35 0 30

D 20 25 30 0

Find the shortest route visiting each city exactly once and returning to the start.

Answer:
Approach: Exhaustive Search / Brute Force
Fix city A as the starting point. Find all permutations of the remaining 3 cities (B, C, D). Total
permutations = (n-1)! = (4-1)! = 3! = 6 routes All Possible Routes and Their Costs:

Route Distance Calculation Total Cost (km)

A→B→C→D→A 10 + 35 + 30 + 20 95

A→B→D→C→A 10 + 25 + 30 + 15 80

A→C→B→D→A 15 + 35 + 25 + 20 95

A→C→D→B→A 15 + 30 + 25 + 10 80

A→D→B→C→A 20 + 25 + 35 + 15 95

A→D→C→B→A 20 + 30 + 35 + 10 95

Optimal Solution:
Minimum cost = 80 km
Optimal routes: A→B→D→C→A OR A→C→D→B→A (both are 80 km — they are reverses of each other)

Time Complexity Analysis:

• Brute Force TSP: O((n-1)!) ≈ O(n!)
• For n=4: 3! = 6 routes
• For n=10: 9! = 362,880 routes
• For n=20: 19! ≈ 1.2 × 10¹⁷ routes — computationally infeasible This exponential growth is why
TSP is classified as NP-Hard.

Task 5 — Question 3: Stock Buy-Sell for Maximum Profit (Greedy)

Full Question:
Given an array prices[] of size n denoting the cost of stock on each day, find the maximum total profit if we can
buy and sell the stocks any number of times. We can only sell a stock which we have bought earlier and we
cannot hold multiple stocks on any day.
Input: prices[] = {100, 180, 260, 310, 40, 535, 695}
Output: 865
Explanation: Buy on day 0 (100), sell on day 3 (310) → profit = 210. Buy on day 4 (40), sell on day 6
(695) → profit = 655. Maximum Profit = 210 + 655 = 865

Answer:
Algorithm: Greedy Approach
The key insight is: Add the profit whenever the price rises from one day to the next. This is equivalent to buying
at every local minimum and selling at every local maximum.

Step-by-Step Solution:
Day Price Action Profit

0 (Mon) 100 Buy -

1 (Tue) 180 Price rising — hold -

2 (Wed) 260 Price rising — hold -

3 (Thu) 310 Sell (peak before drop) 310 - 100 =

210

4 (Fri) 40 Buy (new low) -

5 (Sat) 535 Price rising — hold -

6 (Sun) 695 Sell (end of array) 695 - 40 = 655

Total Maximum Profit = 210 + 655 = 865

Greedy Justification:
At each step, if prices[i+1] > prices[i], we add the difference (prices[i+1] - prices[i]) to profit. This captures ALL
upward movements.

Time Complexity: O(n) | Space Complexity: O(1)

Task 5 — Question 4: Subset Sum Problem using Backtracking
Full Question:
Solve the Subset Sum problem using backtracking for the set {2, 3, 7, 8, 10} and a target sum of 15.
List all possible subsets that satisfy the condition.

Answer:
Problem Setup:
Set = {2, 3, 7, 8, 10}, Target = 15
We use backtracking to explore all subsets systematically.

Backtracking Tree Exploration:

At each node, we decide to INCLUDE or EXCLUDE each element:

Include 2 → {2}
Include 3 → {2,3}
Include 7 → {2,3,7} = 12 → continue
Include 8 → {2,3,7,8} = 20 > 15 → PRUNE
Exclude 8:
Include 10 → {2,3,7,10} = 22 > 15 → PRUNE
Exclude 7:
Include 8 → {2,3,8} = 13 → continue
Include 10 → {2,3,8,10} = 23 > 15 → PRUNE
Exclude 8:
Include 10 → {2,3,10} = 15 → *** SOLUTION *** ✓
Exclude 3:
Include 7 → {2,7} = 9 → continue
Include 8 → {2,7,8} = 17 > 15 → PRUNE
Exclude 8:
Include 10 → {2,7,10} = 19 > 15 → PRUNE
Exclude 7:
Include 8 → {2,8} = 10 → continue
Include 10 → {2,8,10} = 20 > 15 → PRUNE
Exclude 8:
Include 10 → {2,10} = 12 ≠ 15
Exclude 2:
Include 3 → {3}
Include 7 → {3,7} = 10 → continue
Include 8 → {3,7,8} = 18 > 15 → PRUNE
Exclude 8:
Include 10 → {3,7,10} = 20 > 15 → PRUNE
Exclude 7:
Include 8 → {3,8} = 11 → continue
Include 10 → {3,8,10} = 21 > 15 → PRUNE
Exclude 8:
Include 10 → {3,10} = 13 ≠ 15
Exclude 3:
Include 7 → {7}
Include 8 → {7,8} = 15 → *** SOLUTION *** ✓
Exclude 8:
Include 10 → {7,10} = 17 > 15 → PRUNE
Exclude 7:
Include 8 → {8}
Include 10 → {8,10} = 18 > 15 → PRUNE
Exclude 8:
Include 10 → {10} ≠ 15
All Valid Subsets (Summing to 15):
• Subset 1: {2, 3, 10} → 2 + 3 + 10 = 15 ✓
• Subset 2: {7, 8} → 7 + 8 = 15 ✓

Time Complexity: O(2^n) — explores all 2^5 = 32 subsets in worst case With pruning,
the actual number explored is significantly less.

Task 5 — Question 5: Bipartite Matching / Marriage Problem

Full Question:
The two richest families in Westeros have decided to enter into an alliance by marriage. The first family has 10
sons, the second has 10 girls. The ages of the kids in the two families match up. To avoid impropriety, each child
must marry someone either their own age, or someone one position younger or older (i.e., in a path graph
matching).
Questions: (a) How many different acceptable marriage arrangements marrying all 20 children are possible? (b)
How many if exactly 6 boys marry girls NOT their own age? (c) Can you generalize? (d) Apply a recurrence
relation.

Answer:
Understanding the Graph:
The bipartite graph connects boy i to girl i-1, girl i, and girl i+1 (path graph). We must find a PERFECT MATCHING
in this graph.

Part (a): Total perfect matchings for 10 boys and 10 girls

This is equivalent to counting the number of ways to tile a 1×n strip with 1×1 and 1×2 dominoes, which follows
the Fibonacci sequence.

Let M(n) = number of perfect matchings for n boys and n girls.

Recurrence: M(n) = M(n-1) + M(n-2)
Base cases: M(1) = 1, M(2) = 2

n M(n) Meaning

1 1 1 matching: (B1-G1)

2 2 2 matchings: (B1-G1,B2-G2) or (B1-G2,B2-G1)

n M(n) Meaning

3 3

4 5

5 8
 6 13

7 21

8 34

9 55

10 89 ANSWER to Part (a)

Answer (a): M(10) = 89 different acceptable marriage arrangements

Part (b): Exactly 6 boys marry girls NOT their own age
If 6 boys marry 'off-age' (i.e., cross-matches), that means 4 boys marry their exact age match, and 6 boys marry
one position up or down.
The cross-matches form pairs. 6 cross-matches = 3 adjacent pairs that cross-match.
This is equivalent to choosing 3 non-overlapping adjacent pairs from 10 positions, where each pair swaps.
Number of ways to choose k non-overlapping adjacent pairs from n positions = C(n-k, k)
For n=10, k=3: C(10-3, 3) = C(7, 3) = 35
Answer (b): 35 arrangements with exactly 6 boys marrying off-age

Part (c): Generalization

For n boys and n girls with k cross-matches (k must be even, say k = 2m):
Number of arrangements with exactly 2m cross-matches = C(n-m, m)
Total perfect matchings = Σ C(n-m, m) for m = 0 to floor(n/2) = Fibonacci(n+1)

Part (d): Recurrence Relation

M(n) = M(n-1) + M(n-2), with M(0) = 1, M(1) = 1
This is the Fibonacci recurrence, and the sequence M(1), M(2), ... = 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
TASK 6

Task 6 — Question 1: Time Complexity Tracing of Three Functions

Full Question:
Trace the complexity of the following functions:
i) function(int n): nested for loops with break statement ii)
void function(int n): while loop with s += i iii) void
function(int n): triple nested loop with doubling

Answer — Function (i):

void function(int n) { if
(n==1) return; for (int i=1;
 i<=n; i++) { for (int j=1;
j<=n; j++) {
printf("*");
break;
}
}
}

Analysis:
• The outer loop runs n times (i = 1 to n)
• The inner loop runs only ONCE each time because of the 'break' statement
• So printf("*") is executed exactly n times total Time Complexity of Function (i): O(n)

Answer — Function (ii):

void function(int n) {
int i = 1, s = 1;
while (s <= n) {
i++; s += i;
printf("*");
}
}

Analysis:
s is the sum of first k natural numbers after k iterations:
s = 1 + 2 + 3 + ... + k = k(k+1)/2
Loop terminates when s > n, i.e., k(k+1)/2 > n → k ≈ √(2n) → k = O(√n)
Time Complexity of Function (ii): O(√n)
Answer — Function (iii):
void function(int n) {
int count = 0;
for (int i = n/2; i <= n; i++)
for (int j = 1; j <= n; j = 2*j)
for (int k = 1; k <= n; k = k*2)
count++;
}

Analysis:
• Outer loop (i): runs from n/2 to n → runs n - n/2 + 1 = n/2 times → O(n) iterations
• Middle loop (j): j doubles each time (1, 2, 4, 8, ...) → runs O(log n) iterations
• Inner loop (k): k doubles each time (1, 2, 4, 8, ...) → runs O(log n) iterations
Total = O(n) × O(log n) × O(log n) = O(n log²n)
Time Complexity of Function (iii): O(n log²n)
Task 6 — Question 2: Merge Sort on Array A=[36,25,40,2,7,80,15]
Full Question:
Apply the Merge Sort algorithm to the array A=[36,25,40,2,7,80,15] and show how you would split and merge
the array step by step.

Answer:
Initial Array: [36, 25, 40, 2, 7, 80, 15]

Phase 1: Splitting (Divide)

Level 0: [36, 25, 40, 2, 7, 80, 15]
Level 1: [36, 25, 40, 2] [7, 80, 15]
Level 2: [36, 25] [40, 2] [7, 80] [15]
Level 3: [36] [25] [40] [2] [7] [80] [15]

Phase 2: Merging (Conquer) Merge

[36] and [25]:
Compare 36 vs 25 → take 25, then 36
Result: [25, 36]

Merge [40] and [2]:

Compare 40 vs 2 → take 2, then 40
Result: [2, 40]

Merge [25, 36] and [2, 40]:

Compare 25 vs 2 → take 2
Compare 25 vs 40 → take 25
Compare 36 vs 40 → take 36
Take remaining 40
Result: [2, 25, 36, 40]

Merge [7] and [80]:

Compare 7 vs 80 → take 7, then 80
Result: [7, 80]

Merge [7, 80] and [15]:

Compare 7 vs 15 → take 7
Compare 80 vs 15 → take 15
Take remaining 80
Result: [7, 15, 80]

Final Merge [2, 25, 36, 40] and [7, 15, 80]:
Compare 2 vs 7 → take 2
Compare 25 vs 7 → take 7
 Compare 25 vs 15 → take 15
Compare 25 vs 80 → take 25
Compare 36 vs 80 → take 36
Compare 40 vs 80 → take 40
Take remaining 80
Result: [2, 7, 15, 25, 36, 40, 80]

Final Sorted Array: [2, 7, 15, 25, 36, 40, 80]

Time Complexity: O(n log n) for all cases | Space: O(n)

Task 6 — Question 3: 0/1 Knapsack using Dynamic Programming

Full Question:
To solve the 0/1 Knapsack Problem using dynamic programming, figure out which treasures to pack to
maximize the total value, and at the same time keeping below the backpack's weight limit. (Note: Solved with
representative example — Items: W={2,3,4,5}, V={3,4,5,6}, Capacity=8)

Answer:
Items Table:
Item Weight Value

1 2 3

2 3 4

3 4 5

4 5 6

Capacity W = 8
DP Table dp[i][w] = max value using first i items with capacity w:

Item \ Cap 0 1 2 3 4 5 6 7 8

0 (none) 0 0 0 0 0 0 0 0 0

1 (w=2,v=3) 0 0 3 3 3 3 3 3 3

2 (w=3,v=4) 0 0 3 4 4 7 7 7 7

3 (w=4,v=5) 0 0 3 4 5 7 8 9 9

4 (w=5,v=6) 0 0 3 4 5 7 8 9 10

Maximum Value = dp[4][8] = 10

Backtracking to Find Selected Items:

• dp[4][8]=10 ≠ dp[3][8]=9 → Include Item 4 (w=5, v=6). Remaining cap = 8-5 = 3
 • dp[3][3]=4 ≠ dp[2][3]=4 → Item 3 not included (equal). Skip
• dp[2][3]=4 ≠ dp[1][3]=3 → Include Item 2 (w=3, v=4). Remaining cap = 3-3 = 0
• Done — no more capacity

Optimal Selection: Items 2 and 4 → Total weight = 8, Total value = 10 Time

Complexity: O(n × W) | Space Complexity: O(n × W)

Task 6 — Question 4: Hamiltonian Cycle using Backtracking

Full Question:
Discuss the algorithm to determine Hamiltonian Cycle in a graph using backtracking. For the following graph
determine the Hamiltonian cycle.

Answer:
Algorithm — Hamiltonian Cycle using Backtracking:
1. Start from vertex 0, add it to the path.
2. Try adding each adjacent vertex not already in the path.
3. If all vertices are visited and last vertex connects back to start → Hamiltonian Cycle found.
4. If no valid vertex exists, backtrack by removing last added vertex.
5. Repeat until a solution is found or all possibilities exhausted.

Graph (Adjacency Matrix from Task 7, Q4 — 4 vertices):

[0, 1, 1, 0]
[1, 0, 1, 1]
[1, 1, 0, 1]
[0, 1, 1, 0]
Edges: 0-1, 0-2, 1-2, 1-3, 2-3

Backtracking Execution:
Start: path = [0]
Add 1 (0-1 exists): path = [0, 1]
Add 2 (1-2 exists): path = [0, 1, 2]
Add 3 (2-3 exists): path = [0, 1, 2, 3]
All 4 vertices visited! Check if 3→0 exists: No edge (0 in row 3 = 0).
BACKTRACK
No more options from 2. Backtrack: path = [0, 1]
Add 3 (1-3 exists): path = [0, 1, 3]
Add 2 (3-2 exists): path = [0, 1, 3, 2]
All 4 vertices visited! Check if 2→0 exists: Yes (adj[2][0]=1). ***
SUCCESS ***

Hamiltonian Cycle Found: 0 → 1 → 3 → 2 → 0

Time Complexity: O(n!) in worst case

Task 6 — Question 5: Bipartite Matching — Max Cardinality Matching

Full Question:
Apply Bipartite Matching method to find a max cardinality matching.
Graph: Left set {1,2,3,4,5}, Right set {A,B,C,D,E} with connections shown in the figure.

Answer:
Bipartite Matching — Augmenting Path Method (Hopcroft-Karp concept):

Algorithm Steps:
6. Initially, all vertices are unmatched.
7. For each left vertex, try to find an augmenting path using BFS/DFS.
8. An augmenting path alternates between unmatched and matched edges.
9. If found, augment (flip) the matching along this path.
10. Repeat until no augmenting path exists.

Example Execution (standard 5-5 bipartite graph):

Assume edges: 1-A, 1-B, 2-B, 3-C, 3-D, 4-D, 5-E (representative example)

Step 1: Match 1 → A (direct edge, free)

Step 2: Match 2 → B (direct edge, free)
Step 3: Match 3 → C (direct edge, free)
Step 4: Try 4 → D (direct edge, free) → Match 4 → D
Step 5: Try 5 → E (direct edge, free) → Match 5 → E
Maximum Matching: {(1,A), (2,B), (3,C), (4,D), (5,E)} Maximum
Cardinality = 5 (perfect matching)

Key Theorem (König's Theorem):

In a bipartite graph, the size of maximum matching = minimum vertex cover.
Time Complexity: O(V × E) using augmenting paths | O(E√V) using Hopcroft-Karp
TASK 7

Task 7 — Question 1: Master Theorem for Divide-and-Conquer

Full Question:
Imagine you're working on a project that involves processing a large dataset. You've developed an algorithm to
perform a certain task on this dataset, and you want to analyze its time complexity to understand how it will
perform as the dataset size grows. Your algorithm splits the dataset into two equal parts, processes each part
recursively, and then combines the results. Each recursive call takes n/2 time, where 'n' is the size of the dataset.
Assume that the time complexity of your algorithm can be described using the Master's Theorem. Use it to
analyze the time complexity.

Answer:
Recurrence Relation:
T(n) = 2T(n/2) + n
(2 subproblems, each of size n/2, combining cost = n)

Master Theorem:
For T(n) = aT(n/b) + f(n):
• a = number of subproblems (a ≥ 1)
• b = factor by which input size is reduced (b > 1)
• f(n) = cost of dividing and combining

Three Cases:
Case 1: If f(n) = O(n^(log_b(a) - ε)) for some ε > 0 → T(n) = Θ(n^(log_b(a)))
Case 2: If f(n) = Θ(n^(log_b(a))) → T(n) = Θ(n^(log_b(a)) · log n) Case 3: If
f(n) = Ω(n^(log_b(a) + ε)) for some ε > 0 → T(n) = Θ(f(n))

Applying to Our Problem:

a = 2, b = 2, f(n) = n n^(log_b(a)) =
n^(log_2(2)) = n^1 = n Compare f(n) = n
with n^(log_b(a)) = n:
f(n) = n = Θ(n^1) = Θ(n^(log_b(a))) →
This is Case 2!

Result: T(n) = Θ(n log n)

This is the same complexity as Merge Sort — O(n log n), which is optimal for comparison-based sorting and many
divide-and-conquer algorithms.
Task 7 — Question 2: Quick Sort on Array A=[44,33,11,55,77,90,40,60,99,22,88]
Full Question:
Apply the Quick Sort algorithm to the array A=[44 33 11 55 77 90 40 60 99 22 88] and show how you would split
and merge the array step by step.

Answer:
Initial Array: [44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88] Strategy: Use
last element as pivot each time.

Pass 1: Pivot = 88
Array: [44, 33, 11, 55, 77, 90, 40, 60, 99, 22 | 88]
Partition: elements < 88 go left, elements > 88 go right
< 88: [44, 33, 11, 55, 77, 40, 60, 22]
> 88: [90, 99]
After partition: [44, 33, 11, 55, 77, 40, 60, 22, 88, 90, 99]
↑ pivot in final position

Pass 2 (Left subarray): [44, 33, 11, 55, 77, 40, 60, 22] — Pivot = 22
< 22: [11]
> 22: [44, 33, 55, 77, 40, 60]
Result: [11, 22, 44, 33, 55, 77, 40, 60]

Pass 3 (Right of 22): [44, 33, 55, 77, 40, 60] — Pivot = 60
< 60: [44, 33, 55, 40]
> 60: [77]
Result: [44, 33, 55, 40, 60, 77]

Pass 4: [44, 33, 55, 40] — Pivot = 40

< 40: [33]
> 40: [44, 55]
Result: [33, 40, 44, 55]

Pass 5: [44, 55] — Pivot = 55

< 55: [44]
> 55: []
Result: [44, 55]

Pass 6 (Right subarray): [90, 99] — Pivot = 99

< 99: [90]
> 99: []
Result: [90, 99]

Final Sorted Array: [11, 22, 33, 40, 44, 55, 60, 77, 88, 90, 99]
Time Complexity:
• Best Case: O(n log n) — when pivot always divides array into equal halves
• Average Case: O(n log n)
 • Worst Case: O(n²) — when pivot is always the smallest or largest element
Space Complexity: O(log n) average for recursion stack

Task 7 — Question 3: 0/1 Knapsack using Dynamic Programming (Capacity W=5)

Full Question:
Solve Knapsack problem using Dynamic Programming.
Capacity W = 5
Item Weight Value

1 2 12

2 1 10

3 3 20

4 2 15

Find the optimal subset.

Answer:
DP Table: dp[i][w] = maximum value using first i items with capacity w

Item \ Cap 0 1 2 3 4 5

0 (none) 0 0 0 0 0 0

1 0 0 12 12 12 12
(w=2,v=12)

2 0 10 12 22 22 22
(w=1,v=10)

3 0 10 12 22 30 32
(w=3,v=20)

4 0 10 15 25 30 37
(w=2,v=15)
DP Recurrence:
If w[i] ≤ w: dp[i][w] = max(dp[i-1][w], dp[i-1][w-w[i]] + v[i]) If
w[i] > w: dp[i][w] = dp[i-1][w]

Maximum Value = dp[4][5] = 37

Backtracking to Find Selected Items:

• dp[4][5]=37 ≠ dp[3][5]=32 → Include Item 4 (w=2, v=15). Remaining cap = 5-2 = 3
• dp[3][3]=22 = dp[2][3]=22 → Item 3 not included
 • dp[2][3]=22 ≠ dp[1][3]=12 → Include Item 2 (w=1, v=10). Remaining cap = 3-1 = 2
• dp[1][2]=12 ≠ dp[0][2]=0 → Include Item 1 (w=2, v=12). Remaining cap = 2-2 = 0

Optimal Subset: Items {1, 2, 4}

Total Weight = 2+1+2 = 5 (exactly at capacity)
Total Value = 12+10+15 = 37 (maximum possible)
TASK 8

Task 8 — Question 1: Best and Worst Case Time Complexity of Function

Full Question:
Observe the best case and worst-case time complexity of the following function:
void fun(int n, int arr[]) {
int i = 0, j = 0; for (; i
< n; ++i)
while (j < n && arr[i] < arr[j])
j++;
}

Answer:
Understanding the Code:
The outer for loop runs from i=0 to n-1 (n iterations).
The inner while loop increments j (NOT i). j is NOT reset inside the for loop — it persists across iterations.

Key Observation:
Variable j starts at 0 and can only increment. It NEVER decreases. Since j can go from 0 to at most n, the while
loop in TOTAL across all iterations of the for loop can execute at most n times.

Best Case Analysis:

The while loop condition fails immediately (arr[i] >= arr[j]) for every i.
Example: Sorted array in descending order [5,4,3,2,1] — each arr[i] ≥ arr[0], so while never executes. Total
operations = n (just the outer for loop) Best Case Time Complexity: Ω(n)

Worst Case Analysis:

The total number of while loop iterations across ALL for loop iterations is bounded by n, because j is
monotonically increasing from 0 to n.
Total operations = n (outer loop) + n (total while loop iterations) = 2n Worst Case
Time Complexity: O(n)

Conclusion:
Both best and worst case are O(n). Therefore: Time
Complexity = Θ(n) (Tight Bound)

Task 8 — Question 2: Convex Hull using Graham Scan

Full Question:
Given a set of points P={(1,1),(2,2),(3,3),(5,0),(0,0),(4,4)} apply the Graham Scan or Gift Wrapping algorithm to
find the convex hull of the points. Show your steps.

Answer:
Step 1: Find the lowest point (anchor):
Lowest y-coordinate: (0,0). If tie, choose leftmost. Anchor
point P0 = (0,0)

Step 2: Sort remaining points by polar angle with respect to P0:

Point Angle from (0,0) Distance

(5,0) 0° (along x-axis) 5

(1,1) 45° √2 ≈ 1.41

(2,2) 45° 2√2 ≈ 2.83

(3,3) 45° 3√2 ≈ 4.24

(4,4) 45° 4√2 ≈ 5.66

Sorted order by angle (collinear points sorted by distance): (0,0), (5,0), (1,1), (2,2), (3,3), (4,4) Note: For
collinear points at the same angle, keep only the farthest: (0,0), (5,0), (4,4)

Step 3: Graham Scan — Push/Pop stack:

Start: Stack = [(0,0)]
Add (5,0): Stack = [(0,0), (5,0)]
Add (4,4): Check turn at (5,0)
Cross product of (0,0)→(5,0)→(4,4):
(5-0,0-0)=(5,0), (4-5,4-0)=(-1,4)
Cross = 5×4 - 0×(-1) = 20 > 0 → LEFT TURN → keep
Stack = [(0,0), (5,0), (4,4)]

Step 4: Close the hull back to start: Check (4,4)

→ (0,0): Left turn → valid

Convex Hull Points (in order): (0,0) → (5,0) → (4,4) → (0,0)

Verification:
All other points (1,1), (2,2), (3,3) lie on the line y=x between (0,0) and (4,4) — they are INSIDE or ON the hull,
which is correct.
Time Complexity: O(n log n) due to initial sorting
Task 8 — Question 3: Minimum Spanning Tree using Kruskal's Algorithm
Full Question:
Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's Algorithm (MST: Really Special
Subtree).
Graph: Multiple vertices connected by weighted edges (as shown in the figure with vertices 0-8 and various
weights).

Answer:
Kruskal's Algorithm Steps:
11. Sort all edges by weight in ascending order.
12. Initialize a Union-Find (Disjoint Set) for all vertices.
13. For each edge (in sorted order): if the two vertices are in different components, add the edge to MST
and union the components.
14. Stop when MST has (V-1) edges.

Example Execution (Representative graph with 9 vertices, 0-indexed): Assume edges

sorted by weight:
Edge Weight Action Reason

0-1 1 Add to MST Different components

1-6 2 Add to MST Different components

6-7 2 Add to MST Different components

5-6 4 Add to MST Different components

4-5 5 Add to MST Different components

3-4 5 Add to MST Different components

2-3 7 Add to MST Different components

8-4 8 Add to MST Different components (8th edge → MST

complete)
MST properties:
• MST has exactly V-1 = 8 edges for 9 vertices
• MST is acyclic and connects all vertices
• No edge can be added without creating a cycle
Time Complexity: O(E log E) for sorting | O(E α(V)) for union-find operations Overall: O(E log E) ≈
O(E log V)

Task 8 — Question 4: Rat in a Maze using Backtracking

Full Question:
Implement a backtracking algorithm to solve Rat in a Maze using recursion.

Answer:
Problem Description:
A rat starts at (0,0) in an N×N maze and must reach (N-1,N-1). The rat can only move Right or Down. A cell with 1
is open, 0 is blocked.

Example Maze (4×4):

1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

Algorithm:
Function solveMaze(maze, x, y, solution):
IF (x, y) == (N-1, N-1) AND maze[x][y] == 1:
solution[x][y] = 1
PRINT solution
RETURN True
IF isSafe(maze, x, y):
solution[x][y] = 1 // Mark cell
IF solveMaze(maze, x+1, y, solution): RETURN True // Move DOWN
IF solveMaze(maze, x, y+1, solution): RETURN True // Move RIGHT
solution[x][y] = 0 // BACKTRACK — unmark cell
RETURN False
RETURN False

Execution Trace:
(0,0) → Mark. Try Down:
(1,0) → Mark. Try Down:
(2,0) = 0. BLOCKED. Backtrack
Try Right:
(1,1) → Mark. Try Down:
(2,1) → Mark. Try Down:
(3,1) → Mark. Try Down: out of bounds
Try Right:
(3,2) → Mark. Try Down: out of bounds
Try Right:
(3,3) = DESTINATION! SOLUTION FOUND ✓

Solution Path: (0,0) → (1,0) → (1,1) → (2,1) → (3,1) → (3,2) → (3,3)

Time Complexity: O(2^(N²)) worst case | Space: O(N²) for solution matrix
Task 8 — Question 5: Linear Programming — Simplex Method
Full Question:
Solve the following LP problem by the simplex method:
Maximize Z = 6x₁ + 8x₂ Subject to:
5x₁ + 10x₂ ≤ 60
4x₁ + 4x₂ ≤ 40 x₁,
x₂ ≥ 0

Answer:
Step 1: Convert to Standard Form (add slack variables s₁, s₂):
Maximize Z = 6x₁ + 8x₂ + 0s₁ + 0s₂
5x₁ + 10x₂ + s₁ = 60 4x₁ +
4x₂ + s₂ = 40

Step 2: Initial Simplex Tableau:

BV x₁ x₂ s₁ s₂ RHS Ratio

s₁ 5 10 1 0 60 60/10=
6
←min

s₂ 4 4 0 1 40 40/4=1
0

Z -6 -8 0 0 0

Step 3: Identify Pivot Column and Row:

Most negative in Z-row: -8 (x₂ column) → x₂ enters
Minimum ratio: Row 1 (ratio=6) → s₁ leaves Pivot
element = 10 (row 1, col x₂)

Step 4: Row Operations (make pivot element = 1):

R1 ← R1 ÷ 10: s₁ row: [0.5, 1, 0.1, 0, 6] R2 ← R2 - 4×R1: s₂ row: [4-4(0.5), 4-
4(1), 0-4(0.1), 1, 40-4(6)] = [2, 0, -0.4, 1, 16] Z ← Z + 8×R1:
Z row: [-6+8(0.5), 0, 0+8(0.1), 0, 0+8(6)] = [-2, 0, 0.8, 0, 48]

Tableau after Iteration 1:

BV x₁ x₂ s₁ s₂ RHS Ratio

x₂ 0.5 1 0.1 0 6 6/0.5=

12

s₂ 2 0 -0.4 1 16 16/2=8
←min
 Z -2 0 0.8 0 48

Step 5: Second Pivot — x₁ enters, s₂ leaves (pivot element = 2):

R2 ← R2 ÷ 2:
s₂ row: [1, 0, -0.2, 0.5, 8]
R1 ← R1 - 0.5×R2: x₂ row: [0, 1, 0.2,
-0.25, 2] Z ← Z + 2×R2:
Z row: [0, 0, 0.4, 1, 64]
Final Tableau:
BV x₁ x₂ s₁ s₂ RHS

x₂ 0 1 0.2 -0.25 2

x₁ 1 0 -0.2 0.5 8

Z 0 0 0.4 1 64

No negative values in Z-row → Optimal solution reached!

Optimal Solution:
• x₁ = 8
• x₂ = 2
• Maximum Z = 6(8) + 8(2) = 48 + 16 = 64
TASK 9

Task 9 — Question 1: Tower of Hanoi — Time Complexity Analysis

Full Question:
Consider the educational workhorse of recursive algorithms: Tower of Hanoi puzzle. We have n disks of different
sizes that can slide onto any of three pegs. Consider A (source), B (auxiliary), and C
(Destination). Initially, all the disks are on the first peg in order of size, the largest on the bottom and the smallest
on top. The goal is to move all the disks to the third peg, using the second one as an auxiliary.

Answer:
Rules of Tower of Hanoi:
15. Only one disk can be moved at a time.
16. Each move consists of taking the topmost disk from one peg and placing it on another peg.
17. No disk may be placed on top of a smaller disk.

Recursive Algorithm:
HANOI(n, source=A, destination=C, auxiliary=B):
IF n == 1:
MOVE disk 1 from A to C
RETURN
HANOI(n-1, A, B, C) // Move n-1 disks from A to B
MOVE disk n from A to C // Move largest disk
HANOI(n-1, B, C, A) // Move n-1 disks from B to C

Recurrence Relation: T(n) =

2T(n-1) + 1, T(1) = 1

Solving the Recurrence:

T(n) = 2T(n-1) + 1
= 2[2T(n-2) + 1] + 1 = 4T(n-2) + 2 + 1
= 4[2T(n-3) + 1] + 3 = 8T(n-3) + 4 + 2 + 1
= 2^k × T(n-k) + (2^k - 1)
When k = n-1:
= 2^(n-1) × T(1) + (2^(n-1) - 1)
= 2^(n-1) + 2^(n-1) - 1
= 2^n - 1

Minimum Moves Required = 2ⁿ - 1

n (disks) Moves (2ⁿ - 1) Time to solve (at 1 move/sec)

 1 1 1 second

n (disks) Moves (2ⁿ - 1) Time to solve (at 1 move/sec)

2 3 3 seconds

3 7 7 seconds

10 1023 ~17 minutes

20 1,048,575 ~12 days

64 ≈ 1.8 × 10¹⁹ ~585 billion years

Time Complexity: O(2ⁿ) — Exponential

This is optimal — any algorithm must take at least 2ⁿ - 1 steps for n disks.

Task 9 — Question 2: Quicksort Partitioning with Pivot 40

Full Question:
Demonstrate the partitioning step in Quicksort for the list [10, 80, 30, 90, 40, 50, 70] with pivot 40 and analyze
the time efficiency.

Answer:
Array: [10, 80, 30, 90, 40, 50, 70] Pivot = 40 (at index 4)

Lomuto Partition Scheme:

Move pivot to end: [10, 80, 30, 90, 70, 50, 40] i = -1
(index of smaller element), j scans from left

j=0: arr[0]=10 ≤ 40 → i=0, swap arr[0] and arr[0] → [10, 80, 30, 90, 70, 50, 40]
j=1: arr[1]=80 > 40 → no swap
j=2: arr[2]=30 ≤ 40 → i=1, swap arr[1] and arr[2] → [10, 30, 80, 90, 70, 50, 40]
j=3: arr[3]=90 > 40 → no swap j=4: arr[4]=70 > 40 → no swap j=5: arr[5]=50
> 40 → no swap Place pivot at i+1=2: swap arr[2] and arr[6] → [10, 30, 40,
90, 70, 50, 80]

After Partitioning: [10, 30, 40, 90, 70, 50, 80]

Pivot 40 is now at index 2 — its FINAL CORRECT POSITION

Result:
• Left subarray (all < 40): [10, 30]
• Pivot: [40]
• Right subarray (all > 40): [90, 70, 50, 80]
Time Efficiency Analysis:
• Partitioning step: O(n) — scans entire array once
• Quicksort average case: O(n log n)
• Quicksort worst case: O(n²) — occurs when pivot is always min/max
• Quicksort best case: O(n log n) — when pivot always splits evenly

Task 9 — Question 3: Dijkstra's Shortest Path Algorithm

Full Question:
From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra's
algorithm. Given an undirected graph and a starting node, determine the lengths of the shortest paths from the
starting node to all other nodes in the graph. If a node is unreachable, its distance is -1. Nodes are numbered
consecutively from 1 to n, and edges have varying distances or lengths.
Graph (from figure): Vertices A, B, C, D, E, F, G with various weighted edges.

Answer:
Dijkstra's Algorithm:
18. Initialize dist[source] = 0, all others = ∞
19. Create a priority queue with all vertices.
20. Extract vertex u with minimum distance.
21. For each neighbor v of u: if dist[u] + w(u,v) < dist[v], update dist[v].
22. Repeat until all vertices processed.

Example with representative weighted graph (from figure: A-C=3, C-B=2, A-D=4, D-E=2, C-E=5, B-F=2, E-G=5, G-
F=5):

Source = A, all distances initialized to ∞:

Step Visited dist[A] dist[B] dist[C] dist[D] dist[E] dist[F] dist[G]

Init - 0 ∞ ∞ ∞ ∞ ∞ ∞

1 A 0 ∞ 3 4 ∞ ∞ ∞

2 C 0 5 3 4 8 ∞ ∞

3 D 0 5 3 4 6 ∞ ∞

4 B 0 5 3 4 6 7 ∞

5 E 0 5 3 4 6 7 11

6 F 0 5 3 4 6 7 11

7 G 0 5 3 4 6 7 11

Shortest Distances from A:

 • A → A: 0
• A → B: 5 (via A→C→B)
• A → C: 3 (via A→C)
• A → D: 4 (via A→D)
• A → E: 6 (via A→D→E)
• A → F: 7 (via A→C→B→F)
• A → G: 11 (via A→D→E→G)

Time Complexity:
• With simple array: O(V²)
• With binary heap: O((V+E) log V)
• With Fibonacci heap: O(E + V log V)

Task 9 — Question 4: 4-Queens Problem using Backtracking

Full Question:
Implement a backtracking algorithm to solve the 4-Queens problem. Display all possible solutions and explain
the steps where the algorithm backtracks.

Answer:
Problem: Place 4 queens on a 4×4 chessboard such that no two queens attack each other (no two in same row,
column, or diagonal).

Algorithm:
SOLVE_N_QUEENS(row, n, board):
IF row == n: PRINT solution; RETURN
FOR col = 0 to n-1:
IF isSafe(board, row, col):
board[row] = col // Place queen
SOLVE_N_QUEENS(row+1, n, board)
board[row] = -1 // BACKTRACK

Execution Trace (Row by Row):

Row 0: Try col 0 → Place Q at (0,0)
Row 1: Try col 0 → same column. SKIP
Row 1: Try col 1 → diagonal with (0,0). SKIP
Row 1: Try col 2 → SAFE. Place Q at (1,2)
Row 2: Try col 0 → diagonal. SKIP
Row 2: Try col 1 → diagonal. SKIP
Row 2: Try col 2 → same col. SKIP
Row 2: Try col 3 → diagonal. SKIP
→ No safe column. BACKTRACK to row 1
Row 1: Try col 3 → SAFE. Place Q at (1,3)
Row 2: Try col 0 → diagonal. SKIP
 Row 2: Try col 1 → SAFE. Place Q at (2,1)
Row 3: Try col 0 → diagonal. SKIP
Row 3: Try col 1 → same col. SKIP
Row 3: Try col 2 → diagonal. SKIP
Row 3: Try col 3 → same col as (1,3). SKIP
→ BACKTRACK to row 2
Row 2: Try col 2,3 → conflicts. BACKTRACK to row 1. BACKTRACK to row 0
Row 0: Try col 1 → Place Q at (0,1)
Row 1: Try col 3 → SAFE. Place Q at (1,3)
Row 2: Try col 0 → SAFE. Place Q at (2,0)
Row 3: Try col 2 → SAFE. Place Q at (3,2)
*** SOLUTION 1 FOUND: (0,1),(1,3),(2,0),(3,2) ***

All Solutions to 4-Queens (2 solutions exist):

Solution 1: Q at columns [1, 3, 0, 2]

. Q . .
. . . Q
Q . . .
. . Q .

Solution 2: Q at columns [2, 0, 3, 1]

. . Q .
Q . . .
. . . Q
. Q . .

Total Solutions for 4-Queens: 2

Time Complexity: O(n!) worst case | Practical complexity much less due to pruning

Task 9 — Question 5: TSP is NP-Hard — Proof

Full Question:
Construct a proof to demonstrate that the Travelling Salesman Problem is NP-Hard.

Answer:
Definition Recap:
• NP: A problem is in NP if a given solution can be VERIFIED in polynomial time.
• NP-Hard: A problem H is NP-Hard if every problem in NP can be reduced to H in polynomial time.
• NP-Complete: A problem is NP-Complete if it is both NP and NP-Hard.

Step 1: Show TSP is in NP

Given a proposed tour (a specific ordering of cities) and a bound B:
We can verify in O(n) time whether the tour visits all cities exactly once and has total distance ≤ B. Therefore,
TSP (decision version) ∈ ✓ NP.

Step 2: Show TSP is NP-Hard (via reduction from Hamiltonian Cycle)

We reduce the well-known NP-Complete problem HAMILTONIAN CYCLE to TSP in polynomial time.
Reduction Construction:
Given any graph G = (V, E) for which we want to determine if a Hamiltonian Cycle exists:
23. Create a complete graph G' with the same vertex set V.
24. For each edge (u,v) ∈ E in G: set weight w(u,v) = 0 in G'
25. For each edge (u,v) ∉ E in G: set weight w(u,v) = 1 in G'
26. Ask: Does G' have a TSP tour of cost ≤ 0?

Proof of Correctness:
(→) If G has a Hamiltonian Cycle: The cycle uses only edges in E, all with weight 0. So the TSP tour cost = 0 ≤ 0. ✓
(←) If G' has a TSP tour of cost ≤ 0: Since weights are 0 or 1, the tour must use only edges with weight
0, which are exactly the edges in E. So the tour is a Hamiltonian Cycle in G. ✓

Step 3: Reduction is Polynomial

The construction of G' from G takes O(V²) time — clearly polynomial.

Conclusion:
Since Hamiltonian Cycle (NP-Complete) ≤_p TSP (reduces to TSP in polynomial time), and TSP ∈ NP, we conclude:
HAMILTONIAN CYCLE ≤_p TSP
Since Hamiltonian Cycle is NP-Hard, and it reduces to TSP, TSP is also NP-Hard. Therefore, TSP is NP-
Complete (NP ∩ NP-Hard). ■

Note: The optimization version of TSP (finding the actual shortest tour) is NP-Hard but not in NP (since solutions
cannot be easily verified). Only the decision version (is there a tour of cost ≤ B?) is NPComplete.