Introduction to Algorithms: A Creative Approach
This book emphasizes the creative aspects of algorithm design by examining steps used in the process of algorithm development. The heart of the creative process lies in an analogy between proving mathematical theorems by induction and designing combinatorial algorithms. The book contains hundreds of problems and examples. It is designed to enhance the reader's problem-solving abilities and understanding of the principles behind algorithm design.
Results 1-3 of 19
In a divide-and-conquer algorithm, the problem is divided into smaller
subproblems, each subproblem is solved recursively, and a combine algorithm is
used to solve the original problem. Assume that there are a subproblems, each of
size 1 /b ...
We have reduced the problem to two smaller subproblems: P(n-\,K) and P(n- \,K -
kn). To complete the solution, we have to strengthen the hypothesis. We need to
solve the problem not only for knapsacks of size K, but also for knapsacks of all ...
Fortunately, in this case there is no need to solve each subproblem separately.
The key to this observation is that there are not too many different subproblems
altogether. Each possible subproblem involves computing C(i, j) for some i and j