## Exercises #### Sections 5.1 and 5.2 1. Apply the Backtracking algorithm for the *n*-Queens problem ([Algorithm 5.1](LiB0040.html#492)) to the problem instance in which *n* = 8, and show the actions step by step. Draw the pruned state space tree produced by this algorithm up to the point where the first solution is found. 2. Write a backtracking algorithm for the *n*-Queens problem that uses a version of procedure *expand* instead ofa version of procedure *checknode*. 3. Show that, without backtracking, 155 nodes must be checked before the first solution to the *n* = 4 instance of the *n*-Queens problem is found (in contrast to the 27 nodes in [Figure 5.4](LiB0039.html#483)). 4. Implement the Backtracking algorithm for the *n*-Queens problem ([Algorithm 5.1](LiB0040.html#492)) on your system, and run it on problem instances in which *n* = 4, 8, 10, and 12. 5. Improve the Backtracking algorithm for the *n*-Queens problem ([Algorithm 5.1](LiB0040.html#492)) by having the promising function keep track of the set of columns, of left diagonals, and of right diagonals controlled by the queens already placed. 6. Modify the Backtracking algorithm for the *n*-Queens problem ([Algorithm 5.1](LiB0040.html#492)) so that, instead of generating all possible solutions, it finds only a single solution. 7. Suppose we have a solution to the *n*-Queens problem instance in which *n* = 4. Can we extend this solution to find a solution to the problem instance in which *n* = 5? Can we then use the solutions for *n* = 4 and *n* = 5 to construct a solution to the instance in which *n* = 6 and continue this dynamic programming approach to find a solution to any instance in which *n* > 4? Justify your answer. 8. Find at least two instances of the *n*-Queens problem that have no solutions. #### Section 5.3 1. Implement [algorithm 5.3](LiB0041.html#503) (Monte Carlo estimate for the Backtracking algorithm for the *n*-Queens problem) on your system, run it 20 times on the problem instance in which *n* = 8, and find the average of the 20 estimates. 2. Modify the Backtracking algorithm for the *n*-Queens problem ([Algorithm 5.1](LiB0040.html#492)) so that it finds the number of nodes checked for an instance of a problem, run it on the problem instance in which *n* = 8, and compare the result against the average of Exercise 9. #### Section 5.4 1. Use the Backtracking algorithm for the Sum-of-Subsets problem ([Algorithm 5.4](LiB0042.html#517)) to find all combinations of the following numbers that sum to *W* = 52:  Show the actions step by step. 2. Implement the Backtracking algorithm for the Sum-of-Subsets problem ([Algorithm 5.4](LiB0042.html#517)) on your system, and run it on the problem instance of Exercise 11. 3. Write a backtracking algorithm for the Sum-of-Subsets problem that does not sort the weights in advance. Compare the performance of this algorithm with that of [Algorithm 5.4](LiB0042.html#517). 4. Modify the Backtracking algorithm for the Sum-of-Subsets problem ([Algorithm 5.4](LiB0042.html#517)) so that, instead of generating all possible solutions, it finds only a single solution. How does this algorithm perform with respect to [Algorithm 5.4](LiB0042.html#517)? 5. Use the Monte Carlo technique to estimate the efficiency of the Backtracking algorithm for the Sum-of-Subsets problem ([Algorithm 5.4](LiB0042.html#517)). #### Section 5.5 1. Use the Backtracking algorithm for the *m*-Coloring problem ([Algorithm 5.5](LiB0043.html#527)) to find all possible colorings of the graph below using the three colors red, green, and white. Show the actions step by step. [](figu229_1_0.jpg) 2. Suppose that to color a graph properly we choose a starting vertex and a color to color as many vertices as possible. Then we select a new color and a new uncolored vertex to color as many more vertices as possible. We repeat this process until all the vertices of the graph are colored or all the colors are exhausted. Write an algorithm for this greedy approach to color a graph of *n* vertices. Analyze this algorithm and show the results using order notation. 3. Use the algorithm of Exercise 17 to color the graph of Exercise 16. 4. Suppose we are interested in minimizing the number of colors used in coloring a graph. Does the greedy approach of Exercise 17 guarantee an optimal solution? Justify your answer. 5. Compare the performance of the Backtracking algorithm for the *m*-Coloring problem ([Algorithm 5.5](LiB0043.html#527)) and the greedy algorithm of Exercise 17. Considering the result(s) of the comparison and your answer to Exercise 19, why might one be interested in using an algorithm based on the greedy approach? 6. Write an algorithm for the 2-Coloring problem whose time complexity is not worst-case exponential in *n*. 7. List some of the practical applications that are representable in terms of the *m*-Coloring problem. #### Section 5.6 1. Use the Backtracking algorithm for the Hamiltonian Circuits problem ([Algorithm 5.6](LiB0044.html#534)) to find all possible Hamiltonian Circuits of the following graph. [](figu229_2_0.jpg) Show the actions step by step. 2. Implement the Backtracking algorithm for the Hamiltonian Circuits problem ([Algorithm 5.6](LiB0044.html#534)) on your system, and run it on theproblem instance of Exercise 23. 3. Change the starting vertex in the Backtracking algorithm for the Hamiltonian Circuits problem ([Algorithm 5.6](LiB0044.html#534)) in Exercise 24 and compare its performance with that of [Algorithm 5.6](LiB0044.html#534). 4. Modify the Backtracking algorithm for the Hamiltonian Circuits problem ([Algorithm 5.6](LiB0044.html#534)) so that, instead of generating all possible solutions, it finds only a single solution. How does this algorithm perform with respect to [Algorithm 5.6](LiB0044.html#534)? 5. Analyze the Backtracking algorithm for the Hamiltonian Circuits problem ([Algorithm 5.6](LiB0044.html#534)) and show the worst-case complexity using order notation. 6. Use the Monte Carlo Technique to estimate the efficiency of the Backtracking algorithm for the Hamiltonian Circuits problem ([Algorithm 5.6](LiB0044.html#534)). #### Section 5.7 1. Compute the remaining values and bounds after visiting node (4, 1) in [Example 5.6](LiB0045.html#541) ([Section 5.7.1](LiB0045.html#538)). 2. Use the Backtracking algorithm for the 0–1 Knapsack problem ([Algorithm 5.7](LiB0045.html#548)) to maximize the profit for the following problem instance. Show the actions step by step.  3. Implement the Backtracking algorithm for the 0–1 Knapsack problem ([Algorithm 5.7](LiB0045.html#548)) on your system, and run it on the problem instance of Exercise 30. 4. Implement the dynamic programming algorithm for the 0–1 Knapsack problem (see Section 4.4.3) and compare the performance of this algorithm with the Backtracking algorithm for the 0–1 Knapsack problem ([Algorithm 5.7](LiB0045.html#548)) using large instances of the problem. 5. Improve the Backtracking algorithm for the 0–1 Knapsack problem ([Algorithm 5.7](LiB0045.html#548)) by calling the promising function after only a move to the right. 6. Use the Monte Carlo technique to estimate the efficiency of the Backtracking algorithm for the 0–1 Knapsack problem ([Algorithm 5.7](LiB0045.html#548)). #### Additional Exercises 1. List three more applications of backtracking. 2. Modify the Backtracking algorithm for the *n*-Queens problem ([Algorithm 5.1](LiB0040.html#492)) so that it produces only the solutions that are invariant under reflections or rotations. 3. Given an *n × n × n* cube containing *n*3 cells, we are to place *n* queens in the cube so that no two queens challenge each other (so that no two queens are in the same row, column, or diagonal). Can the *n*-Queens algorithm ([Algorithm 5.1](LiB0040.html#492)) be extended to solve this problem? If so, write the algorithm and implement it on your system to solve problem instances in which *n* = 4 and *n* = 8. 4. Modify the Backtracking algorithm for the Sum-of-Subsets ([Algorithm 5.4](LiB0042.html#517)) to produce the solutions in a variable-length list. 5. Explain how we can use the Backtracking algorithm for the *m*-Coloring problem ([Algorithm 5.5](LiB0043.html#527)) to color the edges of the graph of Exercise 16 using the same three colors so that edges with a common end receive different colors. 6. Modify the Backtracking algorithm for the Hamiltonian Circuits problem ([Algorithm 5.6](LiB0044.html#534)) so that it finds a Hamiltonian Circuit with minimum cost for a weighted graph. How does your algorithm perform? 7. Modify the Backtracking algorithm for the 0–1 Knapsack problem ([Algorithm 5.7](LiB0045.html#548)) to produce a solution in a variable–length list.