# FOCS 2006 Problem Set 3 Solutions

## Problem 1

**Consider an optimization of **merge sort** in which the original list of length n is divided into disjoint sublists of length k, these lists are sorted using **insertion sort

**, and then the**

*n/k*sublists of length*k*are merged (pairwise, successively, as in merge-sort) until the final sorted list of length*n*is achieved.**How many steps will it take to sort each of the sublists of length***k*? Give your answer in asymptotic (Theta, like big-Oh) notation. Indicate whether your analysis is best, worst, or average case.Insertion sort is (worst and average cases)

*Theta(n*. SInce our input is of size^{2})*k*, this is*Theta(k*. (Best case, i.e., assuming the sublists were magically sorted, would be^{2})*Theta(k)*to verify. But it ain't gonna happen.)**How many steps will it take to sort***all*of the sublists of length*k*? Again, use Theta and indicate what you're analyzing.Saying that sorting a sublist is

*Theta(k*means that there is some constant^{2})*c*for which*c k*is a good estimate of the number of steps. (Well, technically it means that there are two constants,^{2}*c*and_{1}*c*, and the actual number of steps_{2}*steps*is bounded by*c*_{1}k^{2}<= steps <= c_{2}k^{2}

but I'm going to cheat and just use

*c*so I don't have to keep writing the double bounds.)Since there are

*n/k*sublists, each taking*c k*steps, this is^{2}*n/k * c k*, which is^{2}= n c k^{2}/ k = c n k*Theta(nk)*. (For those who want the gorey details, this argument can be made twice with*c*, <=,_{1}*c*, and >= to really prove_{2}*Theta*. I will be satisfied with any reasonable approximation of the derivation, including waving hands madly in the obviously right direction or stating the correct answer by fiat.) This is again a worst or average case. (They're the same here, as the difference is just in the expected constant if the list isn't pessimally organized.)**Once the***n/k*sublists of length*k*are individually sorted, how long will it take to merge them all back together? Again, Theta and case....Now that the sublists are sorted, we do a standard merge on them. This will take

*log*passes, each of size_{2}n/k*n*, for a bound of*n log*. That is, the (worst, average) case is_{2}n/k*Theta(n log (n/k))*.To see this, consider the merging problem: We start with

*n/k*little lists and merge them pairwise, generating*n/2k*somewhat larger lists. This progression is building up the binary tree from the little lists at the leaves to the whole big merged list at the root (which is of course on top because this is an upside-down computational tree...). We know that this tree has depth*log*, so there are_{2}(n/k)*log*passes. Each pass touches each of the_{2}(n/k)*n*elements exactly once, when it's being put into place in its own merge-list, so each pass is*Theta(n)*.*Theta(log (n/k) )*passes of size*Theta(n)*yields a running time for this phase of*Theta(n log (n/k))*.**Given your analysis and what you know about merge sort, how should we choose***k*(as a function of*n*) so that this algorithm is asymptotically (Theta-notation) comparable to merge sort?This would be a good time to remind ourselves that merge sort is

*Theta(n log n)*. Before we answer this question, we need to take a minute to put the algorithm back together. The total algorithm has two basic steps:- Sort the little lists.
- Merge the sorted little lists into one big sorted list.

The time for this algorithm is

*Theta(nk) + Theta(n log (n/k))*. Note that, without knowing what*k*is, we don't know which term dominates.For example, if we set

*k=1*, this is*Theta(n*1) + Theta(n log (n/1)) = Theta(n) + Theta(n log n) = Theta(n log n)*, i.e., the*n log n*term dominates. This is asymptotically comparable to merge sort, which isn't particularly surprising because it*is*merge sort.If on the other hand, we choose

*k=n*, we get*Theta(n*n) + Theta(n log (n/n)) = Theta(n*, with the^{2}) + Theta(n) = Theta(n^{2})*nk*(now*n*) term dominating.^{2}The question, then, is how to pick

*k*so that we get the most improvement -- make the*n log (n/k)*term small -- without doing worse than merge sort. If we don't worry about constants -- which is the next question (and also this one specifically says "asymptotically comparable") -- we can observe that the*Theta(n log (n/k))*term will never do worse than*Theta(n log n)*, which means that we can safely ignore it in picking*k*. That means that we just need to to ensure that the other term --*Theta(nk)*is better than*Theta(n log n)*.Happily,

*Theta(nk) <= Theta(n log n)*will be true as long as*k <= log n*.**Merge sort typically has a higher constant factor on its (asymptotic) running time than insertion sort. How could this be taken into account in selecting k?**Oops, here come those pesky constants.What the above analysis really means is that there are some constants (again, I'm only going to use one for each Theta rather than constant above and constant below) for which our new algorithm runs in

*c*steps. The question points out that_{insert}n k + c_{merge}n log (n/k)*c*, i.e., merge sort has a much bigger constant._{merge}>> c_{insert}Any time that we can make

*k*bigger, it helps the*c*term, since it reduces the number of merges. And making_{merge}n log (n/k)*k*bigger isn't so unreasonable in the first term if*c*. We want_{insert}<< c_{merge}*c*_{insert}n k < c_{merge}n log n

i.e.,

*c*_{insert}k < c_{merge}log nor

*k < (c*_{merge}/c_{insert}) log nAs long as we adhere to this constraint, we're going to be improving the running time of mergesort by using this algorithm. Since

*c*, this could be a large constant multiplier on the value of_{merge}>> c_{insert}*k*.

## Problem 2

View the solution in this PDF.

## Problem 3

Here's an example of one acceptable answer to parts a and b. Other variant answers are acceptable as well:

sentence --> noun_phrase, verb_phrase, prepositional_phrase. sentence --> noun_phrase, verb_phrase. noun_phrase --> core_noun_phrase. noun_phrase --> adjective, core_noun_phrase. core_noun_phrase --> determiner, noun. core_noun_phrase --> proper_noun. verb_phrase --> verb_intransitive. verb_phrase --> verb_transitive, noun_phrase. prepositional_phrase --> preposition, noun_phrase. adjective --> [ambidextrous]. determiner --> [a]. determiner --> [the]. noun --> [whangdoodle]. noun --> [hippogriff]. preposition --> [with]. proper_noun --> [ophelia]. proper_noun --> [rodriguez]. proper_noun --> [compassion]. % well, not really a PN, but doesn't take a det verb_intransitive --> [pirouettes]. verb_transitive --> [chastises].