How 'bout an Algorithms forum?

[David Weitzman]

There's plenty of talk at the Ranch about OO programing and web programing and Java, but there doesn't seem to be a great place for down-and-dirty discussions of cool stuff like heuristics, writing parsers, genetic algorithms, artificial intellegence, etc., etc., etc. Some algorithm stuff could be put in Performance, but that's not really the right place for most of it.
Yay or nay?
[ June 15, 2003: Message edited by: David Weitzman ]

[Thomas Paul]

Ya know... I just don't think gravity is that cool.

[David O'Meara]

Gravity sucks.
My only experience with the funky-algorithm stuff was solving the Travelling Salesman Problem using the Simulated Annealing Heuristic (and it looks great animated), but most of the general algorithm stuff that turns up at the Ranch fits into either Pefformance, or tends to wander into Patterns or one of the JiG forums.
Can't say I've seen a discussion that was really algorithm-specific enough to point to a new forum... In general, yep there should possibly be one, but the general greenhorn is lucky if they can poke polynomial performance with a stick.
I've run out of things to say now.
Dave

[Thomas Paul]

There is no such thing as gravity... the earth sucks.

[Cindy Glass]

What about "General Computing"?

[David Weitzman]

Issue one: How can anyone not like gravity?! Issac Newton seemed to think it was cool. Bottom line: it keeps you from falling off the Earth and spinning into frigid/scalding oblivion.
Now that that's out of the way...
How about just renaming the Performance forum to Algorithms and Performance? There are Java performance issues that don't have to do with algorithms and a whole truckload of algorithm issues that don't have to do with performance, but overall it's a good match. It's not like the Performance forum is getting more traffic than it can handle right now.
Such a forum could hold things ranging from "Recursion vs. Iteration" to "Will JIT optimize this?" to "Tutorial >> 96 different ways to solve the Travelling Salesman Problem".
General Computing doesn't appear suited to algorithm discussion based on its description: "operating systems, applications, hardware, drivers, features, etc. General computer use stuff."
New thoughts?

[Jim Yingst]

Gravity... is a harsh mistress.
Hmmm... Performance and Algorithms has some potential, I think. Since there's often significant crossover between the two, and Performance is generally a pretty low-volume forum anyway. It does make some sense that we identify one forum as most appropriate for general algorithm questions - as it is now they're spread over more places than necessary. If P & A takes off too much, swamping non-algorithmic Performance questions, then we could create a separate forum for Algorithms. Until that point, P & A seems like a good fit to me. Other opinions?

[Michael Ernest]

Every once in a while a forum idea comes along that everybody wants to read. I think the real question is, who will write?
The thing about performance is that, at its very best level of discourse, it represents an unending puzzle. At its worst, it degenerates into "why isn't my code fast?" With algorithms, the subject is even more abstract, and I know for myself if people post 400 lines of code and the phrase "please comment," I'll run screaming to Blatant Advertising.

I'm sure Jim could add some grist, if he's not already slammed with other sheriffing. Who else among us qualfies as a credible, content-generating fool for algorithm/heuristic discussion? Hell, who here knows the difference between an algorithm and a heuristic? (Map: no fair googling the answer).
[ May 22, 2002: Message edited by: Michael Ernest ]

[David Weitzman]

With algorithms, the subject is even more abstract, and I know for myself if people post 400 lines of code and the phrase "please comment," I'll run screaming to Blatant Advertising.

People who post bad questions will not get answers and all will sort itself out. Ultimately most questions tend to come from people who don't know how to approach the problem in the first place.

I'm sure Jim could add some grist, if he's not already slammed with other sheriffing. Who else among us qualfies as a credible, content-generating fool for algorithm/heuristic discussion? Hell, who here knows the difference between an algorithm and a heuristic? (Map: no fair googling the answer).

I get the impression that you're not an algorithm person. While it can be confusing at times, I find that seeing some of the elegant solutions to problems leaves me with a "That's not so hard. Why didn't I think of that?" feeling.
I'm sure a list of qualified persons could be generated if necessary. Mark Herschberg jumps to mind as being well-versed in that sort of thing (cryptography in particular might lead to some interesting discussions). For that matter anyone with a degree in CS could probably do a decent job.
By expanding the scope of the Performance forum it would be possible to simultaniously improve the usefulness of it while clearing out some of the mish-mash of Java in General.
Why does Orion have its own forum while JBoss doesn't? I don't know the particular reasons. Why do most of the questions in the Programmer Certification forum fail to mention certification? Habit I suppose.
Why doesn't one of the most fundamental, universal (we're talking beyond OO here), timeless, unavoidable aspects of programming have its own forum? It must be oversight. Algorithms must be an area that the JavaRanch community needs to work on.
Once you know how to read the manual, some of the JavaRanch forums may seem unnecessary. The elusive game of Algorithms, however, will always be able to challenge both the best of the worst and the best of the best.

[Michael Ernest]

Originally posted by David Weitzman:

I get the impression that you're not an algorithm person.

Leaving that impression is my little way of saying I for one won't be jumping into this feet first trying to educate people. I'm doing that much now in Distributed, and it's tough going. A healthy forum needs writers to read, that's erally all I was trying to get across.

[Thomas Paul]

Originally posted by Michael Ernest:
Hell, who here knows the difference between an algorithm and a heuristic? (Map: no fair googling the answer).

A heuristic is a very hairy person and an algorithm is an insult meaning that you dance just like Al Gore.

[paul wheaton]

I'll create the forum in the Engineering section if somebody will promise to promote it (outside of JavaRanch as well as inside) and make sure it is full of discussion.
As Mike mentioned - this is a topic that I don't see people spending a lot of time talking about. It is an interesting topic, but I'm concerned the forum will be dead. Somebody that is willing to put the time into it can make it fly - but it isn't going to be easy!

[Jim Yingst]

Well, I'm not volunteering either for extra duty promoting Algorithms as a separate forum. Though I would certainly read it, and probably participate. But if it's annexed on to Performance (a fairly low-volume forum as well) then Algorithms would have an opportunity to grow naturally - we can just shift algorithm-related discussions there as they occur elsewhere. If the discussions don't take off, that's OK too.

[Mapraputa Is]

The reason why people do not talk much about algorithms is easy: they do not need to. How many times have you written your own sort program? There is always one ready to use. All databases have sorting service, heck, even Micro$oft Word have "Sort..." options! In 99,99% cases precooked algorithm will make you happy.
Having said that... "...The elusive game of Algorithms, however, will always be able to challenge both the best of the worst and the best of the best." - I like it! There wont probably be a lot of traffic, but if we simply add "algorithms" to "performance" forum, as Jim proposed, it wont be a problem.
Algorithm and a heuristic... tough. Here is what came to my mind... An algorithm is guaranteed to work and a heuristic.. perhaps. An algorithm has some formal proof in its background and a heuristic doesn't. If there were an algorithm capable to solve a problem in acceptable time there wouldn't be a need for heuristics. An algorithm is written by a computer scientist and a heuristic by anybody who tries to solve a problem. Heuristic is a cheap dirty version of algorithm, in use when you are too stupid to implement correct version.
All the definitions above are based on my experience. Once I needed algorithm to "normalize" Russian words - they have up to 36 different forms and you can imagine what a simple keyword search returns. :roll: I saw a decent algorithm in a book, but it was just too complicated, tedious and time-consuming for me to program. So I simply tried several most frequent variable parts and calculated how well they discriminate the forms. It was a linguistics barbarism and atrocity, but finally it worked correctly in 80% of cases and the rest was entrusted to a woman with a degree in philology to sort by hand. This way we both felt as useful members of society. Of course, we called it "a heuristic" :roll:

[Mapraputa Is]

Hm... Thinking about algorithms, I remembered Huffman encoding trees I was reading recently, and then it occured to me that UTF-8 is nothing but Huffman algorihm implementation!

[David Weitzman]

Heuristic is a cheap dirty version of algorithm, in use when you are too stupid to implement correct version.

A heuristic need not be any easier to understand than a 100% accurate algorithm. It may simply run faster.

[Mapraputa Is]

... or gives acceptable approximation?

[David O'Meara]

Originally posted by Mapraputa Is:
... or gives acceptable approximation?

That's what I was going to say, it's a bit hard to program 'near enough' into a greedy algorithm
Heuristics allow us to give solutions to Non-Polynomial problems in a realistic timeframe, as long as you are more concerned about getting an answer rather than the exact solution.
Like solutions to the TSP (Traveling Salesman), when I was doing stuff for it, solving for 20 points bute-force would take till the end of the universe, but it could make a guess at a good answer for 600+ points in a few minutes and animate it too.

[Mapraputa Is]

Hm... Michael, have you tried to Google for heuristic? Surprisingly, it's more challenging task than to come up with my own definitions.
The best I found is:
"Based on or involving trial and error. (2) Convincing without being rigorous"
Then I switched to my native language to resort to the ultimate source of wisdom - "Big Soviet encyclopedia" (they put it on the Internet! ) and here we are:
"Using heuristics reduce calculation time compared to the method of full looking over all possible alternatives, the results aren't usually the best, but only acceptable, applying heuristics methods do not always ensure solving a problem."
See - I was right!
P.S. David O'Meara post makes me think that we need a forum on algorithms...

[David O'Meara]

For that matter anyone with a degree in CS could probably do a decent job.
I feel I fall into this category. Most of the Algorithm stuff was studies-related...
From www.dictionary.com

Computer Science. Relating to or using a problem-solving technique in which the most appropriate solution of several found by alternative methods is selected at successive stages of a program for use in the next step of the program.

[David Weitzman]

Quote from Mapraputa Is:

"What keeps us on this globe except force of gravity?"
Stanislaw Jerszy Lec. "Unkempt Thoughts"

There's no getting around it. Gravity is cool.

[Mark Herschberg]

Wow, someone thinks I know something. Even better, he spelled my name correctly! (bonus points :-)
Seriously. I like the idea of algorithms, but I think for now it belongs in performance, until demand is shown. I think we should consider a rename of the forum to "Performance & Algorithms." I actually consider that to be one of the more interesting forums, and I'm a little disappointed that there's not more traffic there.
For the record, I've forgotten ever algotihm I've ever learned. Well, close to that. Usually when I need an algotihm, especially searching and sorting, I just check the CLR Algorithm's book. Thankfully, I did learn the meta-lesson in my alogrithms class, so I may be useful afterall.
I generally think of a heuristic as a trial and error derived guide. I would've gone to dictionary.com, but I see David O'Meara beat me to it.

--Mark

PS

Thomas Paul wrote:

A heuristic is a very hairy person and an algorithm is an insult meaning that you dance just like Al Gore.

Augh, that was horrible! My compliments :-p
[ May 27, 2002: Message edited by: Mark Herschberg ]

[Ilja Preuss]

I would have said that a heuristic is an algorithm which doesn't ensure that it will always give the correct result.
Regarding the original topic, I think an "Algorithms and Performance" forum wouldn't be a bad idea.
[ May 27, 2002: Message edited by: Ilja Preuss ]

[David O'Meara]

But (for example) I would see many formulas that won't return the best solution as 'algorithms' rather than heuristics, such as the 'Nearest Neighbour' method for the TSP (again).
I tend to see Algorithms as a 'greedy instruction set' - based on the greedy algorithm itself. At each stage it makes a decision on how to act based on a number of possible choices, but how this decision is arrived at is deterministic. Under the same conditions it will make the same choice every time.
There's a level of uncertainty, diconnection, nondetermanism or randomness involved in heuristics.
The 'Simulated annealing' solution to the TSP uses the simulation of crystal growth to solve the problem. A path is free to move into if it desires for no real reason, but the chance it will take a 'bad step' is reduced as the process continues.
Genetic algorithms allow two solutions to be merged in a random way, then the output is given a chance of survival based on the new state...
Do we need to go back to study notes?

[Ilja Preuss]

From http://music.dartmouth.edu/~wowem/hardware/algorithmdefinition.html:

Heuristic methods have sometimes been contrasted with algorithmic methods for finding problem solutions, and a certain amount of intellectual blood has been shed unnecessarily on this battlefield. Without getting into the subtleties of the disagreement, we observe that the term "algorithm" is used with considerable ambiguity in mathematics and logic. Under one commonly held definition, algorithms are decision procedures which are guaranteed to produce the solution being sought, given enough time. . .

Mhh, seems to me that with the suited definition of "solution being sought", every heuristic can be seen as an algorithm...

[Michael Ernest]

Such is the way of all important ideas in academic exercise. There is a denotative meaning, which no one really argues with, but finds rather boring: 'algorithm' is really for mathematicians, 'deconstruction' a specialized toy for one branch of postmodern literary critics, just as 'conception' is a biological concept. As clinical terms, these words have little worrisome baggage. It's in their appropriated ("connotative") state they become contentious.
At the heart of each tensions resides an unintended user community whose demands on the words derive from pre-conceived, sometimes orthogonal agenda (You can tell I'm going to be on this "effect precedes cause" thing for a while). In computing, solutions are good, but solutions with known, finite computational costs are the real prize. The notion of repetitive operation appeals to them, so they look to algorithms even though they are not strict mathematicians. In literary analysis, deconstruction seems to mean "dissembling the text" if you are a New Critic, demonstrating the text's self-cancelling nature if you're a reception theorist ("a text means whatever you bring to it"); or it's a proof of literature's propagandistic agenda, if you are a blithering idiot with tenure. Finally, conception a scientific meaning that isn't nearly as tortured as the "legal" meaning of conception, where it's nothing more than a line in the sand at the steps of the Supreme Court.
So for people interested in computation, the idea of an algorithm has to be bent and problematized to be useful. My dictionary says an algorithm is "a rule of procedure for solving a mathematical problem...that frequently involved the repetition of an operation." For heuristic I have "serving to guide, discover, or reveal, specifically, valuable for empirical research but but unproved or incapable of proof."
There are two good reasons alone for keeping a 35-year old dictionary around: a less contemporary perspective can shed a lot of light.
But back to the main point, a programmer's idea of an algorithm isn't often even Donald Knuth's idea of an algorithm, which I think every programmer should be required to recite before they're passed on to us as informed practitioners. The vast majority of programming effort is, by these definitions, heuristic, for the simple reason that most programs never go to the trouble of proving the validity of their results.
[ May 27, 2002: Message edited by: Michael Ernest ]

[Mapraputa Is]

Funny, I have the same feelings about "algorithm" definition. They now teach informtics in schools in Russia, and I wondered what exactly do they teach if 1) obviously it's impossible to educate enough teachers for a short period of time 2) most schools (outside of big cities) do not have anything that looks like computer So what do they teach? I looked at the syllabus and what did I see? Of course - "definition of algorithm"! :roll: I can imagine this kingdom of boredom...
Since then "definition of algorithm" is my favorite swear expression
[ May 27, 2002: Message edited by: Mapraputa Is ]

[Mark Herschberg]

Originally posted by Ilja Preuss:
I would have said that a heuristic is an algorithm which doesn't ensure that it will always give the correct result.

Originally posted by David O'Meara:
I tend to see Algorithms as a 'greedy instruction set' - based on the greedy algorithm itself. At each stage it makes a decision on how to act based on a number of possible choices, but how this decision is arrived at is deterministic. Under the same conditions it will make the same choice every time.
There's a level of uncertainty, diconnection, nondetermanism or randomness involved in heuristics.

A lot of algorithms in crypto are probabilistic. Your security is quite likely based on such schemes.
--Mark

[Donald R. Cossitt]

The coolest thing about 'gravity' is that whether I understand this stuff or not - it works!