Re: Proving or disproving new search algorithm is better than binary search.

spaceman wrote:
The goal is for me to practice writing a paper - I want to publish.

Patricia is right in suggesting you look at papers in the journals or
conferences where you want to publish. The style of papers there will
show you what to write and how to write it. Immitation is not only a
good form of flattery it's a good way of becoming part of a clique.
From what you've written you've only had a sample of 1 paper
before--not much to imitate, and certainly not a broad look at
different papers and writing styles, all of which are appropriate to
different jouransl and conferences.

Now, to your specific question. Sy you are wiriting a paper on a
search algorithm. If I were reading it, I would expect to see several
things.

First, a description of what the problem area is and why it is
interesting and important to solve. Perhaps, you developed your
search algorithm to find a specific truck with specific cargo using
GPS information on the trucks' locations and cargo manifests. Or
perhaps, your search works on poaitive integer numbers in an unsorted
array with duplicates. Show a case where you have a problem with data
organized that way.

Second, if there is some theory and notation commonly used for your
problem, you need to show that, often by reference to a textbook on
the field. In the compiler field, most papers say assume the notation
used in Aho, Hopcroft, and Ullman (the dragon book) and then give some
specific notations useful to the paper itself.

Third, if there are theoretical underpinnings to your work, you may
also need to give some proofs of major results. Perhaps, some aspect
of geometry makes your GPS algorithm work. If you discovered that
aspect and it makes your algorithm work, show the reader a proof. In
my opinion, a well-written paper does this twice actually, a casual
eay-to-read description of the result being proved, so that a reaqder
can uncerstand the result without reading the proof, and a proof in a
rigorous method, so that the serious reader can check out the details
of the proof, especially if the result seems surprizing (and thus
suspect).

Fourth, a pseudo-code description of the algorithm. Something that I
could take to my favorite computer and re-implement. This is often
mixed in with the proof portion, as these are the body of your paper
and what people reading it are try to get.

Fifth, if there are practical aspects to the problem, some
measurements of how the algorithm actually worked on some sample
problems. Depending upon your subject area, there may be standard
problem sets that are generally solved. For example, I read papers on
network intrusion systems, and such applications amost always use the
Snort pattern set and the darpa databases for their test data. For
compiler optimization work, there is the spec benchmark. If there is
another paper on this same kind of seach, try to reuse the sample
problem set those authors used.

If there isn't another paper on the same topic (more about this in
point six), you will have to invent a problem set. If you have to
invent one, you want one that you can run your algorithm on, and some
competitive algorithm to show that your algorithm has the desired
characteristics. It doesn't need to be any specific size, but you do
want it to be large enough that your measurements show something. An
algorithm that runs for a few seconds may be enough, if you can
measure and show the speed difference.

However, the key thing about the measurements is that they show your
algorithm was actually implemented and tested. If you write an
algorithm for a super-computer and can't run it on a super-computer,
the readers can't trust that you know what you are talking about.
Thus, if you only have a PC, write about algorithms that are efficient
on your PC. Algorithms that speed up applications on PCs are perfectly
important and useful--in fact, more people will care if you make their
PC faster than if you make some computer they never use work better.

Sixth, you also should compare to previous work in the field. Note
that if there are no other papers in the field this will be difficult.
That should also tell you something else, no one else may care about
the results. That goes back to the reading of published papers ideas.
The easiest and best way to come up with a paper topic is to read
other papers. There will usually be something in the other papers you
read that you can do simpler or better or differently. When you find
that, you have your paper topic, and an example of how your paper
should look etc. The paper sill also have a reference list of other
papers that the authors used, and those are more things to read.
Moreover, since the paper got published, you know that the authors
were interested in the topic and so were the reviewers. Thus, you
have a target audience.

Seventh, you should have some ideas of future directions. That guides
the person reading your paper to somethings that they might
investigate. what aspects of the problem are not yet solved and would
be good if they were solved?

Finally, your paper needs references and a bibliography. What papers
contained the ideas your paper is extending? What papers should
people who are interested in the topic area read? Again, if you write
a paper on a topic area where you've read a paper, that gives you some
idea of the relevant bibliography. Moreover, the paper you read that
gave you the idea you are pbulishing on should definitely be in your
bibliography. And, if you are publishing a paper on a topic where no
papers have been written before, good luck, you have picked the
toughest course possible.

One last comment, a lot of papers are written on work sponsored by
grants. That is someone paid someone to do the research. That's
actually part of my job, handing out money to people who do research
that my employer is interested in. If you want to make a living doing
this, finding out which problems other people want solved is
important, since that's how you will get them to pay you. Again,
seeing what papers are being published is a clue in that direction.
.

Relevant Pages