Backtracking

• Read section 12.1 (pages 423-430)
• What is the state-space tree? what do its nodes reflect? What about the leaves?
• Which nodes are called **promising*, and which are called nonpromising?
• What does the state-space tree look like for the Hamiltonian circuit problem?
  • How can we know at each step in the Hamiltonian circuit state-space tree what options we should have available and whether we are done?
• What does the state-space tree look like for the subset-sum problem?
  • How does does ordering the set’s elements in increasing order benefit the algorithm?
  • What are the two conditions that allow us to stop examining a particular node in the tree?
  • Does the sum \(\sigma_{j=i+1}^n a_j\) need to be computed at each node?
• Describe in words the overall process for the backtracking algorithm.
• How can we use backtracking to solve the \(k\)-coloring problem?
• Practice problems: 12.1.5, 12.1.6