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
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 <- Bassignment 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++. --BlckKnght
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
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?
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)
- 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 largerr 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.)
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)