1What is the primary objective of the n-Queens problem?
Backtracking: n-Queens Problem
Easy
A.To place queens on a chessboard such that they cover all the squares.
B.To find the shortest path for a queen to traverse the entire board.
C.To capture all queens on the chessboard using a single knight.
D.To place queens on an chessboard such that no two queens attack each other.
Correct Answer: To place queens on an chessboard such that no two queens attack each other.
Explanation:
The n-Queens problem asks to position queens on an board so that no two queens share the same row, column, or diagonal.
Incorrect! Try again.
2In the n-Queens problem, which of the following conditions constitutes an attack between two queens?
Backtracking: n-Queens Problem
Easy
A.Being in the same row, column, or diagonal.
B.Being placed on the same color square.
C.Being exactly an -shape apart like a knight.
D.Being placed in adjacent squares only.
Correct Answer: Being in the same row, column, or diagonal.
Explanation:
In chess, a queen can move any number of squares horizontally, vertically, or diagonally. Thus, they attack each other if they share a row, column, or diagonal.
Incorrect! Try again.
3Is there a valid solution for the 2-Queens problem on a chessboard?
Backtracking: n-Queens Problem
Easy
A.No, there is no valid solution.
B.Yes, there is exactly one solution.
C.Yes, there are two solutions.
D.Yes, but only if they are of different colors.
Correct Answer: No, there is no valid solution.
Explanation:
For a board, placing a queen in any square will immediately attack all other squares on the board, making it impossible to place a second queen safely.
Incorrect! Try again.
4What is a Hamiltonian Circuit in a graph?
Hamiltonian Circuit Problem
Easy
A.A cycle that visits every vertex exactly once and returns to the starting vertex.
B.A tree that connects all the vertices in a graph with minimum total edge weight.
C.The shortest path between a designated source and destination.
D.A path that visits every edge exactly once and returns to the starting vertex.
Correct Answer: A cycle that visits every vertex exactly once and returns to the starting vertex.
Explanation:
A Hamiltonian Circuit (or cycle) is defined as a closed loop in a graph that visits every single vertex exactly once before returning to the start.
Incorrect! Try again.
5Which of the following algorithm design techniques is commonly used to find all Hamiltonian Circuits in a graph?
Hamiltonian Circuit Problem
Easy
A.Divide and Conquer
B.Greedy Method
C.Backtracking
D.Dynamic Programming
Correct Answer: Backtracking
Explanation:
Backtracking is widely used to explore all possible paths in the state-space tree to find cycles that visit every vertex exactly once.
Incorrect! Try again.
6What is the goal of the Subset-Sum Problem?
Subset-Sum Problem
Easy
A.To find a subset of a given set whose elements sum to a specified target value.
B.To find the sum of all elements in a given set.
C.To divide a set into two subsets with the maximum possible difference in sums.
D.To find the subset with the maximum possible sum.
Correct Answer: To find a subset of a given set whose elements sum to a specified target value.
Explanation:
The Subset-Sum problem asks whether there is a subset of a given set of positive integers that adds up exactly to a given target sum .
Incorrect! Try again.
7In a backtracking solution for the Subset-Sum problem, what represents a state in the state-space tree?
Subset-Sum Problem
Easy
A.The total number of sets possible.
B.A sorted array of the elements.
C.The maximum element in the subset.
D.A sequence of decisions on whether to include or exclude specific items.
Correct Answer: A sequence of decisions on whether to include or exclude specific items.
Explanation:
The state-space tree for the Subset-Sum problem is built by making binary decisions at each level: either include the current item in the subset or exclude it.
Incorrect! Try again.
8What is the primary difference between Branch-and-Bound and Backtracking?
Branch-and-Bound: Assignment Problem
Easy
A.There is no difference; they are exactly the same.
B.Branch-and-Bound is generally used for optimization problems and uses a bounding function, while Backtracking is used for finding all solutions.
C.Backtracking is only for graphs, while Branch-and-Bound is only for trees.
D.Backtracking uses a bounding function, while Branch-and-Bound does not.
Correct Answer: Branch-and-Bound is generally used for optimization problems and uses a bounding function, while Backtracking is used for finding all solutions.
Explanation:
Branch-and-Bound calculates a bound at each node to prune parts of the search space that cannot yield a better solution than the current best, making it ideal for optimization problems.
Incorrect! Try again.
9What is the objective of the Assignment Problem?
Branch-and-Bound: Assignment Problem
Easy
A.To maximize the time taken to complete all tasks.
B.To assign as many jobs as possible to a single worker.
C.To assign jobs to workers such that the total cost is minimized.
D.To assign workers to jobs such that every worker gets at least two jobs.
Correct Answer: To assign jobs to workers such that the total cost is minimized.
Explanation:
The Assignment Problem deals with optimally matching agents (workers) to tasks (jobs) on a one-to-one basis to minimize the overall cost.
Incorrect! Try again.
10In the context of Branch-and-Bound, which version of the Knapsack problem is typically solved?
Knapsack Problem
Easy
A.Fractional Knapsack Problem
B.0/1 Knapsack Problem
C.Unbounded Knapsack Problem
D.Multiple Knapsack Problem
Correct Answer: 0/1 Knapsack Problem
Explanation:
The 0/1 Knapsack problem is an NP-hard optimization problem commonly solved using Branch-and-Bound to explore the inclusion or exclusion of items while pruning suboptimal paths.
Incorrect! Try again.
11For solving the 0/1 Knapsack problem using Branch-and-Bound, how is the upper bound typically calculated for a node?
Knapsack Problem
Easy
A.By adding the weights of all items without checking capacity.
B.By taking the average profit of all items.
C.By assuming all remaining items have zero weight.
D.By solving the remaining capacity using the Fractional Knapsack greedy approach.
Correct Answer: By solving the remaining capacity using the Fractional Knapsack greedy approach.
Explanation:
To get a tight upper bound for the 0/1 Knapsack problem in a branch-and-bound tree, the algorithm temporarily relaxes the binary constraint and uses the greedy fractional knapsack approach for the remaining capacity.
Incorrect! Try again.
12What is the objective of the Traveling Salesman Problem (TSP)?
Traveling Salesman Problem
Easy
A.To visit every city exactly once and return to the starting city with the minimum total cost.
B.To visit as many cities as possible within a given distance limit.
C.To find the shortest path between two specific cities.
D.To find a path that uses the minimum number of edges regardless of weight.
Correct Answer: To visit every city exactly once and return to the starting city with the minimum total cost.
Explanation:
TSP requires finding a Hamiltonian cycle of minimum total weight in a complete weighted graph.
Incorrect! Try again.
13Which of the following problems is the Traveling Salesman Problem most closely related to conceptually?
Traveling Salesman Problem
Easy
A.Hamiltonian Circuit
B.Knapsack Problem
C.Graph Coloring
D.Minimum Spanning Tree
Correct Answer: Hamiltonian Circuit
Explanation:
TSP is essentially the optimization version of the Hamiltonian Circuit problem, where the goal is to find a Hamiltonian circuit with the smallest total edge weight.
Incorrect! Try again.
14What defines a Vertex Cover in an undirected graph?
Vertex-Cover Problem and Set-Covering Problem
Easy
A.A set of edges that connects all vertices.
B.A set of vertices such that every edge in the graph is incident to at least one vertex in the set.
C.The maximum number of vertices that share no edges.
D.A cycle that covers all the vertices in the graph.
Correct Answer: A set of vertices such that every edge in the graph is incident to at least one vertex in the set.
Explanation:
A vertex cover is a subset of vertices such that for every edge in the graph, either or .
Incorrect! Try again.
15The standard approximation algorithm for the Vertex-Cover problem achieves what approximation ratio?
Vertex-Cover Problem and Set-Covering Problem
Easy
A.
B.2
C.1.5
D.3
Correct Answer: 2
Explanation:
The classic greedy approximation algorithm for Vertex Cover (picking an arbitrary edge and adding both endpoints) guarantees a solution that is at most 2 times the size of the optimal vertex cover.
Incorrect! Try again.
16What is the goal of the Set-Covering Problem?
Vertex-Cover Problem and Set-Covering Problem
Easy
A.To find the minimum number of subsets whose union contains all elements of the universe.
B.To cover a graph with the minimum number of edges.
C.To sort a set of elements into ascending order.
D.To find the maximum number of disjoint sets in a collection.
Correct Answer: To find the minimum number of subsets whose union contains all elements of the universe.
Explanation:
In the Set-Covering problem, you are given a universe of elements and a collection of subsets. The goal is to select the fewest subsets that together contain every element in the universe.
Incorrect! Try again.
17Which common heuristic is used to approximate the Set-Covering problem?
Vertex-Cover Problem and Set-Covering Problem
Easy
A.Always pick the subset with the fewest elements.
B.Divide and Conquer to split the universe in half.
C.Dynamic Programming to test all possible subset combinations.
D.A Greedy approach that iteratively picks the subset covering the most remaining uncovered elements.
Correct Answer: A Greedy approach that iteratively picks the subset covering the most remaining uncovered elements.
Explanation:
The greedy approximation algorithm for Set Cover repeatedly selects the set that covers the maximum number of currently uncovered elements.
Incorrect! Try again.
18What is the objective of the 1D Bin Packing Problem?
Bin Packing Problems
Easy
A.To maximize the value of items placed in a single bin.
B.To pack a set of items into a single bin of unlimited capacity.
C.To pack items into bins such that every bin has the exact same weight.
D.To minimize the number of bins of fixed capacity required to hold a set of items.
Correct Answer: To minimize the number of bins of fixed capacity required to hold a set of items.
Explanation:
The Bin Packing problem seeks to distribute a collection of items with given sizes into the minimum possible number of bins, where each bin has a fixed capacity.
Incorrect! Try again.
19Which of the following is a standard approximation algorithm for the Bin Packing Problem?
Bin Packing Problems
Easy
A.Dijkstra's Algorithm
B.Kruskal's Algorithm
C.First Fit
D.Floyd-Warshall Algorithm
Correct Answer: First Fit
Explanation:
First Fit is a simple heuristic for Bin Packing where each item is placed into the first bin that has enough remaining capacity to hold it.
Incorrect! Try again.
20In the context of the Bin Packing Problem, what does the 'Next Fit' heuristic do?
Bin Packing Problems
Easy
A.It searches all previously opened bins for the tightest fit.
B.It tries to place the item in the bin with the most empty space.
C.It places the item in the current bin if it fits; otherwise, it closes the current bin and opens a new one.
D.It sorts the items in decreasing order before packing them.
Correct Answer: It places the item in the current bin if it fits; otherwise, it closes the current bin and opens a new one.
Explanation:
Next Fit is an online algorithm that only keeps the most recently opened bin active. If the current item doesn't fit, it starts a new bin and never looks back at the older ones.
Incorrect! Try again.
21In the n-Queens problem solved using backtracking, how is the diagonal conflict checked for two queens placed at positions and ?
Backtracking: n-Queens Problem
Medium
A.
B.
C. or
D. or
Correct Answer:
Explanation:
Two queens share a diagonal if the absolute difference between their row indices equals the absolute difference between their column indices, which is mathematically represented as .
Incorrect! Try again.
22What is the structure of the state-space tree for the 4-Queens problem if we restrict each row to contain exactly one queen?
Backtracking: n-Queens Problem
Medium
A.A 4-ary tree of depth 4
B.A tree where each node has varying children based on column availability
C.A complete graph of 4 vertices
D.A binary tree of depth 4
Correct Answer: A 4-ary tree of depth 4
Explanation:
If we place one queen per row, the first queen has 4 column choices, the second has 4 (ignoring constraints temporarily to define the full state space), making it a 4-ary tree of depth 4 before pruning.
Incorrect! Try again.
23When applying backtracking to find a Hamiltonian Circuit starting at vertex , when does the algorithm successfully record a solution?
Backtracking: Hamiltonian Circuit Problem
Medium
A.When all edges of the graph have been traversed exactly once
B.When a cycle of any length is detected
C.When the path contains all vertices and there is an edge from the last vertex to
D.When the path reaches length
Correct Answer: When the path contains all vertices and there is an edge from the last vertex to
Explanation:
A Hamiltonian Circuit must visit every vertex exactly once and return to the starting vertex. Thus, a solution is found when the partial path has distinct vertices and an edge exists from the -th vertex back to .
Incorrect! Try again.
24During the backtracking search for a Hamiltonian Circuit, which condition causes the algorithm to backtrack from the current vertex ?
Backtracking: Hamiltonian Circuit Problem
Medium
A.Vertex has a degree greater than 2
B.No unvisited adjacent vertex can be found from
C.The graph contains a bipartite subgraph
D.Vertex is adjacent to
Correct Answer: No unvisited adjacent vertex can be found from
Explanation:
The algorithm backtracks when it reaches a dead end, meaning there are no adjacent vertices from the current vertex that have not already been included in the current path.
Incorrect! Try again.
25Let be the total sum of all elements, and be the target sum. If the elements are sorted in non-decreasing order, which condition justifies pruning the state space tree at node with current sum ?
Backtracking: Subset-Sum Problem
Medium
A.
B.Both A and B
C.Neither A nor B
D.
Correct Answer: Both A and B
Explanation:
Pruning occurs if adding the next smallest element exceeds the target (), or if adding all remaining elements to the current sum still falls short of the target ().
Incorrect! Try again.
26If the subset-sum problem state space is represented as a binary tree, what does a left child and a right child typically represent at depth ?
Backtracking: Subset-Sum Problem
Medium
A.Left child: substitute , Right child: add
B.Left child: stop search, Right child: continue search
C.Left child: include , Right child: exclude
D.Left child: smaller weight, Right child: larger weight
Correct Answer: Left child: include , Right child: exclude
Explanation:
In a binary state-space tree for the subset-sum problem, branches represent decisions: moving left typically means including the -th element in the subset, and moving right means excluding it.
Incorrect! Try again.
27In the branch-and-bound approach to the Assignment Problem, how is the lower bound for a given node typically calculated?
Branch-and-Bound: Assignment Problem
Medium
A.By computing the sum of the diagonal elements
B.By using the Hungarian algorithm to solve the subproblem exactly
C.By subtracting the smallest element in each row and each column to reduce the cost matrix
D.By finding the maximum element in each row and column
Correct Answer: By subtracting the smallest element in each row and each column to reduce the cost matrix
Explanation:
The lower bound is computed by reducing the cost matrix. This involves subtracting the row minimums from each row, and then column minimums from each column, and summing these minimums.
Incorrect! Try again.
28Consider an assignment problem matrix. If assigning worker 1 to job 1 results in a reduced matrix with a further reduction cost of , and the initial reduction cost was , what is the lower bound of the node representing this assignment?
Branch-and-Bound: Assignment Problem
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The lower bound for a child node is calculated as: Bound of parent () + cost of the assigned edge ( in the parent's reduced matrix) + the cost to further reduce the new child matrix ().
Incorrect! Try again.
29In the branch-and-bound solution for the 0/1 Knapsack Problem, how is the upper bound typically calculated for a specific node to prune branches?
Branch-and-Bound: Knapsack Problem
Medium
A.By taking the maximum value-to-weight ratio item and multiplying it by remaining capacity
B.By discarding all items that exceed the remaining capacity
C.By solving the remaining items using the Fractional Knapsack greedy approach
D.By summing the values of all remaining items
Correct Answer: By solving the remaining items using the Fractional Knapsack greedy approach
Explanation:
The Fractional Knapsack problem provides an optimal upper bound for the 0/1 Knapsack problem because allowing fractions can only increase or equal the maximum possible value, providing a strict upper limit.
Incorrect! Try again.
30When using Best-First Search (Branch-and-Bound) for a maximization problem like 0/1 Knapsack, which node is selected next from the priority queue?
Branch-and-Bound: Knapsack Problem
Medium
A.The node with the lowest lower bound
B.The node with the highest upper bound
C.The node with the smallest weight
D.The node at the deepest level of the tree
Correct Answer: The node with the highest upper bound
Explanation:
In a maximization problem, best-first search selects the node with the highest potential (highest upper bound) to explore first, as it is most likely to lead to the optimal solution.
Incorrect! Try again.
31In the Branch-and-Bound algorithm for TSP using the reduced cost matrix, what constraint must be added when an edge is included in the path?
Branch-and-Bound: Traveling Salesman Problem
Medium
A.Set the entire matrix to zero except for row and column
B.Subtract the cost of from all other matrix elements
C.Set row and column to infinity
D.Set row and column to infinity, and set the reverse edge to infinity
Correct Answer: Set row and column to infinity, and set the reverse edge to infinity
Explanation:
When edge is chosen, the salesman leaves city and enters city . To prevent revisiting, row and column are set to infinity. The reverse edge is also set to infinity to prevent premature subtours.
Incorrect! Try again.
32For a complete graph with vertices, what is the maximum number of leaves in the state-space tree for the Traveling Salesman Problem if we fix the starting city?
Branch-and-Bound: Traveling Salesman Problem
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
Fixing the starting city leaves cities to visit. The number of possible distinct tours (permutations of the remaining cities) is .
Incorrect! Try again.
33Consider the 2-approximation algorithm for the Vertex Cover problem that picks an arbitrary edge, adds both endpoints to the cover, and removes all incident edges. Why is the approximation ratio exactly 2?
Vertex-Cover Problem and Set-Covering Problem
Medium
A.Because it selects exactly two vertices for every edge in the graph
B.Because the graph must be an Eulerian circuit
C.Because the optimal cover must contain at least one vertex from each chosen edge, while the algorithm picks both
D.Because it uses a bipartite matching algorithm that doubles the edges
Correct Answer: Because the optimal cover must contain at least one vertex from each chosen edge, while the algorithm picks both
Explanation:
The algorithm finds a maximal matching. Any valid vertex cover must include at least one endpoint of every edge in this matching. By picking both endpoints, the algorithm selects at most twice the optimal number of vertices.
Incorrect! Try again.
34The greedy approximation algorithm for the Set-Covering problem selects the set that covers the most uncovered elements at each step. What is its approximation ratio for a universe of size ?
Vertex-Cover Problem and Set-Covering Problem
Medium
A.
B.
C.
D.
Correct Answer:
Explanation:
The greedy algorithm for Set-Covering yields an approximation ratio bounded by the -th harmonic number , which is .
Incorrect! Try again.
35Which of the following describes the relationship between a Minimum Spanning Tree (MST) and a Metric TSP tour?
Branch-and-Bound: Traveling Salesman Problem
Medium
A.The optimal TSP tour has exactly twice the weight of the MST
B.The weight of the MST is an upper bound on the optimal TSP tour weight
C.The weight of the MST is a lower bound on the optimal TSP tour weight
D.The MST always contains the optimal TSP tour as a subgraph
Correct Answer: The weight of the MST is a lower bound on the optimal TSP tour weight
Explanation:
If we remove one edge from an optimal TSP tour, we get a spanning tree. Therefore, the weight of the Minimum Spanning Tree is strictly less than or equal to the weight of the optimal TSP tour, serving as a lower bound.
Incorrect! Try again.
36In the context of the 1D Bin Packing Problem, what is the competitive ratio of the First-Fit algorithm compared to the optimal offline solution?
Bin Packing Problems
Medium
A.At most 2
B.Exactly 1
C.At most
D.At most
Correct Answer: At most
Explanation:
It has been proven that the First-Fit heuristic uses at most bins, making its asymptotic approximation ratio 1.7.
Incorrect! Try again.
37How does the First-Fit Decreasing (FFD) heuristic improve upon the standard First-Fit algorithm for Bin Packing?
Bin Packing Problems
Medium
A.It sorts the items in non-increasing order of their sizes before packing
B.It allows items to be split across multiple bins
C.It processes items online without needing to see all items in advance
D.It sorts the bins by their remaining capacity
Correct Answer: It sorts the items in non-increasing order of their sizes before packing
Explanation:
First-Fit Decreasing (FFD) is an offline algorithm that sorts items from largest to smallest before applying the First-Fit strategy. This prevents small items from taking up space needed by larger items later, improving the approximation ratio to .
Incorrect! Try again.
38Which of the following statements is true regarding the Vertex-Cover and Set-Covering problems?
Vertex-Cover Problem and Set-Covering Problem
Medium
A.Both problems can be solved in polynomial time
B.Vertex-Cover is a special case of the Set-Covering problem
C.Set-Covering is a special case of the Vertex-Cover problem
D.Neither problem admits any approximation algorithm
Correct Answer: Vertex-Cover is a special case of the Set-Covering problem
Explanation:
Vertex-Cover can be modeled as a Set-Covering problem where the universe is the set of all edges, and each set corresponds to a vertex containing all its incident edges.
Incorrect! Try again.
39Consider a 0/1 Knapsack problem with a capacity of 10. You are at a node where current weight is 6 and current profit is 40. The remaining items are Item 3 (Weight 5, Profit 30) and Item 4 (Weight 4, Profit 20). Using the fractional knapsack bound, what is the upper bound of this node?
Branch-and-Bound: Knapsack Problem
Medium
A.$90$
B.$64$
C.$70$
D.$40$
Correct Answer: $64$
Explanation:
Remaining capacity = . Next best item is Item 3 (ratio = ). Item 4 ratio = . We take of Item 3. Profit = .
Incorrect! Try again.
40The Next-Fit (NF) heuristic for Bin Packing maintains only one open bin at a time. What is the asymptotic approximation ratio of Next-Fit?
Bin Packing Problems
Medium
A.2.5
B.2
C.1.5
D.1
Correct Answer: 2
Explanation:
Next-Fit closes a bin as soon as an item does not fit and never looks back. It can be shown that , so its asymptotic approximation ratio is exactly 2.
Incorrect! Try again.
41In the -Queens problem solved using backtracking, how many distinct valid configurations exist for , considering all symmetries as separate solutions?
Backtracking: n-Queens Problem
Hard
A.14
B.6
C.10
D.4
Correct Answer: 4
Explanation:
For the $6$-Queens problem, there are exactly 4 distinct valid arrangements. This is a known result for , contrasting with which has 92.
Incorrect! Try again.
42Which of the following bounding functions correctly prunes the search tree in a bitwise backtracking solution for the -Queens problem?
Backtracking: n-Queens Problem
Hard
A.Checking if left_diagonal & right_diagonal & column equals $0$.
B.Checking if left_diagonal | right_diagonal | column contains a $1$ at the candidate position.
C.Checking if left_diagonal + right_diagonal == column.
D.Checking if left_diagonal ^ right_diagonal ^ column is $0$ at the candidate position.
Correct Answer: Checking if left_diagonal | right_diagonal | column contains a $1$ at the candidate position.
Explanation:
In bitwise backtracking, a bitwise OR of the attacked diagonals and columns identifies all unsafe positions. A $1$ at a candidate bit position implies the position is under attack.
Incorrect! Try again.
43Consider a bipartite graph where $|U|
eq |V|G$?
Backtracking: Hamiltonian Circuit Problem
Hard
A.The backtracking algorithm will always find a circuit in time.
B.The problem is solvable in polynomial time if the graph is planar.
C.A Hamiltonian Circuit exists if the minimum degree is at least 3.
D.A Hamiltonian Circuit cannot exist.
Correct Answer: A Hamiltonian Circuit cannot exist.
Explanation:
A bipartite graph can only have a Hamiltonian cycle if the two partitions have the exact same number of vertices, because any cycle must alternate between the two sets.
Incorrect! Try again.
44When applying backtracking to find a Hamiltonian cycle in a dense graph, what is the theoretical maximum depth of the state space tree?
Backtracking: Hamiltonian Circuit Problem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The maximum depth of the state space tree is equal to the number of vertices , as each level of the tree corresponds to adding a new vertex to the path.
Incorrect! Try again.
45In the Subset-Sum problem for a set of elements sorted in ascending order, let be the current sum and be the sum of remaining elements. Which of the following bounding conditions strictly prunes the search space efficiently?
Backtracking: Subset-Sum Problem
Hard
A. or
B.
C. or
D.
Correct Answer: or
Explanation:
The search can be pruned if adding the next smallest item exceeds the target sum , or if the current sum plus all remaining items is strictly less than .
Incorrect! Try again.
46Given the set where , how many nodes are explored by the standard backtracking algorithm (with optimal pruning) to find the subset sum ?
Backtracking: Subset-Sum Problem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
Because the weights are powers of 2, the greedy choice is always optimal and uniquely determines the subset. The pruning conditions will eliminate all branches except the single correct path, leading to nodes.
Incorrect! Try again.
47In the Branch-and-Bound approach for the Assignment Problem using the Hungarian algorithm to compute lower bounds, what is the tightest lower bound for a node in the state-space tree?
Branch-and-Bound: Assignment Problem
Hard
A.The cost of the partial assignment plus the solution to the relaxed assignment problem on the remaining matrix.
B.The sum of the minimum elements of the unassigned columns.
C.The sum of the minimum elements of the unassigned rows.
D.The cost of the partial assignment multiplied by the remaining dimension.
Correct Answer: The cost of the partial assignment plus the solution to the relaxed assignment problem on the remaining matrix.
Explanation:
The tightest bound is obtained by solving the remaining subproblem optimally (or a strong relaxation thereof), which in the assignment problem can be done by applying the Hungarian method to the unassigned submatrix.
Incorrect! Try again.
48Which of the following correctly differentiates Branch-and-Bound from Backtracking in solving the Assignment Problem?
Branch-and-Bound: Assignment Problem
Hard
A.Backtracking cannot be applied to optimization problems.
B.Backtracking computes a heuristic lower bound at each node to prune the search space.
C.Branch-and-Bound guarantees a polynomial time complexity.
D.Branch-and-Bound explores the search space using BFS or Best-First Search guided by a cost bound, whereas Backtracking uses DFS.
Correct Answer: Branch-and-Bound explores the search space using BFS or Best-First Search guided by a cost bound, whereas Backtracking uses DFS.
Explanation:
Branch-and-Bound typically utilizes Best-First Search or BFS to expand the most promising nodes based on bounding functions, whereas Backtracking inherently relies on DFS.
Incorrect! Try again.
49For the 0/1 Knapsack problem using Branch-and-Bound, let elements be sorted by descending value-to-weight ratio. How is the upper bound at a node typically calculated?
Branch-and-Bound: Knapsack Problem
Hard
A.By adding the maximum values of the remaining items irrespective of weight.
B.By taking the sum of the values of all remaining items.
C.By evaluating the remaining items using dynamic programming in time.
D.By adding the values of remaining items that fit entirely, plus the fractional value of the first item that doesn't fit.
Correct Answer: By adding the values of remaining items that fit entirely, plus the fractional value of the first item that doesn't fit.
Explanation:
The fractional knapsack solution on the remaining capacity provides a valid and easily computable upper bound for the 0/1 knapsack problem in a maximization context.
Incorrect! Try again.
50In a Best-First Branch-and-Bound approach for the 0/1 Knapsack Problem, what can cause the state-space tree to degenerate into an exhaustive search?
Branch-and-Bound: Knapsack Problem
Hard
A.When the knapsack capacity is infinitely large.
B.When all items have the same weight but different values.
C.When all items have identical value-to-weight ratios.
D.When the items are sorted in ascending order of weights.
Correct Answer: When all items have identical value-to-weight ratios.
Explanation:
If all items have the same ratio, the fractional upper bound is identical for multiple branches, failing to effectively prune the tree and causing the algorithm to explore almost all subsets.
Incorrect! Try again.
51In the Branch-and-Bound solution for the Traveling Salesman Problem (TSP), a common lower bound is computed by halving the sum of the two minimum weight edges incident to each vertex. Why is this bound mathematically valid?
Branch-and-Bound: Traveling Salesman Problem
Hard
A.Because every vertex in a TSP tour must have exactly degree 2.
B.Because the TSP tour is a collection of disjoint cycles.
C.Because it ignores the weights of edges not in the tour.
D.Because it equals the weight of the Minimum Spanning Tree.
Correct Answer: Because every vertex in a TSP tour must have exactly degree 2.
Explanation:
In any valid TSP tour, every vertex is connected by exactly two edges. The sum of the two smallest edges incident to each vertex gives a lower bound on the sum of the tour's edges, counting each edge twice.
Incorrect! Try again.
52If the cost matrix of a TSP instance satisfies the triangle inequality, how does the 1-tree relaxation bound compare to the fractional 2-factor bound?
Branch-and-Bound: Traveling Salesman Problem
Hard
A.Both bounds always equal the optimal tour cost.
B.The 1-tree bound is always strictly greater.
C.The fractional 2-factor bound is undefined for metric spaces.
D.The 1-tree bound is generally weaker or equal to the Held-Karp (fractional 2-factor) bound.
Correct Answer: The 1-tree bound is generally weaker or equal to the Held-Karp (fractional 2-factor) bound.
Explanation:
The Held-Karp lower bound (based on the fractional 2-factor or LP relaxation) is one of the tightest polynomial-time lower bounds for metric TSP, generally dominating simple 1-tree relaxations unless iterative subgradient optimization is applied to the 1-tree (which converges to the Held-Karp bound).
Incorrect! Try again.
53A standard 2-approximation algorithm for Vertex-Cover selects an arbitrary edge, adds both endpoints to the cover, and removes all incident edges. What is the worst-case tight bound of this approximation ratio?
Vertex-Cover Problem and Set-Covering Problem
Hard
A.Exactly $2$
B.Exactly $1$
C.Exactly
D.Exactly
Correct Answer: Exactly $2$
Explanation:
The algorithm finds a maximal matching. Since each edge in the matching requires at least one vertex in any valid vertex cover, taking both endpoints yields a cover at most twice the optimal size. This bound is tight for a collection of disjoint stars.
Incorrect! Try again.
54Consider the greedy approximation algorithm for the Set-Covering Problem. If the size of the optimal set cover is and the universe has elements, the greedy algorithm guarantees a solution of size at most:
Vertex-Cover Problem and Set-Covering Problem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The greedy algorithm for Set-Cover provides an approximation ratio of . Therefore, if the optimal cover size is , the greedy algorithm produces a cover of size at most .
Incorrect! Try again.
55Which of the following statements distinguishes the approximability of the Vertex-Cover problem from the Set-Covering problem?
Vertex-Cover Problem and Set-Covering Problem
Hard
A.Neither problem can be approximated within a factor of .
B.Both problems admit a Fully Polynomial Time Approximation Scheme (FPTAS).
C.Set-Cover can be approximated within a constant factor, while Vertex-Cover cannot.
D.Vertex-Cover can be approximated within a constant factor, while Set-Cover cannot be approximated within a constant factor unless .
Correct Answer: Vertex-Cover can be approximated within a constant factor, while Set-Cover cannot be approximated within a constant factor unless .
Explanation:
Vertex cover has a known 2-approximation algorithm. Set cover cannot be approximated better than unless .
Incorrect! Try again.
56In the context of the Bin Packing Problem, what is the asymptotic approximation ratio of the First Fit Decreasing (FFD) heuristic?
Bin Packing Problems
Hard
A.$2$
B.
C.
D.
Correct Answer:
Explanation:
The First Fit Decreasing (FFD) algorithm guarantees an asymptotic approximation bound of .
Incorrect! Try again.
57For the online Bin Packing problem, what is the competitive ratio of the Next Fit algorithm?
Bin Packing Problems
Hard
A.$2$
B.$1.7$ (exactly )
C.$1.5$
D.$1$
Correct Answer: $2$
Explanation:
The Next Fit algorithm has a tight competitive ratio of 2. It never requires more than bins because the sum of items in any two adjacent bins is strictly greater than 1.
Incorrect! Try again.
58Consider an instance of the Bin Packing problem where all item sizes satisfy . Which algorithm is guaranteed to produce an optimal packing?
Bin Packing Problems
Hard
A.Next Fit
B.First Fit Decreasing
C.Random Fit
D.No polynomial-time algorithm can guarantee optimality unless .
Correct Answer: No polynomial-time algorithm can guarantee optimality unless .
Explanation:
Even with sizes strictly greater than , the problem reduces to 3-Partition, which is strongly NP-hard. Thus, no polynomial-time algorithm guarantees an optimal solution.
Incorrect! Try again.
59During the execution of a Branch-and-Bound algorithm for an Assignment Problem using a reduced cost matrix for bounding, suppose a node at depth has a lower bound . If a valid assignment is completed from this node, what is the minimum cost of that assignment?
Branch-and-Bound: Assignment Problem
Hard
A.
B.
C.
D.
Correct Answer:
Explanation:
The lower bound represents the minimum possible cost to complete the assignment from the current node. Therefore, any valid complete assignment derived from this node will have a cost of at least .
Incorrect! Try again.
60If the Subset-Sum Problem is modified such that elements can be negative, which standard pruning technique in the state-space tree immediately becomes invalid?
Backtracking: Subset-Sum Problem
Hard
A.Sorting the array by absolute values.
B.Storing previously visited states to avoid redundant computation.
C.Pruning when the current sum exceeds the target sum .
D.Pruning when the remaining elements cannot bridge the gap to .
Correct Answer: Pruning when the current sum exceeds the target sum .
Explanation:
If elements can be negative, exceeding the target sum does not mean the path is invalid, because subsequent negative numbers can reduce the sum back down to .