Divide and Conquer

Divide and conquer is a way to break complex problems into smaller problems that are easier to solve, and then combine the answers to solve the original problem. Divide and conquer is a powerful algorithm design technique used to solve many important problems such as mergesort, quicksort, calculating Fibonacci numbers, and performing matrix multiplication. There are also many problems that humans naturally use divide and conquer approaches to solve, such as sorting a stack of playing cards or looking for a phone number in a phone book.

Divide and conquer can be done in three broad steps, divide (into subproblems), conquer (by solving the subproblems), and combine (the answers to solve the original problem). Divide and conquer has a recursive step, where subproblems are solved, and a base case, which is the point where the problem can't be broken down any further.

How do you order a deck of cards?

There are many examples of problems for which humans naturally take a divide and conquer approach. Let’s say you have a stack of playing cards that you want to put in order. Sorting the entire deck is the original problem, but we can break this into subproblems by comparing only some of the cards at a time.

To do this, take the first and second card from the unsorted deck and sort those. Take another card from the unsorted deck and sort that into the sorted deck. Keep doing this until the entire deck has been sorted. Here, we divide into subproblems by sorting only some of the cards at once. At each step, we take one card from the unsorted list (the divide step), and put it into the sorted list (this makes up both the conquer and combine steps).

Divide:
The divide step breaks the original problem into subproblems that are smaller instances of the original problem.

Conquer:
The conquer step solves the subproblems recursively.

Combine:
The combine step puts the solved subproblems together to solve the original problem.

There is a variation of divide and conquer where the problem is reduced to one subproblem. Binary search is a popular example that uses decrease and conquer. Binary search looks through a sorted list to see if a desired element is in the list. It does this efficiently by halving the search space during each iteration of the program. Basically, binary search finds the middle of the list, asks “is the element I’m looking for larger or smaller than this?” and then cuts the list in half and searches only in the left list if the element is smaller, and the right list if the element is bigger. It repeats this process until it finds the element it is looking for (or reports back that the element isn’t in the list at all).

Describe how you would use decrease and conquer approach to find page 88 in a 350 page textbook.

Open the book to any page. If the page you’ve opened to is greater than 88, flip some number of pages toward the beginning of the book (and some number of pages toward the end of the book if the page number is smaller than 88). Now look at the new page number you’ve turned to. If the number is less than 88, flip some amount toward the end of the book (the amount you flip by should decrease with each iteration, since you don’t want to lose progress by overshooting), and if the number is greater than 88, flip some number of pages toward the beginning of the book. Repeat until you find page 88.

How to use divide and conquer:

• Given a problem, identify a number of significantly smaller subproblems.
• Solve each subproblem recursively (do this until the subproblem is a base-case).
• Combine these solutions into a solution for the main problem.

Computer Science:
Divide-and-conquer algorithms often follow a generic pattern: they solve a problem of size \(n\) by recursively solving \(a\) subproblems of size \(\dfrac{n}{b}\), and then combine these answers in \(O(n^d)\) time. This general form can be represented by the following recurrence relation: \[T(n) = aT(\dfrac{n}{b}) + O(n^d).\] The master theorem can be used to solve the recurrence relation for a closed form solution.

Recurrence relations are useful for determining the efficiency of algorithms.

Here is an example of merge sort, a divide and conquer algorithm in Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0
    while left_idx < len(left) and right_idx < len(right):
        # change the direction of this comparison to change the direction of the sort
        if left[left_idx] <= right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

    if left:
        result.extend(left[left_idx:])
    if right:
        result.extend(right[right_idx:])
    return result

def merge_sort(m):
    if len(m) <= 1:
        return m

    middle = len(m) // 2
    left = m[:middle]
    right = m[middle:]

    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

Here is an example of binary search, a reduce and conquer algorithm in Python.^[1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def it_binarySearch(mylist, target):
        first = 0
        last = len(mylist)-1

        while first<=last:
            midpoint = (first + last)/2
            if mylist[midpoint] == target:
                return midpoint
            else:
                if target < mylist[midpoint]:
                    last = midpoint-1
                else:
                    first = midpoint+1

        return None

test_list = [0,3,4,7,9,11,34,46,57,65]
print(it_binarySearch(test_list, 4))
print(it_binarySearch(test_list, 30))
print(it_binarySearch(test_list, 57))

1. , . The Binary Search. Retrieved April 1=30, 2016, from http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html