... and now I'm thinking that a sorting network is *not* the way to go.
My sorting networks will always do O(n^2) comparisons. The decision
tree solution will do O(n) comparisons in the best case, so I'll pursue
decision trees.
--
Richard Kasperowski (mailto:[EMAIL PROTECTED])
Tel: 617-576-1552, Fax: 617-576-2441
http://www.altisimo.com/
--- Begin Message ---
> 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/
--- End Message ---
