Which of the following methods is commonly used to solve the Assignment Problem?
Correct Answer: B. Hungarian Method
Explanation: The Hungarian Method is specifically designed to solve assignment problems in polynomial time. It works by: 1) Reducing the cost matrix 2) Finding the minimum number of lines to cover all zeros 3) Making additional reductions until an optimal assignment is found The algorithm has O(n³) complexity for n workers and n tasks.
The Assignment Problem is a special case of which optimization problem?
Correct Answer: B. Transportation Problem
Explanation: The Assignment Problem is a special case of the Transportation Problem where: - Number of sources (workers) equals number of destinations (tasks) - Each supply and demand equals 1 - The goal is to assign each worker to exactly one task with minimum cost Both are special cases of Linear Programming problems.
In an Assignment Problem, if there are 'n' tasks and 'n' workers, the complexity of the Hungarian Algorithm is:
Correct Answer: C. O(n³)
Explanation: The Hungarian Algorithm has a time complexity of O(n³) because: 1) It requires n iterations to reduce the matrix 2) Each iteration involves O(n²) operations to: - Subtract minimum values - Cover zeros with lines - Adjust the matrix This makes it efficient for moderate-sized problems.
Which of the following is TRUE about the Assignment Problem?
Correct Answer: B. It can be solved using Dynamic Programming
Explanation: Key facts about Assignment Problems: - Can be formulated as DP with O(n2ⁿ) time complexity (less efficient than Hungarian) - Can handle maximization by converting to minimization - Requires dummy rows/columns for unequal agents/tasks - Each agent is assigned to exactly one task The DP approach considers all possible assignments systematically.
The 0-1 Knapsack Problem can be solved using:
Correct Answer: C. Dynamic Programming
Explanation: The 0-1 Knapsack Problem is optimally solved using Dynamic Programming: - Builds a table of subproblem solutions - Stores maximum value for each weight capacity - Time complexity O(nW) where n = items, W = capacity Greedy methods don't guarantee optimality for 0-1 Knapsack (though they work for fractional version).
What is the time complexity of the dynamic programming solution to the 0-1 Knapsack Problem?
Correct Answer: B. O(nW), where n = number of items, W = capacity
Explanation: The DP solution fills a table of size n×W: - n = number of items - W = knapsack capacity Each cell takes constant time to compute This is pseudo-polynomial time - polynomial in the numeric value of W, but exponential in the number of bits needed to represent W.
Which variant of the Knapsack Problem can be solved optimally using the greedy method?
Correct Answer: C. Fractional Knapsack
Explanation: The Fractional Knapsack Problem can be optimally solved by: 1) Sorting items by value-to-weight ratio 2) Taking items in descending order of ratio 3) Taking fractions of items if needed This works because we can take partial items to fill capacity exactly. The greedy approach doesn't work for 0-1 Knapsack where items must be taken whole.
In the 0-1 Knapsack Problem, the Branch-and-Bound method improves performance by:
Correct Answer: B. Calculating lower and upper bounds to prune search space
Explanation: Branch-and-Bound for 0-1 Knapsack: 1) Builds a state space tree of possible solutions 2) Computes upper bounds using fractional knapsack (optimistic estimate) 3) Computes lower bounds from current solution (pessimistic estimate) 4) Prunes branches where upper bound < best known solution This avoids exploring unpromising paths while still guaranteeing optimality.
The time complexity of solving TSP using brute-force is:
Correct Answer: C. O(n!)
Explanation: Brute-force TSP examines all possible permutations of cities: - For n cities, there are (n-1)!/2 possible unique tours - This grows factorially with n - For 10 cities: ~181,440 tours - For 15 cities: ~43 billion tours This makes brute-force impractical for n > 10.
Which technique gives an optimal solution to the TSP but is not scalable for large inputs?
Correct Answer: C. Branch-and-Bound
Explanation: Branch-and-Bound for TSP: - Provides optimal solutions (unlike heuristics) - Uses lower bounds to prune unpromising paths - Still has exponential time complexity in worst case - Practical for n up to ~50 cities - More efficient than brute-force but still limited by problem complexity
The TSP is an example of which class of problems?
Correct Answer: B. NP-Hard
Explanation: The Traveling Salesman Problem is: 1) NP-Hard - At least as hard as the hardest problems in NP 2) The decision version ("Is there a tour shorter than k?") is NP-Complete 3) Not known to be in P (no polynomial-time solution exists) 4) The optimization version is harder than the decision version
Which of the following is NOT a heuristic for solving TSP approximately?
Correct Answer: C. Dijkstra's Algorithm
Explanation: Common TSP heuristics include: 1) Nearest Neighbor 2) Nearest/Farthest Insertion 3) Christofides (3/2-approximation for metric TSP) 4) 2-opt, 3-opt local search Dijkstra's Algorithm is for finding shortest paths in graphs, not for solving TSP. It could be used as a subroutine in some TSP algorithms but isn't a TSP heuristic itself.