4.2-2 Argue the solution to
is by appealing to the recursion tree.
The shortest path to a leaf occurs when we take the heavy branch each time. The height k is given by , meaning or .
The longest path to a leaf occurs when we take the light branch each time. The height k is given by , meaning or .
The problem asks to show that , meaning we are looking for a lower bound
On any full level, the additive terms sums to n. There are full levels. Thus
4.2-4 Use iteration to solve T(n) = T(n-a) + T(a) + n, where is a constant.
Why don't CS profs ever stop talking about sorting?!
You should have seen most of the algorithms - we will concentrate on the analysis.
Applications of Sorting
One reason why sorting is so important is that once a set of items is sorted, many other problems become easy.
Searching
Speeding up searching is perhaps the most important application of sorting.
Closest pair
Once the numbers are sorted, the closest pair will be next to each other in sorted order, so an O(n) linear scan completes the job.
Element uniqueness
Sort them and do a linear scan to check all adjacent pairs.
This is a special case of closest pair above.
Frequency distribution - Mode
Sort them and do a linear scan to measure the length of all adjacent runs.
Median and Selection
Once the keys are placed in sorted order in an array, the kth largest can be found in constant time by simply looking in the kth position of the array.
Convex hulls
Convex hulls are the most important building block for more sophisticated geometric algorithms.
Once you have the points sorted by x-coordinate, they can be inserted from left to right into the hull, since the rightmost point is always on the boundary.
Without sorting the points, we would have to check whether the point is inside or outside the current hull.
Adding a new rightmost point might cause others to be deleted.
Huffman codes
If you are trying to minimize the amount of space a text file is taking up, it is silly to assign each letter the same length (ie. one byte) code.
Example: e is more common than q, a is more common than z.
If we were storing English text, we would want a and e to have shorter codes than q and z.
To design the best possible code, the first and most important step is to sort the characters in order of frequency of use.
Character | Frequency | Code |
f | 5 | 1100 |
e | 9 | 1101 |
c | 12 | 100 |
b | 13 | 101 |
d | 16 | 111 |
a | 45 | 0 |
Selection Sort
A simple sorting algorithm is selection sort.
Sweep through all the elements to find the smallest item, then the smallest remaining item, etc. until the array is sorted.
Selection-sort(A)
for i = 1 to n
for j = i+1 to n
if (A[j] < A[i]) then swap(A[i],A[j])
It is clear this algorithm must be correct from an inductive argument, since the ith element is in its correct position.
It is clear that this algorithm takes time.
It is clear that the analysis of this algorithm cannot be improved because there will be n/2 iterations which will require at least n/2 comparisons each, so at least comparisons will be made. More careful analysis doubles this.
Thus selection sort runs in time.
Binary Heaps
A binary heap is defined to be a binary tree with a key in each node such that:
Conditions 1 and 2 specify shape of the tree, and condition 3 the labeling of the tree.
The ancestor relation in a heap defines a partial order on its elements, which means it is reflexive, anti-symmetric, and transitive.
Partial orders can be used to model heirarchies with incomplete information or equal-valued elements. One of my favorite games with my parents is fleshing out the partial order of ``big'' old-time movie stars.
The partial order defined by the heap structure is weaker than that of the total order, which explains
Constructing Heaps
Heaps can be constructed incrementally, by inserting new elements into the left-most open spot in the array.
If the new element is greater than its parent, swap their positions and recur.
Since at each step, we replace the root of a subtree by a larger one, we preserve the heap order.
Since all but the last level is always filled, the height h of an n element heap is bounded because:
so .
Doing n such insertions takes , since the last n/2 insertions require time each.
Heapify
The bottom up insertion algorithm gives a good way to build a heap, but Robert Floyd found a better way, using a merge procedure called heapify.
Given two heaps and a fresh element, they can be merged into one by making the new one the root and trickling down.
Build-heap(A)
n = |A|
For do
Heapify(A,i)
Heapify(A,i)
left = 2i
right = 2i+1
if then
max = left
else max = i
if and (A(right] > A[max]) then
max = right
if then
swap(A[i],A[max])
Heapify(A,max)
Rough Analysis of Heapify
Heapify on a subtree containing n nodes takes
The 2/3 comes from merging heaps whose levels differ by one. The last row could be exactly half filled. Besides, the asymptotic answer won't change so long the fraction is less than one.
Solve the recurrence using the Master Theorem.
Let a = 1, b= 3/2 and f(n) = 1.
Note that , since .
Thus Case 2 of the Master theorem applies.
where we interpret n/b to mean either or . Then T(n) can be bounded asymptotically as follows:
Exact Analysis of Heapify
In fact, Heapify performs better than , because most of the heaps we merge are extremely small.
In general, there are at most nodes of height h, so the cost of building a heap is:
Since this sum is not quite a geometric series, we can't apply the usual identity to get the sum. But it should be clear that the series converges.
Proof of Convergence
Series convergence is the ``free lunch'' of algorithm analysis.
The identify for the sum of a geometric series is
If we take the derivative of both sides, ...
Multiplying both sides of the equation by x gives the identity we need:
Substituting x = 1/2 gives a sum of 2, so Build-heap uses at most 2n comparisons and thus linear time.
The Lessons of Heapsort, I
"Are we doing a careful analysis? Might our algorithm be faster than it seems?"
Typically in our analysis, we will say that since we are doing at most x operations of at most y time each, the total time is O(x y).
However, if we overestimate too much, our bound may not be as tight as it should be!
Heapsort
Heapify can be used to construct a heap, using the observation that an isolated element forms a heap of size 1.
Heapsort(A)
Build-heap(A)
for i = n to 1 do
swap(A[1],A[i])
n = n - 1
Heapify(A,1)
If we construct our heap from bottom to top using Heapify, we do not have to do anything with the last n/2 elements.
With the implicit tree defined by array positions, (i.e. the ith position is the parent of the 2ith and (2i+1)st positions) the leaves start out as heaps.
Exchanging the maximum element with the last element and calling heapify repeatedly gives an sorting algorithm, named Heapsort.
Heapsort Animations
The Lessons of Heapsort, II
Always ask yourself, ``Can we use a different data structure?''
Selection sort scans throught the entire array, repeatedly finding the smallest remaining element.
For i = 1 to n
A: Find the smallest of the first n-i+1 items.
B: Pull it out of the array and put it first.
Using arrays or unsorted linked lists as the data structure, operation A takes O(n) time and operation B takes O(1).
Using heaps, both of these operations can be done within time, balancing the work and achieving a better tradeoff.
Priority Queues
A priority queue is a data structure on sets of keys supporting the following operations:
These operations can be easily supported using a heap.
Applications of Priority Queues
Heaps as stacks or queues
Both stacks and queues can be simulated by using a heap, when we add a new time field to each item and order the heap according it this time field.
This simulation is not as efficient as a normal stack/queue implementation, but it is a cute demonstration of the flexibility of a priority queue.
Discrete Event Simulations
The stack and queue orders are just special cases of orderings. In real life, certain people cut in line.
Sweepline Algorithms in Computational Geometry
Greedy Algorithms
Example: Sequential strips in triangulations.
Danny Heep