DESIGN

ALGORITHMS
Efficient algorithms are essential because they
allow large problems to be solved within practical
time and resource limits.
Even a small improvement in time complexity—
such as reducing O(n²) to O(n log n)—can
transform an algorithm’s real-world performance.
Understanding algorithm design strategies helps
programmers choose the right approach for
solving diverse computational problems
effectively.
[Sidebar Title]
Design and Analysis of Algorithms
(DAA) is a core subject that focuses
on creating efficient solutions to
computational problems.
It teaches how to construct
algorithms, analyze their
correctness, and evaluate their
performance in terms of time and
space complexity.
The subject covers major
algorithmic strategies such as Divide
& Conquer, Greedy Method,
Dynamic Programming,
Backtracking, Branch & Bound, and
Graph Algorithms.
DAA forms the foundation for
writing optimized programs and
understanding the theoretical limits
of computation
 Analyzing Recursive Algorithms and
Solving Recurrences

Analysis of Recursive Algorithms

Recursion is one of the central techniques in algorithm design. A recursive algorithm

works by solving a problem in terms of one or more smaller subproblems that are
structurally

identical to the original.

Recursion is a powerful idea because it allows us to break down large, complex

problems

into simpler components that are easier to reason about, solve, and analyze. This

section explores the fundamental ideas behind recursive algorithms, why recursion
matters,

what constitutes a valid recursive solution, and how we analyze the running time of

such algorithms using recurrence relations.

1.1 What is Recursion?

Recursion is a programming technique where a function calls itself to solve smaller

versions

of the same problem. This technique leverages the natural structure of many problems,

where the solution to the problem depends on solutions to smaller subproblems.

Essential Components of a Recursive Function Every recursive function must

contain two essential elements:

• Recursive Calls — These are calls to the same function but with a smaller input

size. They allow the algorithm to move gradually toward the base case.

• Base Case — This is a stopping condition that prevents the algorithm from
recursing

indefinitely. A base case must be simple, direct, and must not contain any
recursive call.

Without a valid base case, a recursive algorithm will not terminate and would eventually

cause a stack overflow.

Allocation of memory blocks sizes
0.1 Backtracking approach
Let assume Memory block sizes = {4, 7, 10, 11, 13, 17}
Target Sum = 24

Backtracking Algorithm (Subset-Sum Style)

1. Start from the first element and maintain a running sum.

2. At each step, you have two choices for a block:

o Include it in the current subset

o Exclude it and move to the next block

3. If the running sum becomes 24, record the subset.

4. If the running sum exceeds 24, backtrack (stop exploring that path).

5. Continue until all combinations are explored.

Tracing valid subsets that form sum = 24

After applying backtracking, the subsets that exactly sum to 24 are:

 {4, 7, 13} = 24

 {7, 17} = 24

 {11, 13} = 24

So, the backtracking approach will output:

All solutions = {4,7,13}, {7,17}, {11,13}.

0.2 Unnecessary computation – Back tracking

Naïve exhaustive search generates all possible subsets (2ⁿ subsets), even those whose
partial sums are already greater than 24.
→ This wastes time.
 1. Backtracking prunes (cuts off) useless branches early.
Whenever the running sum becomes greater than 24, it immediately stops
exploring that path.

2. This avoids checking hundreds of unwanted combinations, reducing time

complexity drastically in practice.

Real-life analogy :

Imagine packing a bag with exactly 24 kg weight:

If you already placed items weighing 25 kg, you instantly stop and remove items; you
don’t continue adding more.
Backtracking works in the same smart way.

Concept of Knapsack Dynamic programme for

Knapsack
0.1 DP Table (rows = items, columns = capacity 0–8)

0.2 Items to include (Backtracking from DP table)

 Start from DP[4][8] = 46

 46 ≠ DP[3][8] (30) → Choose D

Capacity = 8 – 5 = 3

 DP[3][3] = DP[2][3] = DP[1][3] = 8 → Choose A

Selected Items = {D, A}

0.3 Maximum Profit

Maximum profit = 46

Reasoning for Big O Notation:

0.1 Recurrence using Backward Substitution :

M(n) = 2M(n–1) + 1 , M(1) = 1

Step 1: Expand backward

M(n)
= 2M(n–1) + 1
= 2[2M(n–2) + 1] + 1
= 4M(n–2) + 2 + 1
= 4[2M(n–3) + 1] + 3
= 8M(n–3) + 4 + 3

After k steps:
M(n) = 2ᵏ M(n–k) + (2ᵏ – 1)

Set n – k = 1, so k = n – 1

Substitute:
M(n) = 2ⁿ⁻¹·M(1) + (2ⁿ⁻¹ – 1)
= 2ⁿ⁻¹·1 + 2ⁿ⁻¹ – 1
= 2ⁿ – 1

Final Answer : M(n) = 2ⁿ – 1

0.2 Time Complexity

for (i = 1; i <= n; i = i + 1)
for (j = i; j <= i; j = j + 1)

print("Hi");

Reasoning:
  Outer loop runs n times.

 Inner loop runs from j = i to j = i, so it executes exactly 1 time for every value of i.

 Therefore, total prints = n × 1 = n.

Time Complexity:

O(n)

Classify P or NP-completion:

0.1 :

0.1.1 : Check whether a number is prime

This problem belongs to class P.

Because primality can be checked in polynomial time using algorithms like trial division
up to √n or the AKS primality test (runs in poly-time).
Hence, it is not NP-complete.

0.1.2 Subset Sum = k

This problem is NP-complete.

Given a set S and target k, checking if any subset sums exactly to k is the classical
Subset Sum problem, which is proven to be NP-complete.
The solution can be verified quickly, but finding it requires exponential time in the worst
case.
0.2 Relationship between NP, NP-complete, NP-hard

 NP: Problems whose solutions can be verified in polynomial time.

 NP-Complete: Hardest problems in NP; every NP problem can be reduced to

them in polynomial time.

 NP-Hard: At least as hard as NP-complete problems but may not be in NP

(verification not guaranteed poly-time).
Relationship:
NP-complete ⊆ NP, and NP-hard includes NP-complete plus harder problems outside
NP.

Directed acyclic graph :

0.1 Topological Sort (Valid Order)

To do a topological sort, we start with nodes that have no incoming edges.

Nodes with no incoming edges:
F, E

Pick any of them first (both are valid).

Let’s go with the natural left-to-right flow:

1. F, E

2. After removing F: C and A get closer

After removing E: B and A get closer
Next node with no incoming edges: C

3. Remove C → D is now dependent only on B

Next choose B (it has no remaining incoming edge)

4. Remove B → D now becomes free

5. Remove E earlier also freed A once both F & E removed → A

6. Finally: D

One valid topological order:

F, E, C, B, A, D

(Note: Other orders like F, E, B, C, A, D also work, as long as dependencies stay

respected.)

0.2 Tasks affected in the schedule

Let’s see who depends on B:

 There is an edge B → D
 And D appears to be one of the final tasks in the graph.
So if B is delayed, then:

 Task D will definitely be delayed

because it cannot start until B is completed.
What about A, C, F, E?

 A doesn’t depend on B → unaffected

 C doesn’t depend on B → unaffected

 F is an initial node → unaffected

 E is an initial node too → unaffected

Only the tasks that lie after B in the dependency chain get affected.

Conquer BS on sorted array :

Sequence of Recursive
We use:
mid = floor((low + high) / 2)

Call 1: Binary_search(A, 0, 8)

 low = 0, high = 8
 mid = floor((0 + 8) / 2) = 4

 A[mid] = A[4] = 12

12 > 8 → search left half

Call 2: Binary_search(A, 0, 3)

 low = 0, high = 3

 mid = floor((0 + 3) / 2) = 1

 A[mid] = A[1] = 6

6 < 8 → search right half

Call 3: Binary_search(A, 2, 3)
  low = 2, high = 3

 mid = floor((2 + 3) / 2) = 2

 A[mid] = A[2] = 8
FOUND at index 2

So recursion returns 2 all the way up.

0.2 Recurrence for Worst-Case Running Time

Binary search divides the array into half each time.

So the recurrence is: T(n) = T(n/2) + O(1)

(We just compute mid and compare → constant work)

Solve it:

Every step halves the problem:

T(n) = T(n/2) + c

= T(n/4) + 2c

= T(n/8) + 3c

...

= T(n / 2^k) + kc

Stop when:
n / 2^k = 1 → k = log₂(n)

So:

T(n) = O(log n)

Tight asymptotic bound: Θ(log n)

0.3 Strassen vs Standard Matrix Multiplication

Standard Matrix Multiplication

 Uses 8 multiplications for each divide step

 Time complexity: O(n³)

Strassen’s Algorithm
  Breaks matrices into submatrices

 BUT instead of 8 multiplications, it cleverly uses 7 multiplications

 A bit more addition overhead, but multiplication dominates cost

Key Innovation:

Strassen reduces multiplications from 8 → 7 using algebraic manipulation.

Result:

This gives time complexity:

O(n^log₂7) ≈ O(n^2.807)

Which is faster than O(n³).

Dijkstra’s Algorithm :
Let the distance array be in order: [A, B, C, D]
Initialize:

 dist(A) = 0

 dist(B) = ∞

 dist(C) = ∞

 dist(D) = ∞
Visited set S = { }
Iteration 1

Pick unvisited vertex with smallest distance → A (0)

Add to S: S = {A}

Relax edges from A:

 A–B: dist(B) = min(∞, 0 + 3) = 3

 A–C: dist(C) = min(∞, 0 + 4) = 4

 A–D: dist(D) = min(∞, 0 + 4) = 4

Distance array after Iteration 1:

[0, 3, 4, 4]
Iteration 2

Smallest unvisited distance → B (3)

Add to S: S = {A, B}
Relax edges from B:

 B–A: 0 already better, no change

 B–C: candidate 3 + 5 = 8 > current 4, no change

Distance array after Iteration 2:
[0, 3, 4, 4]
Iteration 3

Next smallest unvisited → C (4)

Add to S: S = {A, B, C}

Relax edges from C:

 C–A: 4 + 4 = 8 > 0, no change

 C–B: 4 + 5 = 9 > 3, no change

 C–D: 4 + 1 = 5 > 4, no change

Distance array after Iteration 3:

[0, 3, 4, 4]
Iteration 4

Last vertex → D (4)

Add to S: S = {A, B, C, D}

Relax edges from D (A, C) – neither improves any distance.

Final distance array:

[0, 3, 4, 4]
So shortest distances from A:

 to A = 0

 to B = 3

 to C = 4

 to D = 4
0.2 Shortest Path
Possible simple paths:

1. A → C directly: cost = 4

2. A → B → C: cost = 3 + 5 = 8

3. A → D → C: cost = 4 + 1 = 5

Minimum is the direct edge:

Shortest path: A → C
Total distance = 4

Greedy Approach :
0.1 Let’s sort projects by profit:
1. A (100, deadline 4)

2. F (30, deadline 2)

3. C (27, deadline 2)

4. D (25, deadline 1)

5. B (19, deadline 1)

6. E (15, deadline 3)

Max deadline = 4 → So we have slots:

[1, 2, 3, 4]

0.2 Step-by-Step Scheduling

We'll fill slots one by one.

0.2.1 Project A (profit 100, deadline 4)

Latest free slot ≤ 4 = slot 4

→ Assign A → slot 4

Slots: _ _ _ A
0.2.2 Project F (profit 30, deadline 2)

Latest free slot ≤ 2 = slot 2

→ Assign F → slot 2
Slots: _ F _ A

0.2.3 Project C (profit 27, deadline 2)

Latest free slot ≤ 2 = slot 2

But slot 2 is already taken.
Check slot 1 → free → assign C → slot 1

Slots: C F _ A

0.2.4 Project D (profit 25, deadline 1)

Latest slot ≤ 1 = slot 1

But slot 1 is taken by C
→ Can't schedule D

0.2.5 Project B (profit 19, deadline 1)

Same issue as D
→ Can't schedule B

0..2. 6 Project E (profit 15, deadline 3)

Latest free slot ≤ 3 = slot 3

→ Assign E → slot 3

Slots: C F E A

Final Selected Projects with Slots

Slot Project

1 C

2 F

3 E
Slot Project

4 A

0.3 Maximum Profit

Add the profits of selected projects:

 C → 27

 F → 30

 E → 15

 A → 100

Total = 27 + 30 + 15 + 100 = 172

-
-
-
-
-
-