VBSPU

Assignment Answer Key

Design and Analysis of Algorithms (DAA)
4th Semester
SECTION A — Very Short Answers

Q1. Define an algorithm.

An algorithm is a finite, well-defined sequence of instructions or steps designed to solve a specific
problem or perform a computation. It takes input, processes it, and produces output.
Key Properties:
Input, Output, Definiteness, Finiteness, Effectiveness.
Example:
Algorithm to find the maximum of two numbers: Input a, b → if a > b then max = a else max = b →
Output max.

Q2. What is time complexity?

Time complexity is the amount of time an algorithm takes to complete as a function of the length of the
input (n). It describes how the running time grows as input size increases.
Common Notations:
O(1) – Constant | O(log n) – Logarithmic | O(n) – Linear | O(n²) – Quadratic | O(2ⁿ) – Exponential
Example:
Linear search on an array of n elements has time complexity O(n) — it may check all n elements in the
worst case.

Q3. Define Big-O notation.

Big-O notation O(f(n)) describes the upper bound (worst-case) of an algorithm's time or space
complexity. It tells us how the algorithm performs in the worst possible scenario.
Formal Definition:
f(n) = O(g(n)) if there exist positive constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀.
Example:
f(n) = 3n² + 5n + 2 → O(n²), because for large n, n² dominates.

Q4. What is a recurrence relation?

A recurrence relation is a mathematical equation that defines a sequence recursively — each term is
expressed using previous terms. In algorithms, it describes the running time of recursive algorithms.
Example:
Merge Sort: T(n) = 2T(n/2) + O(n), where T(1) = O(1). Solving this by Master Theorem gives T(n) = O(n
log n).

Q5. Define the Divide and Conquer technique.

Divide and Conquer is an algorithm design paradigm that breaks a problem into smaller subproblems,
solves each subproblem recursively, and combines the results to obtain the solution.
Three Steps:
1. Divide – Break the problem into sub-problems. 2. Conquer – Recursively solve sub-problems. 3.
Combine – Merge the sub-problem solutions.
Examples:
Merge Sort, Quick Sort, Binary Search, Strassen's Matrix Multiplication.

Q6. What is the Greedy method?

The Greedy method is an algorithmic approach where at each step, the locally optimal (best immediate)
choice is made with the hope that this leads to a globally optimal solution.
Key Characteristics:
Makes decisions one at a time, never backtracks, optimal for certain problems.
Examples:
Fractional Knapsack, Dijkstra's Algorithm, Kruskal's / Prim's Algorithm, Activity Selection Problem.

Q7. Define Dynamic Programming.

Dynamic Programming (DP) is an optimization technique that solves problems by breaking them into
overlapping subproblems, solving each subproblem once, and storing results in a table (memoization /
tabulation) to avoid recomputation.
Key Properties:
Optimal Substructure + Overlapping Subproblems.
Examples:
0/1 Knapsack, Matrix Chain Multiplication, Fibonacci Series, Longest Common Subsequence (LCS).

Q8. What is Backtracking?

Backtracking is a general algorithm for finding solutions by incrementally building candidates and
abandoning (backtracking) a candidate as soon as it is determined that it cannot lead to a valid
solution.
Approach:
Build solution step by step. If a constraint is violated at any step, undo the last step (backtrack) and try
another option.
Examples:
N-Queens Problem, Sudoku Solver, Subset Sum, Graph Coloring.

Q9. Define a spanning tree.

A spanning tree of a connected, undirected graph G = (V, E) is a subgraph that includes all vertices V
but contains only |V| – 1 edges such that all vertices are connected with no cycles.
Properties:
Contains all n vertices | Has exactly n–1 edges | No cycles | Graph must be connected.
Example:
For a graph with 4 vertices (A, B, C, D), a spanning tree will have exactly 3 edges connecting all
vertices without any cycle. Algorithms: Kruskal's, Prim's.
Q10. What is the Traveling Salesman Problem (TSP)?
The Traveling Salesman Problem (TSP) asks: Given a list of n cities and the distances between each
pair of cities, what is the shortest possible route that visits every city exactly once and returns to the
starting city?
Complexity:
TSP is NP-Hard. Brute force solution is O(n!). Can be solved using Branch and Bound, Dynamic
Programming (Held-Karp algorithm O(n²·2ⁿ)), or approximation algorithms.
Example:
Cities: A, B, C, D. Find the minimum-cost Hamiltonian cycle (visits all cities once, returns to start).
SECTION B — Short Answers

Q1. Explain the analysis of algorithms with examples.

Definition:
Algorithm analysis is the process of determining the computational complexity of an algorithm — the
amount of time, storage, and resources needed.
Types of Analysis:
1. Best Case – Minimum time required (Ω notation). Example: Linear search finds element at index 0 →
O(1). 2. Worst Case – Maximum time required (O notation). Example: Linear search, element not
present → O(n). 3. Average Case – Expected time over all inputs (Θ notation). Example: Linear search
→ O(n/2) ≈ O(n).
Example — Linear Search:
Best: O(1) | Average: O(n/2) | Worst: O(n)
Example — Binary Search:
Best: O(1) | Average: O(log n) | Worst: O(log n)

Q2. Describe Selection Sort with its time complexity.

Definition:
Selection Sort is a simple comparison-based sorting algorithm. It divides the array into a sorted and
unsorted part. In each pass, it finds the minimum element from the unsorted part and places it at the
beginning.
Algorithm:
for i = 0 to n-2:
min_idx = i
for j = i+1 to n-1:
if arr[j] < arr[min_idx]: min_idx = j
swap arr[i] and arr[min_idx]

Example (sorting [64, 25, 12, 22, 11]):

Pass 1: Min=11, swap with 64 → [11, 25, 12, 22, 64] Pass 2: Min=12, swap with 25 → [11, 12, 25, 22,
64] Pass 3: Min=22, swap with 25 → [11, 12, 22, 25, 64] Pass 4: Min=25, already in place → [11, 12,
22, 25, 64]
Time Complexity:
Best Case: O(n²) | Average Case: O(n²) | Worst Case: O(n²) Space Complexity: O(1) — In-place
sorting.

Q3. Explain Merge Sort with an example.

Definition:
Merge Sort is a Divide and Conquer algorithm. It divides the array into two halves, recursively sorts
each half, and then merges the sorted halves.
Algorithm:
MergeSort(arr, l, r):
if l < r:
mid = (l+r)/2
 MergeSort(arr, l, mid)
MergeSort(arr, mid+1, r)
Merge(arr, l, mid, r)

Example (sorting [38, 27, 43, 3]):

[38, 27, 43, 3] → Split: [38, 27] | [43, 3] [38, 27] → [38] | [27] → Merge: [27, 38] [43, 3] → [43] | [3] →
Merge: [3, 43] Final Merge: [27, 38] + [3, 43] → [3, 27, 38, 43]
Time Complexity:
All Cases: O(n log n) | Space: O(n)

Q4. Discuss the Fractional Knapsack problem.

Definition:
In the Fractional Knapsack problem, we can take fractions of items (not just whole items). The goal is to
maximize the total value in a knapsack of capacity W.
Greedy Strategy:
Calculate value/weight ratio for each item. Sort in decreasing order of ratio. Take items greedily (full
item first, fractional if needed).
Example:
Items: (value=60, wt=10), (value=100, wt=20), (value=120, wt=30) | Capacity W=50 Ratios: 6, 5, 4 Sort:
Item1(ratio 6), Item2(ratio 5), Item3(ratio 4) Take all of Item1: 10 kg, value=60 Take all of Item2: 20 kg,
value=100 Take 20/30 of Item3: 20 kg, value=80 Total: 50 kg, Total Value = 60+100+80 = 240
Time Complexity:
O(n log n) — due to sorting.

Q5. Explain Matrix Chain Multiplication with an example.

Definition:
Matrix Chain Multiplication is a DP problem that finds the optimal parenthesization of a sequence of
matrices to minimize the number of scalar multiplications.
Key Idea:
Multiplying an m×n matrix with an n×p matrix costs m×n×p scalar multiplications. The order of
multiplication affects cost, not the result.
Example:
Matrices: A(10×30), B(30×5), C(5×60) Option 1: (A×B)×C = (10×30×5) + (10×5×60) = 1500+3000 =
4500 Option 2: A×(B×C) = (30×5×60) + (10×30×60) = 9000+18000 = 27000 Optimal: (A×B)×C with cost
4500.
Time Complexity:
O(n³) using DP | Space: O(n²)

Q6. Explain Dijkstra's algorithm with an example.

Definition:
Dijkstra's Algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph
with non-negative edges.
Algorithm Steps:
1. Set distance of source = 0, all others = ∞ 2. Add source to priority queue 3. Pick vertex u with
minimum distance 4. For each neighbor v: if dist[u] + weight(u,v) < dist[v], update dist[v] 5. Repeat until
all vertices processed
Example:
Graph: A→B(4), A→C(2), C→B(1), B→D(5), C→D(8) Source: A dist[A]=0, dist[B]=∞, dist[C]=∞,
dist[D]=∞ Visit A: dist[B]=4, dist[C]=2 Visit C(min=2): dist[B]=min(4, 2+1)=3, dist[D]=min(∞,2+8)=10 Visit
B(min=3): dist[D]=min(10, 3+5)=8 Visit D(min=8): Done Shortest paths: A→B=3, A→C=2, A→D=8
Time Complexity:
O((V + E) log V) with min-heap | O(V²) with array

Q7. Write a short note on the Branch and Bound technique.

Definition:
Branch and Bound is a systematic search algorithm used for solving optimization problems, especially
NP-hard problems like TSP and 0/1 Knapsack. It explores the solution space as a tree.
How it Works:
Branch: Split the problem into sub-problems (branches/nodes in a tree). Bound: Calculate an
upper/lower bound for each node. Prune: Discard branches where bound is worse than current best
solution.
Example (0/1 Knapsack):
Use an upper bound (fractional knapsack value) for each node. If bound ≤ current best, prune that
branch. Explore only promising branches.
Advantage over Backtracking:
Branch and Bound uses bounds to prune the search tree earlier, making it more efficient for
optimization problems.

Q8. What is Bucket Sort? Explain with an example.

Definition:
Bucket Sort distributes elements into a number of buckets, sorts each bucket individually (using another
algorithm or recursively), and then concatenates the buckets.
Steps:
1. Create n empty buckets 2. Put array elements into appropriate buckets 3. Sort each bucket (e.g.,
using insertion sort) 4. Concatenate all sorted buckets
Example:
Array: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68] Create 10 buckets (0.0–0.1), (0.1–
0.2),... Bucket 1: [0.17, 0.12] → sorted: [0.12, 0.17] Bucket 2: [0.26, 0.21, 0.23] → sorted: [0.21, 0.23,
0.26] ... etc. Result: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]
Time Complexity:
Average Case: O(n+k) | Worst Case: O(n²) | Best for uniformly distributed data.

Q9. What is Radix Sort? Explain with an example.

Definition:
Radix Sort is a non-comparative sorting algorithm that sorts numbers digit by digit, from the least
significant digit (LSD) to the most significant digit (MSD), using a stable sort like Counting Sort as a
subroutine.
Steps:
1. Find max element to determine number of digits 2. Do counting sort for each digit position (units,
tens, hundreds...)
Example (sorting [170, 45, 75, 90, 802, 24, 2, 66]):
After sorting by units digit (0): [170, 90, 802, 2, 24, 45, 75, 66] After sorting by tens digit (0): [802, 2, 24,
45, 66, 170, 75, 90] After sorting by hundreds digit (0): [2, 24, 45, 66, 75, 90, 170, 802] Sorted!
Time Complexity:
O(d × (n + k)) where d = digits, k = digit range (0–9). Space: O(n+k). Efficient for integers with fixed
number of digits.

Q10. What is Kruskal's algorithm?

Definition:
Kruskal's Algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST) of a connected,
undirected, weighted graph by adding edges in increasing order of weight, skipping edges that form a
cycle.
Steps:
1. Sort all edges by weight in ascending order 2. Pick the smallest edge. If it doesn't form a cycle, add
to MST 3. Repeat until MST has V–1 edges (Uses Union-Find data structure to detect cycles)
Example:
Graph edges: (A-B,4), (A-C,2), (B-D,5), (C-D,1), (B-C,3) Sorted: (C-D,1), (A-C,2), (B-C,3), (A-B,4), (B-
D,5) Add (C-D,1): MST={CD} Add (A-C,2): MST={CD, AC} Add (B-C,3): MST={CD, AC, BC} → 3 edges
for 4 vertices. Done! MST total weight = 1+2+3 = 6
Time Complexity:
O(E log E) — due to sorting edges.
SECTION C — Long Answers

Q1. Discuss Quick Sort with its time complexity.

Definition:
Quick Sort is a Divide and Conquer sorting algorithm. It picks a pivot element and partitions the array
such that elements less than pivot are on the left and elements greater are on the right, then recursively
sorts each side.
Algorithm:
QuickSort(arr, low, high):
if low < high:
pi = Partition(arr, low, high)
QuickSort(arr, low, pi-1)
QuickSort(arr, pi+1, high)

Partition(arr, low, high):

pivot = arr[high]
i = low - 1
for j = low to high-1:
if arr[j] <= pivot:
i++
swap arr[i] and arr[j]
swap arr[i+1] and arr[high]
return i+1

Detailed Example (sorting [10, 7, 8, 9, 1, 5]):

Pivot = 5 (last element) Partition: [1] [5] [10, 7, 8, 9] Left [1]: already sorted Right [10,7,8,9]: Pivot=9 →
[7,8] [9] [10] [7,8]: Pivot=8 → [7] [8] Final: [1, 5, 7, 8, 9, 10]
Time Complexity:
Best Case: O(n log n) — pivot always divides array equally. Average Case: O(n log n) — random pivot.
Worst Case: O(n²) — pivot is always smallest/largest (sorted input).
Space Complexity:
O(log n) average (recursive stack) | O(n) worst case.
Advantages:
In-place sorting, cache-friendly, fastest in practice for large data.

Q2. Explain the Counting and Probability Theorems with examples.

Counting Theorem (Fundamental Principle of Counting):
If an event A can occur in m ways and event B can occur in n ways, then both A and B together can
occur in m × n ways (Multiplication Principle).
Addition Principle:
If event A can occur in m ways OR event B can occur in n ways (mutually exclusive), then either A or B
can occur in m + n ways.
Example — Counting:
A password has 3 digits (0-9) and 2 uppercase letters (A-Z). Possible passwords = 10³ × 26² = 1000 ×
676 = 676,000
Permutations and Combinations:
P(n,r) = n! / (n-r)! — Ordered selection of r items from n C(n,r) = n! / (r! × (n-r)!) — Unordered selection
Example — Permutation:
Arrange 3 books out of 5 on a shelf: P(5,3) = 5!/2! = 60 ways
Example — Combination:
Choose 3 students out of 5 for a team: C(5,3) = 5!/(3!×2!) = 10 ways
Probability Theorems:
P(A) = (Favorable outcomes) / (Total outcomes) P(A∪B) = P(A) + P(B) – P(A∩B) Conditional: P(A|B) =
P(A∩B)/P(B) Bayes' Theorem: P(A|B) = P(B|A)·P(A) / P(B)
Example — Probability:
Tossing a fair coin twice: Total outcomes = 4 {HH, HT, TH, TT} P(at least one Head) = 3/4 = 0.75

Q3. Describe the 0/1 Knapsack problem.

Definition:
In the 0/1 Knapsack problem, we have n items each with weight wᵢ and value vᵢ, and a knapsack of
capacity W. We must select items such that total weight ≤ W and total value is maximized. Items cannot
be broken — either take it (1) or leave it (0).
DP Approach:
Define dp[i][w] = maximum value using first i items with capacity w. Recurrence: if w[i] > w: dp[i][w] =
dp[i-1][w] else: dp[i][w] = max(dp[i-1][w], v[i] + dp[i-1][w-w[i]])
Example:
Items: Item1(wt=2, val=6), Item2(wt=2, val=10), Item3(wt=3, val=12) | Capacity W=5 DP Table
(rows=items, cols=capacity 0–5):
0 1 2 3 4 5
i=0 0 0 0 0 0 0
i=1 0 0 6 6 6 6
i=2 0 0 10 10 16 16
i=3 0 0 10 12 16 22

Maximum value = dp[3][5] = 22

Tracing which items are selected:

dp[3][5]=22 ≠ dp[2][5]=16 → Item3 included (val=12, wt=3). Remaining capacity=2. dp[2][2]=10 ≠ dp[1]
[2]=6 → Item2 included (val=10, wt=2). Selected: Item2 + Item3 | Total value = 10+12 = 22
Time Complexity:
O(n × W) — Pseudo-polynomial. Space: O(n × W) or optimized O(W).

Q4. Describe the 8-Queen problem.

Definition:
The 8-Queens problem is to place 8 queens on an 8×8 chessboard such that no two queens attack
each other — no two queens share the same row, column, or diagonal.
Approach: Backtracking
Place queens row by row. For each row, try all 8 columns. Check if placement is safe. If safe, place
queen and move to next row. If no safe column found, backtrack to previous row.
Safety Check Conditions:
1. No queen in same column 2. No queen in same left diagonal (row-col = constant) 3. No queen in
same right diagonal (row+col = constant)
Algorithm:
 solve(row):
if row == 8: print solution; return
for col = 0 to 7:
if isSafe(row, col):
place queen at (row, col)
solve(row+1)
remove queen from (row, col) // backtrack

Example — Partial Trace for 4-Queens:

Row 0: Try col 0 → Place Q at (0,0) Row 1: col 0? No (same col). col 1? No (diagonal). col 2? Place Q
at (1,2) Row 2: col 0? No (diagonal). col 1? No. col 2? No (same col). col 3? No. Backtrack! Row 1 col
3: Place Q at (1,3) Row 2: col 0? No. col 1: Place Q at (2,1) Row 3: col 3? Place Q at (3,3)? No
diagonal conflict! → Solution found: [(0,0),(1,3),(2,1),(3,3)]
Solution Count:
The 8-queens problem has 92 distinct solutions (12 fundamental solutions ignoring
reflections/rotations).
Time Complexity:
O(n!) in worst case, but backtracking prunes many branches, making it much faster in practice.

Q5. What is Binary Tree Traversal?

Definition:
Binary Tree Traversal is the process of visiting (reading/processing) each node in a binary tree exactly
once in a systematic order. There are 3 main depth-first traversals and 1 breadth-first traversal.
1. Inorder Traversal (Left → Root → Right):
Visit left subtree, then root, then right subtree. For a BST, inorder gives elements in sorted ascending
order.
Inorder(node):
if node != NULL:
Inorder([Link])
print [Link]
Inorder([Link])

2. Preorder Traversal (Root → Left → Right):

Visit root first, then left subtree, then right subtree. Used to create a copy of the tree.
Preorder(node):
if node != NULL:
print [Link]
Preorder([Link])
Preorder([Link])

3. Postorder Traversal (Left → Right → Root):

Visit left, then right, then root. Used to delete the tree or evaluate expression trees.
Postorder(node):
if node != NULL:
Postorder([Link])
Postorder([Link])
print [Link]

4. Level Order Traversal (Breadth-First):

Visit all nodes level by level from root to leaves using a Queue.
Example Tree:
1
/ \
2 3
/ \
4 5
Traversal Results:
Inorder (L-Root-R): 4 → 2 → 5 → 1 → 3 Preorder (Root-L-R): 1 → 2 → 4 → 5 → 3 Postorder (L-R-
Root): 4 → 5 → 2 → 3 → 1 Level Order (BFS): 1 → 2 → 3 → 4 → 5
Time Complexity:
All traversals: O(n) — each node is visited exactly once. Space: O(h) for recursive (h = height) | O(n) for
level order (queue size).
Applications:
Inorder: BST sorting. Preorder: Copying tree, prefix expression. Postorder: Deleting tree, postfix
expression. Level Order: Finding shortest path, tree width.