Divide and conquer Flashcards
Divide and conquer general approach
“Divide and conquer refers to a class of algorithmic techniques in which one breaks the input into several parts, solves the problem in each part recursively, and then combines the solutions to these subproblems into an overall solution.
Analyzing the running time of a divide and conquer algorithm generally involves solving a recurrence relation that bounds the running time recursively in terms of the running time on smaller instances.
(†) Divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.”
Mergesort
“Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls.
—in the form of the two sorted halves—using the linear-time algorithm for merging sorted lists that we saw in Chapter 2.
we also need a base case for the recursion: once the input has been reduced to size 2, we stop the recursion and sort the two elements by simply comparing them to each other.”
Unrolling a recursion
“accounting for the running time across the first few levels, and identify a pattern that can be continued as the recursion expands. One then sums the running times over all levels of the recursion.
Mergesort:
Analyzing the first few levels: At the first level of recursion, we have a single problem of size n, which takes time at most cn plus the time spent in all subsequent recursive calls. At the next level, we have two problems each of size n/2.
Summing over all levels of recursion: *the same upper bound of cn applies to total amount of work performed at each level**. The number of times the input must be halved in order to reduce its size from n to 2 is log2 n. So summing the cn work over log n levels of recursion, we get a total running time of O(n log n).”
Recurrence relations with q>2 subproblems
other algorithms find it useful to spawn q > 2 recursive calls.
Recurrence relations with Q=1 subproblems
”
we see that, unlike the previous case, the total work per level when q = 1 is actually decreasing as we proceed through the recursion.
Identifying a pattern: At an arbitrary level j, we still have just one instance; it has size n/2j and contributes cn/2j to the running time.
(5.5) Any function T(·) satisfying (5.3) with q = 1 is bounded by O(n).
“
Counting Inversions
“But what’s a good way to measure, numerically, how similar two people’s rankings are?
A natural way to quantify this notion is by counting the number of inversions. We say that two indices i < j form an inversion if ai > aj, that is, if the two elements ai and aj are “out of order.”
There are three inversions in this sequence: (2, 1), (4, 1), and (4, 3).
show how to count the number of inversions much more quickly, in O(n log n) time.
So the crucial routine in this process is Merge-and-Count. Suppose we have recursively sorted the first and second halves of the list and counted the inversions in each. We now have two sorted lists A and B, containing the first and second halves, respectively.
We want to produce a single sorted list C from their union, while also counting the number of pairs (a, b) with a ∈ A, b ∈ B, and a > b.
Because A and B are sorted, it is actually very easy to keep track of the number of inversions we encounter. On the other hand, if bj is appended to list C, then it is smaller than all the remaining items in A, and it comes after all of them, so we increase our count”
Finding the closest pair of points
“Given n points in the plane, find the pair that is closest together. the O(n log n) algorithm.
We define Q to be the set of points in the first ⌈n/2⌉ positions of the list Px (the “left half”) and R to be the set of points in the final ⌊n/2⌋ positions of the list Px (the “right half”).
Trick is that we are guaranteed only to compare 15 points between left and right half! (see images)”
