---
## ✅ **Repeated 2-Mark Questions**
1. What is Backtracking?
➤ Repeated: 4 times — **Dec 2021, Dec 2022, May 2023, May 2024**
2. Define/What is NP-Hard problem?
➤ Repeated: 4 times — **May 2021, Dec 2023, May 2023, May 2024**
3. What is a Multistage graph?
➤ Repeated: 4 times — **Dec 2019, Dec 2021, May 2023, May 2024**
4. What is BFS?
➤ Repeated: 3 times — **Dec 2021, May 2023, May 2024**
5. What is Articulation Point?
➤ Repeated: 3 times — **Dec 2021, May 2022, May 2023**
6. Define the term Algorithm / Characteristics of Algorithm
➤ Repeated: 4 times — **Dec 2022, May 2021, May 2022, May 2023**
7. Define the Knapsack problem
➤ Repeated: 3 times — **Dec 2020, Dec 2021, May 2023**
8. What is Comparison Tree?
➤ Repeated: 3 times — **Dec 2019, Dec 2021, May 2024**
9. What is State Space Tree?
➤ Repeated: 2 times — **May 2021, May 2024**
10. State/Define Principle of Optimality
➤ Repeated: 3 times — **May 2021, Dec 2021, Dec 2023**
11. What is the 8-Queens problem?
➤ Repeated: 3 times — **Dec 2020, Dec 2021, Dec 2023**
---
## ✅ **Repeated 6-Mark Questions**
1. Explain Hamiltonian Cycles
➤ Repeated: 4 times — **May 2021, Dec 2022, May 2023, Dec 2023**
2. Explain Tree Vertex Splitting
➤ Repeated: 3 times — **Dec 2019, May 2023, May 2024**
3. Explain Multistage Graph
➤ Repeated: 3 times — **Dec 2021, May 2023, May 2024**
4. Write/Apply Quicksort Algorithm
➤ Repeated: 3 times — **Dec 2020, Dec 2022, May 2024**
5. Explain NP-Hard and NP-Complete Problems
➤ Repeated: 3 times — **Dec 2021, May 2023, Dec 2022**
6. Explain String Editing Problem
➤ Repeated: 3 times — **Dec 2020, May 2022, Dec 2023**
7. Draw/Explain Comparison Tree
➤ Repeated: 3 times — **Dec 2019, Dec 2022, May 2024**
8. Write short notes on Space Complexity
➤ Repeated: 3 times — **Dec 2019, Dec 2020, May 2023**
9. Explain Depth First Search (DFS)
➤ Repeated: 3 times — **May 2022, May 2023, Dec 2023**
---
## ✅ **Repeated 10-Mark Questions**
1. Explain Strassen’s Matrix Multiplication
➤ Repeated: 3 times — **Dec 2019, Dec 2021, Dec 2023**
2. Describe 0/1 Knapsack Problem
➤ Repeated: 4 times — **Dec 2020, Dec 2021, Dec 2023, May 2024**
3. Write Backtracking for Sum of Subset Problem
➤ Repeated: 3 times — **Dec 2019, Dec 2022, May 2021**
4. Use Branch and Bound for TSP Problem
➤ Repeated: 3 times — **Dec 2021, Dec 2023, May 2021**
5. Discuss NP-Hard and NP-Complete Classes
➤ Repeated: 3 times — **Dec 2019, May 2021, Dec 2022**
6. Apply Divide and Conquer with Example
➤ Repeated: 3 times — **Dec 2020, Dec 2022, May 2023**
7. Write Merge Sort Algorithm
➤ Repeated: 3 times — **Dec 2021, May 2021, May 2022**
8. Explain Job Sequencing with Deadlines
➤ Repeated: 3 times — **Dec 2020, May 2021, May 2022**
9. Write Dijkstra’s Algorithm or All-Pairs Shortest Path
➤ Repeated: 3 times — **Dec 2019, Dec 2022, May 2023**
---
---
## ✅ **Repeated 2-Mark Questions – Detailed Answers**
### 1. **What is Backtracking?**
Backtracking is a general algorithmic technique used to solve problems
incrementally by trying partial solutions and then abandoning them if they do not
lead to a complete solution (this process is called "backtracking").
It is applied to problems that involve **constraints and decision trees**, such as:
* 8-Queens Problem
* Sudoku Solver
* Subset Sum
* Hamiltonian Cycle
👉 **Core Idea:**
If a decision leads to a dead end, backtrack and try another path.
---
### 2. **Define / What is an NP-Hard Problem?**
An NP-Hard problem is one for which **no polynomial-time solution is known**, and
every problem in NP can be **reduced** to it in polynomial time.
👉 **Key Points**:
* NP-Hard ⊇ NP-Complete
* May or may not be in NP (i.e., may not be verifiable in polynomial time)
* Example: Halting Problem, Travelling Salesman Problem (optimization version)
---
### 3. **What is a Multistage Graph?**
A Multistage Graph is a **directed, weighted graph** arranged in stages (0 to k),
where edges exist only from one stage to the next.
🔹 It is used in **Dynamic Programming** to find shortest/cheapest paths.
👉 **Application**: Route optimization with multiple stages (like ticket booking
systems, task scheduling).
---
### 4. **What is BFS?**
Breadth-First Search (BFS) is a graph traversal technique that explores all nodes
at the current depth before moving to the next depth level.
🔹 It uses a **queue**.
🔹 Useful for finding **shortest paths in unweighted graphs**.
---
### 5. **What is an Articulation Point?**
An articulation point in a graph is a vertex whose removal **increases the number
of connected components**. In simpler terms, removing it **disconnects** the graph.
👉 Used in network reliability and analysis.
---
### 6. **Define the term Algorithm / Characteristics of Algorithm**
**Algorithm**: A step-by-step finite procedure to solve a problem or compute a
function.
**Characteristics**:
1. Finiteness
2. Definiteness
3. Input
4. Output
5. Effectiveness
---
### 7. **Define the Knapsack Problem**
The Knapsack Problem involves choosing items with given weights and values to
maximize value without exceeding the capacity of the knapsack.
🔹 Types:
* 0/1 Knapsack (select or skip items)
* Fractional Knapsack (can break items)
---
### 8. **What is a Comparison Tree?**
A Comparison Tree is a **binary decision tree** used to represent the sequence of
comparisons made during sorting/searching.
🔹 Internal nodes: comparisons
🔹 Leaves: final outcomes
---
### 9. **What is a State Space Tree?**
A state space tree is a **tree representation of all possible states** that a
problem can be in. Each node represents a partial solution.
🔹 Used in **Backtracking and Branch & Bound**.
---
### 10. **Define Principle of Optimality**
The Principle of Optimality (from Dynamic Programming) states:
> "An optimal solution to the problem contains optimal solutions to its
subproblems."
🔹 Used in **shortest paths, knapsack, matrix chain multiplication**, etc.
---
### 11. **What is the 8-Queens Problem?**
The 8-Queens problem requires placing 8 queens on a chessboard such that **no two
queens threaten each other**.
🔹 Solved using **backtracking** by placing queens one by one and checking
conflicts.
---
6-mark exam questions.
---
### ✅ 1. **Explain Hamiltonian Cycles**
A **Hamiltonian Cycle** in a graph is a cycle that visits each vertex **exactly
once** and returns to the starting point.
#### 🔹 Definition:
Given a graph $G = (V, E)$, a **Hamiltonian Cycle** is a cycle that passes through
every vertex once and returns to the start. If such a cycle exists, the graph is
said to be **Hamiltonian**.
#### 🔹 Properties:
* Each vertex appears **once** in the cycle.
* The cycle is **closed** (i.e., it ends at the starting vertex).
* Used in **routing**, **circuit design**, and **path optimization**.
#### 🔹 Example:
Graph:
```
A --- B
| |
D --- C
```
One Hamiltonian Cycle: A → B → C → D → A
#### 🔹 Algorithm (Backtracking-based):
```pseudo
1. Start at any vertex (say v).
2. Try all vertices as the next node and check:
- Not already visited
- Edge exists from current node to candidate node
3. If all vertices are visited and last connects to first → cycle.
4. Else backtrack and try another path.
```
#### 🔹 Applications:
* Travelling Salesman Problem (TSP)
* Network routing
* Genome sequencing
✅ This answer includes definition, properties, example, algorithm outline, and
applications — well-justified for 6 marks.
---
### ✅ 2. **Explain Tree Vertex Splitting**
**Tree Vertex Splitting** is a method to reduce the **degree** of a vertex by
splitting it into multiple vertices, maintaining connectivity.
#### 🔹 Why is it needed?
In applications like **optimal storage on tapes**, some systems have restrictions
like max 2 or 3 edges per vertex. To meet such constraints, we use vertex
splitting.
#### 🔹 Example:
Original Tree:
```
A
/ | \
B C D
```
Max allowed degree = 2 → Split A into A1 and A2:
```
A1
/ \
B A2
/ \
C D
```
Now, all vertices satisfy the degree constraint.
#### 🔹 Applications:
* Storage optimization
* Routing networks
* Reducing complexity in trees
✅ Clear justification with transformation, example, and practical relevance.
---
### ✅ 3. **Explain Multistage Graph**
A **Multistage Graph** is a directed, weighted graph split into **multiple levels
(stages)**. Each edge connects a vertex in stage $i$ to stage $i+1$.
#### 🔹 Purpose:
Used to solve **shortest path** or **minimum cost path** problems via **dynamic
programming**.
#### 🔹 Structure:
* Graph has **k stages**
* Path starts from stage 0 and ends at stage $k$
* Edges exist **only** from one stage to the next
#### 🔹 Backward Approach Algorithm:
Let $cost[i]$ = min cost from node $i$ to destination
```pseudo
For each vertex in reverse order:
cost[i] = min(cost[j] + weight(i, j)) for all j adjacent to i
```
#### 🔹 Example:
Graph:
```
Stage 0: S
Stage 1: A, B
Stage 2: C, D
Stage 3: T
Edges:
S→A(1), S→B(2)
A→C(3), B→C(1), B→D(2)
C→T(4), D→T(1)
```
Shortest Path: S → B → D → T → Cost = 2 + 2 + 1 = **5**
✅ Includes graph concept, algorithm, and example with calculation.
---
### ✅ 4. **Write/Apply Quicksort Algorithm**
**QuickSort** is a highly efficient **divide and conquer** algorithm used for
sorting.
#### 🔹 Steps:
1. Select a **pivot** element.
2. Partition the array such that:
* Elements < pivot go to left
* Elements > pivot go to right
3. Recursively apply the same process.
#### 🔹 Algorithm:
```pseudo
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], arr[j]
swap arr[i+1], arr[high]
return i+1
```
#### 🔹 Example:
Sort \[45, 23, 42, 8, 56]
1. Pivot = 56 → all elements < pivot → sorted recursively.
2. Further pivots: 8, 23, etc.
#### 🔹 Time Complexity:
* Best / Avg: O(n log n)
* Worst (when array is already sorted): O(n²)
✅ Full algorithm with working example and time complexity.
---
### ✅ 5. **Explain NP-Hard and NP-Complete Problems**
#### 🔹 NP (Nondeterministic Polynomial Time):
Problems whose **solutions can be verified in polynomial time**.
#### 🔹 NP-Complete:
1. Belongs to NP
2. Every NP problem is reducible to it in polynomial time
#### 🔹 NP-Hard:
1. As hard as NP-Complete
2. Not necessarily in NP
3. **May not be verifiable in polynomial time**
#### 🔹 Diagram:
```
P ⊆ NP ⊆ NP-Complete ⊆ NP-Hard
```
#### 🔹 Examples:
* **NP-Complete**: 3-SAT, Subset Sum
* **NP-Hard**: Halting Problem, TSP (optimization)
#### 🔹 Importance:
These problems help understand **computational limits** and **efficiency**.
✅ Includes distinctions, properties, examples, and Venn diagram structure.
---
### ✅ 6. **Explain String Editing Problem**
The **String Editing Problem** (or Edit Distance) finds the **minimum operations**
needed to convert one string into another.
#### 🔹 Allowed Operations:
* Insertion
* Deletion
* Substitution
#### 🔹 Dynamic Programming Solution:
Let $dp[i][j]$ = edit distance between first $i$ characters of X and $j$ of Y
```pseudo
if X[i-1] == Y[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(
dp[i-1][j], // deletion
dp[i][j-1], // insertion
dp[i-1][j-1] // substitution
)
```
#### 🔹 Example:
X = “kitten”, Y = “sitting” → Output = 3
(kitten → sitten → sittin → sitting)
✅ Clearly explained with algorithm, logic, and example.
---
### ✅ 7. **Draw/Explain Comparison Tree**
A **Comparison Tree** is a binary decision tree used to analyze **comparison-based
algorithms**, such as sorting.
#### 🔹 Structure:
* Internal nodes: comparisons (e.g., a < b)
* Leaves: sorted permutations
* Depth of tree = number of comparisons
#### 🔹 Example (3 elements: A, B, C):
```
A < B
/ \
A<B<C B<C?
/ \ \
ACB ABC CBA
```
Total permutations: 3! = 6 → Tree has 6 leaves
#### 🔹 Lower Bound:
Minimum comparisons = log₂(n!)
For n = 3, log₂(6) ≈ 2.58 → minimum 3 comparisons
✅ Diagram + theoretical explanation with implications in sorting.
---
### ✅ 8. **Write Short Notes on Space Complexity**
**Space Complexity** is the amount of **memory used** by an algorithm as a function
of input size.
#### 🔹 Components:
1. **Fixed Space** (constants, program code)
2. **Input Space**
3. **Auxiliary Space** (temporary variables)
4. **Recursion Stack** (for recursive functions)
#### 🔹 Example:
```cpp
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n-1);
}
```
* Input: n
* Auxiliary: constant
* Recursion stack: O(n)
Total Space: O(n)
#### 🔹 Importance:
* Useful for **embedded systems**
* Helps reduce **memory usage** in large applications
✅ A complete explanation with breakdown and real code example.
---
### ✅ 9. **Explain Depth First Search (DFS)**
DFS is a **graph traversal** technique that explores a branch fully before moving
to the next one.
#### 🔹 Mechanism:
* Uses **stack** (or recursion)
* Starts from a node, marks it visited, and recursively visits unvisited adjacent
nodes.
#### 🔹 DFS Algorithm:
```pseudo
DFS(vertex v):
mark v as visited
for each neighbor u of v:
if u is not visited:
DFS(u)
```
#### 🔹 Example Graph:
```
A — B — C
|
D — E
```
Start from A → Order: A → B → C → D → E (depending on graph representation)
#### 🔹 Applications:
* Cycle detection
* Topological sort
* Connected components
✅ Full explanation with algorithm and example.
---
Absolutely! Below are the **fully developed, 10-mark answers** for your repeated
questions — detailed with explanations, step-by-step procedures, algorithms, and
examples. These are written to be exam-ready and justify the full 10 marks.
---
### ✅ 1. **Explain Strassen’s Matrix Multiplication**
Strassen’s algorithm is an optimized matrix multiplication method that reduces the
number of **multiplications** required compared to the standard approach.
---
#### 🔹 Traditional Matrix Multiplication:
Given two $n \times n$ matrices A and B, standard multiplication takes:
$$
T(n) = O(n^3)
$$
---
#### 🔹 Strassen’s Idea:
Divide each matrix into 4 submatrices of size $\frac{n}{2} \times \frac{n}{2}$ and
compute **7 matrix multiplications** (instead of 8).
---
#### 🔹 Recursive Steps:
Let A and B be:
```
A = |A11 A12| B = |B11 B12|
|A21 A22| |B21 B22|
```
Compute:
```
M1 = (A11 + A22)(B11 + B22)
M2 = (A21 + A22)(B11)
M3 = (A11)(B12 - B22)
M4 = (A22)(B21 - B11)
M5 = (A11 + A12)(B22)
M6 = (A21 - A11)(B11 + B12)
M7 = (A12 - A22)(B21 + B22)
```
Then:
```
C11 = M1 + M4 - M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 - M2 + M3 + M6
```
---
#### 🔹 Time Complexity:
$$
T(n) = 7T(n/2) + O(n^2) \Rightarrow T(n) = O(n^{\log_2 7}) \approx O(n^{2.81})
$$
---
#### 🔹 Example:
Multiply:
$$
A = \begin{bmatrix} 1 & 3 \\ 7 & 5 \end{bmatrix}, \quad
B = \begin{bmatrix} 6 & 8 \\ 4 & 2 \end{bmatrix}
$$
Use the above formulas to compute.
✅ **Justification**: Covers algorithm, recursion, time analysis, and example.
---
### ✅ 2. **Describe 0/1 Knapsack Problem**
The **0/1 Knapsack Problem** is a classic **optimization** problem using **dynamic
programming**.
---
#### 🔹 Problem Statement:
Given:
* $n$ items with weights $w_1, w_2, ..., w_n$
* Corresponding profits $p_1, p_2, ..., p_n$
* Knapsack capacity = W
Choose a subset of items such that:
* Total weight ≤ W
* Total profit is maximized
Each item is either taken (1) or not taken (0).
---
#### 🔹 Dynamic Programming Table:
Let $K[i][w]$ be max profit for first $i$ items with capacity $w$.
$$
K[i][w] =
\begin{cases}
0 & \text{if } i=0 \text{ or } w=0 \\
K[i-1][w] & \text{if } w_i > w \\
\max(K[i-1][w], p_i + K[i-1][w - w_i]) & \text{otherwise}
\end{cases}
$$
---
#### 🔹 Example:
Items:
| Item | Weight | Profit |
| ---- | ------ | ------ |
| 1 | 1 | 1 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
| 4 | 5 | 7 |
Capacity $W = 7$
Optimal solution: Items 2 and 4 → Total Profit = 11
✅ **Justification**: Includes problem setup, DP logic, and example.
---
### ✅ 3. **Write Backtracking for Sum of Subset Problem**
Backtracking is used to find **all subsets** of a set that sum to a given number
$M$.
---
#### 🔹 Problem Statement:
Given:
* A set of positive integers $S = \{s_1, s_2, ..., s_n\}$
* A target sum $M$
Find all subsets such that sum of elements = $M$
---
#### 🔹 Backtracking Algorithm:
```pseudo
SumOfSubsets(i, weight, total):
if weight == M:
output solution
else:
for j = i to n:
if weight + s[j] ≤ M:
include s[j]
SumOfSubsets(j + 1, weight + s[j], total - s[j])
exclude s[j]
```
---
#### 🔹 Example:
Set: {10, 7, 5, 18, 12, 20, 15},
Target $M = 35$
One solution: {10, 5, 20}
Another: {15, 20}
✅ **Justification**: Clearly includes algorithm, pruning condition, and example.
---
### ✅ 4. **Use Branch and Bound for TSP Problem**
The **Travelling Salesman Problem (TSP)** aims to find the **shortest possible
route** visiting all cities once and returning to the origin.
---
#### 🔹 Branch and Bound Approach:
Use **cost matrix reduction + bounding function** to prune paths.
---
#### 🔹 Steps:
1. **Start with a reduced cost matrix**: subtract min value in rows and columns.
2. **Bound** = sum of reductions
3. **Branch**: choose a city and go deeper recursively.
4. **Prune** paths with bound > best solution found.
---
#### 🔹 Example:
Given Cost Matrix:
| | A | B | C | D |
| - | -- | -- | -- | -- |
| A | ∞ | 20 | 30 | 10 |
| B | 15 | ∞ | 16 | 4 |
| C | 3 | 5 | ∞ | 2 |
| D | 19 | 6 | 18 | ∞ |
Compute initial bound, explore branches like A→D, D→B, etc., update the cost.
✅ **Justification**: Describes bounding, reduction, traversal with example.
---
### ✅ 5. **Discuss NP-Hard and NP-Complete Classes**
---
#### 🔹 P:
Problems solvable in **polynomial time**
#### 🔹 NP:
Problems whose **solutions can be verified** in polynomial time
#### 🔹 NP-Complete:
* In NP
* Every NP problem reducible to it in polynomial time
#### 🔹 NP-Hard:
* **As hard as** NP-Complete
* Not necessarily in NP
* May not be **verifiable** in polynomial time
---
#### 🔹 Venn Diagram:
```
P ⊆ NP ⊆ NP-Complete ⊆ NP-Hard
```
---
#### 🔹 Examples:
* **NP-Complete**: 3-SAT, Subset Sum
* **NP-Hard**: Halting Problem, TSP (optimization)
---
#### 🔹 Importance:
Understanding these helps in:
* Complexity theory
* Cryptography
* Algorithm design
✅ Includes class definitions, hierarchy, examples, and importance.
---
### ✅ 6. **Apply Divide and Conquer with Example**
---
#### 🔹 Definition:
**Divide and Conquer** splits a problem into subproblems, solves each recursively,
and combines the results.
---
#### 🔹 Steps:
1. **Divide**: split input
2. **Conquer**: recursively solve
3. **Combine**: merge results
---
#### 🔹 Example: Merge Sort
```pseudo
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)
```
---
#### 🔹 Merge Sort Example:
Input: \[38, 27, 43, 3, 9, 82, 10]
Divide → Sort each half → Merge back
---
#### 🔹 Time Complexity:
$$
T(n) = 2T(n/2) + O(n) = O(n \log n)
$$
✅ Strong example with logic, application, and complexity.
---
### ✅ 7. **Write Merge Sort Algorithm**
---
#### 🔹 Merge Sort:
A **stable**, comparison-based sorting algorithm using **divide and conquer**.
---
#### 🔹 Algorithm:
```pseudo
MergeSort(A, l, r):
if l < r:
m = (l + r) / 2
MergeSort(A, l, m)
MergeSort(A, m+1, r)
Merge(A, l, m, r)
Merge(A, l, m, r):
create left and right subarrays
merge while comparing
```
---
#### 🔹 Example:
Input: \[45, 23, 42, 8, 56]
1. Divide → \[45, 23], \[42, 8, 56]
2. Recursively sort
3. Merge into \[8, 23, 42, 45, 56]
---
#### 🔹 Time Complexity:
* Best, Average, Worst = O(n log n)
✅ Justification: includes complete algorithm, example, and complexity.
---
### ✅ 8. **Explain Job Sequencing with Deadlines**
---
#### 🔹 Problem:
Schedule jobs to maximize **profit**, where:
* Each job $j_i$ has deadline $d_i$
* And profit $p_i$
Only **one job** can be scheduled per unit time.
---
#### 🔹 Greedy Approach:
1. Sort jobs in **descending profit**
2. For each job, schedule in latest available slot before deadline
3. If no slot, skip job
---
#### 🔹 Example:
| Job | Profit | Deadline |
| --- | ------ | -------- |
| A | 100 | 2 |
| B | 19 | 1 |
| C | 27 | 2 |
| D | 25 | 1 |
| E | 15 | 3 |
Scheduled Order: A, C, E → Max Profit = 142
✅ Includes greedy algorithm, scheduling logic, and example.
---
### ✅ 9. **Write Dijkstra’s Algorithm or All-Pairs Shortest Path**
---
#### 🔹 Dijkstra’s Algorithm:
Finds the **shortest path** from a source node to all other nodes in a **weighted
graph** (non-negative edges).
---
#### 🔹 Algorithm:
```pseudo
1. Set dist[source] = 0, others = ∞
2. Mark all vertices unvisited
3. Select unvisited node with smallest dist
4. For each neighbor, update dist if new path is shorter
5. Repeat until all nodes visited
```
---
#### 🔹 Example:
Graph:
```
A —1— B —2— C
| |
4 3
| |
D —1— E —5— F
```
Source: A
Find shortest paths to all vertices.
---
#### 🔹 Complexity:
* Using min-heap: O((V + E) log V)
✅ Justified with full algorithm, explanation, and practical usage.
---
Let me know if you'd like this compiled as a **PDF** or **printable notes**.
