This is the last labsheet of the semester and you have until the end of May to complete it. Although the lab is not assessed, you must complete it as it reinforces concepts from the lectures especially regarding the divide and conquer problem solving technique and recursion. The labsheet is in two parts: some review exercises from the text ; and an important problem-solving technique, motivated by its use in solving a larger-sized problem representative of the types of problems that can be solved with computers.
Divide and conquer is the name for a problem-solving technique whereby a problem is solved by splitting (dividing) it into two or more smaller sub-problems of the same type, solving (conquering) each of the sub-problems, then combining these solutions to derive a solution to the original problem.
A simple example from real life is delivering mail to a county containing (say) 100 towns: the problem can be divided into four sub-problems by splitting the mail into geographical regions (north, south, east, west), then solving each sub-problem by delivering the mail within that region.
Divide and conquer is a naturally-recursive technique: if the west region above still contained 60 towns, then we might apply the same technique again to divide that region still further. So the overall solution would look like this:
def deliverMail(towns):
if len(towns) < threshhold:
visit each relevant house
else:
regions = divide towns into four lists
map(deliverMail, regions)
Thus a divide-and-conquer solution to a problem has four components:
PROBLEM SOLVING QUESTION 7.1) One of the fastest comparison-based sorting algorithms is mergesort. A long list is sorted by splitting it into two at its mid-poiint, sorting the two halves separately, then merging them back together - which is easy because the two halves are now in order. This is clearly a divide-and-conquer algorithm: the problem of sorting a big list is split into two sub-problems of the same type, then those solutions are combined.
You can implement mergesort by writing two recursive functions.
PROBLEM SOLVING QUESTION 7.2) Another fast comparison-based sorting algorithm is quicksort. Given a list xs with more than one element, take the first element of xs (known as the pivot), then partition the other elements of xs into two sub-lists, the first containing all of the elements which are less than the pivot, the second containing all of the other elements, e.g. partition([3,8,1,2,9,7], 5) = ([3,1,2], [8,9,7]). The sorting is completed by sorting these two lists separately, then simply appending the two results together, because we know that the smaller values are on the first sub-list.
quicksort is clearly also a divide-and-conquer algorithm. In fact it is the converse of mergesort: it still works by splitting the list into two, sorting the pieces, then re-combining them, but it applies its comparisons during the splitting process, rather than during the combining process.
You can implement quicksort by writing two recursive functions.