Design and Analysis of

Algorithms - Exam Notes

Prepared for 5 Marks Questions

1. N-Queens Problem
Definition
The N-Queens problem is a classic backtracking problem where we need to place N queens on an N×N chessboard such
that no two queens attack each other[1][4].

Key Concepts
A queen can attack horizontally, vertically, and diagonally
Each queen must be in a different row, column, and diagonal
No two queens should threaten each other

Algorithm Approach
1. Start with the first row and try placing a queen in each column
2. Check if the placement is safe (no conflicts)
3. If safe, place the queen and move to the next row
4. If all queens are placed successfully, record the solution
5. If placement leads to conflict, backtrack and try the next column
6. Repeat until all possibilities are explored

Example: 4-Queens Problem

Board: 4×4 chessboard

Solution 1: Queens at positions: [2, 4, 1, 3]

Row 1: Queen at column 2

Row 2: Queen at column 4
Row 3: Queen at column 1
Row 4: Queen at column 3

Solution 2: Queens at positions: [3, 1, 4, 2]

 Row 1: Queen at column 3
Row 2: Queen at column 1
Row 3: Queen at column 4
Row 4: Queen at column 2

Time Complexity
Time: O(N!) - explores all possible configurations
Space: O(N) - recursion stack and tracking arrays

Code Structure

isSafe(board, row, col):

Check row, columns, and diagonals
Return true if safe, false otherwise

solveNQueens(board, row):
if row == N:
Add solution
return
for col in 0 to N-1:
if isSafe(board, row, col):
Place queen
solveNQueens(board, row+1)
Remove queen (backtrack)

2. NP-Complete Problem
Definition
NP-Complete problems are the hardest problems in the NP (Nondeterministic Polynomial time) class. A problem is NP-
Complete if it satisfies two conditions[2][5]:

1. It is in NP (solution can be verified in polynomial time)

2. It is NP-Hard (all NP problems can be reduced to it)

Key Characteristics
Decision Problem: Output is either "yes" or "no"
Verification: Solutions can be verified quickly (polynomial time)
Hardness: If any NP-Complete problem can be solved in polynomial time, all NP problems can be solved in
polynomial time
 Properties
1. No polynomial-time algorithm is known for NP-Complete problems
2. If one NP-Complete problem is solved in polynomial time, all can be solved
3. All NP-Complete problems are equally hard

Example: 3-SAT Problem

Problem: Given a Boolean formula with variables x₁, x₂, x₃, etc., can we assign TRUE/FALSE values to satisfy the
formula?

Instance: Formula: (x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ ¬x₃) ∧ (x₁ ∨ ¬x₂ ∨ x₃)

Solution Approach:

Try all possible assignments: 2ⁿ combinations

Check if any assignment satisfies all clauses
If yes, the formula is satisfiable

Assignment: x₁ = TRUE, x₂ = TRUE, x₃ = FALSE

Clause 1: TRUE ∨ TRUE ∨ FALSE = TRUE

Clause 2: FALSE ∨ TRUE ∨ TRUE = TRUE
Clause 3: TRUE ∨ FALSE ∨ FALSE = TRUE
Result: Satisfiable

Common NP-Complete Problems

Traveling Salesman Problem (TSP)
Hamiltonian Circuit
3-SAT
Knapsack Problem (decision version)
Graph Coloring
Clique Problem

3. Assignment Problem
Definition
The Assignment Problem involves assigning n tasks to n agents (or workers) such that each task is assigned to exactly
one agent, and the total cost is minimized[3][6].

Hungarian Method Algorithm

 The Hungarian Method is the most efficient algorithm for solving the assignment problem.

Steps
1. Create Cost Matrix: n×n matrix where element (i,j) represents cost of assigning task j to agent i
2. Row Reduction: Subtract minimum element of each row from all elements in that row
3. Column Reduction: Subtract minimum element of each column from all elements in that column
4. Cover Zeros: Cover all zeros using minimum number of horizontal and vertical lines
5. Optimality Check: If number of lines equals n, optimal assignment found; otherwise continue
6. Matrix Adjustment: Find smallest uncovered element, subtract from all uncovered elements, add to elements
covered by both lines
7. Repeat: Steps 4-6 until optimal solution found

Example
Cost Matrix:

Task1 Task2 Task3 Task4

Agent1 9 2 7 8
Agent2 6 4 3 7
Agent3 5 8 1 8
Agent4 7 6 9 4

After Row Reduction:

Task1 Task2 Task3 Task4

Agent1 7 0 5 6
Agent2 3 1 0 4
Agent3 4 7 0 7
Agent4 3 2 5 0

After Column Reduction:

Task1 Task2 Task3 Task4

Agent1 4 0 5 6
Agent2 0 1 0 4
Agent3 1 7 0 7
Agent4 0 2 5 0

Optimal Assignment:

Agent1 → Task2 (Cost = 2)

Agent2 → Task3 (Cost = 3)
 Agent3 → Task3 (Cost = 1)
Agent4 → Task4 (Cost = 4)
Total Minimum Cost = 10

Time Complexity
Time: O(n³)
Space: O(n²)

4. Backtracking Algorithm
Definition
Backtracking is a systematic trial-and-error algorithmic technique that builds solutions incrementally and abandons
(backtracks) a solution as soon as it determines that the solution cannot lead to a valid complete solution[21][24].

How It Works
1. Choose: Start by making a choice that could lead toward a solution
2. Explore: Recursively move forward with this choice
3. Check Validity: If the choice leads to an invalid state, undo it (backtrack)
4. Repeat: Continue until all possibilities are explored or valid solution found

General Algorithm

Backtrack(solution):
if solution is complete:
return solution

for each choice in available choices:

if choice is valid:
Make choice
Backtrack(updated solution)
Undo choice (backtrack)

Key Properties
Uses recursion
Explores all possibilities systematically
Prunes invalid branches early
Uses DFS (Depth-First Search) approach
 Example: Maze Solving
Problem: Find path from Start (S) to Exit (E) in a maze

Maze:

S 0 0 1
1 0 1 0
0 0 0 1
1 1 0 E

(0 = open space, 1 = wall)

Algorithm:

1. Start at position S(0,0)

2. Try moving Right → Success, move to (0,1)
3. Try moving Down → Success, move to (1,1)
4. Try moving Right → Blocked by wall
5. Try moving Down → Success, move to (2,1)
6. Continue until reaching E(3,3)

Path Found: S → Right → Down → Down → Right → Down → Right → E

Applications
N-Queens Problem
Sudoku Solver
Maze Problems
Graph Coloring
Subset Sum Problem

Time Complexity
Worst Case: O(k^n) where k is branching factor, n is depth
Space: O(n) for recursion stack

5. Prim's Algorithm
Definition
Prim's Algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST) of a weighted, connected, undirected
graph[22][28].
 Key Concept
A Minimum Spanning Tree connects all vertices with minimum total edge weight, without forming cycles.

Algorithm Steps
1. Choose a random starting vertex and add it to MST
2. Find the minimum weight edge connecting MST to a vertex outside MST
3. Add that edge and vertex to MST
4. Repeat step 2-3 until all vertices are included in MST

How It Works
Starts with single vertex
Grows the tree by adding one vertex at a time
Always selects the minimum weight edge that connects tree to non-tree vertex
Uses greedy approach at each step

Example
Graph:

Vertices: A, B, C, D, E
Edges with weights:
A-B: 2
A-C: 3
B-C: 1
B-D: 4
C-D: 2
C-E: 5
D-E: 3

Execution:

1. Start: Select vertex A, MST =

2. Step 1: Edges from A: (A-B:2), (A-C:3). Choose A-B (minimum), MST = {A, B}
3. Step 2: Edges available: (A-C:3), (B-C:1), (B-D:4). Choose B-C, MST = {A, B, C}
4. Step 3: Edges available: (A-C:3), (B-D:4), (C-D:2), (C-E:5). Choose C-D, MST = {A, B, C, D}
5. Step 4: Edges available: (B-D:4), (D-E:3), (C-E:5). Choose D-E, MST = {A, B, C, D, E}

MST Edges: A-B, B-C, C-D, D-E Total Weight: 2 + 1 + 2 + 3 = 8

Pseudocode
 Prim(Graph, start_vertex):
MST = {start_vertex}
edges = []

while MST does not contain all vertices:

min_edge = null
for each vertex v in MST:
for each edge (v, u) where u not in MST:
if edge weight < min_edge weight:
min_edge = (v, u)

Add min_edge to MST

Add destination vertex to MST

return MST

Time Complexity
Using Adjacency Matrix: O(V²)
Using Min-Heap: O(E log V)
Space: O(V + E)

6. Kruskal's Algorithm
Definition
Kruskal's Algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST) by sorting edges and adding them
in increasing order of weight, while avoiding cycles[23][26].

Algorithm Steps
1. Sort all edges in ascending order of their weights
2. Initialize MST as empty
3. For each edge (in sorted order):
If adding edge doesn't create cycle, add it to MST
Otherwise, skip the edge
4. Stop when MST has (V-1) edges

Cycle Detection
Uses Union-Find (Disjoint Set) data structure to detect cycles efficiently.
 Example
Graph:

Edges with weights:

PQ: 1
ST: 2
QR: 3
RS: 4
PT: 5
PR: 7
PS: 10

Sorted Edges: PQ(1), ST(2), QR(3), RS(4), PT(5), PR(7), PS(10)

Execution:

1. Add PQ (weight 1): No cycle, MST =

2. Add ST (weight 2): No cycle, MST = {PQ, ST}
3. Add QR (weight 3): No cycle, MST = {PQ, ST, QR}
4. Add RS (weight 4): No cycle, MST = {PQ, ST, QR, RS}
5. Check PT (weight 5): Creates cycle (P-Q-R-S-T-P), skip
6. Check PR (weight 7): Creates cycle, skip
7. Check PS (weight 10): Creates cycle, skip

MST Edges: PQ, ST, QR, RS Total Weight: 1 + 2 + 3 + 4 = 10

Pseudocode

Kruskal(Graph):
MST = []
Sort all edges by weight

for each edge (u, v) in sorted order:

if adding (u, v) does not create cycle:
Add (u, v) to MST
if MST has (V-1) edges:
break

return MST

Difference: Prim's vs Kruskal's

Aspect Prim's Kruskal's
 Aspect Prim's Kruskal's
Approach Vertex-based Edge-based
Growth Grows single tree Merges multiple trees
Data Structure Priority Queue Union-Find
Graph Type Works only on connected graphs Works on disconnected graphs
Efficiency Better for dense graphs Better for sparse graphs

Time Complexity
Time: O(E log E) or O(E log V)
Space: O(V + E)

7. Knapsack Problem
Definition
The 0/1 Knapsack Problem is an optimization problem where we have a knapsack with maximum weight capacity W, and
n items, each with weight wᵢ and value vᵢ. Goal is to maximize total value without exceeding weight capacity[41][44].

Constraint
Each item can either be included (1) or excluded (0) - cannot take fractional items.

Dynamic Programming Approach

Recurrence Relation:

K[i][w] = max(K[i-1][w], vᵢ + K[i-1][w-wᵢ])

where:
K[i][w] = maximum value with i items and capacity w
K[i-1][w] = value without including item i
vᵢ + K[i-1][w-wᵢ] = value with item i

Example
Input:

Capacity W = 8
Items:
Item 1: weight=5, value=15
Item 2: weight=4, value=20
 Item 3: weight=3, value=21

DP Table:

w=0 w=1 w=2 w=3 w=4 w=5 w=6 w=7 w=8

i=0 0 0 0 0 0 0 0 0 0
i=1 0 0 0 0 0 15 15 15 15
i=2 0 0 0 0 20 20 20 20 35
i=3 0 0 0 21 21 21 41 41 41

Solution:

Include Item 2 (weight=4, value=20)

Include Item 3 (weight=3, value=21)
Total weight = 7, Total value = 41

Items Selected: {Item 2, Item 3} Maximum Value: 41

Algorithm Steps
1. Create DP table of size (n+1) × (W+1)
2. Initialize first row and column to 0
3. For each item i and weight w:
If wᵢ ≤ w: K[i][w] = max(K[i-1][w], vᵢ + K[i-1][w-wᵢ])
Else: K[i][w] = K[i-1][w]
4. Return K[n][W]

Time Complexity
Time: O(nW) - pseudo-polynomial
Space: O(nW)

8. Maximum Flow Problem

Definition
Given a flow network (directed graph) where each edge has a capacity, find the maximum amount of flow that can be
sent from source (s) to sink (t) such that[42]:

Flow on edge ≤ capacity of edge

Incoming flow = Outgoing flow (except at s and t)

Ford-Fulkerson Algorithm
 Most common algorithm to solve maximum flow problem.

Algorithm Steps
1. Start with initial flow = 0
2. While there exists an augmenting path from s to t:
Find augmenting path using BFS or DFS
Calculate bottleneck capacity (minimum capacity on path)
Increase flow along path by bottleneck capacity
Update residual capacities
3. Return maximum flow

Key Concepts
Augmenting Path: Path from source to sink with available capacity
Residual Graph: Graph showing remaining capacities
Residual Capacity: Original capacity - current flow
Bottleneck: Minimum capacity on augmenting path

Example
Flow Network:

Capacity
s → A: 16
s → C: 13
A → B: 12
A → C: 10
B → t: 20
C → A: 4
C → D: 14
D → B: 7
D → t: 4

Execution:

1. Path 1: s-A-B-t, Bottleneck = min(16, 12, 20) = 12

Flow = 12
2. Path 2: s-C-D-t, Bottleneck = min(13, 14, 4) = 4
Flow = 12 + 4 = 16
3. Path 3: s-C-D-B-t, Bottleneck = min(9, 10, 7, 8) = 7
Flow = 16 + 7 = 23
4. No more augmenting paths
 Maximum Flow: 23

Pseudocode

FordFulkerson(Graph, s, t):
max_flow = 0

while there exists augmenting path from s to t:

path = find_path_BFS(s, t)
bottleneck = min capacity on path

for each edge in path:

increase flow by bottleneck
update residual capacity

max_flow += bottleneck

return max_flow

Time Complexity
Time: O(E × max_flow) - basic Ford-Fulkerson
Edmonds-Karp (using BFS): O(VE²)
Space: O(V + E)

9. Hamiltonian Circuit
Definition
A Hamiltonian Circuit is a path in a graph that visits every vertex exactly once and returns to the starting vertex[43][46]. It
forms a cycle that includes all vertices.

Difference from Eulerian Circuit

Hamiltonian: Visits every vertex once
Eulerian: Visits every edge once

Problem Statement
Given a graph G, determine if a Hamiltonian Circuit exists, and if so, find it.
 Backtracking Approach
1. Start from an arbitrary vertex (usually vertex 0)
2. Try to visit all other vertices
3. Check if current vertex is adjacent to next unvisited vertex
4. If yes, add to path and recurse
5. If path visits all vertices and returns to start, circuit found
6. Otherwise, backtrack and try different path

Example
Graph:

Vertices: a, b, c, d, e, f
Edges:
a-b, a-c, a-d
b-f, b-c
c-e, c-d
d-e
e-f

Execution (starting from 'a'):

1. Start: a
2. Try: a → b → c → d → e → f (dead end, f not connected to a)
3. Backtrack to e, try: a → b → c → e (dead end)
4. Backtrack to c, try: a → b → f → e → c → d → a ✓

Hamiltonian Circuit Found: a → b → f → e → c → d → a

Alternative Circuit: a → b → c → e → d → f (if path exists)

Brute Force Approach (For TSP)

For complete graph with n vertices:

Total Hamiltonian circuits = (n-1)!

For n=4: circuits = 3! = 6

Example: Finding Shortest Hamilton Circuit

Vertices: A, B, C, D
Weights:
A-B: 10, A-C: 15, A-D: 20
B-C: 35, B-D: 25
C-D: 30

All Circuits:

A-B-C-D-A: 10+35+30+20 = 95
A-B-D-C-A: 10+25+30+15 = 80 ✓ (Minimum)
A-C-B-D-A: 15+35+25+20 = 95
A-C-D-B-A: 15+30+25+10 = 80 ✓ (Minimum)
A-D-B-C-A: 20+25+35+15 = 95
A-D-C-B-A: 20+30+35+10 = 95

Optimal Circuit: A-B-D-C-A (Weight = 80)

Algorithm

HamiltonianCircuit(graph, path, pos):

if pos == n:
if edge exists from path[pos-1] to path[0]:
return true
return false

for vertex v from 1 to n:

if isSafe(v, graph, path, pos):
path[pos] = v
if HamiltonianCircuit(graph, path, pos+1):
return true
path[pos] = -1 // backtrack

return false

Time Complexity
Time: O(N!) - factorial complexity
Space: O(N) - path storage

10. Dynamic Programming

 Definition
Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them down into
simpler overlapping subproblems, solving each subproblem once, and storing their solutions[61][67].

Two Essential Properties

1. Overlapping Subproblems: Same subproblems are solved multiple times
2. Optimal Substructure: Optimal solution can be constructed from optimal solutions of subproblems

Two Approaches
1. Memoization (Top-Down): Recursion + caching
2. Tabulation (Bottom-Up): Iterative + table filling

Steps to Solve DP Problems

1. Identify if problem has optimal substructure
2. Define state/subproblem
3. Write recurrence relation
4. Identify base cases
5. Implement using memoization or tabulation

Example 1: Fibonacci Numbers

Problem: Find nth Fibonacci number

Recurrence:

F(n) = F(n-1) + F(n-2)

F(0) = 0, F(1) = 1

Without DP (Exponential Time):

fib(5) calls fib(4) and fib(3)

fib(4) calls fib(3) and fib(2)
fib(3) is computed multiple times!

With DP (Memoization):
memo = [-1] * (n+1)

def fib(n):
if n <= 1:
return n
if memo[n] != -1:
return memo[n]

memo[n] = fib(n-1) + fib(n-2)

return memo[n]

Result for n=5:

F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5

Answer: 5

Example 2: Longest Common Subsequence (LCS)

Problem: Find length of longest common subsequence in two strings

Strings: "ABCD" and "ACDF"

Recurrence:

LCS[i][j] = LCS[i-1][j-1] + 1 if X[i] == Y[j]

= max(LCS[i-1][j], LCS[i][j-1]) if X[i] != Y[j]

DP Table:

"" A C D F
"" 0 0 0 0 0
A 0 1 1 1 1
B 0 1 1 1 1
C 0 1 2 2 2
D 0 1 2 3 3

LCS: "ACD" (Length = 3)

Common DP Problems
Fibonacci Numbers
Longest Common Subsequence
0/1 Knapsack
 Matrix Chain Multiplication
Edit Distance
Coin Change Problem
Subset Sum
Longest Increasing Subsequence

Time Complexity
Reduces: Exponential → Polynomial
Example: Fibonacci O(2ⁿ) → O(n)

11. Greedy Method

Definition
Greedy Algorithm is an algorithmic paradigm that builds solutions piece by piece, always choosing the next piece that
offers the most obvious and immediate benefit (local optimum)[62][71].

Greedy Choice Property

At each step, make the choice that looks best at that moment, hoping it will lead to global optimum.

When Greedy Works

1. Problem has optimal substructure
2. Greedy choice property holds
3. Local optimum leads to global optimum

General Approach
1. Sort/order elements based on some criterion
2. Pick the best available option at each step
3. Check if choice is feasible
4. If feasible, add to solution
5. Repeat until solution is complete

Example 1: Coin Change Problem

Problem: Make change for amount using minimum number of coins

Amount: $18 Available Coins: $5, $2, $1 (unlimited)

Greedy Approach:
1. Use maximum $5 coins: 18/5 = 3 coins, remainder = 3
2. Use maximum $2 coins: 3/2 = 1 coin, remainder = 1
3. Use $1 coins: 1/1 = 1 coin, remainder = 0

Solution: 3×$5 + 1×$2 + 1×$1 = $18 Total Coins: 5 coins

Example 2: Activity Selection Problem

Problem: Select maximum number of non-overlapping activities

Activities with [start, finish] times:

A1: [1, 3]
A2: [2, 5]
A3: [4, 7]
A4: [1, 8]
A5: [5, 9]
A6: [8, 10]

Greedy Strategy: Select activity with earliest finish time

Execution:

1. Sort by finish time: A1(3), A2(5), A3(7), A5(9), A6(10), A4(8)

2. Select A1 [1,3], finish = 3
3. Select A3 [4,7] (starts after 3), finish = 7
4. Select A6 [8,10] (starts after 7), finish = 10

Selected Activities: A1, A3, A6 (Total: 3 activities)

Example 3: Fractional Knapsack

Problem: Fill knapsack to maximize value (fractional items allowed)

Capacity: 50 kg Items:

Item 1: 10kg, value=60 (ratio: 6)

Item 2: 20kg, value=100 (ratio: 5)
Item 3: 30kg, value=120 (ratio: 4)

Greedy Strategy: Select items by value/weight ratio

Execution:

1. Sort by ratio: Item1(6), Item2(5), Item3(4)

2. Take full Item1: weight=10, value=60, remaining=40
3. Take full Item2: weight=20, value=100, remaining=20
4. Take 20kg of Item3: weight=20, value=80, remaining=0
 Total Value: 60 + 100 + 80 = 240

Difference: Greedy vs Dynamic Programming

Aspect Greedy Dynamic Programming
Approach Local optimum All possibilities
Choice Never reconsiders Evaluates all options
Efficiency More efficient Less efficient
Optimality Not always optimal Always optimal
Examples Prim's, Kruskal's Knapsack, LCS

Greedy Algorithms in DAA

Prim's Algorithm
Kruskal's Algorithm
Dijkstra's Algorithm
Huffman Coding
Activity Selection
Fractional Knapsack

Time Complexity
Varies by problem, typically O(n log n) due to sorting.

YouTube Video Recommendations

Best YouTube Channels for DAA:
1. Abdul Bari - Algorithms Playlist

URL: [Link]
([Link]
Comprehensive coverage of all DAA topics
Clear explanations with animations
Covers: N-Queens, Backtracking, DP, Greedy, Graph algorithms

2. Jenny's Lectures CS IT - DAA Course

URL: [Link]
([Link]
Complete DAA syllabus coverage
Exam-oriented approach
Topics: Prims, Kruskal's, Dynamic Programming, NP-Complete
3. Specific Topic Videos:

N-Queens Problem: [Link] ([Link]

v=xFv_Hl4B83A)
Knapsack Problem (DP): [Link]
([Link]
Prim's and Kruskal's: [Link] ([Link]
v=6LikZhGLRgU)
Hamiltonian Circuit: [Link] ([Link]
v=u9zNwN6z-q4)

Quick Revision Tips

For 5 Marks Questions:
1. Write Algorithm/Steps (1.5 marks)
2. Provide Example with execution (2 marks)
3. Time & Space Complexity (0.5 mark)
4. Explanation/Key Points (1 mark)

Important Points to Remember:

N-Queens: Backtracking with safety checks
NP-Complete: Verification in polynomial time
Assignment: Hungarian method with row/column reduction
Backtracking: DFS with pruning
Prim's: Vertex-based MST, greedy
Kruskal's: Edge-based MST, uses Union-Find
Knapsack: DP with table, O(nW)
Max Flow: Ford-Fulkerson with augmenting paths
Hamiltonian: Visit all vertices once, return to start
DP: Memoization/Tabulation, overlapping subproblems
Greedy: Local optimum, immediate benefit

Good Luck with Your Exam!