Unit 6: Backtracking, Approximation, and Complexity Classes - Practice Quiz

1 What is the goal of the n-Queens Problem?

2 Which technique is commonly used to solve the n-Queens Problem?

3 What is a Hamiltonian circuit in a graph?

4 What does the Subset-Sum Problem ask?

5 What is the main purpose of a bound in Branch and Bound?

6 When is a node commonly pruned in Branch and Bound?

7 What is the usual objective of the Assignment Problem?

8 What is maximized in the standard Knapsack Problem?

9 In the Knapsack Problem, how many times may each item be selected?

10 What does the Traveling Salesman Problem seek?

11 Why are approximation algorithms used?

12 What does an approximation ratio describe?

13 What property must a vertex cover satisfy?

14 What is the objective of the Set-Covering Problem?

15 What is minimized in the standard Bin Packing Problem?

16 What do complexity classes generally group together?

17 What does the complexity class P contain?

18 What is a defining feature of problems in NP?

19 Which statement correctly describes an NP-Hard problem?

20 When is a decision problem called NP-Complete?

21 Queens have already been placed at positions and on a board. In which column can a queen be safely placed in row without immediately attacking either queen?

22 Each list gives the column positions of queens in rows through . Which list represents a valid solution to the -Queens problem?

23 An undirected graph has vertices and edges . Which sequence forms a Hamiltonian circuit?

24 For the set , which target cannot be obtained as the sum of a subset of ?

25 For a minimization assignment problem, a lower bound is computed by adding the minimum entry of each row while ignoring column conflicts. For the cost matrix , what is this lower bound?

26 In a minimization problem, the current best complete solution has cost . Which live node can be safely pruned based only on its lower bound?

27 Three workers must be assigned distinct jobs . Their cost matrix is . What is the minimum total assignment cost?

28 A knapsack has capacity . Items have pairs , , , and . What is the maximum obtainable value?

29 For cities , the symmetric distances are , , , , , and . Starting at , what tour is produced by the nearest-neighbor heuristic, and what is its cost?

30 A minimization algorithm has an approximation ratio of . If the optimal solution has cost , what is the largest cost guaranteed for the algorithm's solution?

31 The standard -approximation algorithm for Vertex Cover finds a maximal matching and selects both endpoints of every matched edge. If the matching contains edges, how many vertices does the algorithm select?

32 Let and let , , , and . Which sets are selected by the greedy Set-Cover algorithm?

33 Bins have capacity . How many bins does First Fit Decreasing use for items with sizes ?

34 Which relationship between standard complexity classes is known to be true?

35 A decision problem has a deterministic algorithm whose running time is . What can be concluded from this information?

36 For the Hamiltonian Circuit decision problem, which object serves as an appropriate polynomial-size certificate for a yes-instance?

37 If a problem is NP-hard, which statement follows from the definition of NP-hardness?

38 Which pair of conditions is sufficient to classify a decision problem as NP-complete?

39 Suppose is NP-complete, , and belongs to . What can be concluded about ?

40 What would follow if a deterministic polynomial-time algorithm were discovered for any one NP-complete problem?

41 In an -Queens backtracking search, queens have been placed at , , , and , where each pair denotes . Which columns are currently legal for the queen in row ?

42 Let be a simple graph with vertices. For every pair of nonadjacent vertices and , suppose . What follows from this condition?

43 An exact meet-in-the-middle algorithm solves Subset-Sum by dividing numbers into two equal-sized groups and generating all subset sums of each group. Ignoring polynomial factors, what are its typical time and space complexities?

44 A branch-and-bound algorithm minimizes an objective and currently has an incumbent solution of cost . Three live nodes have valid lower bounds , , and . If only solutions strictly better than the incumbent matter, which nodes may be pruned immediately?

45 For the assignment cost matrix what lower bound is obtained by first subtracting each row minimum and then subtracting each resulting column minimum?

46 In a knapsack branch-and-bound node, the current solution has weight and profit , while capacity is . Remaining items, ordered by profit-to-weight ratio, are . What fractional-knapsack upper bound applies to this node?

47 For metric TSP, an algorithm doubles a minimum spanning tree, takes an Euler tour, and shortcuts repeated vertices. Which inequality justifies its approximation guarantee?

48 Which statement correctly characterizes a fully polynomial-time approximation scheme for an optimization problem?

49 Let be any maximal matching in an unweighted graph, and let contain both endpoints of every edge in . Which statement is always true?

50 For weighted Vertex-Cover, consider the LP relaxation with for every edge and . If all vertices satisfying are selected, what guarantee follows?

51 For weighted Set-Cover on universe , which greedy rule and worst-case guarantee form the standard approximation algorithm?

52 Bins have capacity , and item sizes are . What are, respectively, the numbers of bins used by First-Fit Decreasing and by an optimal packing?

53 Assume . If is NP-complete under polynomial-time many-one reductions, which conclusion is necessarily valid?

54 A language has a deterministic polynomial-time verifier, and every certificate has length at most for a constant , where is the input length. Which classification follows unconditionally?

55 Suppose a decision language has polynomial-length certificates verifiable in deterministic polynomial time for every yes-instance. What can be concluded from this fact alone?

56 Which statement about an NP-hard problem under polynomial-time many-one reductions is correct?

57 A decision problem satisfies , and has a polynomial-time verifier with polynomial-length certificates. What is the strongest justified conclusion?

58 To reduce Hamiltonian Circuit on an -vertex graph to metric-free TSP decision, construct a complete graph with edge weight for edges of and weight for nonedges. Which threshold makes the reduction correct?

59 Subset-Sum has a dynamic program running in time, where is the target, yet its decision version is NP-complete. Which explanation resolves this apparent contradiction?

60 For a minimization problem, a polynomial reduction creates instances satisfying: yes-instances have , while no-instances have , for a fixed . What would a polynomial-time -approximation imply?