> I am having a problem understanding "The Loopless MetaSorter" > (prerequisite to problem 5.)
It is a challenging problem, and I'm glad to see that people are starting to ask questions about it. > http://harvard.altisimo.com/cscie119/homework/hw3/MetaSorter.pdf. > The MetasSorter notes are similar to lecture notes, but there is no > corresponding video. The notes seem too concise to be understood > by themselves. It is notes for a lecture I haven't given. Remember that you don't need to understand everything there to start thinking about the problem. The notes are going to be something you re-read multiple times. > Is there anything that I can do to understand the MetaSorter > notes better? Are there any references that can I look-up? If you can make it to section, I'm sure Rich and Hans will be getting questions on the topic. You could take a look at the discussion of Decision trees in the second lecture on Sorting, and the discussion of Insertion Sort in the first lecture on sorting. I would say that you need to understand the following before you can put a solution together. While you may not be able to do all the steps today, you can get started on those that you don't know how to do, but can understand how to approach. For example, learning Insertion Sort will be a good investment of time. 1) How the sample output solves the problem of sorting 3 items 2) How you might generate the 'preamble' - the portion of the program before the first 'if' 3) How Insertion Sort works. 4) How to turn the logic of Insertion Sort into a sequence of questions. That is, how to draw the decision tree that Insertion Sort represents. You need to understand how to draw these trees by hand before you can generate them automatically. 5) How to generate those questions automatically - that is, how to generate the if statements 6) How to carry along the "answers" to those questions: the permutations that are printed in each leaf: that is, how to generate the printf statements. This builds on point 3 and 4 above. You don't need to understand the discussion of improvements to the algorithm (Binary Insertion Sort, Merge Insertion). You -will- find that these discussions make more sense as you understand the problem better. - jeff parker
