31251 Lecture Notes - Lecture 4: Object-Oriented Programming, Ordered Pair, Adjacency Matrix
Week 4 Lecture
Divide and Conquer
• A major aspect of divide and conquer is to solve a problem by recursively
decomposing the instance into smaller instances and sub-problems.
• For many recurrences, we use the Master Theorem:
• The general framework for a divide and conquer algorithm is:
o Divide instances into a set of sub-problems
o If a sub-problem is small enough, solve it, otherwise recursively split the
sub-problem.
o Combine the sub-problem solutions into a whole solution.
• To make a Divide-and-Conquer problem work, the problem has to be recursively
similar, i.e. can an instance be broken up into smaller instances of the same
problem.
• The number and the size of the sub-problems must be in the right balance.
• You must be able to recombine sub-solutions into a solution efficiently.
Recursion
• Recursion is a central component of Divide-and-Conquer
• Whilst it is possible to phrase everything in computer science in terms of recursion,
it may look neat, but it often leads to inefficient and broken code.
• When defining your own recursive algorithm, carefully specify the preconditions
(what must be true about the input before you start the algorithm. You also need to
carefully specify the post conditions (what must be true about the output when
ou’re doe. These oditions will then apply at every step of the recursion.
• You also need to work out how to measure the size of an instance so you can know
how many recursions to complete.
• If the sub-istaes do’t fit the preoditios, ou a eed to rethik the
conditions established.
• Make sure the keep the number of cases as small as possible.
• If the sub-instance is small enough, just solve it using brute force.
Recursion vs Iteration
• Recursion often gives simple algorithms, meaning they are trickier to make efficient,
whereas iterative algorithms are often quite easy to make efficient however they
often result in hard to understand code.
• Both approaches can be used as they are equally as powerful, you must just think
about what works best for the problem.
• When deciding between the two consider:
o Is the problem naturally recursive or iterative?
o Have you worked out how to terminate the algorithm?
o Will the same information be reused?
find more resources at oneclass.com
find more resources at oneclass.com
