Everything2
Near Matches
Ignore Exact
Full Text
Everything2

algorithm

created by Harry

(idea) by haggai (5.1 mon) (print)   ?   1 C! I like it! Wed Apr 05 2000 at 18:07:48

One kind of algorithms which even non-geeks use regularly, and which is amazingly popular on Everything is cooking recipes. In cuisine as in programming, good implementation of the outlined procedures can be just as challenging and creative as the abstract work, and can fail or succeed spectacularly.

(idea) by WWWWolf (1.2 y) (print)   ?   1 C! I like it! Mon Mar 26 2001 at 21:32:57

"Cryptography is a black art; if you don't know what you're doing, you can easily get into trouble."

- Bruce Schneier: Applied Cryptography, 2nd ed.

Algorithms are, as told above, "blueprints" of how specific computing tasks should be done.

There are many different sorts of algorithms for many tasks, some better suited for some tasks, some for others. Good rules to remember:

  1. Don't pick them from your hat. Choose well.
  2. Don't make shit up. Someone who had IQ way, way, way above yours invented a better one, so use that instead. (And there's nothing to be ashamed of about that! The details of implementation are what really matter. Picking the correct course of action is a form of art, too!)

During the "Data Structures and Algorithms" course last year, the lecturer told a common story about students who tried to make the required assignment: People made up their own algorithms, ended up doing things that were of exponential complexity, and spent hours and hours trying to make the correct implementation. People who picked up an algorithm shown on lectures and made their assignment based on that information made highly efficient programs very quickly and lived happily ever after.

Consider this one, for example: Bubble sort is O(n²) in worst case - sorting 100 items takes 100² = 10000 units of time. Quick sort (that they called the "sign of academic background") is O(n log n) on average - sorting 100 items takes 460.52 units of time. For 1*106 items, the times are 1*1012 and 1.3816*107. Clearly some improvement...

Most beginners will only make fancy versions of bubble sort, so knowing the quick sort algorithm will help a lot. Indeed, if you try to make a better algorithm when you only know how bubble sort works, you may end up creating an algorithm that's even worse than bubble sort.

To illustrate the importance of picking the correct algorithm, let me say that quick sort performs badly on almost-ordered data, but bubble sort is very fast in that case.

And the Schneier quote above tells a lot about the importance: If you try to make your own encryption algorithm, you may end up making a very insecure algorithm. To repeat: Don't think you're too smart when the smart guys have already made really cool algorithms. =)


(thing) by rp (19.5 hr) (print)   ?   2 C!s I like it! Tue Mar 27 2001 at 16:18:34

Webster is definitely outdated on this, the word is in a different category today: we don't speak of 'algorithm' as a mass noun. An algorithm is a concrete recipe for execution. It is not limited to calculation. So we need a better definition, and dew's - now deleted - left room for improvement.

An algorithm is a specific combination of discrete steps, observations or actions, into a complex method. It is described in terms of elementary entities, objects, properties, actions, processes and events. The algorithm itself consists of the way in which these are combined into a whole method. The execution of an algorithm is the sequence of actions resulting from applying the algorithm - the result varies depending on the circumstances, which may lead to different outcomes.

One example of an algorithm is the cookbook recipe. Elementary entities (ingredients and tools), observations ('a teaspoonful', '300 g', 'boiling', 'fully dissolved'), actions ('chop into small pieces', 'mix', 'bring to the boil'), processes ('melt', 'boil') and events (in cooking, always changes of state) are used as the basic materials; the recipe is the algorithm describing how to combine them in order to create a specific dish.

The same description applies to computer algorithms. A computer algorithm is what a particular computer program does, or a particular part of it; the program is a concrete implementation of the algorithm.

Note that continuous processes and external, unpredictable events may be part of algorithms. Calculation is a more limited form of algorithm execution in which such processes and events do not occur; the problem domain is described in terms of a complex, but discrete state; all observations are tests of state, all actions are changes of state, and no external state changes occur during the algorithm's execution Such algorithms of calculation are the type usually discussed in theoretical computing science, which has an extensive theory on the properties of such algorithms and the relationships between them. A calculation is the result of the execution of such an algorithm.

A nondeterministic algorithm does not uniquely determine the course of action at every point, but leaves a choice between a set of options. We usually think of algorithms as deterministic, but this particular notion is important in the theoretical study of algorithms, summarised in the question, still open in theory, whether or not P = NP.

Calculation is often numerical, and the classical algorithmics of algebra, of addition, subtraction, multiplication and division, are greatly emphasized in school. Some well-known numerical algorithms, such as Euclid's algorithm to detemine the greatest common divisor, are known from ancient times.

Now that computers are everywhere, algorithms in different types of data become more important: searching and transformations on text strings, image manipulation algorithms on vector-based or bitmapped images, manipulations on databases, document structures, or other forms of structured data.

Part of the art of algorithm design is good use of complex data structures. Different representations of data typically have different efficiency characteristics. For instance, lists of items can be stored in an array, linked list, or hash table, each with different average cost in time and space for various typical access and update operations..

dido makes the interesting point that an algorithm is supposed to terminate on all input -- in other words, it must express a computable function. The main reason I find this interesting is that I do not consider this requirement to be part of what an algorithm is, while dido does. For example, for me the famous Collatz sequence describes an algorithm, while dido cannot tell. Some Googling demonstrates that, like dido and me, dictionaries of computing science disagree on this matter. So I will just leave you with a reminder to carefully examine whether the definition of "algorithm" you encounter assumes guaranteed termination or not.


(thing) by flyingroc (1.1 y) (print)   ?   1 C! I like it! Mon Oct 01 2001 at 22:03:21

From m-w.com: an algorithm is: broadly, a step-by-step procedure for solving a problem or accomplishing some end especially by a computer

The theory of algorithms deals with the study of characteristics of algorithms such as efficiency in terms of time and space.



(definition) by Webster 1913 (print) 1 C! I like it! Tue Dec 21 1999 at 21:43:14

Al"go*rism (#), Al"go*rithm (#), n. [OE. algorism, algrim, augrim, OF. algorisme, F. algorithme (cf. Sp. algoritmo, OSp. alguarismo, LL. algorismus), fr. the Ar. al-Khowarezmi of Khowarezm, the modern Khiwa, surname of Abu Ja'far Mohammed ben Musa, author of a work on arithmetic early in the 9th century, which was translated into Latin, such books bearing the name algorismus. The spelling with th is due to a supposed connection with Gr. number.]

1.

The art of calculating by nine figures and zero.

2.

The art of calculating with any species of notation; as, the algorithms of fractions, proportions, surds, etc.

 

© Webster 1913.


printable version
chaos

The Art of Computer Programming bubble sort Euclid's algorithm Quick Sort
Big-oh notation Donald Knuth Celebrity Problem knapsack problem
Bloom Filter Proof that the greedy algorithm for egyptian fractions terminates Sorting is O(n log n) Good old fashioned fucking
preemptive multitasking Weighted Fair Queuing greedy algorithm card shuffling algorithms
Eratosthenes' Sieve complexity Integer Relation Detection Algorithm Deadlock
Playing a record at the wrong speed P = NP heuristic matrix multiplication
Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.
  Epicenter
Login
Password

password reminder
register

Everything2 Help

Cool Staff Picks
After stirring Everything, these nodes rose to the top:
The Badlands
Nuclear Weapons Do Not Function Without Yellow Tape
Squash
Is Taiwan a part of China?
E2 Prose Writers Group
Orientalism
The 1989 U.S. Invasion of Panama
Arizona
How to read to a child
Hammond B-3
Bush v. Gore
George S. Kaufman
Ailurophobia
New Writeups
cryforhelp
Major dictionaries of the world(review)
Glowing Fish
The Uncanny X-Men and the New Teen Titans(thing)
WolfKeeper
Launch loop(idea)
TendoKing
Katana(person)
Wuukiee
Highly ornamental cultivars of brambles still have as many thorns as their wild counterparts(idea)
TheDeadGuy
Editor Log: May 2008(log)
everyday j.Lo
pray do not molest them(thing)
ammie
Bands Who Take Their Names from Eighteenth-century English Poetry and Prose(idea)
shaogo
Under My Thumb(review)
ammie
Rock On(person)
The Custodian
The Dresden Files(thing)
Ouzo
PETA becomes you, a proposed future(fiction)
Ereneta
Stone Soup, Part Two(fiction)
jjen
Sorrier than I ever thought I would be(personal)
locke baron
Moskva class antisubmarine cruiser(thing)
This affordable entertainment brought to you by The Everything Development Company