Appendix C. Exercises and Solutions
In this appendix, you will find a comprehensive set of exercises and their corresponding solutions, organized by chapter, to enhance your understanding and application of the material presented in this book. These exercises are designed to reinforce the concepts, theories, and practical skills covered throughout the chapters.
Chapter 2: A Deeper Look at Search and Optimization
Exercises
1. MCQs: Choose the correct answer for each of the following questions.
1.1. _________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms and whose solutions are hard to find but easy to verify.
- P
- NP
- co-NP
- NP-Complete
- NP-hard
1.2. Which of the following benchmark/toy problems is not NP complete?
- Bin packing
- Knapsack problem
- Minimum spanning tree
- Hamiltonian circuit
- Vertex cover problem
1.3. _________ is the class of decision problems whose “No” answer can be verified in polynomial time.
- P
- NP
- co-NP
- NP-Complete
- NP-hard
1.4. Which of the following real-world problems is NP-hard?
- Image matching
- Single Machine Scheduling
- Combinational Equivalence Checking
- Capacitated Vehicle Routing Problem (CVRP)
- Container/truck loading
1.5. _________ is a theory that focuses on classifying computational problems according to their resource usage and relating these classes to each other.
- Optimization complexity
- Time complexity
- Computational complexity
- Operation Research
- Decision complexity