***UNIT 3 – Short Questions***
1. **What is the Greedy Method in algorithm design?**
The Greedy method builds a solution step-by-step by always choosing the option that seems best
(optimal) at the moment. It never revisits decisions. It works for problems with the greedy-choice
property and optimal substructure.
2. **Steps in Job Sequencing with Deadlines using a Greedy approach.**
• Sort jobs in descending order of profit.
• Create a time slot array of size equal to the max deadline.
• For each job, place it in the latest available slot before its deadline.
• If no slot is free, skip the job.
• Compute total profit.
3. **Compare Fractional Knapsack and 0/1 Knapsack.**
• Fractional Knapsack allows taking fractions of items; solved using greedy.
• 0/1 Knapsack takes whole items only; solved using dynamic programming.
• Fractional gives optimal greedy solution; 0/1 cannot be solved greedily.
4. **Explain Kruskal’s algorithm for Minimum Cost Spanning Trees.**
• Sort all edges by weight.
• Pick the smallest edge that does not form a cycle.
• Use Union–Find to detect cycles.
• Continue until (V–1) edges are selected.
5. **Dynamic programming solution for String Editing.**
Use an (m×n) DP table where DP[i][j] represents edit distance between prefixes.
Recurrence:
• If characters match → DP[i][j] = DP[i−1][j−1]
• Else → 1 + min(insert, delete, replace)
6. **Compare Dijkstra’s and Bellman-Ford algorithms.**
• Dijkstra: Works only for non-negative weights; faster.
• Bellman-Ford: Works for negative weights; detects negative cycles; slower.
---------------------------------------------------------
***UNIT 4 – Backtracking & Branch and Bound***
1. **General Method of Backtracking.**
Backtracking tries to build a solution incrementally and abandons a partial solution as soon as it is
known to be invalid (dead-end). It uses DFS with pruning.
2. **Solution approach for 8-Queens using Backtracking.**
• Place queens row by row.
• For each row, try each column.
• Check if the position is safe (no same column, diagonal).
• If safe, place queen and move to next row; else backtrack.
3. **Sum of Subsets Problem with Backtracking.**
Given a set of numbers and a target sum, backtracking tries including or excluding each number.
Pruning is done when the sum exceeds the target or no further solution is possible.
4. **Graph Coloring Problem with Backtracking.**
Assign colors to vertices ensuring adjacent vertices do not share the same color.
Try color 1…m for each vertex; if invalid, backtrack and try next color.
5. **Branch and Bound method in algorithm design.**
Branch and Bound explores solution space like a tree.
• Branch → generate child nodes
• Bound → compute lower/upper bound
• Prune nodes where bound exceeds best-known solution.
6. **Compare Branch and Bound vs Backtracking in 0/1 Knapsack.**
• Backtracking: explores all possibilities but prunes only invalid ones.
• B&B;: uses bounds (profit estimates) to prune large portions.
• B&B; is more efficient for optimization problems like knapsack.
---------------------------------------------------------
***UNIT 5 – NP Hardness & NP Completeness***
1. **What are NP Hard and NP Complete problems?**
• NP-Hard: At least as hard as NP problems; may not be in NP.
• NP-Complete: Problems that are both in NP and NP-Hard.
2. **Cook’s theorem and its significance.**
Cook proved that SAT is NP-Complete.
Significance: it established the foundation of NP-Completeness theory, enabling reductions from SAT
to other problems.
3. **Clique Decision Problem (CDP) as NP-Hard.**
Given a graph G and integer k, determine if G contains a clique of size ≥ k.
It is NP-Hard because SAT can be reduced to CDP.
4. **Chromatic Number Decision Problem (CNDP).**
Given a graph G and integer k, determine if G can be colored using ≤ k colors without adjacent vertices
sharing color.
It is NP-Complete.
5. **Traveling Salesperson Decision Problem (TSP).**
Given cities and distances, determine if a tour exists with cost ≤ K.
It is NP-Hard because Hamiltonian cycle reduces to TSP.
6. **Scheduling Identical Processors vs Job Shop Scheduling.**
• Identical processors scheduling: all processors same; simpler but NP-Hard.
• Job shop scheduling: jobs have machine-order constraints; more complex and strongly NP-Hard.