text:
Objective-C Programming/in depth

Now that you have familiarised yourself with the basics of writing a class (you should now be able to construct a simple class or two, and manipulate them), let's have a look at some of Objective-C's deeper features.

Dynamic typing and binding
This is one of Objective-C's strongest features, and allows for greater flexibility and simplicity.

Let's look at something we only glossed over before: the type id.

The id type
Objective-C provides a special type that can hold a pointer to any object you can construct with Objective-C—regardless of class. This type is called id, and can be used to make your Objective-C programming generic.

Let's look at an example of what is known as a container class, that is, a class that is used to hold an object, perhaps in a certain data structure.

Say our container class is a linked list, and we have a linked list of LinkedListNode objects. We don't know what data we might put into the linked list, so this suggests that we might use an id as a central data type. Our interface then might look like This means that we could store any class of object in any linked list node, and we would be able to recover them from the node as easily.

Consequences
Keeping with the previous example, say we have a linked list of Document objects. Say now, we want to calculate the word count of each document in the list, by means of a wordCount method.

But, since an id type can hold a pointer to any object, how do we know that the object has the <tt>wordCount</tt> method defined? How do we know that what we are getting out is indeed a <tt>Document</tt>?

We could merely declare different classes for lists containing <tt>Documents</tt>, or lists containing other types, but this duplicates a lot of functionality, which is not the best practice and we lose the generic nature of our <tt>LinkedListNode</tt> class.

Objective-C provides you with many different solutions to this problem.

Dynamic binding
Say that our linked list doesn't just contain <tt>Document</tt>s, but has also <tt>Spreadsheet</tt> and <tt>Chart</tt> objects as well. Let's assume all these objects have a <tt>title</tt> method defined, but implemented differently. Since at the core of <tt>LinkedListNode</tt> is the <tt>id</tt> class, how would we know which <tt>title</tt> method will be called when we pull out an object from our linked list? Will it be <tt>Document</tt>'s? Or <tt>Chart</tt>'s? Dynamic binding is a solution to this problem.

Dynamic binding means that when we call a certain object's method, and there are several implementations of that method, the right one is figured out at runtime. In Objective-C, this idea is used, but is also extended - you are permitted to send any message to any object. At first glance this may sound rather dangerous, but in fact this allows you a lot of flexibility.

Let's return to our example. We want to print out all the titles of the objects in the linked list, based on their <tt>title</tt> method. Dynamic binding means that the right method to be called (<tt>Documents</tt>'s, <tt>Spreadsheet</tt>'s, or <tt>Chart</tt>'s <tt>title</tt> method) will be figured out at runtime, and we can simply have a loop in the form Dynamic binding is fine for certain circumstances, and can make some other code unexpectedly clearer. However, other circumstances may require more than just this. I want to say more but this is all basics for dynamic binding.

isKindOfClass
Say we are not assured that the objects we place into the <tt>LinkedListNode</tt>s are not all <tt>Document</tt>s. If we have, for example, a <tt>Chart</tt> object in one of the nodes, and it doesn't have <tt>wordCount</tt> defined (in Objective-C terminology, we say that <tt>Chart</tt> objects do not respond to <tt>wordCount</tt>), and we try and do something like:

this would produce a runtime error when <tt>p</tt> points to the node containing the <tt>Chart</tt> object, because <tt>Chart</tt> doesn't respond to the <tt>wordCount</tt> message. We ask the <tt>Chart</tt> to give us a word count, but it doesn't know what to do! In Objective-C, in this example, <tt>Chart</tt> or any other object can do two things: We'll look at the second situation in the next section. So, in this instance, the program fails and reports an error.
 * 1) fail, and report the error, or
 * 2) send the message on to another object to handle.

For this instance, the best Objective-C feature for now, is to use <tt>Object</tt>'s <tt>isKindOfClass:</tt> method. We can add the following check, to get:

This loop will skip over the <tt>Chart</tt> object in this instance. The class method, <tt>class</tt>, returns a class object. The type <tt>Class</tt> is a special type that can hold a pointer to any class object (similar to how <tt>id</tt> can hold a pointer to any object). The instance method <tt>class</tt> also returns the class object for the class of the object. This means that if we wrote the test as <tt>[p class] == [Document class]</tt>, we could test whether the object's class is exactly <tt>Document</tt>. We could also achieve this result using <tt>[p isMemberOfClass:[Document class]]</tt>. This contrasts with <tt>[p isKindOfClass:[Document class]]</tt>, which will check if the object is that class or any of its subclasses (since, due to inheritance, any instance of a subclass "is a" instance of the superclass too). In most cases, <tt>isKindOfClass:</tt> is the better way to test whether an object is an instance of a class.

This sort of behaviour is a way that polymorphism is implemented in Objective-C. Polymorphism is a feature of methods that can be applied to different types, which could have different behaviour when applied to those types.

This sort of behaviour can, of course, become unwieldy when used improperly. Objective-C gives you, however, ways of addressing this. We can either make sure that all objects that we may want to work on have a predefined set of methods implemented, by using what is known as a protocol, or we can "tack on" extra methods to the class, to eliminate this redundant checking, by using what is known as a category. Let's look at protocols first.

Protocols
Spies and secret agents must need to make themselves known to other agents, in order to collect information from others. However, the agents must know whether the other spy or agent is really on their side—the bad guys could send a fake spy in to give the other spies false information! So some form of authentication is usually used, such as a password or a passphrase, or a secret handshake, or they may meet at a certain pre-arranged location. All these are examples of protocols to establish whether a person is trustworthy enough.

Objective-C uses protocols in exactly the same manner. An <tt>id</tt> holds any object—we want to make sure that if we call some method upon the contents of an <tt>id</tt> variable, it is guaranteed to respond to it.

A protocol, in Objective-C, is a list of method declarations that any class that wishes to adopt the protocol must implement.

We write a protocol in a similar way to writing an <tt>@interface</tt> declaration. Here is one typical protocol. Note that we can call the protocol the same as a class—this is okay. It may be useful to place this <tt>Document</tt> protocol in the same header as the <tt>Document</tt> class, or we may want to keep it in a separate file.

If we want to signify that the <tt>Document</tt> class adheres (or is said to conform, in Objective-C) to the <tt>Document</tt> protocol, we must say this in the <tt>@interface</tt> declaration. We do this by writing The <tt><Document></tt> means that the interface to the <tt>Document</tt> class adheres to the <tt>Document</tt> protocol.

Let's revisit our <tt>LinkedListNode</tt> class. Recall we wanted to get the sum of all the words in each document. But, in our <tt>LinkedListNode</tt> class, the core datatype is an <tt>id</tt>. There are basically no restrictions on what we can put into an <tt>id</tt> variable. Ideally, what we'd like to do is say something along the lines of "all objects that adhere to the X, Y or Z protocol". We use angle brackets again to specify this.

Let's create a new class, call it <tt>LinkedListDocument</tt>. This class only has in each node an object that conforms to the <tt>Document</tt> protocol. Instead of saying <tt>id data</tt> in the interface, we say instead:

In order to use the protocol in the type specification, or in the interface specification, we must import the header file in which the protocol is defined.

"Inheritance" of protocols
A protocol can incorporate other protocols that have been defined, in a similar way to inheritance, but there is no hierachy imposed upon protocols like there are in classes. For example, in the <tt>Document</tt> protocol, we could write it this way instead: This allows us to structure and compartmentalize our protocols at a greater level. However, note that a protocol's method declarations can be empty! This means that we can use "empty" protocols to mark or group certain objects based on a higher level than merely what methods the conforming objects respond to (for example, creating an "empty" <tt>GraphicsBased</tt> or <tt>TextBased</tt> protocol in order to set the printer mode, which <tt>Document</tt>, <tt>Spreadsheet</tt>, or <tt>Chart</tt> objects could adopt).

conformsTo
Say we now want to write an <tt>addDocument:</tt> method to our <tt>LinkedListDocument</tt> class. We could write something like which means that any object we must pass in to the <tt>addDocument</tt> method must conform to the <tt>Document</tt> protocol. This may be a little restrictive. We may want to have a declaration like

and return <tt>NO</tt> when the new document doesn't conform to the <tt>Document</tt> protcol, for instance. How can we do this? We may want something that works a little like <tt>isKindOfClass:</tt>. Objective-C provides us with a method <tt>conformsTo:</tt> for just this purpose. We can then write <tt>addDocument:</tt> like

Note the <tt>@protocol(Document)</tt> symbol. This acts in just the same way as <tt>[Document class]</tt> does, except that <tt>@protocol(Document)</tt> returns a <tt>Protocol</tt> object instead of a class object.

If we however have a protocol, and we want to test whether it incorporates another protocol, we can use <tt>conformsTo:</tt> as well. For example, given the protocols above ("Inheritance" of protocols), would give <tt>YES</tt> as a result.

 * In Java, the keyword "interface" means the same as "protocol" in Objective-C . Objective-C uses "interface" to define a declaration for a class, as in "C++" , so the declaration can be used in header files which can be included in client source files for use. The older C++ and Objective-C do not separate the concerns of defining storage layout and function address tables , so an Objective-C "interface" can only be used for one implementation file , whereas in Java, only non-storage declarations such as constants and function names and inner interfaces are defined in interface definitions, so these can be reused amongst various implementation classes. The C++ equivalent of a protocol is a abstract class , where in the declaration definition, all the functions end with " = 0;" . In C++,  object implementations of abstract classes can't be received as copy constructed parameters via functions , but can be received as abstract class pointers. In Objective-C , every object made by calling alloc on a class and instantiated with a init function is returned as a pointer to an object , and there seems to be no mechanism for automatic allocation and deallocation on the stack in a function scope , as occurs with non-pointer variable declarations within the body of a function, as in C++.  Java also follows the objective-C lead of only allowing object creation via the "new" keyword and a constructor .  In Java, interfaces are regarded as a kind of superclass relationship, so "X.class.isAssignableFrom(o)" can be used to test for conformance of an object o to a  interface  X.

Categories
Let's return now to our previous example, where we have <tt>LinkedListNode</tt>s which do not contain only <tt>Document</tt>s. We want to get the sum of all the words in all the <tt>Document</tt>s in the linked list. Recall our previous solution that we added a check

However, this sort of check isn't quite the best solution, on a couple of levels. If we've only got <tt>Document</tt>, <tt>Spreadsheet</tt>, and <tt>Chart</tt> objects, and neither <tt>Spreadsheet</tt> nor <tt>Chart</tt> objects have a way of providing a word count, then, in essence, their word count could be said to be 0. What we want to do, now, is somehow "stick on" a small implementation of <tt>wordCount</tt> that simply returns 0 for objects that have no word count, and then we can remove the check that we have before and merely let dynamic binding do it's work.

Categories provide this way of "sticking on" extra methods, as an alternative to subclassing. What categories do, is a way of building up a class based on separate pieces that are logically grouped together, for example, by category (hence the name).

So, how do we define a category? We write it in a similar form to the <tt>@interface</tt> declaration, but we do this separately.

Here's an example of a <tt>WordCount</tt> category, on the <tt>Spreadsheet</tt> class. We first create an interface for the category: which goes into a header file, and then the implementation of the category

which can go in a <tt>.m</tt> file. Importing the category's header file means that the category is being used. We can do a similar procedure for <tt>Chart</tt> or any other object we need to add a category to.

Now, <tt>Spreadsheet</tt> or any other object that has this category, now has a valid <tt>wordCount</tt> method defined upon it (albeit a simple stub method, but we can do anything we like otherwise), so writing the loop

will be successful since if <tt>[p data]</tt> returns a <tt>Spreadsheet</tt>, the <tt>wordCount</tt> method will be used.

Note: methods declared in categories override preexisting methods. This means that we can do some neat tricks (see the Advantages section below). Also beware that the behaviour in picking a method declared in two categories is undefined.

Advantages of categories
Categories allow us to split up a large class into several pieces. Each can be developed and created independently, and then brought together at the end to form the class.

As a consequence however, this allows us some nice advantages. We can, in essence, extend the functionality of any class that may fall into our hands, whether it is in a class you create yourself, or in a binary form, such as in the OPENSTEP/Cocoa/GNUstep frameworks, we can add a category to <tt>NSString</tt> to provide functionality that the original <tt>NSString</tt> did not provide. It is possible to even add categories to <tt>Object</tt>! Categories can also be used to override previous functionality, which allows us then to "patch" these preexisting classes also, which might be provided with a bug. However, this should be done carefully and only as necessary.

A word on categories
And to finish off this section, let's hear some words of wisdom about categories:
 * What is truly relevant and exciting is how naturally logic is shifted to the appropriate class. Any time Objective-C code looks at the class of an object (using the -isKindOfClass: [isKindOf] method), it is likely that there exists a better, more efficient implementation using categories. This can be generalized with a design heuristic: "Let the runtime do the work of deciding the class of an object". By using the runtime effectively, a developer can often remove some if/then and most case statements. The benefit is obvious: simpler, cleaner code and better performance, since the runtime is optimized for this task.

example of polymorphism to eliminate if..then and switch..case type testing
Elimination of case statements using polymorphic child classes of a base type or category is mundanely shown in this example:

During runtime of a Snake touchscreen game, a user changes the state of the Snake by touching the screen. The snake object has 4 properties of East, West, North, and South MovementAndResponseState objects, all which have a reference to the owning Snake object and can access needed properties of the Snake object. The MovementAndResponseState class is composed of a MovementCategory and ResponseCategory, the movement category handles the movement of the snake in a particular direction by determining the next position on the snake's list of positions, and the response category handles the response to touch, by determining which of East, West, North, or South properties should be the Current direction property of the Snake object, in response to a user touch event. The snake object would have the following delegate pattern:-

The generalization is that in applications that respond to arbitrary user input and are event driven, alternatives exist to the main window loop with a massive case statement that type tests which event type occurred and dispatches to custom handling code.

 * " http://en.wikipedia.org/wiki/Message_loop_in_Microsoft_Windows " describes the venerable message loop-and-case-statements, and mentions frameworks later hiding this stuff, e.g. having GUI designers that link the handler code to a designed graphical element ala delphi-style properties, cocoa-style arrow dragging between designer editor and program text editor, or per-gui-control-object observer pattern "addXXXListener" callback registries , as in sun java's awt and swing frameworks and eclipse swt framework.

title: Objective-C Programming/in depth


text:
Cookbook:Garlic, Tomato and Cheddar Sandwich

| Vegetarian cuisine | Sandwiches

A delicious sandwich for breakfast and fast food!

Ingredients

 * 2 slices brown bread
 * 1 clove garlic
 * 1 green chili
 * 1 tomato
 * 5 long slices extra mature cheddar cheese
 * 1 tablespoon olive oil
 * 1 teaspoon lemon juice
 * Salt to taste
 * Black pepper to taste

Procedure

 * 1) Toast the two slices of brown bread, until one of the two is not soft anymore (the second one can be).
 * 2) Rub the garlic clove on the hard piece of toasted bread, until only a little piece is left. Chop what's left, and scatter on the bread.
 * 3) Cut the tomato in two, and crush each side on the same piece of bread. Then spread the juice, cut what's left of the tomato, and put it on the bread.
 * 4) Add the olive oil, by being careful not to add more oil than there is bread.
 * 5) Add the salt and pepper. Slice or crush the chili, and scatter on the piece of bread. Add the lemon juice.
 * 6) Neatly add the slices of cheddar, then close the sandwich with the remaining piece of bread.

Notes, tips, and variations

 * If you prefer warm sandwiches, the same sandwich can be baked in the oven for a couple of minutes, until the tomatoes and garlic are half-cooked and the cheddar has melted (be careful not to burn it). Avoid the microwave.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
User:Ivn~enwikibooks

Hola

http://ivn.blogia.com/

title: User:Ivn~enwikibooks


text:
Talk:Russian/Lesson 2

Untitled
sda

Corrections
There is a common error among the phrases on this page. The practice of о being pronounced as /a/ only applies to the syllable immediately before the stress.

Exx. "зовут" -> /zavut/

 * молоко and скоро ;) 62.16.243.119 15:36, 20 August 2007 (UTC)
 * I am also confused about this. According to this guide, the stressed syllable sounds like "oh", the syllable before that sounds like "ah", and all of the others sound like "uh". If that is the case, shouldn't the pronunciation of хорошо́ be 'khu-ra-SHO', instead of 'kha-ru-SHO'?  I have not studied Russian for a while, so I do not remember which way is correct. 76.111.190.30 (discuss) 18:54, 22 November 2013 (UTC)

Stress
The stress on some words also appears to be incorrect. I will correct some now... --Wolfox4777 16:32, 31 October 2007 (UTC)

I have replaced some of the apostrophes that were used as stress marks with stress marks, so the words don't look like "don't". --Nhesketh (talk) 22:12, 8 August 2008 (UTC)

IPA
It would be nice if someone familiar with IPA could fix this page, and leave the latin for the transliteration instead of pronunciation. 62.16.243.119 15:37, 20 August 2007 (UTC)

title: Talk:Russian/Lesson 2


text:
Cookbook:Requested Recipes

These are recipes that a user or reader would like to see, but that the cookbook does not currently have. You can create them by yourself, writing the recipe (see Cookbook:Policy/Recipe template). Delete the entry here, when the recipe has been created.

 * Slow Cooker Chicken Noodle Soup
 * Mint Imperial
 * Fu
 * Ohagi
 * Gosht Shahi Korma
 * Noodles Chaing Mai
 * Kadhai Murgh Afghani
 * Curry Mussaman
 * plain nasi (or chinese rice)
 * Chocolate Toffee Covered Matza
 * Sichuan Hotpot / Chongqin Hotpot (Chinese)
 * Bún Ma˘ng (Vietnamese)
 * Satay (Thai)
 * Peanut Butter Cups
 * Pocky (Japanese) I've looked everywhere, but I can't find out what goes into the biscuits - see Wikipedia article
 * Beef Linguini - Made with a garlic butter sauce
 * College Cookbook - A cookbook for college students that has easy to make recipes and is nutritional helpful. See: Category:Very Easy recipes
 * Garlic Knots
 * Butterscotch Pudding
 * Lavender French Macaron
 * In general: French Macaron
 * Pelmini Russian Pelmini
 * Pelmini Russian Pelmini
 * Cookbook:Lascania
 * Globi (Roman sweet enjoyed on Saturnalia.)
 * Skyr (Icelandic)
 * Navratan Korma
 * Slow Cooker Taco Soup (requester has this recipe in vague instructional diagram form, and plans to fully document it the next time it's made)

ספר מתכונים/מתכונים מבוקשים

title: Cookbook:Requested Recipes


text:
Algorithms

Table of Contents

 * Preamble
 * Introduction
 * Mathematical Background
 * Divide and Conquer
 * Randomization
 * Backtracking
 * Dynamic Programming
 * Greedy Algorithms
 * Hill Climbing
 * Unweighted Graph Algorithms
 * Distance approximations
 * Appendix A: Ada Implementation
 * Appendix B: Sources

Contributors
Macneil Shonle A large portion of my contributions here come from lectures made by [Impagliazzo] at UCSD. I like this project because it gives me a chance to explain algorithms in the way that I finally understood them

Matthew Wilson I typed in an outline after finishing a graduate algorithms course. M. Shonle has taken this textbook and really made it something great.

Martin Krischik I supplied the Ada examples for the algorithms. You never know if an algorithm works until you have actually implemented it.

See also the Sources list for contributions used with permission.

Algoritmia

title: Algorithms


text:
Classical Mechanics/Symplectic Spaces

What makes the phase space variables "momentum" and "position" (p, q) so special, compared to other possible choices such as the set of variables "velocity" and "position"? The reason is the additional property of the phase space (p,q) of having a "symplectic structure".

Let us define a "symplectic unit matrix"

$$I \equiv \sqrt{-1}$$

where -1 is an even-dimensional unit matrix. The dimension of the matrices we are talking about is the phase-space dimension, which is always even (each position variable is paired with a momentum variable). This is essentially the matrix generalization of the imaginary unit that we know from complex algebra. Simply put, symplectic spaces arise when unit matrices are replaced by symplectic matrices in strategically chosen places.

This sounds simple, but there is a catch: what is the square root of a matrix? As we already know from complex algebra, there isn't just one single answer for the square root. In mechanics, the root that we mean by I is moreover 'totally antisymmetric'. This still does not completely determine what I is. To get further, we need to think about the physics in phase space. In particular, we will encounter the phenomenon of volume preservation under temporal evolution.

title: Classical Mechanics/Symplectic Spaces


text:
Cookbook:Denver Crunch

 * United States | Dessert

Denver Crunch is a layered dessert that includes a crunchy base, a cream cheese middle, and a fruit top.

Crust

 * 2 cups flour
 * 1 cup chopped pecans
 * 2 cup brown sugar
 * 1 cup butter

Filling

 * 11 oz cream cheese
 * 1 cup powdered sugar
 * 1 tsp vanilla
 * Fruit filling of choice

Crust

 * 1) Mix crust ingredients like pie crust until crumbly.
 * 2) Press in pan. Bake at 350°F until brown. Cool.
 * 3) Take fork and crumble into small pieces. Some may be reserved for topping if you choose.

Filling

 * 1) Beat cream cheese, sugar, and vanilla until fluffy.
 * 2) Spoon the filling on the crust until it is covered.
 * 3) Top with your favorite fruit filling.

Notes, tips, and variations

 * Thickened blackberries and boysenberries make excellent toppings.

title: Cookbook:Denver Crunch


text:
Cookbook:Blackberry

The blackberry is a small, dark purple berry.

Characteristics
Blackberries are made of many small seeded drupelets clustered around a central core. Unlike with raspberries, this core is not left behind on the plant when picking, and blackberries are solid all the way through. When ripe, the fruits are shiny and deep purple to black in color. They are very tart and produce a purple juice when crushed.

Varieties
Since blackberry plants easily hybridize, there are many cultivars with more than one species in their ancestry.
 * Dewberries (R. caesius) are smaller than blackberries and can be distinguished by the white waxy coating on the fruits, which also usually have fewer drupelets.
 * Boysenberries were bred from blackberries, loganberries, and raspberries.

Seasonality
Blackberries reach their peak in the summer, specifically July to August. In warmer climates, the season may start earlier and end later. For instance, the Californian blackberry season starts in May and ends in October.

Superstition in the UK holds that blackberries should not be picked after September 15, as the devil has claimed them and left his mark on the leaves. There is some value behind this legend, since wetter and cooler weather often allows the fruit to become infected by various molds including Botrytis. These molds can give the berries an unpleasant flavor and toxicity.

Selection and storage
It’s best to buy fresh berries when they are in-season, as they are cheaper, riper, and more flavorful. Blackberries should be dry, firm, well-shaped, dark purple to black, and shiny—they will not ripen further after picking. Avoid purchasing berries with juice stains, which may be a sign that the berries are crushed and possibly moldy. Soft, watery fruit that means the berries are overripe; dehydrated, wrinkled fruit means the berries have been stored too long.

The fresh berries do not keep long —they should be stored in the fridge and eaten within a week after purchase. Moisture will increase spoilage, so store them in a single layer if possible. For longer storage, freeze them in airtight containers for up to several months. After thawing, they will be most suitable for cooked applications since the freezing damages their structural integrity.

Use
Blackberries may be eaten raw or prepared in a variety of ways, including both sweet and savory applications. They may be made into sweet sauces and preserves, mixed into fruit salad, churned into ice cream, used as garnish, fermented into wine, cooked into sauces, and more. Baked goods such as cakes and scones may incorporate fresh or frozen blackberries—if using frozen berries, fold them into batter while still frozen.

title: Cookbook:Blackberry


text:
Latin/Phonology

Latin phonology should be somewhat familiar to many readers, since it is an ancestor to the phonological systems of many of the world's most popular languages. In addition, one system of Latin phonology remains alive today, in institutions such as the Roman Catholic Church; this system is known as ecclesiastical Latin.

The Roman alphabet has five basic vowels: a, e, i, o, u. In addition, there are five diphthongs: ae, au, eu, oe, ou. There are seventeen basic consonants: b, c, d, f, g, h, j, l, m, n, p, q, r, s, t, v, x. There are three letters that are found only in foreign borrowings: two consonants (k, z) and one vowel (y). There are also a few consonant digraphs. To further complicate things, in many texts i and j are both written i (very common) while both u and v are often both written u (less common, and found in some modern printings) or both written v (very common in ancient inscriptions). For more detail, see Latin spelling and pronunciation on Wikipedia.

Pronunciation Guide
(using IPA notation)

Diphthongs and Diagraphs
A diphthong is a vowel combination that is pronounced as a single sound. It is often described as a ‘glide’ between two vowels. A diagraph is a similar combination--the only difference between the two is that both the vowels are distinctly pronounced.

Diphthongs

Diagraphs

title: Latin/Phonology


text:
User talk:Mmartin

HSE Maths Proof questions answered
Thank you very much for pointing out the mistakes for me. Xiaodai 08:57, 20 Jul 2004 (UTC)

Algorithms text
Hi Martin: I'm not sure if the Algorithms wikibook should really include that many wikilinks links like that. It's different from an encyclopedia entry and should be self-contained. That is, it might be better to keep outside surfing to a minimum. What do you think? MShonle 22:40, 18 Oct 2004 (UTC)

Wiki links
I put those links in the algorithms book because I had to look them up myself because I don't know all the technical terms. They are in the prerequisites section of the document so I thought it would be nice to find links to what you should read before reading this document. But if you think that they should be covered somewhere in the book or readers should know that before attempting to read the book it's ok with me.

MMartin 10:05, 20 Oct 2004 (UTC)

 * Maybe referencing them to the Data Structures wikibook would be better (which, sadly, is mostly just wikipedia links for the moment). MShonle 19:22, 20 Oct 2004 (UTC)

 * Sounds like a good idea, although it might be better to do this when there is actual content in the Data Structures wiki book. You can change the links now if you want to, but the users will be send to the wikipedia pages anyway. The only argument for referencing the Data Structures book now is that the book might be looked at one extra time and someone might write content for it. Mmartin 12:15, 22 Oct 2004 (UTC)

 * Well, it's probably suitable either way. I guess I just had a knee-jerk reaction because I didn't want the whole book itself to be filled with links. But since it's just the prereqs it's all fine. (I don't want too many links because I want the reader to, in theory, be able to print out the book and read it. Some of us have even been tossing the idea around of writing a wiki to latex to pdf converter, to get really nicely formatted books made. Alas, no time.) But good point about getting more traffic to the Data Structures book. It's really struggling. MShonle 16:34, 22 Oct 2004 (UTC)

3D OBJECTS
41.116.180.37 (discuss) 19:40, 12 November 2023 (UTC)

 * Discuss 41.116.180.37 (discuss) 19:41, 12 November 2023 (UTC)

Pure Mathematics
@Mmartin 41.116.106.250 (discuss) 06:31, 20 January 2024 (UTC)

title: User talk:Mmartin


text:
User:Free Bear

hi this is me :)

title: User:Free Bear


text:
Talk:Algorithms

Guidelines and direction
Welcome to the project! Thanks all for your contributions. If you are new to writing for this book please read the following guidelines and style adopted:

 * 1) This is a techniques-oriented book: We aren't aiming to create an encyclopedia of every algorithm ever created, nor are we trying to present the absolutely best versions of particular algorithms (though we can of course mention the state of the art and where to find it). At this book's heart, we discuss the high-level "tricks" used by many algorithms in the hope of demystifying them.
 * 2) The book uses pseudocode to efficiently explain the algorithms, but the pseudocode should be clear and expository (and commented when there is a chance for confusion). Additionally, this book includes (will include) Python implementations of the algorithms in an appendix. Appendecies can be written for other languages as well.
 * 3) This is a teaching book: The materials should help the student and the autodidact alike in learning the material. If material requires information not specified in the prerequisites, that information should be covered too. The hope is that after covering this text, the reader can better consult Knuth and CLR (and other algorithms books we should recommend).
 * 4) Use primary sources as much as possible. This is good practice for two reasons: (1) because the book is technique-oriented, sometimes the first presentation of an algorithm is the clearest guide to its insight. For example, the original paper on quicksort simply relied upon "random" in order to get good performance. The layers of deterministic optimizations to quicksort over the past four decades have helped the algorithm, but only mystify a beautiful idea further. And, (2) because this is a free/open book, we must be very careful that we use proper citations and never plagarize other material. (Always ask for permission if you need to use a secondary source.)
 * 5) Use the wikipedia as another source for material, but edit the material to present only the main points and ideas: the encyclopedic detail of the wikipedia can become a distraction when trying to read a book that is not meant to be a reference book.
 * 6) Use the mathematical royal "we" for some phrases, but try to use the second-person "you" as much as possible: it makes sentences easier to construct that also sound more direct.
 * 7) Look for insights into understanding an algorithm or a part of the software engineering process in general.
 * 8) We cover backtracking before dynamic programming and greedy algorithms because both can be thought of as special cases of backtracking.
 * 9) Randomization is an important concept that's gaining more and more ground: it's discussed early instead of later because it shouldn't be thought of as an "advanced" or intimidating topic. It represents an attitude that shows where cutting edge research is heading, so we should be one of the books that best absorbs this paradigm.
 * 10) Please use "active voice", rather than "passive voice". ( Too many texts say stuff like "A null is put on the end of every string.". Huh ? Does that mean I need to make sure I manually add more code to add a newline to the end ? Does that mean the routine already puts a newline at the end of the code ? Does that mean the OS puts these newlines there ? Active voice avoids all this confusion: "The readline puts a null on the end of the string". )

Chapter headings and buckets
I just finished an advanced algorithms course, and this is what we covered. Right now, this is a terribly disorganized list because I'm dumping topics from my handwritten notes here. Later we should reorganize this. I suggest we follow the "big buckets first" approach and keep this as a one-page article until the length becomes unmanageable. Disprosia, when you replaced all my level-one headings, you didn't replace my level-two headings, so you flattened out my list. Some items were children of other items, but now, everything is one the same plane. Was this intentional? If so, it'd be nice if you posted a reason behind that.

 * My two-cents: I think that One-Level headings should be used for Chapter titles. This isn't the wikipedia, so the taboo against using one-level headings doesn't exist. These chapters might be best viewed as separate web-pages, and if that feature were to be implemented, discriminating based on one-level headings would be a good way to go. But I don't know the general wikibook rule of doing it, so I won't modify it back yet. Mshonle 21:35, 30 Jul 2004 (UTC)

This section looks outdated. Should it be removed? --jyasskin 22:19, 22 Jan 2005 (UTC)

 * Sure, is there a standard place to archive it? MShonle 23:49, 22 Jan 2005 (UTC)

Code versus Pseudo Code (was "Guidelines")
Here are my thoughts on where the book should go:

(Mshonle 21:02, 23 Jul 2004 (UTC))
 * 1) introduce backtracking before DP and greedy algorithms, as backtracking is easy to understand and helps in the understanding of DP and greedy.
 * 2) I intend on posting more notes from my own classes.
 * 3) we should use some pseudocode language that makes the algorithms themselves as clear as possible. We shouldn't do just one popular language or try to use multiple languages. pseduocode I've seen lately matches python, so maybe we'll want it to look more like a typed-Python
 * 4) we may want to consider genetic algorithms as well.

Thanks for all the work you've done! Here's my thoughts:
 * 1) I prefer well-commented real code (in any language) over pseudocode.  Pseudocode can be ambiguous.  I suggest we list as many code implementations of algorithms as possible.  I like python and C, but I don't want to get a language war started.  I just know I don't like pseudocode.
 * 2) Genetic algorithms (I think) are used in NP-complete problems, so we should introduce them after that point.

--Waxmop 18:24, 4 Aug 2004 (UTC)

 * For point 1: I think pseudocode is superior to explaining an algorithm than "real code". It's very, very hard to introduce algorithmic concepts if you have language implementation issues to contend with on top of that. Furthermore, I've seen a lot of algorithms books, and only the best books used pseudocode (we'll ignore for the moment that Knuth chose assembly). The syntax I've been using shouldn't be ambiguous at all: if you think something is ambiguous, you should mention it and we can work on it. Also, the pseudocode borrows heavily from Python anyway, only it's *less* ambiguous. For example, I include "end if" (as "fi") and "end for" (as "repeat") so that you can see where one if ends and another begins.

 * I've seen languages mark the bottom of a loop with "next" (BASIC), "loop" (ASM), or "continue" (C). Is there some real language that uses "repeat" ? (I think it's fine for pseudocode). -- DavidCary 03:15, 18 Nov 2004 (UTC)

 * Knuth presented the loop-while-repeat structure in one of his essays in the Literate Programming book. Because the pseudocode looks close enough to Python, but contains different features, it's important to make it look different enough so there's no confusion. The compromise was to include Python implementations of everything in an appendix, so no ambiguity would exist (provided the reader knew Python). MShonle 16:00, 18 Nov 2004 (UTC)

 * I also made this point for the data-structures book: there's no real advantage of including as many languages as possible: the current fad language (which is either Java or C#) and Python should be sufficient. If you want to create a "Python Implementation" appendix for all of the code in the book, feel free, but I most certainly do not want to clutter the text with three different implementations of the same thing (which makes the text look like it has a lack of focus and readers will get bored because perhaps they only care about C++ instead). I propose we use pseudocode for all of the book, and only attempt "real" implementations in an appendix (perhaps on a separate web-page). That should resolve your concernes.

 * For point 2: Genetic algorithms is its own technique, and this is a technique driven book, so if we were to cover them they should get their own chapter. (The "techniques" for NP-complete problems are proving their NP-completeness; i.e. the technique is run-time analysis of the polynomial time verifier and reductions. The backtracking section will include implementations for several NP-complete problems.) Either way, it would be a good idea to include an NP-complete approximation algorithm in the genetic algorithms chapter. I haven't made an outline for it yet as I don't have the materials to cover it. MShonle 19:13, 4 Aug 2004 (UTC)

Here's an example of comparing code. Here's the Python version:

def get_ugliest_puppy(puppies): ugliest = None for p in puppies: if ugliest = None: ugliest = p    elif p.ugliness > ugliest.ugliness: ugliest = p return ugliest

And now the pseudocode:

// find-max -- returns the maximum element, or -infinity if the array is empty function find-max(array vals): let result := $$-\infty$$ for-each v in vals: result := max(result, v) repeat return result end

Where the text will note that max between any object and negative infinitiy will always result in the object. You also note that code should be heavily commented: this is primarily a text, so the "comments" are the descriptions. But I do like the idea of having a sentence before each function, to hammer home "this is what this function should do". (It's good practice in real-life, as well.)

By allowing mathematics into the code, which is what all successful pseudocode based books do, you can speak on the higher-level of mathematics. The Aho book uses "sets" and only later do they mention different data-structures to use to make Dijkstra more efficient. (I think when the Dijkstra section gets written it will be worthy to discuss those trade offs.) There is a danger of being too mathematically clever, but part of the point of the book is to bring the reader into the world of mathematics.

Thinking of "well, I guess I need an if in there that needs to check each time if we're iterating for the first time or not" is not mathematical: it's just implementation details. In contrast, thinking of a for loop as a way to generalize the "max" function is loaded with detail. Once you arm the reader with that insight, they might see where that line of thinking can apply elsewhere.

Note, if we jumped into the functional programming zone, the function would be a one liner:

function find-max(array vals) := reduce(max, null, vals)

I do not think that's the way to go: Then the algorithm becomes too subtle and the solution only seems to be from the heavens: not from some general principle.

Eitherway, I think the strongest argument in favor of pseudocode (after the expository reasons) is that it's less likely to alienate readers than picking one specific language (picking multiple languages doesn't solve the problem because it turns the book into a comparitive programming language text instead of an algorithmic technique text; but a linked-to appendix of implemenations is a fine solution: such code should also have test cases and run results to show that it actually works). MShonle 22:30, 4 Aug 2004 (UTC)

Example pseudocode.
We can put links in the main text that point to implementations in each language. Maybe it would look something like this:

function return-1: return 1 end

The table code for it looks ugly, but it'll be out of the way from the reading yet also easy to access. (Naturally, little code snippits don't need the link, but each completed algorithm could have one.) MShonle 20:42, 5 Aug 2004 (UTC)

Some code we can use
Eric Lippert is allowing us to use this entry from his blog to cover the longest common subsequence. We just need to provide the above link in our references section. (Mshonle 21:02, 23 Jul 2004 (UTC))

Techniques versus Types of Data Philosophy
Because this is a text book, and not an encyclopedia, of algorithms, this book should focus on the underlying algorithmic techniques involved. Text books tend to discuss algorithms in two different ways: the "types of data"-oriented book breaks algorithms discussed into directed graph, undirected graph, string algorithms, and trees chapters; while the techniques-oriented book breaks algorithms discussed into the different techniques used: dynamic programming, greedy algorithms, and divide and conquer.

Naturally, there are books that merge the two philosophies. However, in order to carry a coherent message, and to aid learning, I believe this book should be technique-oriented. The insights to understanding greedy algorithms is aided when you see examples that include directed and undirected graphs. The insights to understanding dynamic programming (a particularly challenging topic to some) is aided when you see examples that include text, numerical, and graph problems. Some people get stuck in certain ways of thinking and seeing the methodolgy of one algorithmic solving technique in different contexts helps. Were we to be an exhaustive encyclopedia, we might consider the other presentation. However, this book must start out slim, and will likely be used to supplement other books already used in courses. Therefore, providing the high-level insights will be beneficial.

We do not want a book that merely brings down "from the heavens" solutions like Dijsktra's algorithm without giving the firm footing underneath to allow people to make their own algorithms. Mshonle 06:48, 30 Jul 2004 (UTC)

Time to break up the single page...
I made a spelling edit to the text and I got a warning that the algorithms pages is 50kb, and some browsers might have trouble. I suggest we break up section into it own link based on the headings. Any other ideas?

 * I think breaking into pages by chapter seems like a good way to do it. The Chapter headings should still exist in the main page (so the table on contents will still be there), but only be links to the full page. That means a chapter might not be able to grow past 32k, though, without seeing the warnings again. I've seen other books try to put a separate page for *everything* and that's just death: No one can read the book as easily, potential future contributors included.

 * Do you know if there is a way to disable to top-level "edit" link? That way the largest text area editable at a time would be a chapter. That would probably be better than the breaking up solution.

 * I've also been discussing writing a tool that can turn the wiki into a pdf file (via latex), which would be a great way to give people something readable. But that shouldn't happen until the book is in better shape. I've been off the project to get work done, but next quarter I'm taking the PhD algorithms class, and I intend to get my notes in as I take it (sure, we've all heard that one before :-). Either way, I don't really like the format of the Data Structures book, which seems to be struggling quite a bit. I think partially the set up seems to encourage people to write wikipedia-like entries (or to copy wikipedia entries), but that's no way to write a textbook. A book needs more focus, and doesn't need to mention all of the history or sidebar level details that are appropriate for an encyclopedia entry. MShonle 03:48, 30 Aug 2004 (UTC)

OK, it's been broken up into chapters. The names of the subsections are the chapter numbers instead of the title of the chapter in hopes to keep the idea that this is all part of a single book, and not a collection of unrelated entries. MShonle 00:28, 29 Sep 2004 (UTC)

Some quick comments after I've read the first chapter:
 * It seems to focus too closely on low-level optimization ( See http://c2.com/cgi/wiki?ProfileBeforeOptimizing http://c2.com/cgi/wiki?OptimizeLater ).
 * It seems to tell people to re-invent the wheel every time (NIH syndrome) rather than use standard library functions.
 * Where's the big-O notation ?

I hope this is covered in later chapters

-- DavidCary

 * Hi David, Big-O notation is covered in the second chapter. Also, I'm not sure why you think that the chapter is focused on low-level optimization? I thought the "When is Efficiency Important?" subsection addressed that quite well. (Moreover, I don't think we even mention any low-level optimizations. We discuss different implementations for to-lower, but that's only to motivate the point for abstraction and the different levels of thinking.) If you are thinking of something else, please do explain.

 * As for the reinventing the wheel: The goal of the book is to introduce algorithmic techniques. We could invent problems (like homework assignments) that don't have solutions in libraries and present algorithms that solve them, but I think it's more natural to present well-known problems, because the motivation is better and the statement of the problem is easier. (The Python appendix has a note to implementers to demonstrate the use of standard libraries.) Either way, reinventing the wheel can be good, too: You want to avoid it as a common practice, but doing it once when taking a course in algorithms can be quite instructive. Every cute guideline has an exception. MShonle 16:13, 18 Nov 2004 (UTC)

Some links that can handy...
See if this community tool can give any help finding other sources...

http://del.icio.us/tag/algorithms

 * This would also be useful for the Computer Science:Advanced Data Structures and Algorithms book, which is much more eclectic in content and is still looking for new items. MShonle 04:49, 29 Dec 2004 (UTC)

 * I think it's cool for any other book but as I saw that you were active on this I just passed the information :) just add to the end next to the tag, I have included it on the C++ book that I'm contributing to...--Panic 05:31, 29 Dec 2004 (UTC)

All Chapters View
I created some templates that redirect to each chapter and then made an Uberpage that includes all of the templates.

You can find the link here: Computer_Science:Algorithms:Full_Text

I don't want to post it too many places yet, because it might cause for some heavy server load. Also, it includes the chapter nav templates at the beginning and end of each chapter: A Chapter_1_contents page (e.g.) would have to be created that would be the real content of the book, and then the single-chapter view of each would include the content plus the navigation, and the many-chapter view would only include all of the content pages. (Navigation might also be hurt in that style.) Perhaps for the Data Structures book we can try it that _content-based way to see how it works because there's still quite a bit of outlining left to do for that book.

Any other ideas welcome. -- MShonle 05:14, 29 Dec 2004 (UTC)

 * I like this concept very much! I started to try a little bit in my private sandbox how to improve this concept and make it more generally accessible. I thought of using templates to shield navigational elements in the PRINT version, so that one does not have to put all the content in templates (which has the disadvantage, that a user can not click "edit this page" on top to make changes). The shielding could work by using templates with parameters, but one has to be a little bit tricky. I've also been playing around with CSS2 page breaks (that currently work in Firefox) which might enhance the printing experience. All of this is in development, but I will let you know when it works, and when I have a handful of simple templates that anybody can use. (For now, if you have some time, help me to review some books and give development stages to some books on the IT bookshelf) (Another hint: templates don't actually have to be in the template: namespace. Each page can be included by preceding ":", like ). --Andreas Ipp 11:58, 15 Jan 2005 (UTC)

 * The Computer Science:Data Structures book handles it a little cleaner, but has the drawback that you are editing a _content page, the pointer of which you need to visit through a template. MShonle 08:11, 16 Jan 2005 (UTC)

Review
Hi MShonle. I just reviewed your book to update your development stages. It is a very clearly written book. I think the chapters are more complete than you suggest by having all the "ToDos" around each chapter. Even without them, the chapters look consistent to me, and I would give more chapters "100%" (and attract more possible readers) if you just deleted the ToDos, or put them collectively at the very end. But having empty subsection titles all over is not so reader-friendly, according to my opinion (and I am a reader! :-) ). See also my comment above on "All Chapters View" .--Andreas Ipp 11:58, 15 Jan 2005 (UTC)

 * Thanks. I think there's some more work that needs to be done before attracting more readers: it's still very much in the cathedral stages right now. Right now trying to get more writers is my primary objective. MShonle 08:14, 16 Jan 2005 (UTC)

 * Followup: Another reason to embed the TODOs right now is because the author of a section has an "ultimate plan" for that section, and the TODOs reflect the structure desired. How to present materials is highly subjective, so there isn't a "default" way for contributors to write, say, a divide and conquer chapter. MShonle 17:48, 17 Jan 2005 (UTC)

 * Hi MShonle, I guess I got your point. If you have a clear view of how things should be structured, then this is probably the best way. You're right, there's no point in presenting something as "ready" if it just is not yet. Actually, when browsing through your chapters, I thought about adding Newton's approximation by myself, but I was not quite sure how it would fit from the programming side (I'm more a physicist..). Keep the work, it is really getting a great book! --Andreas Ipp 21:39, 17 Jan 2005 (UTC)

 * Please do add, w.r.t. Newton's square root method (the general method should probably go in the calculus book isntead). For the programming I can put in the code. (Or, you can post an outline on the talk page before you write too much?) MShonle 23:20, 17 Jan 2005 (UTC)

 * I just added it to your chapter 8, Newton's Root Finding Method. Just after I added it, I found your comment that you just would like the square root formula. Well, I hope it is not too long now, and in principle, the Newton's method should be familiar from middle school (I guess, there is nothing wrong with presenting a little bit of calculus to programmers). --Andreas Ipp 00:16, 18 Jan 2005 (UTC)

 * Thanks! One style note is that we want to use wikipedia links as sparingly as possible: the idea is that the book should be self-contained and someone could print it out and use it, instead of clicking through many external pages. As for the calculus angle, perhaps the square root method itself could be derived from the more general material, and have the algorithm that uses the simpler method (i.e., averaging the guesses) be presented first. Thus, the calculus details can still be there, but be in a starred ("*") section to let the reader know it's not essential to know to understand later material. --MShonle 00:41, 18 Jan 2005 (UTC)

 * A star * section (or a note to skip at first reading) is fine with me. About the Wikipedia links: They won't show on printed material (look at your browser's Print Preview, if it supports CSS), and on screen they add interactivity: If I don't know a word, I just click on it, instead of having to type it into Google. It doesn't mean I have to follow all the links there are. I see it as a possibility to enhance the screen version of Wikibook (by its partner Wikipedia) to something more "live" than a "real" book. This said as a suggestion, the main stylistic decisions are of course determined by the main contributors (which is you..) --Andreas Ipp 02:19, 18 Jan 2005 (UTC)

 * Thanks for the comments: I have nothing against rich-links in principle, but they can create a confusing congitive experience for the reader. For example, they might think "do I need to understand this link?", "do I need to follow this?", and there's no clear answer as to how far the links should be followed. The rule of thumb is that if the link is required, it should be replaced with further exposition in the text instead. If a link isn't required, then perhaps a link at the bottom in a special "for further reading" section could be done. But too much information overload can turn a reader off: it can be exhausting either following links or determining not to follow links. (We may even privately decide that "all links are optional" but the challenge still remains that the reader might not know that, and second guess.)

 * Naturally, I think the wikipedia itself should have as many links as possible (within reason) because part of the value of the wikipedia is the richness of the links as a way for someone doing research to start from, say, Alan Greenspan, and follow links to the Federal Reserve, to the money supply, to inflation. But for wikibooks, I see the goal is primary to educate and have the reader gain special knowledge of a single topic. Too many distractions can hurt the focus. Most of the topics we cover are also wikipedia articles, so the tutorial nature is the value we are adding on top of that. --MShonle 02:47, 18 Jan 2005 (UTC)

 * Sidenote: For one example, links such as "root of a function" are probably best removed with a discussion of what a root of a function is (presumably copied from the wikipedia) and put in the Mathematical Background chapter of the text. Other links, such as "derivative" are probably too advanced: either the user will understand calculus and know already what a derivative is, or wouldn't be enlightened enough following the link: some concepts require a semester to really "get". (Though, I suppose you could make an arugment for including a link to the calculus book.) MShonle 02:57, 18 Jan 2005 (UTC)

 * Sidenote #2: I also forgot to mention the role of the Advanced book: it's much more eclectic in content and is meant to be more of a reference than a tutorial that is read cover-to-cover. Thus, in that context I could also see the high value of using wikipedia links. --MShonle 03:07, 18 Jan 2005 (UTC)

Guidelines Questions

 * Should all math be placed in  tags? This conflicts with the advice at How to write a Wikipedia article on Mathematics, but of course, local guidelines win out. --jyasskin 22:19, 22 Jan 2005 (UTC)

 * My general bias is to use the math tags when possible. It's easier to type the single-quote versions, so there are places that still use them. Also, the pseudocode formatting is different: all variable names are slanted while only functions defined in the book, or as an exercise, are bold-- assumed library functions like max or abs aren't bolded. (This is as opposed to making keywords bold, which draws attention to the very thing that needs the least attention.) Function or variable names refered to in the text probably should not have the math tag, while actual formulas should.

 * The general idea is that a wiki to LaTeX tool will be written and the user can download a clean PDF: the conversion process will be easier if the tag is used consistently. (Also, for publishing, the other plan is that this book and the Data Structures book would be combined into a single Data Structures and Algorithms book.) MShonle 00:19, 23 Jan 2005 (UTC)

 * How deeply nested should headings be? In chapter 2, my first inclination is to make a separate subheading for each term that's defined. Is that reasonable, or are you trying to keep the heirarchy as flat as possible? --jyasskin 22:19, 22 Jan 2005 (UTC)
 * I think it's more of a question of emphasis. The Mathematical Definitions section is primarily there to provide a little more detailed explaination of elements used in later chapters.

 * For example, in the Longest Common Subsequence section I realized that I shouldn't assume everyone knew what a subsequence (or what a sequence) was, so that it needed to be defined along with some suitable examples. Instead of distracting from the discussion with the defintion and examples, I decided to put it in the front of the book. (Another goal is to avoid wikipedia links, so that the reader can enjoy the book on its own (possibly printed out) and not get frustrated trying to figure out what is just a footnote and what is manditory. Of course, much of the content in that section has been copied from the wikipedia, but edited for tutorial purposes.)

 * So, having headings would probably draw too much attention to what really is a glorified footnote and probably attract contributions trying to cover the topic in further depth, even though such depth might not be useful in understanding the rest of the book. MShonle 00:19, 23 Jan 2005 (UTC)

Check sort - precursor to the Rapid sort - used to eliminate duplicates
I have "invented" several algorithms which after having been reduced t minimum form are so simple it is obvious that any other computer programmer could have invented them independently. The Check sort is a good example. The Check sort not only sorts numerical data (and potentially also alphanumeric data converted to its ASCII code) it main value and purpose is in eliminating duplicates. Even though simple enough to have been invented independently and at a prior time I have not been able to find another algorithm which duplicates its function although others have claimed that its successor the Rapid sort is nothing more than a version of the Bucket sort in one instance or the Counting sort in another. I feel that both sort routines are useful and unique enough, however, as to merit their distinction and publication somewhere even though they have not been published elsewhere except on my homepage in 1996 and briefly in the past month in the Wikipedia (now restricted to talk pages) The Rapid sort is now published on line in the Urban Dictionary. Furthermore because I modified the Harvard Chart Method of Logical Equation Reduction to handle multiple states so that I might explore a computer's capability of reducing multiple state logical equations to minimum form and thus be able to "think" at the level of a human being and comment on such issues as to whether God exists or not (which actually as a result led me to the logical definition of God that God is the only entity by definition who can reduce an infinite number of equations having an infinite number of variables with and infinite number of states to minimum form instantaneously) it can not be published under the WP:NOR policy. The same restriction applies to an article entitled "Optimal classification" I wrote about Dr. Rypka's method of microbiological classification after using my own research to answer several questions, clarify several misconceptions and eliminate other points of confusion. I would therefore like to inquire about publication of these methods here. Typetive 09:49, 5 June 2006 (UTC)

 * This book is a catalog of algorithmic techniques, not a catalog of every algorithm ever invented by somebody. I just don't think it really fits the aim of this book. --MShonle 00:57, 3 July 2006 (UTC)
 * Most such algorithms will not find themselves in this book anyway since they were originally published by the ACM or IEEE or other Journals who copyright their publications and require paid membership and or subscriptions or purchase of the articles in which the algorithms appear. In this case the author has presented an algorithm without requiring its purchase, a rare but welcome event. Typative (talk) 17:31, 6 October 2007 (UTC)

Merge with other book: Nay
I see no meritt in merging the Algorithm implementation book with this one. The two books have different aims. To have the best learning experience books must be focused and not aim to be everything to everyone.

My recommended course of action is that the two projects be aware of each other's aims. Given that the table of contents for this book is fixed and stable all that's required is that the new book's plan complements this book's plan. It's probably misleading that both books have the word "Algorithm" in the title. In one, it's the mathematical definition, while the other is the more general programming definition (as a synonym for "subroutine"). --MShonle 01:04, 3 July 2006 (UTC)

 * Fair point. I comment on Talk:Algorithm implementation --Krischik T 06:19, 3 July 2006 (UTC)

```` I am very very new to WIKI, but very very old in the computer game, I published my first computer paper, the design of a random access system for manufacturing control in 1958. I have since retired from BTL/WE/etc and playing at computer. I looked with interest in your development of a book, inh public ..., that is very good. Now the final very very good step would be for you to PROVE conclusively thatthe algorithms that you may illustrate really work, and if the need for final code rather than pseudo code then you MUST prove their equivalency, and then having done that your printing system for the final imprint MUST develop the result of the algorithm in real time using the correct softsware as part of the type setting system, so that you need not actually provide the answer to be typset. That is the most likely point of error. This has been done long ago in the Manual for the sam76 language, and the only time there was a erroneous answer was traced back to a fault in the algorithm manjuscript. An example of what I mean is in Algorithms in Sam76 rectly posted in Wikki. Good Luck Algorithms in Sam76

Standardized pseudocode
Is there a page that specifies the pseudocode that is to be used in this wikibook?

If more than a couple of people are going to contribute, it really needs to be defined and included as an appendix in the book as well as in a style guide. I've spent about 1/2 hr trying to find some kind of specification, and haven't been able to. 69.181.2.10 23:58, 30 August 2006 (UTC) Joe_n_bloe

 * There was a definition called Wikicode but it is now depreciated and was not never used in Algorithms. Personaly I think rightfully - a pseudocode should use little special characters as possible (better begin/end then '{'/'}' - you can look up the meaning of begin in an english dictonary but not the meaning of '{') . Krischik T 08:17, 31 August 2006 (UTC)

Come on!Let's work harder!
It is a pity that this book is far from being complete.I hope this book can be interesting and easy to understand. More examples and pictures and animations are needed. Visame (talk) 19:40, 3 May 2008 (UTC)

print version license
you need to update the license notice in the print version, I would do it but I am not sure how it should read.

Prime numbers
Hello, there is a book in the Mathematics subject, A More Efficient Prime Number Generating Algorithm, that I wonder if it might fit in this book? I have not taken a course on algorithms so I do not know and I wonder what those who have worked on this book think? This book has some original research, it is short (more like a section than a book), and is mostly on an algorithm to make a list of primes. So, I thought maybe it could fit here somewhere. And, since it has no references and seems to have original research, I thought perhaps one of you might know of a reference on the subject to use as well instead of just copying directly from this other "book". Any thoughts? NumberTheorist (talk) 20:10, 14 February 2010 (UTC)
 * Oh, I see above that there is another book, Algorithm Implementation, and perhaps this would fit there instead if it doesn't seem like a good fit here? NumberTheorist (talk) 20:12, 14 February 2010 (UTC)
 * Yes good have in day net .welcome on so side note.what be i done so it by look it after to. 2401:4900:4478:86D4:0:1:DD31:E601 (discuss) 08:35, 29 March 2023 (UTC)

title: Talk:Algorithms


text:
User:Tim Starling

Developer, see w:User:Tim Starling

User:Lobster has responded to a request to cease libel with further libel. This is directly in violation of wiki policy which states that no personal attacks are to be made.

I appologize if this is not the appropriate forum for such issues -- I could not find anything relevant.

Thank you for your time.

--Eibwen 06:25, 27 Sep 2004 (UTC)

title: User:Tim Starling


text:
User talk:Laudaka

Dear Laudaka,

I don't understand the link to WordPerfect WordPerfect on pages . Does that page exist ?
 * http://en.wikibooks.org/wiki/Template:IT_bookshelf
 * http://en.wikibooks.org/wiki/IT_bookshelf

title: User talk:Laudaka


text:
Linear Algebra/Matrices

Matrices and Linear Transformations
It turns out that linear transformations can be represented in a 1-1 fashion in matrices. This chapter will be most likely be a review as the topic has already probably been covered in high school (see this link). The establishment of a one-to-one correspondence between linear transformations and matrices is very important in the study of linear transformations.

Suppose you have a set of basis vectors x1, x2, x3, ..., xm of a vector space X and basis vectors y1, y2, y3, ..., yn of a vector space Y.

Consider a linear transformation T from X to Y, and the vectors

T(x1)=y1a11+y2a21+y3a31+...+ynan1, T(x2)=y1a12+y2a22+y3a32+...+ynan2, T(x3)=y1a13+y2a23+y3a33+...+ynan3, ... T(xm)=y1a1m+y2a2m+y3a3m+...+ynanm,

You can arrange these coefficients in a matrix

$$M= \begin{pmatrix} a_{11} & a_{12} & a_{13} & \ldots & a_{1m} \\ a_{21} & a_{22} & a_{23} & \ldots & a_{2m} \\ a_{31} & a_{32} & a_{33} & \ldots & a_{3m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ a_{n1} & a_{n2} & a_{n3} & \ldots & a_{nm} \\ \end{pmatrix}$$.

Thus, if you have any vector

$$x=\sum_{j=1}^m x_j b_j$$,

Then

$$T(x)=T(\sum_{j=1}^m x_j b_j)=\sum_{j=1}^m b_j T(x_j)=\sum_{j=1}^m b_j \sum_{i=1}^n y_i a_{ij}=\sum_{i=1}^n y_i \sum_{j=1}^m a_{ij} b_j $$

Thus, T(x) is a linear combination of basis vectors

$$\sum_{i=1}^n y_n c_i$$, where

$$c_i=\sum_{j=1}^m a_{ij} b_j$$.

Thus knowledge of a matrix in respect to bases can determine the value of a the result of a linear transformation.

Thus, given any matrix, there is a corresponding function with the results being

$$\sum_{i=1}^n y_n c_i$$, where

$$c_i=\sum_{j=1}^m a_{ij} b_j$$.

This is obviously a linear operator, whose matrix coincides with the matrix used. This establishes the fact that every n by m matrix can determine a linear operator mapping an m dimensional vector space into an n dimensional vector space.

Addition
Define the sum C=A+B where A and B are linear transformations to be the function C(x)=A(x)+B(x). One can easily verify that this is also a linear transformation. You can verify that given two linear transformations A and B, that

 * 1) A+B=B+A
 * 2) (A+B)+C=C+(B+A)
 * 3) A+0=A
 * 4) A+(-A)=0

where 0 is the zero operator -A is the function -A(x) which one can easily verify to be a linear transformation.

Scalar multiplication
Given a linear transformation a, define the function $$\mu A$$ where $$\mu$$ is an element of a field to be the function $$(\mu L)(x)= \mu (L(x))$$.

You can easily verify that given a linear transformations A and B and an elements of a field $$\mu$$, $$\mu_1$$, and $$\mu_2$$, that

 * 1) $$\mu_1 (\mu_2 A) = (\mu_1 \mu_2)A$$
 * 2) $$ 1A=A $$
 * 3) $$ (\mu_1 + \mu_2)A = \mu_1 A + \mu_2 A$$
 * 4) $$ \mu (A+B) = \mu A + \mu B $$

This implies that linear transformations form a vector space.

Multiplication
Given a linear transformation A from X to Y and a linear transformation B from Y to Z, then define the function AB from X to Z to be the composition of the two functions. One can easily verify that this is also a linear transformation.

Here are some useful relations that can easily be verified:

 * 1) $$ \mu (AB) = (\mu A)B$$
 * 2) $$ (A+B)C=AC+BC$$
 * 3) $$ C(A+B)=CA+CB$$
 * 4) $$ (AB)C=A(BC)$$.

Corresponding algebra of matrices
Since there is a one-to-one correspondence between linear transformations from m-dimension spaces to n-dimensional spaces and m-by-n matrices, the addition, scalar multiplication, and multiplication operations are defined in their one-to-one correspondence, and all properties stated above hold for matrices. The addition of matrices M and N can be defined as the matrix that corresponds to the sum m+n where m and n are the linear transformations that correspond to M and N respectively. The other operations are defined similarly.

Addition
Let A = |aij| and B = |bij| be two matrices of dimension n by m. Consider A and B which are the corresponding linear transformations from an m-dimensional vector space M to an n-dimensional vector space N. Let m1, m2, m3, ..., mm, be basis vectors of M and n1, n2, n3, ..., nn be basis vectors of N. Then

$$A(m_i)=\sum_{j=1}^n a_{ij} n_j $$, and $$B(m_i)=\sum_{j=1}^n b_{ij} n_j $$.

Thus

$$(A+B)(m_i)=\sum_{j=1}^n(a_{ij}+b_{ij})n_j$$

so the matrix of this operator has entries |aij+bij|. In other words, the sum of two matrices have entries that are the sum of the corresponding entries of the two matrices.

Examples:

\begin{pmatrix} 1 & 3 \\   1 & 0 \\    1 & 2  \end{pmatrix} + \begin{pmatrix} 0 & 0 \\   7 & 5 \\    2 & 1  \end{pmatrix} = \begin{pmatrix} 1+0 & 3+0 \\   1+7 & 0+5 \\    1+2 & 2+1  \end{pmatrix} = \begin{pmatrix} 1 & 3 \\   8 & 5 \\    3 & 3  \end{pmatrix} $$

Once addition is defined we have obviously also defined subtraction. A - B is computed by subtracting corresponding elements of A and B, and has the same dimensions as A and B. For example:

\begin{pmatrix} 1 & 3 \\   1 & 0 \\    1 & 2  \end{pmatrix} - \begin{pmatrix} 0 & 0 \\   7 & 5 \\    2 & 1  \end{pmatrix} = \begin{pmatrix} 1-0 & 3-0 \\   1-7 & 0-5 \\    1-2 & 2-1  \end{pmatrix} = \begin{pmatrix} 1 & 3 \\   -6 & -5 \\    -1 & 1  \end{pmatrix} $$

Scalar multiplication
Scalar multiplication of matrices shall be defined to be the corresponding matrix of the scalar product of the corresponding linear transformations.

Consider a matrix A with entries |aij| and its corresponding linear transformation A from M to N, and an element of a field $$\mu$$, and let m1, m2, m3, ..., mm, be basis vectors of M and n1, n2, n3, ..., nn be basis vectors of N. Since

$$(\mu A)(m_j)=\sum_{i=1}^m \mu a_{ij} n_i = \mu \sum_{i=1}^m a_{ij} n_i$$, the entries of the corresponding matrix is has entries |$$\mu$$aij|.

For example, multiplication by 2 of a matrix:

 * $$2 \cdot

\begin{pmatrix} 1 & 8 & -3 \\   4 & -2 & 5  \end{pmatrix} = \begin{pmatrix} 2 \cdot 1 & 2\cdot 8 & 2\cdot -3 \\ 2\cdot 4 & 2\cdot -2 & 2\cdot 5 \end{pmatrix} = \begin{pmatrix} 2 & 16 & -6 \\   8 & -4 & 10  \end{pmatrix} $$

Scalar Multiplication has the following properties, which have been proven because of its one-to-one correspondence to Linear Transformations:

 * 1) Left distributivity: (α+β)A = αA+βA.
 * 2) Right distributivity: α(A+B) = αA+αB.
 * 3) Associativity: (αβ)A=α(βA)).
 * 4) 1A = A.
 * 5) 0A= 0.
 * 6) (-1)A = -A.

Matrix multiplication
As above, matrix multiplication will also be defined as its correspondence to linear transformations. The product of two matrices is the corresponding matrices of the product of the corresponding two linear transformations.

Consider an o by n dimensional matrix A with entries |aij|, n by m dimensional matrix B with entries |bij|, and let A be a linear transformation from n-dimensional M to o-dimensional O that corresponds to A, and let B be a linear transformation from m-dimensional N to n-dimensional N that corresponds to B, and let m1, m2, m3, ..., mm, be basis vectors of M, n1, n2, n3, ..., nn, be basis vectors of N, o1, o2, o3, ..., oo, be basis vectors of O. Then

$$(AB)(m_i)=A(\sum_{j=1}^n b_{ji} n_j)=\sum_{j=1}^n b_{ji} A(n_j)=\sum_{j=1}^n b_{ji} \sum_{k=1}^o a_{kj} o_k = \sum_{k=1}^o (\sum_{j=1}^n a_{kj}b_{ji}) o_k$$

Thus the corresponding matrix has entries |pij| that are given by:

$$ p_{ij} = \sum_{k=1}^n a_{ik} b_{kj}$$

For example:

\begin{pmatrix} 1 & 0 & 2 \\      -1 & 3 & 1 \\    \end{pmatrix} \times \begin{pmatrix} 3 & 1 \\       2 & 1 \\        1 & 0 \\    \end{pmatrix} =   \begin{pmatrix}

( 1 \times 3 +  0 \times 2  +  2 \times 1) & ( 1 \times 1 +  0 \times 1  +  2 \times 0) \\

(-1 \times 3 +  3 \times 2  +  1 \times 1) & (-1 \times 1 +  3 \times 1  +  1 \times 0) \\

\end{pmatrix} $$

=   \begin{pmatrix} 5 & 1 \\       4 & 2 \\    \end{pmatrix}. $$

Matrix multiplication has the following properties, which have been verified due to the fact that they are also true of linear transformations.

 * 1) Associativity: A(BC) = (AB)C.
 * 2) Left distributivity: A(B+C) = AB+AC.
 * 3) Right distributivity: (A+B)C = AC+BC.
 * 4) IA = A = AI.
 * 5) α(BC) = (αB)C = B(αC).

Matrix multiplication is in general not commutative, i.e. there exist matrices for which AB $$\ne$$ BA. An example can be given by: $$A = \begin{pmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \end{pmatrix}$$ and $$B = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}$$

The way matrix multiplication is defined seems illogical and strange; why can matrix multiplication not be defined as just multiplying corresponding entries as in the case of addition and scalar multiplication? Unfortunately the actual answer will be available to us only later on in Chapter 3. In the meantime we will satisfy ourselves by noting the advantage that matrix multiplication gives us by representing a linear system in matrix form. This will be clear in the following section.

At this point we see fit to make another definition. An n by n matrix A is invertible if and only if there exists a matrix B such that
 * AB = In = BA.

In this case, B is the inverse matrix of A, denoted by A−1. Clearly the inverse of the identity matrix is itself. We will study invertible matrices in detail later.

One point more is to be noted here. The type of matrix multiplication when the product matrix is simply the matrix obtained by multiplying the corresponding entries of two equal dimension matrices also has a name. It is called the Hadamard product. We shall not use this kind of multiplication. Throughout the book matrix multiplication will always refer to the matrix product defined above.

Determinants of Products of Matrices (Binet's Theorem)
In addition, the determinant is a multiplicative map in the sense that
 * $$\det(AB) = \det(A)\det(B) \,$$ for all n-by-n matrices $$A$$ and $$B$$.

This is generalized by the Cauchy-Binet formula to products of non-square matrices.

Matrices and system of linear equations
The concept of a matrix was historically introduced to simplify the solution of linear systems although they today have much greater and broad-reaching applications. Let's see how a linear system can be represented using a matrix.

Consider a general system of m linear equations with n unknowns:

 * $$\begin{alignat}{7}

a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \cdots + \;&& a_{1n} x_n &&\; = \;&&& b_1     \\ a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \cdots + \;&& a_{2n} x_n &&\; = \;&&& b_2     \\ \vdots\;\;\; &&    && \vdots\;\;\; &&              && \vdots\;\;\; &&     &&& \;\vdots \\ a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \cdots + \;&& a_{mn} x_n &&\; = \;&&& b_m     \\ \end{alignat}$$

The system is equivalent to a matrix equation of the form
 * $$A\mathbf{x}=\mathbf{b}$$

where A is an m×n matrix, x is a column matrix with n entries, and b is a column matrix with m entries.

A= \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix},\quad \mathbf{x}= \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix},\quad \mathbf{b}= \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix} $$

Clearly our manner of defining matrix multiplication is used in representing the linear system in this fashion because now the product of the matrix A and the matrix x gives us precisely the matrix b.

Representing linear systems in this fashion also enables us to easily prove the following theorem:

 Theorem 1: Any system of linear equations has either no solution, exactly one solution or infinitely many solutions.

Proof: Suppose a linear system Ax = b has two different solutions given by X and Y. Then let Z = X - Y. Clearly Z is non zero and A(X + kZ) = AX + kAZ = b + k(AX - AY) = b + k(b - b) = b so that X + kZ is a solution to the system for every possible value of k. Since k can assume infinitely many values so clearly we have an infinite number of solutions.

Exercises
Hints to many of the exercises can be found at Famous Theorems of Mathematics/Algebra/Matrix Theory.

1. Let A and B be m × matrices. Then:
 * (i) $$(kA)^T$$ = $$kA^T$$
 * (ii) $$(A+B)^T = A^T + B^T$$
 * (iii) $$(AB)^T = B^TA^T$$

2. Let a triangular matrix be a square matrix with either all (i,j) entries zero for either i<j (in which case it is called an lower triangular matrix) or for j<i (in which case it is called an upper triangular matrix). Show that any triangular matrix satisfying $$AA^T = A^TA$$ is a diagonal matrix.

3. For a square matrix A show that:
 * (i) $$AA^T$$ and $$A+A^T$$ are symmetric
 * (ii) $$A-A^T$$ is skew symmetric
 * (iii) A can be expressed as the sum of a symmetric matrix, $$\frac{1}{2}(A+A^T)$$ and a skew symmetric matrix $$\frac{1}{2}(A-A^T)$$

4. Suppose A is a m×n matrix and x is a n×1 column vector. Show that if $$x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix}$$ and $$A=\begin{pmatrix}c_1 & c_2 &\cdots c_n \end{pmatrix}$$ where $$c_j=\begin{pmatrix}A_{1j}\\A_{2j}\\\vdots\\A_{mj}\end{pmatrix}$$ then $$Ax = x_1c_1+x_2c_2+\cdots x_nc_n$$. This is also expressed by saying that Ax is a linear combination of the columns of A.

title: Linear Algebra/Matrices


text:
Classic Mac OS

Introduction
Property of: Apple Latest Version: 9.2.2 Status: Ceased Development

The Apple Macintosh platform uses its own operating system known as Mac OS. Subsequent releases of the operating system have been denoted by appending the version number, such as Mac OS 9. With the advent of Mac OS X based on FreeBSD, previous versions have become known as Classic Mac OS and are no longer supported by Apple. Despite the lack of support, many systems running the Classic Mac OS are still in use today.

Graphical User Interface
Mac OS featured the first graphical user interface (GUI) on a mass produced computer. (Xerox produced the first GUI, but it did not enter production.) Many of the features of the original release of Mac OS are still implemented in modern operating systems, including:

 * Icons
 * Shortcuts
 * Mouse usage
 * Visual interactions (e.g. drag and drop)
 * Windows, buttons and dialog boxes
 * Boot directly into visual interface
 * Cut-and-paste

The ability to interact graphically with the operating system significantly reduced the learning curve. Initially many doubted the viability of the Macintosh for business applications, as the GUI was a significant departure from console based terminals. This preconception was dispelled largely through the passage of time and the adoption of GUIs in several other operating systems.

Table of Contents
The Macintosh Interface
 * /Menus and Windows/
 * The  Menu
 * /Application Menu/

title: Classic Mac OS


text:
Robotics/Components/Power Sources

Though perhaps other power sources can be used, the main sources of electrical power for robots are batteries and photovoltaic cells. These can be used separately or together (for practical applications, most solar-powered robots will need a battery backup).

Photo voltaic cell

Photo Voltaic Cells, also known as solar cells are well known for their use as power sources for satellites, green energy creation and pocket calculators. In robotics solar cells are used mainly in BEAM robots. Commonly these consist of a solar cell which charges a capacitor and a small circuit which allows the capacitor to be charged up to a set voltage level and then be discharged through the motor(s) making it move.

For a larger robot solar cells can be used to charge its batteries. Such robots have to be designed around energy efficiency as they have little energy to spare.

Batteries
Batteries are an essential component of the majority of robot designs. Many types of batteries can be used. Batteries can be grouped by whether or not they are rechargeable.

Batteries that are not rechargeable usually deliver more power for their size, and are thus desirable for certain applications. Various types of alkaline and lithium batteries can be used. Alkaline batteries are much cheaper and sufficient for most uses, but lithium batteries offer better performance and a longer shelf life.

Common rechargeable batteries include lead acid, nickel-cadmium (NiCd)and the newer nickel metal-hydride (Ni-MH). NiCd & Ni-MH batteries come in common sizes such as AA, but deliver a smaller voltage than alkaline batteries (1.2V instead of 1.5V). They also can be found in battery packs with specialized power connectors. These are commonly called race packs and are used in the more expensive RC race cars. They will last for some time if used properly. Ni-MH batteries are currently more expensive than NiCd, but are less affected by memory effect.

Lead acid batteries are relatively cheap and carry quite a lot of power, although they are quite heavy and can be damaged when they are discharged below a certain voltage. These batteries are commonly used as backup power supply in alarm systems and UPS.

An extremely common problem in robots is "the microcontroller resets when I turn the motor on" problem. When the motor turns on, it briefly pulls the battery voltage low enough to reset the microcontroller. The simplest solution   is to run the microcontroller on a separate set of batteries.

History of the Battery

The first evidence of batteries comes from discoveries in Sumerian ruins dating around 250 B.C.E. Archaeological digs in Baghdad, Iraq. But the man most credited for the creation of the battery was named Alessandro Volta, who created his battery in the year 1800 C.E. called the voltaic pile. The voltaic pile was constructed from discs of zinc and copper with pieces of cardboard soaked in saltwater between the metal discs. The unit of electric force, the volt, was named to honor Alessandro Volta. A time line of breakthroughs and developments of the battery can be seen here.

How a Battery Works
Most batteries have two terminals on the exterior, one end is a positive end marked “+” and the other end is the negative marked “-”. Once a load, any electronic device, a flashlight, a clock, etc., is connected to the battery the circuit being completed, electrons begin flowing from the negative to positive end, producing a current. Electrons will keep flowing as fast as possible until the chemical reaction on the interior of the battery lasts. Inside the battery there is a chemical reaction going on producing the electrons to flow, the speed of production depends on the battery’s internal resistance. Electrons travel from the negative to positive end fueling the chemical reaction, if the battery isn’t connected then there is no chemical reaction taking place. That is why a battery (except Lithium batteries) can sit on the shelves for a year and there will still be most of the capacity to use. Once the battery is connected from positive to negative pole, the reaction starts, that explains the reason why people have gotten a burn when a 9-volt battery in their pocket touches a coin or something else metallic to connect the two ends, shorting the battery making electrons flow without any resistance, making it very, very hot.

Main Concerns Choosing a Battery

 * -        Geometry of the batteries. The shape of the batteries can be an important characteristic according to the form of the robots.
 * -        Durability. Primary(disposable) or secondary (rechargeable)
 * -        Capacity. The capacity of the battery pack in milliamperes-hour is important. It determines how long the robot will run until a new charge is needed.
 * -        Initial cost. This is an important parameter, but a higher initial cost can be offset by a longer expected life.
 * -	Environmental factors. Used batteries have to be disposed of and some of them contain toxic materials.

PRIMARY (DISPOSABLE) BATTERY TYPES
 * •	Zinc-carbon battery - mid cost - used in light drain applications
 * •	Zinc-chloride battery - similar to zinc carbon but slightly longer life
 * •	Alkaline battery - alkaline/manganese "long life" batteries widely used in both light drain and heavy drain applications
 * •	Silver-oxide battery - commonly used in hearing aids
 * •	Lithium Iron Disulphide battery - commonly used in digital cameras. Sometimes used in watches and computer clocks. Very long life (up to ten years in wristwatches) and capable of delivering high currents but expensive. Will operate in sub-zero temperatures.
 * •	Lithium-Thionyl Chloride battery - used in industrial applications, including computers and electric meters. Other applications include providing power for wireless gas and water meters. The cells are rated at 3.6 Volts and come in 1/2AA, AA, 2/3A, A, C, D & DD sizes. They are relatively expensive, but have a proven ten year shelf life.
 * •	Mercury battery - formerly used in digital watches, radio communications, and portable electronic instruments, manufactured only for specialist applications due to toxicity

Helpful link comparing the most popular types of batteries in many different types of categories

SECONDARY (RECHARGEABLE):

(Will be discussing the two most popular secondary batteries)

Lithium-ion Batteries:

Advantages:

These batteries are much lighter than non-lithium batteries of the same size. Made of Lithium (obviously) and Carbon. The element Lithium is highly reactive meaning a lot of energy can be stored there. A typical lithium-ion battery can store 150 watt-hours of electricity in 1 kilogram of battery. A NiMH (nickel-metal hydride) battery pack can store perhaps 100 watt-hours per kilogram, although 60 to 70 watt-hours might be more typical. A lead-acid battery can store only 25 watt-hours per kilogram. Using lead-acid technology, it takes 6 kilograms to store the same amount of energy that a 1 kilogram lithium-ion battery can handle. Huge difference!

Disadvantages:

Begin degrading once they are created, lasting only two or three years tops, used or not. Extremely sensitive to high temperatures, heat degrades battery even faster. If a lithium battery is completely discharged, it is ruined and a new one will be needed. Because of size and ability to discharge and recharge hundreds of times it is one of the most expensive rechargeable batteries. And a SMALL chance they could burst into flames (internal short, separator sheet inside battery keeping the positive and negative ends apart gets punctured).

Alkaline Batteries:

The anode, the positive end, is made of zinc powder because the granules have a high surface area, increasing the rate of reaction and higher electron flows. It also helps limit the rate of corrosion. Manganese dioxide is use on the cathode, or the negative side, in powder form as well. And potassium hydroxide is the electrolyte in an alkaline battery. There is a separator inside the battery to separate the electrolyte between the positive and negative electrodes.

Fuel Cells

Fuel cells are a possible future replacement for chemical cells (batteries). They generate electricity by recombining hydrogen gas and oxygen. (commercial fuel cells will probably use methanol or other simple alcohols instead of hydrogen). Currently these are very expensive, but this might change in the near future when these cells are more commonly used as a replacement for laptop batteries.

Mechanical
Another way to store energy in a robot is mechanical means. Best known method is the wind-up spring, commonly used in toys, radios or clocks.

Another example of mechanical energy storage is the flywheel. A heavy wheel used to store kinetic energy.

Air Pressure

Some robots use pneumatic cylinders to move their body. These robots can use either a bottle of pressurized air or have a compressor on board. Only the first one is a power source. The latter power source is the batteries powering the compressor. Pneumatic cylinders can deliver very large forces and can be a very good choice for larger walkers or grippers.

Chemical Fuel
The model airplanes there exist small internal combustion engines. These engines can be used to power robots either directly for propulsion or indirectly by driving an alternator or dynamo. A well designed system can power a robot for a very long time, but it's not advisable to use this power system indoors.

title: Robotics/Components/Power Sources