Design and Analysis of Algorithms

Complete Unit-wise Detailed Notes with Diagrams

UNIT 1: Introduction to Algorithms, Asymptotic Analysis, and

Sorting Techniques
1.1 Definition and Basic Properties of Algorithms
An algorithm is a finite, well-defined sequence of steps that takes some input and produces a desired output in finite
time. It is a language-independent description of a solution to a problem.
Basic properties every algorithm must satisfy:
● Input: Zero or more quantities are externally supplied.
● Output: At least one quantity is produced.
● Definiteness: Each instruction must be clear and unambiguous.
● Finiteness: The algorithm must terminate after a finite number of steps.
● Effectiveness: Every instruction must be basic enough to be carried out, in principle, by a person using
paper and pencil.

1.2 Recurrence Relations

A recurrence relation expresses the running time of a recursive algorithm as a function of the running time on
smaller inputs, e.g., T(n) = 2T(n/2) + n for merge sort. Solving a recurrence gives a closed-form (asymptotic)
expression for the algorithm's complexity.
Characteristic Equation Method: Used mainly for linear homogeneous recurrences such as T(n) = a1*T(n-1) +
a2*T(n-2) + ... The recurrence is converted into a polynomial equation (characteristic equation) in a variable x by
substituting T(n-k) = x^(n-k). The roots of this polynomial determine the general solution: distinct real roots give a
solution of the form c1*r1^n + c2*r2^n + ..., while repeated roots contribute polynomial multiplying factors of n.
Master Theorem: Gives a direct solution for divide-and-conquer recurrences of the form T(n) = a*T(n/b) + f(n),
where a >= 1, b > 1. Compare f(n) with n^(log_b a):
● Case 1: If f(n) = O(n^(log_b a - e)) for some e>0, then T(n) = Θ(n^(log_b a)).
● Case 2: If f(n) = Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) * log n).
● Case 3: If f(n) = Ω(n^(log_b a + e)) and the regularity condition holds, then T(n) = Θ(f(n)).
Example: T(n) = 2T(n/2) + n → a=2, b=2, log_b a = 1, f(n)=n=Θ(n^1) → Case 2 → T(n)=Θ(n log n), which is the
complexity of merge sort.

1.3 Asymptotic Notations

Asymptotic notation describes the growth rate of an algorithm's running time as input size n approaches infinity,
independent of machine-specific constants.
● Big-O (O): Upper bound. f(n)=O(g(n)) if there exist constants c>0, n0 such that f(n) <= c*g(n) for all n >=
n0. Represents worst case.
● Big-Omega (Ω): Lower bound. f(n)=Ω(g(n)) if f(n) >= c*g(n) for all n >= n0. Represents best case.
● Big-Theta (Θ): Tight bound. f(n)=Θ(g(n)) if f(n) is both O(g(n)) and Ω(g(n)); the average/exact growth
rate.
 Fig 1.1: Upper (O), Lower (Ω) and average behaviour of f(n)

1.4 Insertion Sort, Selection Sort and Bubble Sort — Case Analysis
Insertion Sort: Builds the sorted array one element at a time by inserting each new element into its correct position
among previously sorted elements. Best case (already sorted): O(n) — only one comparison per element. Worst case
(reverse sorted): O(n²) — each new element must move to the front. Average case is also O(n²).
Selection Sort: Repeatedly selects the minimum element from the unsorted part and places it at the beginning. It
always performs O(n²) comparisons regardless of input arrangement, so best, worst, and average cases are all O(n²);
however swaps are only O(n).
Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order. Best case with an early-exit flag
(already sorted): O(n). Worst case (reverse sorted) and average case: O(n²).

1.5 Amortized Analysis

Amortized analysis finds the average time per operation over a worst-case sequence of operations, even though
individual operations may occasionally be expensive. It guarantees that the average cost per operation is small, even
if a single operation is costly, by 'spreading' the expensive cost over many cheap operations.
● Aggregate Method: Total cost of n operations is computed and divided by n.
● Accounting (Banker's) Method: Assigns an amortized charge to each operation; overcharge on cheap
operations is saved as credit to pay for expensive ones.
● Potential Method: Defines a potential function on the data structure; amortized cost = actual cost + change
in potential.
Application: Dynamic array (vector) doubling — even though occasional resizing costs O(n), the amortized cost of
an insertion is O(1). Other applications include incrementing a binary counter and the union-find (disjoint set) data
structure with path compression.

1.6 Bitonic Sorting Network

A bitonic sequence first increases then decreases (or vice-versa). A Bitonic sorting network is a parallel sorting
network built from comparator stages that first converts an arbitrary sequence into a bitonic sequence, and then
repeatedly applies a 'bitonic merge' (compare-and-swap at distance n/2, n/4, ... ) to produce a fully sorted sequence.
It sorts n elements using O(n log² n) comparators arranged in O(log² n) parallel stages, making it well suited to
hardware and parallel/GPU implementations.
UNIT 2: Divide and Conquer Strategies and Greedy Approach
2.1 Binary Search
Binary search finds a target value in a sorted array by repeatedly halving the search interval: compare the target with
the middle element, and discard the half in which the target cannot lie. Time complexity is O(log n) since the search
space is divided by 2 at every step; this is a direct application of divide-and-conquer with T(n) = T(n/2) + O(1).

2.2 Merge Sort

Merge sort divides the array into two halves, recursively sorts each half, and then merges the two sorted halves into
one sorted array. The merge step takes O(n) and there are log n levels of recursion, giving overall time complexity
Θ(n log n) in all cases (worst, average, best). It is stable but needs O(n) extra space.

Fig 2.1: Recursion tree of Merge Sort — divide, then merge bottom-up

2.3 Quick Sort

Quick sort selects a pivot element and partitions the array so that elements smaller than the pivot go to its left and
larger elements to its right, then recursively sorts both partitions. Average case is O(n log n); worst case (already
sorted array with a poor pivot choice) is O(n²). It sorts in-place, needing only O(log n) auxiliary stack space on
average.

Fig 2.2: One partitioning step of Quick Sort around a chosen pivot
2.4 Heap Sort
Heap sort first builds a max-heap (or min-heap) from the input array in O(n) time, then repeatedly extracts the
maximum (root) and restores the heap property (heapify) in O(log n), giving overall O(n log n) time in all cases. It
sorts in-place with O(1) extra space but is not stable.

Fig 2.3: Binary heap represented as a tree (also stored as an array)

2.5 Strassen's Matrix Multiplication

The conventional way to multiply two n×n matrices takes O(n³) time. Strassen's algorithm divides each matrix into
four n/2 × n/2 submatrices and computes the product using only 7 multiplications (instead of 8) of these
submatrices, combined with several additions/subtractions. This gives the recurrence T(n)=7T(n/2)+O(n²), which
solves to T(n)=O(n^log2(7)) ≈ O(n^2.81), asymptotically faster than the naive method for large n.

2.6 Min-Max Algorithm

The straightforward method to find both minimum and maximum of n elements makes about 2n-2 comparisons. The
divide-and-conquer min-max algorithm splits the array into two halves, recursively finds min and max of each half,
and then compares the two mins and two maxes; this reduces the total number of comparisons to about (3n/2)-2,
which is optimal.

2.7 Greedy Approach — General Idea

A greedy algorithm builds a solution step by step, always choosing the option that looks best (locally optimal) at the
current moment, without reconsidering previous choices, hoping this leads to a globally optimal solution. Greedy
strategies work only when the problem exhibits the greedy-choice property and optimal substructure.

2.8 Job Sequencing with Deadlines

Given n jobs, each with a deadline and profit, and assuming each job takes one unit of time and only one job can run
at a time, the goal is to schedule jobs to maximize total profit while meeting deadlines. The greedy strategy sorts
jobs in decreasing order of profit and assigns each job to the latest available free slot before its deadline; if no such
slot exists, the job is rejected.

2.9 Knapsack Problem (Fractional)

In the fractional knapsack problem, items can be broken into fractions. The greedy strategy computes the value-to-
weight ratio for every item, sorts items in decreasing order of this ratio, and fills the knapsack by picking items
greedily, taking a fraction of an item only if the knapsack cannot hold it fully. This greedy approach gives the
optimal solution in O(n log n) time (dominated by sorting).
2.10 Optimal Merge Pattern
Given several sorted files of different lengths that must be merged pairwise into one file, the goal is to minimize the
total number of record comparisons/moves. The greedy strategy always merges the two smallest files first, using a
min-heap to repeatedly extract and merge the two currently smallest files; this is exactly analogous to building a
Huffman tree and gives the minimum total merge cost.

2.11 Huffman Coding

Huffman coding is a greedy algorithm for lossless data compression that assigns variable-length binary codes to
characters based on their frequencies — more frequent characters get shorter codes. It repeatedly picks the two
nodes (characters/subtrees) with the smallest frequencies, merges them into a new node whose frequency is their
sum, and repeats until one tree remains. The path from root to a leaf gives that character's code, and no code is a
prefix of another (prefix-free code).

Fig 2.4: Huffman tree — edge labels (0/1) give each symbol's code
UNIT 3: Dynamic Programming and its Strategies
3.1 Basic Strategy of Dynamic Programming (DP)
Dynamic programming solves problems by breaking them into overlapping subproblems, solving each subproblem
once, and storing its result (memoization / tabulation) so it is never recomputed. DP applies when a problem has
optimal substructure (an optimal solution is built from optimal solutions of subproblems) and overlapping
subproblems (unlike divide-and-conquer, the same subproblems recur many times). DP can be implemented top-
down (recursion + memoization) or bottom-up (iterative tabulation).

3.2 Multistage Graph

A multistage graph is a directed graph whose vertices are partitioned into stages, with edges only going from one
stage to the next. The goal is to find the minimum-cost path from the source (stage 1) to the destination (last stage).
● Forward approach: cost is computed starting from the destination backward to the source, i.e., cost(i, stage)
is built using costs of the next stage.
● Backward approach: cost is computed starting from the source forward, i.e., the minimum cost to reach
each vertex from the source is built stage by stage.

Fig 3.1: Multistage graph with stage-wise minimum cost path

3.3 Longest Common Subsequence (LCS)

Given two sequences, LCS finds the longest subsequence (not necessarily contiguous) present in both. Let dp[i][j]
be the LCS length of the first i characters of X and first j characters of Y: if X[i]=Y[j], dp[i][j]=dp[i-1][j-1]+1;
otherwise dp[i][j]=max(dp[i-1][j], dp[i][j-1]). Time and space complexity are O(m*n).
 Fig 3.2: DP table for computing LCS of two strings

3.4 Matrix Chain Multiplication

Given a chain of matrices, this problem finds the optimal parenthesization (order of multiplication) that minimizes
the total number of scalar multiplications; the matrices themselves are not multiplied, only the cheapest order of
multiplying them is decided. If m[i][j] is the minimum cost of multiplying matrices i through j, then m[i][j] = min
over k (m[i][k] + m[k+1][j] + p(i-1)*p(k)*p(j)), computed for increasing chain lengths. Time complexity is O(n³).

Fig 3.3: Cost table m[i][j] for Matrix Chain Multiplication

3.5 Optimal Binary Search Tree (OBST)

Given keys with known search-probability frequencies, OBST builds a BST that minimizes the expected total search
cost (probability × depth) rather than just tree height. Using DP, cost[i][j] (the minimum cost of a BST containing
keys i..j) is computed by trying every key k in the range as root and taking the minimum: cost[i][j] = min over k
(cost[i][k-1] + cost[k+1][j] + sum of frequencies from i to j). Time complexity is O(n³) (can be optimized to O(n²)
using Knuth's technique).

3.6 0/1 Knapsack Problem

Unlike the fractional version, in 0/1 Knapsack each item must be taken entirely or not at all, so the greedy method
fails and DP is required. Let dp[i][w] be the maximum value achievable using the first i items with capacity w: dp[i]
[w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]) if wt[i] <= w, else dp[i][w] = dp[i-1][w]. Time and space
complexity are O(n*W), where W is the knapsack capacity.

3.7 Travelling Salesman Problem (TSP) using DP

TSP asks for the minimum-cost Hamiltonian cycle that visits every city exactly once and returns to the start. The DP
(Held–Karp) formulation uses a state (S, i) meaning 'the minimum cost to visit all cities in subset S, ending at city i,'
with transition cost(S,i) = min over j in S,j≠i of (cost(S-{i}, j) + dist(j,i)). This reduces the brute-force O(n!)
complexity to O(n² * 2ⁿ), still exponential but far better than factorial.

3.8 Single Source Shortest Path — Bellman-Ford Algorithm

Bellman-Ford finds shortest paths from a single source to all vertices, and unlike Dijkstra's algorithm, it correctly
handles negative edge weights and can detect negative-weight cycles. It relaxes every edge (u,v): if dist[u]
+weight(u,v) < dist[v], update dist[v]. This relaxation is repeated (V-1) times, and one final pass checks whether any
distance can still be improved — if so, a negative cycle exists. Time complexity is O(V*E).

3.9 All-Pairs Shortest Path — Floyd-Warshall Algorithm

Floyd-Warshall computes the shortest distance between every pair of vertices in a weighted graph (including
negative edges, but not negative cycles). It uses an intermediate-vertex DP: dist[i][j] = min(dist[i][j], dist[i][k] +
dist[k][j]), trying every vertex k as a possible intermediate point, for k = 1 to n. Time complexity is O(n³), and it
works with a simple n×n adjacency/distance matrix.
UNIT 4: Basic Traversal and Search Techniques and
Backtracking
4.1 Breadth First Search (BFS)
BFS explores a graph level by level starting from a source vertex: it visits all neighbours of the source first, then
their neighbours, and so on, using a queue (FIFO) to keep track of vertices to visit next. BFS is useful for finding the
shortest path (in terms of number of edges) in an unweighted graph. Time complexity is O(V+E).

4.2 Depth First Search (DFS)

DFS explores as far as possible along each branch before backtracking, using a stack (either explicit or via
recursion). It is useful for detecting cycles, topological sorting, and finding connected components. Time complexity
is also O(V+E).

Fig 4.1: Sample graph — BFS visits level by level, DFS goes deep first

4.3 Connected Components

A connected component is a maximal set of vertices such that there is a path between every pair of vertices within
the set. Both BFS and DFS can identify all connected components of an undirected graph: starting a fresh traversal
from every unvisited vertex and marking all vertices reached in that traversal as one component takes overall
O(V+E) time.

4.4 Backtracking — Basic Strategy

Backtracking systematically searches for a solution by building it incrementally, one piece at a time, and abandoning
('backtracking' from) a partial solution as soon as it determines that this partial solution cannot possibly lead to a
valid complete solution. This is modeled as exploring a state-space tree using depth-first search, pruning branches
that violate constraints — making it far more efficient than pure brute-force enumeration for many combinatorial
problems.

4.5 N-Queens Problem (4-Queens and 8-Queens)

The N-Queens problem places N queens on an N×N chessboard so that no two queens attack each other (no shared
row, column, or diagonal). Backtracking places queens column by column: for each column, it tries each row,
checks whether placing a queen there conflicts with previously placed queens, and if safe, recurses to the next
column; if no row works, it backtracks to the previous column and tries a different row. For 4-Queens there are 2
distinct solutions, and for 8-Queens there are 92 solutions (12 distinct up to symmetry).

Fig 4.2: Partial backtracking state-space tree for 4-Queens (X = pruned)

4.6 Graph Coloring

The m-coloring problem asks whether the vertices of a graph can be colored using at most m colors so that no two
adjacent vertices share the same color. Backtracking tries assigning colors 1..m to vertices one at a time, checking at
each step whether the current partial coloring is valid, and backtracks whenever a conflict is found. This is used in
applications like register allocation and scheduling, and is NP-complete in general.

Fig 4.3: A valid 3-coloring of a graph — no adjacent vertices share a color

4.7 Hamiltonian Cycles

A Hamiltonian cycle visits every vertex of a graph exactly once and returns to the starting vertex. Backtracking
builds the cycle vertex by vertex: at each step it tries adding an unvisited, adjacent vertex to the path, recurses, and
backtracks if the path gets stuck or if a chosen vertex creates a dead end; if all vertices are included and the last
vertex connects back to the start, a Hamiltonian cycle is found. This problem is NP-complete.
UNIT 5: NP-Hard and NP-Complete Problems
(Note: your syllabus sheet's unit-5 heading reads “Blockchain Applications and Challenges” but the topic list
underneath is entirely about computational complexity/NP-completeness — the notes below cover the listed topics:
NP-hard, NP-complete, Cook's theorem, decision vs optimization problems, and graph-based NP problems.)

5.1 Basic Concepts — P, NP, NP-Hard, NP-Complete

● P (Polynomial time): The class of decision problems solvable by a deterministic algorithm in polynomial
time.
● NP (Nondeterministic Polynomial time): The class of decision problems for which a given solution
('certificate') can be verified in polynomial time.
● NP-Hard: Problems at least as hard as every problem in NP — every NP problem can be reduced to it in
polynomial time. NP-Hard problems need not themselves be in NP (may not even be decision problems).
● NP-Complete (NPC): Problems that are both in NP and NP-Hard — these are the 'hardest' problems within
NP; if any NPC problem is solved in polynomial time, then P = NP.

Fig 5.1: Relationship between P, NP, NP-Complete and NP-Hard (assuming P ≠ NP)

5.2 Non-deterministic Algorithms

A non-deterministic algorithm is a conceptual algorithm that, at each choice point, is allowed to 'guess' the correct
option (as if it could try all options simultaneously) and only needs to verify that the guessed solution is correct.
Formally it consists of a guessing stage (choose(1,n)) followed by a verification stage that runs in polynomial time; a
problem is in NP if such a non-deterministic polynomial-time algorithm exists for it.

5.3 Cook's Theorem

Cook's theorem (Cook–Levin theorem) states that the Boolean Satisfiability Problem (SAT) is NP-complete — it
was the first problem proven NP-complete. It shows that any problem in NP can be reduced to SAT in polynomial
time, by encoding the computation of the non-deterministic verifier for that problem as a Boolean formula that is
satisfiable exactly when the verifier accepts. This result is the foundation for proving NP-completeness of other
problems via polynomial-time reductions from SAT (or from another already-proven NP-complete problem).
5.4 Decision Problems vs Optimization Problems
A decision problem has a yes/no answer (e.g., 'Is there a Hamiltonian cycle of length <= k?'), while an optimization
problem asks for the best solution value (e.g., 'Find the shortest Hamiltonian cycle'). Every optimization problem has
a corresponding decision version, and if the decision version is NP-complete, then the optimization version is at
least NP-hard, since solving the optimization problem would also solve the decision problem (by comparing the
optimal value to k).

5.5 Graph-Based Problems on NP Principle

Many classical graph problems are NP-complete, including: the Hamiltonian Cycle problem, the Travelling
Salesman decision problem, the Graph Coloring (chromatic number) decision problem, the Clique decision problem
(does a graph contain a clique of size >= k), and the Vertex Cover problem (is there a vertex cover of size <= k).
These are all shown NP-complete by polynomial-time reduction from a known NP-complete problem such as SAT
or 3-SAT, following the technique established by Cook's theorem.