Modules 10 and 11

Review questions

  1. What is a combinatorial optimization problem? Give an example of something that is not.
  2. What is the difference between a constructive heuristic and a state-space search heuristic? Explain using bin-packing as an example.
  3. Explain the above in terms of the traveling salesman problem.
  4. What does neighborhood mean in the context of state-space search?
  5. What is the term problem landscape mean?
  6. How can state-space search go wrong and how is this issue addressed?
  7. What are the four types of problems in terms of the level of difficulty?
  8. What is the decision version of a problem? Explain in terms of bin packing.
  9. What does it mean to transform one problem into another?
  10. What is the vertex cover problem?
  11. What is the SAT problem?
  12. What is an NP problem?
  13. Explain Cook's famous result.
  14. What is an NP-Complete problem?
  15. If a problem is NP-Complete, what is the implication? For example, if I were to find a fast (polynomial) algorithm for the vertex-cover problem, what is the implication?
  16. What is the difference between the two types of exhaustive search approaches?
  17. What does the "enumerate all subsets" algorithm have to do with binary numbers? What does this have to do with finding a minimal vertex cover?
  18. What are the key ideas in the algorithm that "enumerates all binary numbers with k 1's"? What does this have to do with the problem of finding a clique of size k?