Introduction to Algorithms - Revision history

wikademia>Wikademia at 17:26, 5 April 2009

2009-04-05T17:26:30Z

← Older revision		Revision as of 17:26, 5 April 2009
Line 96:		Line 96:

	* '''Numerical Computation.''' More and more mathematicians and computer scientists are using computers to do research, eg. to collect data, test new theories or process experimental results. Some researchers have even tried to use computers to prove theorems! (A proof to the four-color theorem was, controversially, completely produced by computer.) Ever faster algorithms need to be invented to cope with this massive increase in demand.		* '''Numerical Computation.''' More and more mathematicians and computer scientists are using computers to do research, eg. to collect data, test new theories or process experimental results. Some researchers have even tried to use computers to prove theorems! (A proof to the four-color theorem was, controversially, completely produced by computer.) Ever faster algorithms need to be invented to cope with this massive increase in demand.

			==See also==
			* [[Courses]]

	[[Category:Computer science]]		[[Category:Computer science]]
	[[Category:Introductions]]		[[Category:Introductions]]
	[[Category:Algorithms]]		[[Category:Algorithms]]

wikademia>Wikademia at 11:20, 23 March 2009

2009-03-23T11:20:57Z

← Older revision		Revision as of 11:20, 23 March 2009
Line 1:		Line 1:
			{{RightTOc}}
	==Introduction==		==Introduction==
	See also [http://en.wikipedia.org/wiki/Algorithm Algorithm] on Wikipedia		See also [http://en.wikipedia.org/wiki/Algorithm Algorithm] on Wikipedia

wikademia>Wikademia: moved Introduction to algorithms to Introduction to Algorithms

2009-03-23T11:20:12Z

moved Introduction to algorithms to Introduction to Algorithms

← Older revision	Revision as of 11:20, 23 March 2009
(No difference)

wikademia>Wikademia: 5 revisions

2009-03-23T11:19:55Z

5 revisions

← Older revision	Revision as of 11:19, 23 March 2009
(No difference)

wikademia>Erkan Yilmaz: +Category:Algorithms

2008-07-17T18:38:50Z

+Category:Algorithms

← Older revision		Revision as of 18:38, 17 July 2008
Line 97:		Line 97:
	[[Category:Computer science]]		[[Category:Computer science]]
	[[Category:Introductions]]		[[Category:Introductions]]
			[[Category:Algorithms]]

wikademia>JWSchmidt: Category:Computer science

2007-06-21T20:38:39Z

Category:Computer science

← Older revision		Revision as of 20:38, 21 June 2007
Line 95:		Line 95:

	* '''Numerical Computation.''' More and more mathematicians and computer scientists are using computers to do research, eg. to collect data, test new theories or process experimental results. Some researchers have even tried to use computers to prove theorems! (A proof to the four-color theorem was, controversially, completely produced by computer.) Ever faster algorithms need to be invented to cope with this massive increase in demand.		* '''Numerical Computation.''' More and more mathematicians and computer scientists are using computers to do research, eg. to collect data, test new theories or process experimental results. Some researchers have even tried to use computers to prove theorems! (A proof to the four-color theorem was, controversially, completely produced by computer.) Ever faster algorithms need to be invented to cope with this massive increase in demand.
	[[Category:Computer ~~Science~~]]		[[Category:Computer science]]
	[[Category:Introductions]]		[[Category:Introductions]]

63.197.134.209: /* Flow Control */

2007-05-02T14:02:40Z

Flow Control

← Older revision		Revision as of 14:02, 2 May 2007
Line 44:		Line 44:

	===Flow Control===		===Flow Control===
	Our current toast making ~~algorithmworks~~ well if you are making toast for yourself, but what if you have a few friends round for breakfast and you need to make them toast as well? The algorithm clearly needs to be improved so that we can make toast for everyone. Also, simply waiting for the toasted is very boring, we could be doing something else while we wait. The third problem with making toast for friends is that they are fussy, what if some of them want butter whilest others prefer margarine, or even just plain toast		Our current toast making algorithm works well if you are making toast for yourself, but what if you have a few friends round for breakfast and you need to make them toast as well? The algorithm clearly needs to be improved so that we can make toast for everyone. Also, simply waiting for the toasted is very boring, we could be doing something else while we wait. The third problem with making toast for friends is that they are fussy, what if some of them want butter whilest others prefer margarine, or even just plain toast

	'''Algorithm for making toast (4.0)'''		'''Algorithm for making toast (4.0)'''

wikademia>Remi0o: added cat

2007-04-14T19:43:48Z

added cat

← Older revision		Revision as of 19:43, 14 April 2007
Line 96:		Line 96:
	* '''Numerical Computation.''' More and more mathematicians and computer scientists are using computers to do research, eg. to collect data, test new theories or process experimental results. Some researchers have even tried to use computers to prove theorems! (A proof to the four-color theorem was, controversially, completely produced by computer.) Ever faster algorithms need to be invented to cope with this massive increase in demand.		* '''Numerical Computation.''' More and more mathematicians and computer scientists are using computers to do research, eg. to collect data, test new theories or process experimental results. Some researchers have even tried to use computers to prove theorems! (A proof to the four-color theorem was, controversially, completely produced by computer.) Ever faster algorithms need to be invented to cope with this massive increase in demand.
	[[Category:Computer Science]]		[[Category:Computer Science]]
			[[Category:Introductions]]

wikademia>JWSchmidt: from Topic:Algorithms

2007-01-14T16:56:06Z

from Topic:Algorithms

New page

==Introduction==
See also [http://en.wikipedia.org/wiki/Algorithm Algorithm] on Wikipedia

==Everyday Example==
Here is a perhaps slightly whimsical example of an algorithm.

'''Algorithm for making toast (1.0)'''
Get a loaf of bread.
Cut one slice from end of the loaf of bread.
Put slice of bread into toaster.
Turn toaster on.
Wait for toaster to finish.
Put toasted bread onto a plate.
Spread butter on toast.

As can be seen, the algorithm is a set of steps that can be followed in order to acheive a result.

===Subprocedures===
Algorithms are often broken down into smaller chunks called or subprocedures. This is both so that they are easier to read, and also because then parts of the algorithm can be reused. What follows is the above algorithm in a more formal manner. The text in italics below are the names of the subprocedures that are being called.

'''Algorithm for making toast (2.0)'''
''get'' a loaf of bread.
''cut slice from'' the loaf of bread.
''move'' the slice of bread ''to'' the toaster.
''turn on'' the toaster.
''wait for'' the toaster to finish.
''move'' the slice of toast ''to'' a plate.
''spread'' the slice of toast ''with'' butter.

===Variables===
In the above example it is fairly simple to follow the piece of toast through the algorithm, but if you imagine that the algorithm could become more complex, and thus the progress of the toast much harder to follow. In order that, at any point in the algorithm, it is clear what is being talked about, names are often given to things. For example

'''Algorithm for making toast (3.0)'''
'''LET''' '''A''' = a loaf of bread
'''LET''' '''T''' = a toaster
'''LET''' '''P''' = a plate
'''LET''' '''B''' = some butter
'''LET''' '''S''' = ''cut slice from'' '''A'''
''move'' '''S''' ''to'' '''T'''
''turn on'' '''T'''
''wait for'' '''T'''
''move'' '''S''' ''to'' '''P'''
''spread'' '''S''' ''with'' '''B'''

===Flow Control===
Our current toast making algorithmworks well if you are making toast for yourself, but what if you have a few friends round for breakfast and you need to make them toast as well? The algorithm clearly needs to be improved so that we can make toast for everyone. Also, simply waiting for the toasted is very boring, we could be doing something else while we wait. The third problem with making toast for friends is that they are fussy, what if some of them want butter whilest others prefer margarine, or even just plain toast

'''Algorithm for making toast (4.0)'''
'''LET''' '''A''' = a loaf of bread
'''LET''' '''T''' = a toaster
'''LET''' '''P''' = a plate
'''LET''' '''B''' = some butter
'''LET''' '''M''' = some margarine

'''FOR''' every friend ('''F''') eating toast{
'''LET''' '''S''' = ''cut slice from'' '''A'''
''move'' '''S''' ''to'' '''T'''
''turn on'' '''T'''
'''WHILE''' '''T''' is not finished{
''talk to'' '''F'''
}
''move'' '''S''' ''to'' '''P'''

'''IF''' '''F''' likes '''B'''{
'''LET X''' = '''B'''
}'''ELSEIF''' '''F''' likes '''M'''{
'''LET X''' = '''M'''
}'''ELSE'''{
'''LET X''' = ''NOTHING''
}
''spread'' '''S''' ''with'' '''X'''
''move'' '''P''' ''to'' '''F'''
}
As can be seen, to resolve the three problems above, I had to implement the three main types of flow control, a '''For Loop''', a '''While Loop''' and an '''If Statement'''. It should be obvious from the example what each of these does. I also involved a new variable '''X''', which unlike the variables I have used before changes its value as the algorithm progresses.

==Basic concepts==
This simple example already contains many components commonly found in most algorithms:

* Instructions. Instructions are the heart and soul of any algorithm. An algorithm will consist of a series of sub-algorithms, each performing a smaller task. Extracting individual digits from the numbers to be added may well be an entire task in itself. Some instructions, like digit addition, can be considered fundemental instructions which cannot be broken up further; all algorithms can eventually be broken down into these instructions, like objects being composed of atoms.

* '''Variables.''' ''temporary'' and ''carry'' are both temporary values used to store additional information the algorithm needs to function correctly or effectively. Their values can ''vary'' as the algorithm progresses, hence their name.

* '''Conditionals.''' Some algorithms may need to make a decision somewhere in it. If the sum of the current two digits is 10 or larger, 1 will be carried over to the next digit position, otherwise nothing (ie. zero) is carried. Conditionals allow an algorithm to selectively execute instructions based on certains ''condition'' which must be satisfied.

* '''Looping.''' The ''for each''...''end for'' instruction means to run certain instructions ''for each'' object in a set, in this case for each digit in a number. This is a special case of '''looping''', the act of repeating a set of instructions while (or until) a goal is reached or a condition is satisfied; in this case while there are digits left (or until there are no digits left). Loops can contain any other instructions, including other loops!

* '''Subprocedures.''' An algorithm may not be able to do all the work on its own. Usually, a large, complex algorithm can be broken up into parts, each perfoming a specific task. Smaller algorithms are easier to reuse, for example the ''for each ...'' digit selection algorithm could be reused in subraction, multiplication and division algorithms, and so on. Breaking up algorithms into logical parts also make it easier to analyze their behaviours and properties from a mathematical point of view.

==Algorithms commonly studied==
Many algorithms are currently under intense study for various reasons. They include:

* '''Sorting algorithms.''' A sorting algorithm will take a set of objects and arrange the objects in ascending (or descending) order. While this is a simple problem and there are many existing algorithms to tackle this problem efficiently, new algorithms (and problems with older ones) are published all the time.

* '''Artificial Intelligence.''' AI algorithms typically accept an input representing its environment (eg. a chess board) and try to find some legal move to respond favourably to the environment or an opponent (eg. calculating a good chess move). Today modern chess AIs can beat even professionals and regularly challenge world grandmasters to intense, decisive matches. Still, some simple board games (like Japanese Go) remain impervious to attack. AI has also been recently employed in anti-fraud software and email spam filters.

* '''Numerical Computation.''' More and more mathematicians and computer scientists are using computers to do research, eg. to collect data, test new theories or process experimental results. Some researchers have even tried to use computers to prove theorems! (A proof to the four-color theorem was, controversially, completely produced by computer.) Ever faster algorithms need to be invented to cope with this massive increase in demand.
[[Category:Computer Science]]