> Can you give me some insight to problem number 5 in homework three. I > cannot begin to think about methods or algorithms that will create for > example the decsion tree of n=3 as shown in the problem statement. If I > could construct the three I have a shot at producing the C code, but I > cannot get started in the construction process. Since I do not see alot of > questions about this on the list server, I would appreciate you not > repeating the question with your response since I am feeling somewhat > [not very intelligent] in comparison. Looks like no one else has a question this > basic..thnx
I bet there are others wondering how to get started. I just got started working on my own solution. Here's what I've been thinking: On the requirements: - Generating C code is not a requirement. My solution will produce Java code. - Reading the input integers from a file is not a requirement. My solution will get its inputs from the command line. The input cases: - The easiest code to generate is the n=1 case. - The next easiest code to generate is the n=2 case. - For n>2, break things down until you reach n=2 the n=2 case. Understand what to generate: - It's hard to write a program that generates text when you don't know what the text should be, so I manually wrote the code for the n=1 case. - Then I manually wrote the code for the n=2 case. - I started manually wrote the code for n=3. I got it wrong. This is trickier than I thought. Don't generate code; generate a model of the code: - I realized that what I really want to generate is a decision tree, then generate a Java code representation of the decision tree. - And I started thinking about sorting networks as an alternative to decision trees. I think I like the sorting network representation of a loopless sort better than a decision tree, so I went with it. (Google will help you learn what a sorting network is. See URL "http://www.google.com/search?q=sorting+network&sourceid=mozilla-search";.) - I think sorting networks are equivalent to decision trees, so everything in the slides still applies. - I manually produced sorting network for cases n=1,2,3,4,5. My naive sorting networks look like they implement Insertion Sort. - With sortings networks, it was pretty easy to see the repetion and to imagine how I might automatically generate a sorting network with an arbitrary number of inputs. I began thinking about writing the code generator. Hold on, big guy: - But I don't really want to write a code generator yet. I want to write a sorting network generator. (A code generator will produce a Java source code representation of the sorting network.) To build a sorting network, use simpler tools: - But I'm not ready to think about implementing SortingNetwork yet. I think a SortingNetwork can be represented as a graph. To build a sorting network, I should create a graph and add vertices and edges until it becomes a sorting network. - So I need a Graph implementation. I don't want to write my own, because I'm sure someone else has already done it and tested it. I'll use the one from the Graphs lecture on the syllabus page, or I'll steal one from somewhere else. - Or maybe I won't implement it as a Graph at all. I also imagine a sorting network as a list of wires and a list of connectors between the wires. Sorting netwonk: - I thought about a SortingNetwork object. First, I thought about the things I would want to be able to ask it to do for me: - Construct an empty version itself, when I tell it how many inputs it will have - Print itself in the usual way, so I can debug it when I get it wrong. That's as far as I've gone so far. Here's what's left: - Maybe find a Graph library and learn how to use it. This one might work: "http://openjgraph.sourceforge.net/";. - Maybe build a generice Network class, which would be the building block of a SortingNetwork. - Write some SortingNetwork tests. - Implement a SortingNetwork class. When all the tests pass, I'll know I'm done writing my SortingNetwork. - Write a code generator class. The code generator will: - Read the input from the command line. - Create a SortingNetwork. (The code generator thinks this is easy: a SortingNetwork knows how to create itself properly.) - Somehow map a SortingNetwork to Java code. - Produce and output the Java code. -- Richard Kasperowski (mailto:[EMAIL PROTECTED]) Tel: 617-576-1552, Fax: 617-576-2441 http://www.altisimo.com/
