Divide, Combine and Conquer
#1 of three algorithm design strategies - divide and conquer (or simply D&C), is based on decomposing the problem in a way that improves performance. Divide the problem instance, solve subproblems recursively, combine the results, and thereby conquer the problem.

1 Tree-Shaped Problems: All About the Balance
The simplest structure such a subproblem graph can have is a tree. Each subproblem may depend on one or more others, but we’re free to solve these other subproblems independently of each other. (if remove this independence, will end up with the kind of overlap and entanglements dealt with by Dynamic Programming.) This straightforward structure means that as long as we can find the proper reduction, we can implement the recursive formulation of our algorithm directly.
the puzzle pieces needed to understand the idea of divide-and-conquer algorithms:

• Divide-and-conquer recurrences
• Strong induction
• Recursive traversal
  

The recurrences tell you something about the performance involved, the induction gives you a tool for understanding how the algorithms work, and the recursive traversal (DFS in trees) is a raw skeleton for the algorithms.

The one crucial addition in the design method of divide and conquer is balance. This is where strong induction comes in: Instead of recursively implementing the step from n-1 to n, we want to go from n/2 to n. That is, we take solutions of size n/2 and build a solution of size n. Instead of (inductively) assuming that we can solve subproblems of size n-1, we assume that we can deal with all subproblems of sizes smaller than n.

• unbalanced: T(n) = T(n-1) + T(1) + n
• balanced: T(n) = 2T(n/2) + n
  

Example - skyline problem
The point is that we can add a building to the skyline in linear time.
Using simple (weak) induction, we now have our algorithm: We start with a single building and keep adding new ones until we’re done. And, of course, this algorithm has a quadratic running time.
To improve this, we want to switch to strong induction - divide and conquer. We can do this by noting that merging two skylines is no harder than merging one building with a skyline: We just traverse the two in “lockstep,” and wherever one has a higher value than the other, we use the maximum, splitting horizontal line segments where needed. Using this insight, we have our second, improved algorithm: To create a skyline for all the buildings, first (recursively) create two skylines, based on half the buildings each, and then merge them. This algorithm, as I’m sure you can see, has a loglinear running time. Exercise 6-1 asks you to actually implement this algorithm.

2 The Canonical D&C Algorithm
The input is a set (perhaps a sequence) of elements; the elements are partitioned, in at most linear time, into two sets of roughly equal size, the algorithm is run recursively on each half, and the results are combined, also in at most linear time.

A General Implementation of the Divide-and-Conquer Scheme
def divide_and_conquer(S, divide, combine):
    if len(S) == 1:
        return S

    L, R = divide(S)
    A = divide_and_conquer(L, divide, combine)
    B = divide_and_conquer(R, divide, combine)

    return combine(A, B)

NOTE: The upper half of the figure represents the recursive calls, while the lower half represents the way return values are combined. Some algorithms (such as quicksort, described later in this chapter) do most of their work in the upper half (division), while some are more active in the lower (combination). The perhaps most well-known example of an algorithm with a focus on combination is merge sort (described a bit later in this chapter), which is also a prototypical example of a divide-and-conquer algorithm.

3 Searching by Halves
binary search (bisection): It divides the problem into two equal halves and then recurses on only one of those halves. The core principle here is still balance. Consider what would happen in a totally unbalanced search. If you recall the “think of a particle” game from Chapter 3, the unbalanced solution would be equivalent to asking “Is this your particle?” for each particle in the universe. The difference is still encapsulated by Figures 6-1 and 6-2, except the work in each node (for this problem) is constant, and we only actually perform the work along a path from the root to a leaf.

#1. Traversing Search Trees ... with Pruning

• Binary Search Tree
• SORTED ARRAYS, TREES, AND DICTS: CHOICES, CHOICES
  

# 2. Selection

• find the kth largest number in an unsorted sequence, in linear time.
  

4 Sorting by Halves

• quicksort vs. timsort in Python
  

5 Tree Balance ... and Balancing
There’s a ton of different tree structures and balancing methods, but they’re generally based on two fundamental operations:

• Node splitting (and merging). Nodes are allowed to have more than two children (and more than one key), and under certain circumstances, a node can become overfull. It is then split into two nodes (potentially making its parent overfull).
• Node rotations. Here we still use binary trees, but we switch edges. If x is the parent of y, we now make y the parent of x. For this to work, x must take over one of the children of y.
  

Note: The 2-3-tree is a special case of the B-tree, which forms the basis of almost all database systems, and disk-based trees used in such diverse areas as geographic information systems and image retrieval. The important extension is that B-trees can have thousands of keys (and subtrees), and each node is usually stored as a contiguous block on disk. The main motivation for the large blocks is to minimize the number of disk accesses.