Talk:Algorithm

Missing image Cscr-featured.png Featured article star

Algorithm is a featured article, which means it has been identified as one of the best articles produced by the Wikipedia community. If you see a way this page can be updated or improved without compromising previous work, feel free to contribute.

---

Contents

1 Basic Definition of the Algorithm 2 Introductory Material 3 Formalized Algorithms 4 Vegnere Cipher 5 Standardized Pseudocode 6 Computer-Science Bias 7 Algorithm Removal 8 Ease of Understanding 1 Choice of Example 1.1 Question on Etymology 1.2 Good Examples 1.3 Reworked the First Paragraph 2 Example algorithm is flawed ... 3 References 4 Link suggestions 5 Etymology

Basic Definition of the Algorithm

I removed: "Some people restrict the definition of algorithm to procedures that eventually finish, while others also include procedures that run forever without stopping." Because, A) its opinion. B) its moronic.

It is not opinion, it is fact. Some people do indeed restrict the term in this way. AxelBoldt 16:55 Jan 4, 2003 (UTC)

Havent you ever heard "non-deterministic algorithm"?? this has been used since the 1950s.

Imagine this algorithm:

  while 1:
      a = random integer from 0 to 10
      if a < 5:
         quit

Thats a set of repeatable steps. yes, the results will be different each time, but its still an algorithm. This is too simple to have a debate on.

Lot's of people will disagree that this is an algorithm. You can't implement it on a Turing Machine, for example. AxelBoldt 17:02 Jan 4, 2003 (UTC)

I agree that this is moronic, but I'm afraid AxelBoldt has a point about many people using it this way. This distinction even makes it into a footnote in the not that technical book Darwin's Dangerous Idea (p. 52). --Ryguasu 05:29 Jan 12, 2003 (UTC)

I just want to add that non-deterministic, applied to algorithms, does not mean non-terminating. Non-deterministics processes are ones that arrive at the set of choices, from recurring multiple choices, straightaway. That is, behavior is as if they make the right choice every time. This overcomes a problem with deterministic processes where a number of very bad choices done first can lead to expenditure of extreme effort, and for some methods there is no perfect first choice. (The famous P = NP question is about a comparison of certain kinds of deterministic procedures and non-deterministic procedures for the same problem.) --Orcmid 01:45, 12 Mar 2004 (UTC)

Hmm, I also want to add that if the random integer procedure uses some source of input not given at the start (say some source of thermal noise), the procedure doesn't qualify as an algorithm either, in the usual strong sense. That is, algorithms of the kind that are the usual focus of attention are ones where all inputs are known in advance and someone could sit down and produce exactly the same result from the given initial input and the procedure. For a human procedure, you could probably ask the person to throw dice and other things, but there is some question whether this would qualify, even though it can certainly be carried out. This strong sense of algorithm is not meant to rule out other (computational) procedures, and many computational procedures realized with computers are not algorithmic. There's no shame. Donald Knuth gives some additional categories in Chapter 1.1 of The Art of Computer Programming, and that is probably a perfectly usable separation. --Orcmid 01:45, 12 Mar 2004 (UTC)

Introductory Material

The introductory paragraphs contain this statement:

Correctly performing an algorithm will not solve a problem if the algorithm is flawed, or not appropriate to the problem. For example, performing the potato salad algorithm will fail if there are no potatoes present, even if all the motions of preparing the salad are performed as if the potatoes were there.

I would like to introduce some related machinery here. My draft goes on too long so it might belong in something else or a subordinate topic. At the same time, I propose that it is useful to honor this in what is written, even if it is left tacit.

Note: I notice that I have improved the separation of algorithm from procedures, but I have still left some ambiguity between a procedure as carried out, and the description of the procedure in a script, recipe, or other writing down of the steps to follow. That matters because the expression of the procedure is to be finite though the carrying out of the procedure is a different story and an algorithm is expressed only when the procedure always completes in a finite number of steps for all valid (well-defined and finitely-expressed) inputs. It is important to sharpen these distinctions because computer programs are expressions of procedures, and it is the the procedure that may or may not be algorithmic. (As I read that, I wonder if it is worth pursuing, unless one can show that careful use of such hair-splitting language clarifies things enough. It needs to be developed further to see, with honoring of the common usage of these terms as much as possible). --Orcmid 21:35, 17 Mar 2004 (UTC)

First, I would start by saying

Correctly performing the procedure will not solve a problem if the procedure is flawed or the algorithm implemented using the procedure is not appropriate to the problem.

I don't have a problem with the hypothetical potato-salad algorithm, though I can see adding

For example, if following the procedure given as "the potato salad algorithm" produces macaroni salad, we know that the procedure is defective (as an algorithm for potato salad). And if the procedure is impossible to follow, or doesn't reach a point of conclusion, we would question whether that procedure delivers an algorithm for anything, let alone potato salad.

Next, it is useful to point out, especially for the young reader, that

We often speak of a particular procedure as realizing an algorithm without concern for what it accomplishes under what conditions, although the recognition of the correctness of an algorithm involves establishing that it satisfies a well-defined purpose with specific input conditions. In too many cases, the purpose of the algorithm is omitted from its name, and some notable algorithms are simply named for the people who codified them.

Some well-known algorithms are Euclid's algorithm (for the greatest common divisor of two numbers), the Sieve of Eratosthenes (for finding prime numbers), Newton's method (for solutions of certain equations), Dijkstra's algorithm (for finding least-cost routes in a network), Warshall's algorithm (for problems to which Dijkstra's algorithm is also applicable), and many more. Other algorithms have been given names that reflect the procedure as well as the purpose: Bubble Sort, Quick Sort, Radix Sort and Merge Sort; Binary search and Hash Lookup. [more Wikipedia links here would be very cool]

Some algorithms are so well-known and familiar that we don't recognize them as such. The procedure printed on the back of bank statements for balancing a checkbook is algorithmic. When a discrepancy arises, it is because of an error following the procedure or in our or the bank's records. The importance of the procedure's use in a valid algorithm for check-book balancing is that any discrepancy is a reliable clue that the problem is in the data or our following of the procedure. If we also have doubts about the validity of the procedure and wonder whether there is a "bug," trouble-shooting a discrepancy is now much more problematic. We often rely on algorithms, including ones realized via computer software, that we do not know how to derive or confirm ourselves. Normally, we take as confirmation having experiences consistent with the procedures being correct.

The most well-known algorithms are the ones we learn as children. The procedures for arithmetic -- addition, subtraction, (long) multiplication, (long) long-division, and so on -- are all algorithmic. These highly-practical algorithms are valuable because of their simplicity. We can count on them and they provide numerous ways for our checking each others work and in finding errors of calculation.

A pocket calculator has comparable, though different, procedures for achieving the same arithmetic results. Because we cannot observe the calculator's procedure, and we use the calculator for operations that we might not know how to duplicate ourselves, it is extremely important to be able to trust that the calculator implements reliable procedures for confirmed algorithms and that it delivers the functions that it is specified to calculate.

We can see that there may be many algorithms that satisfy the requirements of a given problem (the two approaches to Towers of Hanoi would be excellent here). Determining that one has successfully arrived at an algorithm for the desired problem and also determining how good that algorithm is in terms of simplicity and efficiency has led to a body of study known as Analysis of Algorithms.

OK, that's enough for now. I don't know where I would introduce random procedures (for testing primality, for example) as heuristics that can be far more efficient than known algorithms, and how to relate to that. To go deeper, we might also need to broach the notion of what can be done by not requiring an algorithmic approach to a problem, and recognizing that interactive behavior of computers may be algorithmic in the procedures that are applied although the overall interactive process is not itself algorithmic. I think these topics can be acknowledged, but not this close to the front. --Orcmid 23:19, 13 Mar 2004 (UTC) updated by Orcmid 21:20, 17 Mar 2004 (UTC)

Formalized Algorithms

Well, I went and read through some of the early material. There is a "Thus ..." that ends with "Turing-Complete system" that is off the mark in two regards. 1. There is nothing to make "Thus" follow, here. Also, the reference to "Turing-Complete" is very tricky, appeals to knowledge that we don't want to presume, and might even be misleading for those of us who think we know what that means.

Oh. I see the problem. In this paragraph, computer programs are equated with algorithms, rather than with procedures. It is important to remember that not every procedure is an algorithm. Furthermore, not every computer program is even a procedure in the sense required before the satisfaction of the additional conditions can be considered. The particular conditions that a procedure must satisfy to be the procedure of an algorithm are stated well enough in the first paragraph of the article. I don't think we should mess with that. One might say that an algorithm consists of a certain form of procedure plus some other things. In addition, not every computer program is a procedure of the certain form required by the definition of algorithm! (I will leave that as a puzzle for the reader for now. Hint: The procedure that a universal turing machine follows is not an algorithm. Well, that's accurate but not such a great hint. Consider ordinary computers and the impact of input-output operations and using new inputs as part of manipulation of the procedure itself. That's a better hint.) --Orcmid 01:30, 15 Mar 2004 (UTC)

There is some work called for here. For starters, it is not the case that every procedure embodied in a Turing machine is an algorithm. That is not an equivalence. It is the case, for a certain class of problems, there are algorithms for them, and there are Turing-machine representations of those algorithms. But not every Turing machine illustrates, represents, or embodies an algorithm. Maybe that wasn't meant, but it is too easy to read that claim into the text as written. --Orcmid 02:56, 12 Mar 2004 (UTC)

Vegnere Cipher

Where does the new cryptographic algorithm that is supposed to be unbreakable and was developed by a faculty member at M.I.T., I believe, belong here. It works by keys picked up from some random source, like a satellite, that are processed in the encryption but never stored anywhere. The inventor has proved that it is unbreakable with current computational power, and no one contests this apparently. Do you know what I am referring to? RoseParks

Yes, but it isn't really an encryption algorithm itself so much as a novel means of key exchange. Most modern cryptography techniques are like that: everyone has known about one-time pads for a long time, and that they are unbreakable. Modern techniques like RSA and Diffie-Helmann are just ways to safely exchange keys, which can then be used as one-time pads. RSA and DH key exchange protocols can themselves be broken, while professor Rabin's method theoretically cannot be, but it is not yet practical for other reasons.

Thank you. You may remove or do what you want with this. Perhaps other people have read about it and could use your explanation on these pages...maybe a page itself, or somewhere on these pages. RoseParks

Most of the discussion above is pretty confused. Rabin's method isn't theoretically unbreakable, RSA and Diffie-Hellman are essentially never used to exchange one-time pad keys, RSA is not normally thought of as a key-exchange protocol, properly applied RSA may in fact be impossible to break, etc. But I don't have the time to write a section on cryptography just yet. --Kragen

Standardized Pseudocode

I think it would be a great idea if we came to some sort of standard on writing pseudocode. I've used a sort of hybrid procedural style for the algorithms in Linear search and Binary search but I'm wondering if there's a better standard out there. Can we borrow a style from a textbook like Intro to Algorithms? (is this copyrighted or is style a public domain thing like an idea?). Only a fairly small set of control structures is needed -- something to define functions, if-statements, loops, list access, mathematical operators and probably a few more. Comments? Mark Jeays

I do think we should try to do standard pseudocode. I have no idea what that pseudocode should be however. CLR's style is usually clear, but sometimes I find it confusing (often because I do not parse the A <- B assignment syntax properly). I don't think things like pseudocode style are copyrightable... We should make a pseudocode article that defines whatever we use (in addition to explaning what pseudocode is in general), then link to that from every pseudocode example. In addition, we could include examples in other languages (see bubble sort for example) by putting them in subpages like [[:bubble sort/C++|bubble sort/C++]]. --BlckKnght

Robertson L.A, has released a book which attempts to standardise Pseudocode by specifying pseudocode words (READ, GET, DOWHILE etc) in a book "Simple Program Design - A step by Step approach" Nelson Thompson Publishing 2000. The Pseudocode examples are close enough to most High Level Languages so as to easy to translate to any language.

We definitely need code samples for all the algorithms; I think there should be one language (pseudocode or otherwise) on the main page, and implementations in other languages on subpages, as BlckKnght suggested above.

I think some executable language would be far preferable to pseudocode, for the following reasons:

• it's possible to test executable implementations of algorithms to see if they're buggy
• executable languages tend to be more rigorous than pseudocode; people writing in pseudocode tend to gloss over relevant details (like whether the range n..m includes n, m, both, or neither --- this is a huge difficulty with, for example, binary search)

My current favorite languages for this are Scheme, C, and Python.

Python is the most readable of the three; it reads like pseudocode itself. It's also the least standardized of the three, the most rapidly changing, and the one with the most "hidden" stuff going on behind the scenes. (arr.append(item) in Python may allocate new space for the array if the space it's in isn't big enough; that really screws with algorithmic complexity analysis.)

C is the most widely-used of the three, probably the one with the most complex and irregular syntax, the most standardized of the three, the least rapidly changing, and the one with the least "hidden" stuff going on behind the scenes. It's also the most verbose and the least readable for people who aren't familiar with the language or one derived from it. (Although, since it is so widely used, almost anyone who knows how to program is familiar with the language or one derived from it.)

Scheme is intermediate between C and Python, in my opinion, except that it is the least widely used.

For now, I'm going to add implementations in Python to the algorithm pages, and when I have time, I'll add implementations in C and Scheme on subpages.

-- Kragen

Kragen, have a look at the pseudocode page, we thrashed out a "standard pseudocode" for Wikipedia a while ago (though feel free to make suggestions/improvements). The trouble with providing actual implementations of algorithms in real languages is that the trees start to get in the way of the forest. This is less of a problem in Python and Scheme, of course. --Robert Merkel

Computer-Science Bias

An algorithm is not a rough form of a computer program. This is an example (among many) of the distinct Computer-science bias of the Wikipedia.

Not every computer program is an algorithm either, at least according to some of the definitions of algorithm.

I don't have a reference handy, but I have seen algorithm defined to mean, roughly, a finite set of rules that is supposed to produce an answer in a finite number of steps. Therefore, infinite loops (which can occur in computer programs) cannot occur in algorithms according to this definition.

This is, by the way, one of the motivations for the study of the halting problem. How do you prove that a certain method is in fact an algorithm?

Well, it is done one computational procedure at a time. I don't want to be facetious. I agree with the concern here, but we may be mixing too many things together. Maybe the lapse is one of carelessness on the part of computer scientists, though I think it is more of an overgeneralization by practitioners and in the teaching of programming, not so much hard-core computer science. Either way, I think there is a legitimate concern here.

I am concerned with the substitution of computer codes for algorithmic definitions also, though there is nothing that says a computer code can't implement an algorithm. (Be shown to terminate, clearly consist of well-defined operations and rules for their progressive carrying-out, etc.)

But one must be careful about taking a computer code as the expression of an algorithm. For example, there is more assumed in the Ruby illustration of binary search than meets the eye.

So what is to be done here, in this section, and in the expression/illustration of algorithms in Wikipedia? I wouldn't recommend an overhaul, though maybe some tidiness can be introduced. For example, the binary search section currently makes it clear that it is using Ruby as a means for illustrating an algorithm. Considering that it makes the idea of binary search pretty accessible, I would not complain.

Here in the section on algorithm, I would be more concerned. I also think that maybe procedure should be used in a lot of places, including binary search, and not over-use "algorithm" quite so much.

I have given longer expression to my concern in discussions around the notion that programs are rarely algorithms. I also have an in-progress article on the question "Do Programs Teach Algorithms (http://nfocentrale.net/orcmid/readings/R010101.htm)" that, as it happens, uses Binary Search (and Python) as a basis for discussion. --Orcmid 02:09, 12 Mar 2004 (UTC)

There is an important reason to preserve the strict notion of algorithm (and somehow allow the important informal notion of effective procedure to survive as well). It is not just historically valuable, it preserves important content. Many of the historical breakthrough results were produced using the strict notion of algorithm. When there is a relaxed use of the term, now, and those earlier results are repeated, they are implied to cover a wider territory than has ever been demonstrated. That leads to sloppy science and, potentially, outright error. I think we should be more prudent, but still find good ways to speak and write in an informal setting. --Orcmid 02:09, 12 Mar 2004 (UTC)

Algorithm Removal

I removed the following example algorithm, because I think it is incorrect. Starting with the words zzz,yyy,xxx, it will in step one produce yyy,zzz,xxx and then it will produce yyy,xxx,zzz and then it will stop. AxelBoldt 00:33 Oct 8, 2002 (UTC)

An example of an algorithm is this rule (or method or procedure) for alphabetizing a list of names by repeating the specified steps until the job is done:

• Step 1. Compare the first 2 names on the list:
  • a. If the 1st one is alphabetically ahead of the 2nd one, go to step 2.
  • b. If the 2nd one is alphabetically ahead of the 1st one, swap the two of them and then go to step 2.
• Step 2. Pretend the 2nd and 3rd names on the list are the 1st and 2nd ones, and repeat step 1.

No, it doesn't stop then -- you forgot to "repeat[] the specified steps until the job is done." The second time thru, you get xxx,yyy,zzz and then you stop, because "the job is done." -- isis 06:33 Oct 8, 2002 (UTC)

We have to formulate the algorithm clearer then. The whole point of an algorithm is to give unambiguous instructions for a process, and these are hardly unambiguous. Step two for instance talks about the 2nd and 3rd names, but doesn't say what to do if there is no 3rd name. I thought it should stop then, but you actually want a loop. If you say "until the job is done", does that imply that after each step 2, I have to scan through the whole list of names to check if it is already alphabetically ordered, and stop if it is? If so, the algorithm should say that clearly (and it wouldn't be bubblesort).

Also, please don't mark your edits as "minor" if you make major changes to an article. AxelBoldt 14:25 Oct 8, 2002 (UTC)

Ease of Understanding

The whole idea of an encyclopedia is to explain basic concepts to people who don't know anything about them, including (or especially) 10 or 12 year-old-olds. I respectfully submit that anyone who knows what a "greatest common divisor" is (and probably anybody who knows what an "integer" is) already knows what an "algorithm" is. It's okay to put in the stuff that reads like a math textbook, but before that you need introductory material for the ordinary people that are never going to read past that expanded definition in lay terms. What you should really do is write something dynamic that would show a bubble sort of a short alpha list that wouldn't take an explanation at all but would show the items swapping and bubbling up the list. -- isis 22:46 Oct 8, 2002 (UTC)

GCD and HCF are usually covered at junior school level (10-12). Integers are probably called "whole numbers" at that stage, but the concept is graspable. I'm not sure at what age one encounters a term like "algorithm". Later, I think. -- Tarquin 22:50 Oct 8, 2002 (UTC)

There's no question those concepts are taught in math classes at that level, but that's irrelevant to the topic under discussion. My point is that the purpose of an encyclopedia article is to define/introduce its subject to someone who doesn't yet know anything about it. Unless this article explains "algorithm" in terms someone who doesn't already know what one is can understand, it is useless for its intended purpose. Ordinary people (of any age, but I'm talking about only the U.S., and it may be different elsewhere in the world) don't know what GCDs and integers are, and they don't need to know what they are to understand what an algorithm is, so the article should be written (at least at the beginning, and you can put in the technical stuff farther down) in terms they do understand -- that could have been accomplished by using the example of putting a list of numbers in numerical order, for example.

But there's a larger issue I consider pertinent here, and that's that Americans are innumerate, not so much because they're incapable of understanding numerical concepts as that they've acquired a fear of math, and that's the fault of generations of math teachers who didn't understand or couldn't explain the concepts in terms that made them accessible. Those of us who are teaching math now (including teaching it thru the 'pedia) have an obligation to do better by the ones we teach, because math is so much more important a tool than it has ever before been in society. The more non-numerical examples we use to explain the concepts, the less math resistance we have to overcome, and the better (and easier) we get our job done. Therefore "word problems" of practical, everyday matters are better than sets of equations for illustrating mathematical principles, and therefore a list to be alphabetized is better than numbers to be sorted for explaining "algorithm," because it makes the readers comfortable with the concept before they realize it's math and resist it. (I have yet to see a 'pedia article on a mathematical topic that didn't look like it came from a math textbook instead of an encyclopedia.)

I find it interesting that encyclopedias do not seem to reflect your maxim about what encyclopedia articles are for. I think what you propose is laudable, however. How do we deal with the fact that algorithm is listed under Mathematics in the Featured Articles section? --Orcmid 02:41, 12 Mar 2004 (UTC)

So I respectfully insist that the example in this article needs to be of a simple sorting algorithm (and there is none simpler than a bubble sort, so I'm still voting for that) that anyone can understand. I'd like for it to be of alphabetizing items, because that would obviate math anxiety, but if it has to be numerical, make it something like putting checks or invoices in serial-number order. I'd like for it to be dynamic, showing the items swapping in pairs, but I don't know how to program anything that moves, although I've started introducing animated gifs to encourage contributors that do know how to animate illustrations to do so. It is ridiculous not to take advantage of the capabilities of this medium, especially when equations are so deadly dull, and instead of showing the transformations in a mind-numbing list of them, you could have the elements moving in and out of the equations on the screen, and the novelty of that would suck your readers in, so they would pick up the concept before they realized it. -- isis 00:17 Oct 9, 2002 (UTC)

I completely agree with you that the first example should be as simple and intuitive as possible, and sorting names is simpler than computing gcd's. I just didn't like the bubblesort description since it wasn't explicit enough. By the way, I always thought selection sort is simpler: pick the smallest element, put it at the top. Pick the next smallest element, put it at position two, etc. That's how I usually sort things.

Interesting. Bubblesort and selection sort are very closely related. For selection sort, you have to remember where the least element was found and exchange it with the leading element, or otherwise slide things. In Bubblesort, you bring the smallest element to the front by starting at the far end and comparing and exchanging adjacent elements as necessary so the smaller of the two is always moved forward and used in the next comparison. That way, when you complete a sweep, the least member is in the leading slot. Then, on the remaining unsorted n-1 elements, do it again, excluding the already-sorted elements. Rinse, repeat. (Termination condition is that nothing moved, or you can just go until there is only one element left - it will be the largest.)

I think selection sort animates nicely. It is also easier to illustrate as a paper-and pencil method where the sorted list is produced in a separate column. Bubblesort is a little trickier as a computer animation and is not very suitable as a manual procedure (interesting point). I like the Towers of Hanoi because there are two quite different solutions, the problem is easily understood, it exhibits combinatorial explosion, and also shows that (efficient) algorithmic procedures often do not resemble the problem they are solving in a clearcut way -- Euclid's algorithm does that too, more directly. This shows the difference between clarity/directness of solution and optimum effort, and raises important questions about trusting in algorithms we do not understand. I recommend that sorting illustrations be in articles on the specific algorithms, though. The current example of finding the largest element in a list works, although it would be nice to establish the initial conditions (at least one member in the list). One can raise the influence of data representation and use of available elementary operations with even this simple one, including transformation to a similar algorithm employing the same principle (finding the least instead, etc.) --Orcmid 16:39, 15 Mar 2004 (UTC)

As to your contention that Wikipedia articles are too technical for an encyclopedia: here is the start of Encyclopedia Britannica's algorithm article, (fair use):

systematic procedure that produces—in a finite number of steps—the answer to a question or the solution of a problem. The name derives from the Latin translation, Algoritmi de numero Indorum, of the 9th-century Muslim mathematician al-Khwarizmi's arithmetic treatise “Al-Khwarizmi Concerning the Hindu Art of Reckoning.”

For questions or problems with only a finite set of cases or values an algorithm always exists (at least in principle); it consists of a table of values of the answers. In general, it is not such a trivial procedure to answer questions or problems that have an infinite number of cases or values to consider, such as “Is the natural number (1, 2, 3, . . .) a prime?” or “What is the greatest common divisor of the natural numbers a and b?” The first of these questions belongs to a class called decidable; an algorithm that produces a yes or no answer is called a decision procedure.

And it gets worse from there; not a single example. AxelBoldt 00:33 Oct 9, 2002 (UTC)

Articles should of course start with good definition/introduction paragraphs that give a person of average intelligence a good idea what the subject is and why it is important but we shouldn't dumb things down to the point where articles are not useful to people who already know the basics. BTW, we should also aim to be better than Britannica in depth, breadth and accessibility by starting off with the basics and building from there. Just my 2 cents. --mav 00:37 Oct 9, 2002 (UTC)

As to selection sorts being easier than bubble sorts, I guess my age in showing -- I learned to sort in assembly language without matrix notation, and bubble sorts were much easier (at least for me) than selection sorts, especially because when there wasn't enough room to hold two lists of the given length (which was usually the case), the job would bounce instead of running, so it wouldn't be done when the assignment was due. I think most of us do use selection sorts in sorting alphabetical or numerical items that are physically separate (like file cards or cancelled checks), so I think that would be a good example to use, but I'd still like to have a dynamic image of the cards rearranging themselves, the way my Windows shows me my files flying from one folder to another.

Did you cite the Encyclopædia Britannica article because you meant to suggest it was worse than the current Wikipedia article? To me, it's not, -- it starts with a definition that is accurate, complete, and concise, something neither the first sentence nor the first whole paragraph of the current Wikipedia article does. Or did you mean to imply that if ours is no (or not much) worse than theirs, it's acceptable? Even if I considered EB the standard for encyclopedias (and I never have -- I've always preferred the Encyclopedia Americana to EB and Funk & Wagnalls to World Book, which were the standard reference books in libraries when I was in grade-school), I'd still like for the 'pedia to be the best it could, not just as good as the supposed competition.

So mav has expressed my position very well: Each article should start out with introductory material that explains to an average reader what the article is about and why it is important' and then segue into some more advanced material that will appeal to someone who already knows something about the topic (and then there may even be some advanced topics that appeal only to specialists). A reader who wants the basics will read only the introductory part (so it needs to be complete for that purpose), but that part should not be so simplified ("dumbed down") that it will offend the specialist who skims over it getting to the meatier part. -- isis 01:51 Oct 9, 2002 (UTC)

I gave the EB text because I consider it far worse than our article: they start out with saying "in a finite number of steps" which is wrong; then they enter the topic of table lookups for finite problems which is completely besides the point, and then they go right into primes and gcd's without a single example algorithm. And I don't find the definition "systematic procedure that produces—in a finite number of steps—the answer to a question or the solution of a problem" any better than "well-defined method or procedure for solving a problem, usually a problem in mathematics or otherwise relating to the manipulation of information". AxelBoldt 02:45 Oct 9, 2002 (UTC)

Whoa! You threw me. Why do you say "in a finite number of steps" is wrong. They are not implying a fixed number of steps, only a finite number. It is common to require that an algorithm (not every computational procedure) terminate. Since the steps are discrete, that kind of means you can count them, and when the algorithm terminates given a particular input, you can read the counter. Any example of sorting, for example, given a finite input (also a requirement in most definitions of algorithm) had better be one that terminates on any valid input or we would throw it out as an algorithm for sorting. --Orcmid 02:19, 12 Mar 2004 (UTC)

Well, as the saying goes, "There's no accounting for tastes." -- isis 03:03 Oct 9, 2002 (UTC)

Choice of Example

We need a different algorithm for the example; this Euclidean GCD one is too unintuitive. I have a master's in math, and I can't figure it out, so I know ordinary readers can't follow it. -- isis 20:54 Oct 27, 2002 (UTC)

How about the trial division prime testing algorithm, or maybe one of the bin-packing algorithms ?

How about the sieve of Erathosthenes? okay, so it's infinite, but it's a simple prodecure to explain, it's clear how & why it works, and you can limit it to, say, numbers up to 100 so it terminates. I remember doing it at age 10 or so. -- Tarquin 21:09 Oct 27, 2002 (UTC)

I have no idea what that is, but it sounds dirty -- let's do it. -- isis 21:17 Oct 27, 2002 (UTC)

Sieve of Eratosthenes --Imran 21:35 Oct 27, 2002 (UTC)

I'll tell you what: You go out to a shopping area, a mall or downtown, and stop 10 people at random and ask them, and if as many as five of them know what a prime is, I'll agree to this one. The problem I'm having is that the purpose of an example is to clarify things for somebody who's looking the topic up because they don't know anything about it, and none of these mathematical concepts (like "divisor" and "prime") is part of most people's vocabulary, not to mention mind-set. I still say this needs to be an algorithm for something ordinary people understand, like alphabetizing or (if you can't live with its not being numbers) counting or sorting. -- isis 21:52 Oct 27, 2002 (UTC)

Sorting is a simpler concept, but is actually a more complex algorithm in terms of the actions involved and what they do. The sieve is easy: you just write the numbers down then cross them out. It's clear that it works, because when you cross out 2,4,6,8, you're removing all the multiples of 2. I think the explanation on Sieve of Eratosthenes could do with a rewrite though. Some 20% of the shopping mall people will be illiterate, but we're not dumbing down our long words here for them. We must make articles accessible to the intelligent lay-person. That means someone who can look up "prime" and "divides" and quickly grasp the concept. Like I said, it's 10-year old maths: I clearly remember doing it. If people are so innumerate that they forget this stuff ... *sighs in despair* -- Tarquin

I agree with Tarquin, I certainly recall knowing the sieve technique when I was 10-11, possibly it's just a UK education thing.

I think we should assume knowledge of what a prime is in the same we assume people know what a noun is.--Imran 22:19 Oct 27, 2002 (UTC)

Guys, if you're just not willing to put it in terms an average reader of the 'pedia can understand without having to look the words up first, then simply take the example out, because it's not going to do what an example is supposed to do. What you remember from 5th grade is totally irrelevant -- you're not the one that needs to look the word up. The problem is that having an example there that's too hard is worse than not having one at all, because it will scare off someone who was interested enough to try to find out what "algorithm" means. And BTW, people in this country (U.S.) don't know what a noun is, either. -- isis 23:03 Oct 27, 2002 (UTC)

ask the same people you ask about "prime" whether they have any interest in reading about the meaning of the word "Algorithm". Some might -- but those with no grasp of maths concepts will go away happy with the intro text: "Generally, an algorithm is a list of instructions for accomplishing some task..." Knowledge builds on knowledge, and people getting this far should know that. Anyway, why don't we try writing several examples: a sort and the sieve, and leave the GCD too. We can then try and decide which is the simplest to the thick *cough* novice reader. -- Tarquin

I recommend implementing the selection sort algorithm, whether there will be only the sort algorithm or other ones as example(s). It being simple to understand is an issue, that's the right algorithm. Its correctness is easy to get. TCascardo

Question on Etymology

I don't know how to fix this, but I'd like to point out that the article's etymology of "algorithm" doesn't look entirely coherent. The article seems to provide two different stories:

1. It descended from successive translations of an Arabic guy's name.
2. It descended from a word in said Arabic guy's chief work, a word which referred to "the rules of performing arithmetic using Arabic numerals"

There seems to be a missing link here somewhere. --Ryguasu 05:34 Jan 12, 2003 (UTC)

Please read it again more carefully: It says "algorithm" came from his name, and "algebra" came from the name of his book. It may not be expressed clearly enough because all of us who worked on it knew what it meant, so if it doesn't say that to someone who doesn't already know it, please fix it. -- isis 05:46 Jan 12, 2003 (UTC)

Good Examples

I had a thought on the subject of good examples -- how about the Tower of Hanoi algorithm? -- Tarquin 11:52 Jan 24, 2003 (UTC)

Has there been any more consideration of this? I think the problem of demonstrating that the procedure terminates, and it always gets the right result might be a little tricky if you want to keep this informal. The other nice aspect is that there are two different approaches, one that is easy to do with a computer, and the "practical" one that is iterative, rather than recursive, and more economical in a number of ways. The number of moves of disks is the same, of course, unless you slip up, but the housekeeping for one is negligible and the other is a function of the number of disks in the stack (though I would not call it impractical for anything a person would be willing to carry out, or that I would be willing to watch carried out on my computer display). But it is a practical, mostly math-free procedure. Of course, it is sort of fun to see why it works to say that to move the stack of n on post i to post j, you first move the top n-1 to post 6-i-j. --Orcmid 02:33, 12 Mar 2004 (UTC)

Reworked the First Paragraph

Ok, some of the problems with the opening paragraph:

• The definition of the algorithm was prefaced with generally, when broadly-defined was meant. The definition of the algorithm as presented may be restricted, but it is never excepted unless done so erroneously, so it makes sense to be more precise with the modifier.
• The term "list" has a more sequential denotation than does "set" as usually code is very non-linear. Take any assembly code for example and you get my point. I realize that an argument can be made the acutal storage of an implementation of code may be list, but this is not very strong as an argument on two points. First, most code today is non-linear in storage with the advent of shared libraries and subprocedures, and secondly the storage of instructions is really insignificant in comparison with the operation of the code, which is what algorithms are about. Set, therefore, is more precise. I realize for non-computing applications such as a recipe, list is generally the norm, but it seems to me that set is equally understandable to lay persons.
• I added the hyperlink iteration and the term decision with the links to Boolean logic and inequality because comparison and logic are the cornerstone of even the simplest cooking recipes.
• I changed 'mnemonics' as an example of an algorithm, because strictly speaking, a mnemonic device is NOT an algorithm. It is the data structure associated with an alogrithm, as the process of encoding and decoding the original information IS the algorithm. The phrase ROY G BIV is no more an algorithm than an MP3 file. Both are the byproduct of a codec.
• I added the 'heuristics' link, because of the close relation.
• I thought that the bit on policy and mechanism was important for understanding how different algorthims get the same thing done.
• The rest of it I just cleaned up the syntax for conciseness and clarity.

jtvisona 01:51, 14 Aug 2003 (UTC)

Example algorithm is flawed ...

The algorithm to find the highest number in a list is flawed :

• It uses the first element of the list twice
• It fails when the list is empty

--Stephan Leclercq 08:34, 20 Jul 2004 (UTC)

References

Ok, I'm a lazy bastard and I always meant to do it way back in the day when I first put my hands into this article, but Knuth's 3 volume set really should be included in the references.

jtvisona 072004

Link suggestions

An automated Wikipedia link suggester has some possible wiki link suggestions for the Algorithm article, and they have been placed on this page for your convenience.
Tip: Some people find it helpful if these suggestions are shown on this talk page, rather than on another page. To do this, just add {{User:LinkBot/suggestions/Algorithm}} to this page. — LinkBot 10:24, 17 Dec 2004 (UTC)

• (The above leads to Wikipedia:Archive/Refreshing brilliant prose - Science#Applied Arts and Sciences, where there are simply three votes for retention. --Jerzy(t) 21:17, 2005 Feb 8 (UTC))

Etymology

I agree that the "not Greek" insertion is better gone, tho

a) not popular belief and b) it's not from the word to gore, either, but we don't have to explicitly say that

are bad reasons for removal. There is little popular knowledge that it came via Arabic, and irrational is it, normal human minds are far more confused by the anagram than by a coincidental syllable. There's a stumbling block here, and a better-crafted corrective may well be worth while.

For that reason and others, how about some more etymology: what is the usual relationship between -ithm and -ism; it was certainly de-Arabified, and was it Grecified or Latinized? Is there an early Arabic form other than just the personal and place names? Some of these answers may be worth including.
--Jerzy(t) 21:17, 2005 Feb 8 (UTC)

Hi, If everyone agrees that my edit was unecessary so be it, and remove it if you must. However, I agree with you that the resons given a) and b) where at least silly. I think it is popular belief, because of the ending -rithm which is a popular Greek word (logarithm, arithmetic etc etc) and I am also drawing from my experience as a student, where many people thought it had a Greek root. I think it makes more sense for someone who does not know, to assume its Greek rather than Arabic. As for b) and the fact that someone might associate it with "gore" rather than arithmetic, I think that tells a lot about that person. May I suggest a bit less TV and open a book. --Vasileios Zografos 21:29, 8 Feb 2005 (UTC)