Lesson 1

How and why should we write a program that generates all objects from a given set? We'll deal with the “how” throughout this section. For now, let's answer the “why”.

1. Understanding how to generate objects helps to compute their count and to generate a random object.
2. Many computational problems require finding an object with special properties. To find such an object or verify its absence, the ability to generate all objects is useful.
3. Many optimization problems (e.g., the knapsack problem, traveling salesman problem, scheduling problem) involve finding an object that achieves the optimal value of a target function. To solve such problems, it’s important to be able to iterate over all candidates. This makes sense when the search space is not too large. Such implementations are also useful for testing more efficient programs: when developing an efficient solution to an optimization problem, it’s important to ensure that on small inputs it gives the same output as a brute-force program.
4. We’ll introduce the branch and bound method, which allows us to speed up brute-force search in optimization problems. This is a heuristic method: it doesn't provide theoretical guarantees, but often works much faster on practical data.
5. Finally, we’ll show how to optimize brute-force so that the resulting solution is based on dynamic programming. Such a solution will have a strict upper bound on running time.