Design and Analysis of Algorithms - Model Answer Sheet

Dr. Babasaheb Ambedkar Technological University, Lonere

Supplementary Winter-2023 Examination

Course: B.Tech | Semester: IV | Subject Code & Name: BTCOC401 - Design and Analysis of
Algorithms

Maximum Marks: 60 | Duration: 3 Hours

### Q1. Solve Any Two

(A) What is an Algorithm? Explain Criteria of an Algorithm
An algorithm is a finite sequence of well-defined instructions that provide a solution to a
given problem in a systematic way.
Definition:
An algorithm is a step-by-step procedure or formula for solving a problem. It must produce
output after a finite number of steps.
Criteria of a Good Algorithm:
1. Input: Should accept zero or more inputs.
2. Output: Must produce at least one output.
3. Finiteness: Algorithm must terminate after finite steps.
4. Definiteness: Each step must be clearly and unambiguously defined.
5. Effectiveness: All operations must be basic enough to be carried out in a finite time.
6. Generality: Should solve a group of problems, not just one instance.
(B) What is Asymptotic Notation? Explain any three
Asymptotic Notation helps in representing time complexity for large inputs. It abstracts
away constants and low-order terms.
1. Big-O Notation (O)
- Describes upper bound.
- f(n) ∈ O(g(n)) if ∃ c, n₀ such that: f(n) ≤ c·g(n)
- Example: 2n + 3 ∈ O(n)
2. Omega Notation (Ω)
- Describes lower bound.
- f(n) ∈ Ω(g(n)) if ∃ c, n₀: f(n) ≥ c·g(n)
- Example: 3n + 1 ∈ Ω(n)
3. Theta Notation (Θ)
- Describes tight bound.
- f(n) ∈ Θ(g(n)) if ∃ c₁, c₂, n₀: c₁g(n) ≤ f(n) ≤ c₂g(n)
- Example: 5n + 10 ∈ Θ(n)
(C) Define Max and Min Heap. Write Algorithm to Insert in Heap
Heap: A complete binary tree where each node is either:
- Max Heap: Node ≥ its children
- Min Heap: Node ≤ its children
Insert into Max Heap:
1. Place element at end.
2. Compare with parent and bubble up if larger.
3. Repeat until heap property is restored.
Algorithm (Max Heap Insertion):
Insert(H, key):
1. H.size++
2. i = H.size
3. H[i] = key
4. while i > 1 and H[parent(i)] < H[i]:
swap H[i] and H[parent(i)]
i = parent(i)
Example: Insert 50 into Max Heap: [40, 30, 20] → [50, 40, 20, 30]
### Q2. Solve Any Two
(A) Binary Search Algorithm and Time Complexity
Binary Search: Searches a sorted array by repeatedly dividing the search interval.
Algorithm:
BinarySearch(A, key):
1. low = 0, high = n - 1
2. while low <= high:
mid = (low + high) / 2
if A[mid] == key: return mid
else if A[mid] < key: low = mid + 1
else: high = mid - 1
3. return -1
Time Complexity:
- Best case: O(1)
- Average/Worst case: O(log n)
(B) Quick Sort with Performance Analysis
Quick Sort: Divide and conquer based sorting algorithm.
Steps:
1. Choose pivot
2. Partition: smaller on left, larger on right
3. Recursively sort subarrays
Performance:
- Best case: O(n log n)
- Average: O(n log n)
- Worst: O(n²)
(C) Strassen’s Matrix Multiplication
Purpose: Multiply 2x2 matrices using only 7 multiplications
Strassen’s 7 Products:
M1 = (a + d)(e + h)
M2 = (c + d)e
M3 = a(f - h)
M4 = d(g - e)
M5 = (a + b)h
M6 = (c - a)(e + f)
M7 = (b - d)(g + h)
Result Matrix:
C11 = M1 + M4 - M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 - M2 + M3 + M6
### Q3. Solve Any Two
(A) 4-Queens Problem
Backtracking Steps:
1. Place queen in row 1 at each column.
2. For each valid placement, go to next row.
3. Backtrack if placement causes conflict.
State Space Tree:
Each level represents a row.
Each node is a column.
Valid Configuration:
_Q__
___Q
Q___
__Q_
(B) Graph Coloring
Objective: Assign colors to graph vertices such that no adjacent vertices share the same
color.
Example: A-B-C-D-A
Assign A = Red, B = Blue, C = Red, D = Blue
Chromatic number = 2
(C) Branch and Bound (Example: TSP)
Steps:
1. Compute lower bound for each node
2. Branch into subproblems (paths)
3. Bound: Discard paths worse than current best
### Q4. Solve Any Two
(A) Knapsack (n=7, m=15)
Profits = [10,5,15,7,6,18,3]
Weights = [2,3,5,7,1,4,1]
Use DP table to compute max profit.
Final Answer: Maximum profit = 55
(B) Minimum Cost Spanning Tree
Definition: Tree connecting all vertices with minimum total edge weight.
Algorithms:
- Kruskal’s
- Prim’s
(C) Job Sequencing with Deadlines
Steps:
1. Sort jobs by decreasing profit
2. Assign to latest available time slot
Example:
J1,P=100,D=2
J2,P=19,D=1
J3,P=27,D=2
J4,P=25,D=1
Selected = J1, J3 → Profit = 127
### Q5. Solve Any Two
(A) Floyd Warshall Algorithm
Purpose: All-pairs shortest paths.
Steps:
1. Initialize dist[i][j]
2. For each k:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
Time: O(n³)
(B) P vs NP
P: Solvable in polynomial time (e.g., Binary Search)
NP: Verifiable in polynomial time (e.g., SAT)
P ⊆ NP; Open problem: Is P = NP?
(C) DP vs Greedy
| Feature | DP | Greedy |
|---------|----|--------|
| Strategy | Solve all subproblems | Make local optimal choice |
| Overlap | Yes | No |
| Examples | Knapsack, LCS | Kruskal, Prim |