Definition from the lecture week#7:
The very general idea of divide and conquer proof is to partition a problem into b roughly equal subproblems and solve them and then recombine to prove the desired bound on the function based on the already defined subproblems.
A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the related type until these become simple enough to be solved directly. The solution to the sub-problem are then extended and combined to derive a full solution to the original problem.
Probably this would be the most difficult material of the course i have ever faced with by so far. To prove one recursively defined function with a technique of a divide-and-conquer requires not just one but two or more broken down steps to come up with a solution to the original problem.
No comments:
Post a Comment