text:
User talk:Daniel B~enwikibooks

Hallo Daniel,

ich, Franzjosefmehr, Komplexe_Zahlen, weiss nicht, was mit den Lizenzen gemeint ist. Alle Bilder wurden von mir erzeugt und ich geben sie zum allgemeinen Gebrauch frei. Ich habe die Bilder nochmals "hochgeladen" und dabei das Lizenzkaestchen angehakt.

Am Ende meines Textes erscheint eine Testseite aus meinem Russisch-Kurs (http://geocities.com/franzjosefmehr), die ich gerne geloescht haette. Da sie aber auf der Edit-Page nicht erscheint, weiss ich nicht, was ich tun soll. Hast Du eine Idee?

Auf meiner Seite findest Du einige Kurse, die ich eventuell nach WikiPedia transportieren moechte. Schau doch mal, ob das interessant waere.

Ich bin ein lange pensionierter Oberstudienrat und wohne seit 8 Jahren in Brasilien.

Vielen Dank fuer Deine Muehen, Franzjosefmehr

Your account will be renamed
Hello,

The developer team at Wikimedia is making some changes to how accounts work, as part of our on-going efforts to provide new and better tools for our users like cross-wiki notifications. These changes will mean you have the same account name everywhere. This will let us give you new features that will help you edit and discuss better, and allow more flexible user permissions for tools. One of the side-effects of this is that user accounts will now have to be unique across all 900 Wikimedia wikis. See the announcement for more information.

Unfortunately, your account clashes with another account also called Daniel B. To make sure that both of you can use all Wikimedia projects in future, we have reserved the name Daniel B~enwikibooks that only you will have. If you like it, you don't have to do anything. If you do not like it, you can pick out a different name.

Your account will still work as before, and you will be credited for all your edits made so far, but you will have to use the new account name when you log in.

Sorry for the inconvenience.

Yours, Keegan Peterzell Community Liaison, Wikimedia Foundation 23:04, 17 March 2015 (UTC)

Renamed
 This account has been renamed as part of single-user login finalisation. If you own this account you can |log in using your previous username and password for more information. If you do not like this account's new name, you can choose your own using this form after logging in: . -- Keegan (WMF) (talk) 04:51, 19 April 2015 (UTC)

title: User talk:Daniel B~enwikibooks


text:
Cookbook:Cheddar Cheese

| Cheese

Cheddar cheese is a firm yellow cheese made from cow's milk.

Production
Unlike with other cheeses, cheddar cheese curds undergo an eponymous process called "cheddaring". In this process, the curds are repeatedly stacked and cut, which forces more whey out of the curds and gives cheddar its drier texture. The curds are then salted, shaped, and pressed before being allowed to mature for a long period.

Characteristics
Because of the process used to make it, cheddar has a dry and crumbly texture. The rind may be natural or waxed, and the color is typically orange to white, depending on the diet of the cow and the addition of any annatto. The flavor of cheddar can range from mild to very sharp, depending on how long the cheese was left to age—longer aging produces a sharper flavor and more crumbly texture. It is also a good melting cheese.

Selection and storage
Cheddar cheese should always be stored in the fridge in paper or plastic to keep it fresh and prevent it from drying out. Because it is such a hard, dense cheese, mold can simply be cut off a block of cheddar as long as you leave a 1-inch (2.5 cm) border, leaving the rest of the cheese to be eaten.

Use
Cheddar has become a popular cheese in cooking, especially in the US and UK, where it can be used in gratins, cheese sauces, pasta, sandwiches, baked goods, and more. It can also be a part of cheese plates, where it is eaten on its own or with fruits—apple and cheddar is one popular combination.

Substitution
Depending on the age, cheddar can be replaced in a few ways. Mild, well-melting cheeses can substitute for mild cheddar, while other well-aged cheeses (e.g. gouda) can replace sharp aged gouda.

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

title: Cookbook:Cheddar Cheese


text:
Cookbook:Red Leicester Cheese

Red Leicester is an orange coloured cow's milk cheese, originally from Leicestershire in England. It has a firm texture, which makes it suitable for grating, and it is a good choice for use in cheese on toast or with a baked potato. At its best, it has a slightly nutty taste.

title: Cookbook:Red Leicester Cheese


text:
Cookbook:Cheese on Toast

Cheese on toast is a simple concept but easy to get wrong.

Ingredients

 * Thick-cut bread
 * Firm-fleshed strong-flavoured cheese, grated
 * Toppings (e.g. pickles, onion, walnuts, etc.)

Procedure

 * 1) Toast one side of the bread under a medium broiler.
 * 2) Lightly toast the other side of the bread, just enough to warm it, then spread the grated cheese over it. Add desired toppings.
 * 3) Broil the cheesy side of the bread until the cheese is bubbling and brown.
 * 4) Eat quickly, but be careful, as the cheese will be tongue-burningly hot!

title: Cookbook:Cheese on Toast


text:
Azerbaijani

Xan Sarayı, Şəki.

Gedək! (Latin version) !گهدعلىم (Perso-Arabic version)

Azerice

title: Azerbaijani


text:
User:Humblefool~enwikibooks

'Ello! See the talk page if you want to, uh, talk. Otherwise, see you later.

title: User:Humblefool~enwikibooks


text:
Talk:The Pagan Beliefs Surrounding Christmas

Hi -- wikibooks is for textbooks, so I humbly suggest that this material might be better suited for an article in Wikipedia. --Waxmop 20:28, 29 Dec 2004 (UTC)

 * Yes you are right, focusing on Christmas is too narrow. What I will do is create a book about Paganism, and add a chapter about how Paganism influences on western holidays. While I am at it, ill include other holydays that have pagan traits. --Zoohouse 00:32, 30 Dec 2004 (UTC)

Zoohouse, I like your work here. Please keep up the great work. --Karl Wick 22:07, 29 Dec 2004 (UTC)

 * Thank you Karl Wick :)

Moving The Pagan Beliefs Surrounding Christmas
I have been thinking, maybe we should move this book to ''Pagan Beliefs Surrounding Western. Holidays'' What do you folks think? Any suggestions? --Zoohouse 03:47, 31 Dec 2004 (UTC)

Nice work, why not Wikipedia
To reiterate Waxmop's point, while your content is great, Wikibooks is just for textbooks. If this book covered how to celebrate Christmas the Pagan way, it then would be a textbook. But as it is now, it's just information on the subject. If you move your writing over to Wikipedia, more people will read it, as the encyclopedia is higher trafficked. -- user:zanimum

But if I were to write showing how western holidays are based on pagan belifs, whouldn't it be a textbook? --Zoohouse 20:46, 19 Jan 2005 (UTC)

Sure, in some sense, any elaborate explanation of any subject could be considered a textbook. So, under that definition, all material should be included in the wikibooks page. However, in practice, the term textbook has taken on a particular meaning in the wikibooks context. The most popular projects fit any of the following criteria:

 * The work teaches you how to do something, like play a game, or speak a foreign language,
 * The work is an alternative to textbooks used in some mainstream educational curriculum, like US history.

I don't see how your work fits either. Meanwhile your work does look similar to the myriad paganism articles already under development on wikipedia. You're more likely to attract other contributors there than here. Nobody is going to force you to relocate, but you're going against the spirit of the site. --Waxmop 21:54, 19 Jan 2005 (UTC)

I dont seem to be able to find myriad paganism articles... Can you point me to the right direction? --Zoohouse 17:20, 21 Jan 2005 (UTC)

This is what Wikipedia had to say about Wikibooks: "The project is a collection of free textbooks, manuals, and other texts, with supporting book-based texts, that is written collaboratively on this website."

Wikibooks was opened so to "bring education to humanity and reduce the costs and other limitations on learning materials." I dont see how I am going against the spirit of the site. --Zoohouse 17:38, 21 Jan 2005 (UTC)

I say this could belong on both Wikipedia and wikibooks, however, this work would do much better on wikipedia due to popularity. It doesn't take much to transwiki anyway. --Dragontamer 00:32, 25 December 2005 (UTC)

Christmas already has information on these pagan beliefs, including possibly some information not in this book. This book seems too long to move to Wikipedia, so I would keep at Wikibooks. --Kernigh 03:03, 10 January 2006 (UTC)


text:
The Pagan Beliefs Surrounding Christmas/Bibliography

 * McLain, Bill. Do Fish Drink Water?. Quill, 1999.
 * Brain, Marshall. “Is December 25 really the day Jesus was born?” in “How Christmas Works” . October 10, 2003.
 * Wittmann, Kelly. Christmas' pagan origins . October 10, 2003.
 * Christmas Tree Farmers of Ontario. [ctfo@christmastrees.on.ca]. The History of Christmas Trees, Part One in Christmas Tree Farmers of Ontario Virtual Christmas Tree Farm . October 10, 2003


text:
User:Zoohouse

Basic Information

 * Name: Joel Montes de Oca
 * Location: Miami FL USA
 * Age: 20

Music

 * Rock
 * Metal
 * Euro-Tech
 * Old school hip-hop/rap
 * New Age

Groups/Clubs/Activity

 * Mialug
 * wikipedia
 * wikibooks
 * Blogging

Music

 * Rap
 * pop

Others

 * Video games
 * Sports (Unless its something like skate boarding)

Wikipedia

 * 1) United States Flag Code
 * 2) Civic Center Library
 * 3) Coconut Grove Library
 * 4) Allapattah Library
 * 5) Monofilament line
 * 6) South Dade Regional Library
 * 7) Pagan Beliefs Surrounding Christmas
 * 8) Borg scout ship

Wikibooks

 * 1) The Pagan Beliefs Surrounding Christmas

title: User:Zoohouse


text:
User:Batjew

Self
Name: Alec O. Location: CT, USA Age:16

Wikibook projects
-Visual Basic Wrote most everything except for History -Drums

title: User:Batjew


text:
Talk:Sufism/Nasrudin

Wikipedia
Doesn't this belong on wikipedia?--Batjew 01:07, 30 Dec 2004 (UTC)
 * No, it doesn't --Swift (talk) 16:05, 12 June 2008 (UTC)

Fishy Morality
I removed this interpretation from Fishy Morality: "Even a Mulla can be a Jewish mother." Does anyone know what this means? --Kernigh 23:01, 7 December 2005 (UTC)

What the *bleep* do those interpretations add to this all? They flatten everything out in a very moralistic way. I say, get rid of 'em. (IP 130.89.xx.xxx)

 * If you do not like the interpretations, try to add better ones. If we remove the interpretations, then we will need to move this page to a different wiki, because Wikibooks does not allow fiction. --Kernigh 00:17, 8 January 2006 (UTC)

What is this?
I am very confused with this page. I caught it because it is one of the most heavily edited Wikibook modules on this project, yet it is not listed on any bookshelf, and the primary reference is on the VfD forum (in the archive). If not for that, nor on a few user talk pages, this would have been an orphaned book module. I very curious over how anybody has even found this page except through a Google search.

Since it survived a VfD already, I'm going to ask more politely to try and figure out what this is and why does it belong on Wikibooks? Keep in mind that Wikibooks is not a web hosting service, and it seems as though this page is being maintained almost exclusively by a group totally outside of the Wikibooks community, although User:Kernigh does seem to be involved, as are a few other old-timers on Wikibooks.

In addition, because there are some others participating, if it were to be put on a bookshelf, where do you think it ought to go? Literature? Games (aka grouped together with Puzzles and Riddles)? Religion? All three? --Rob Horning 16:41, 15 April 2006 (UTC)

 * As far as I can tell this is a collection of sayings by a religious figure together with annotations (thus making it unsuitable for Wikisource), but I may be wrong. So yes Religion is likely the correct category. GarrettTalk 22:44, 17 April 2006 (UTC)

 * Comment from Kernigh: I have occasionally edited this module. I probably discovered it through Special:Recentchanges, because editors tend to flood Recentchanges by editing it section-by-section. From what I know, Nasrudin is a fictitious figure, invented for the purpose of including him in jokes. It is intended for (educational) humour; Nasrudin does not seem to be particularily smart.

 * If this page only contained jokes, it would be all-fiction and outside the scope of Wikibooks. However, it also contains random interpretations; there appear to be no established interpretations that one can site. This might invoke an obscure "no original ideas" clause in WB:WIW, but somehow I think that was meant to apply to entire books or sections, such as a book inventing a new language or religion, not to applications of existing concepts such as Nasrudin or Bourne Shell Scripting or even Zoph (when software developers put their manual on Wikibooks). --Kernigh 23:53, 18 April 2006 (UTC)

 * I am also confused by this page. What is the source? As far as I can see, anybody can make up a story and attribute it here to Nasreddin.  This is unsupported nonsense.  There are several books of Nasreddin's stories (eg Houman Farzad), this mess is not one of them. I think it should be deleted, but for some reason it supposedly has survived while remaining inchoate.  Here's a parable: where there's smoke, there's fire.  This "book" should be deleted.Abitslow (discuss • contribs) 20:01, 24 May 2014 (UTC)

Interpretations?
Are these interpretation from Sufi philosophy? If so, could someone kindly direct us to a source pertaining to these Sufi interpretations?

Thanks, amesoliman 17:18, 23 April 2006 (UTC)

 * Interpreting a Nasrudin story is kinda like interpreting a Zen koan. Or, to plagiarize the Tao, "The Nasrudin story that can be interpreted is not a Nasrudin story." (See 'Guest of Honor' interpretations to view my attempt at a Nasrudin story interpretation in the spirit of Nasrudin.) But of course, this is just my interpretation of Nasrudin stories ... John Elder 11:04, 4 August 2006 (UTC)

Needs Serious Cleaning Up
I'm now going to remove some of the obviously false interpretations (yes, I know, it's all relative and they're all equally valid - in theory). For example the one with the Jewish Mother, the whole story of the biker bar, "you can't sing" etc. Please supply me with a valid argument for NOT removing these ridiculous interpretations - Wikigeek at gmail, 2 september 2007

Nasreddin
Not that I want to offend any Wikibookians by passing over their judgement for that of Wikipedians, but I was wondering if editors would accept moving this page to Nasreddin. That is the name Wikipedia has settled and I think their argument is good and valid. (That, and it's the name for the character I know from my childhood...) --Swift (talk) 16:20, 12 June 2008 (UTC)

Yes please, remove away. The interpretations muddle the sharp wit of the stories themselves. Let each his own interpretation find. --jsleuth, 20:47, 12 June 2008

title: Talk:Sufism/Nasrudin


text:
Cell Biology/Energy supply/Electron transport

This stage involves using the NADH molecules produced previously, along with electrons from reduced electron carriers, to from molecules of ATP. In eukaryotes this process takes place in the mitochondria, while in oxygen tolerant prokaryotes it takes place in the cell membrane. Some eukaryotic cells, such as red blood cells, do not have mitochondria and therefore cannot use the electron transport chain to produce energy.

In plant cells, energy is used from the sun to start chemical reactions which create ATP.


text:
Data Structures/Introduction

Computers can store and process vast amounts of data. Formal data structures enable a programmer to mentally structure large amounts of data into conceptually manageable relationships.

Sometimes we use data structures to allow us to do more: for example, to accomplish fast searching or sorting of data. Other times, we use data structures so that we can do less: for example, the concept of the stack is a limited form of a more general data structure. These limitations provide us with guarantees that allow us to reason about our programs more easily. Data structures also provide guarantees about algorithmic complexity — choosing an appropriate data structure for a job is crucial for writing good software.

Because data structures are higher-level abstractions, they present to us operations on groups of data, such as adding an item to a list, or looking up the highest-priority item in a queue. When a data structure provides operations, we can call the data structure an abstract data type (sometimes abbreviated as ADT). Abstract data types can minimize dependencies in your code, which is important when your code needs to be changed. Because you are abstracted away from lower-level details, some of the higher-level commonalities one data structure shares with a different data structure can be used to replace one with the other.

Our programming languages come equipped with a set of built-in types, such as integers and floating-point numbers, that allow us to work with data objects for which the machine's processor has native support. These built-in types are abstractions of what the processor actually provides because built-in types hide details both about their execution and limitations.

For example, when we use a floating-point number we are primarily concerned with its value and the operations that can be applied to it. Consider computing the length of a hypotenuse:

let c := sqrt(a * a + b * b)

The machine code generated from the above would use common patterns for computing these values and accumulating the result. In fact, these patterns are so repetitious that high-level languages were created to avoid this redundancy and to allow programmers to think about what value was computed instead of how it was computed.

Two useful and related concepts are at play here:
 * Encapsulation is when common patterns are grouped together under a single name and then parameterized, in order to achieve a higher-level understanding of that pattern. For example, the multiplication operation requires two source values and writes the product of those two values to a given destination. The operation is parameterized by both the sources and the single destination.
 * Abstraction is a mechanism to hide the implementation details of an abstraction away from the users of the abstraction. When we multiply numbers, for example, we don't need to know the technique actually used by the processor, we just need to know its properties.

A programming language is both an abstraction of a machine and a tool to encapsulate-away the machine's inner details. For example, a program written in a programming language can be compiled to several different machine architectures when that programming language sufficiently encapsulates the user away from any one machine.

In this book, we take the abstraction and encapsulation that our programming languages provide a step further: When applications get to be more complex, the abstractions of programming languages become too low-level to effectively manage. Thus, we build our own abstractions on top of these lower-level constructs. We can even build further abstractions on top of those abstractions. Each time we build upwards, we lose access to the lower-level implementation details. While losing such access might sound like a bad trade off, it is actually quite a bargain: We are primarily concerned with solving the problem at hand rather than with any trivial decisions that could have just as arbitrarily been replaced with a different decision. When we can think on higher levels, we relieve ourselves of these burdens.

Each data structure that we cover in this book can be thought of as a single unit that has a set of values and a set of operations that can be performed to either access or change these values. The data structure itself can be understood as a set of the data structure's operations together with each operation's properties (i.e., what the operation does and how long we could expect it to take).

Big-oh notation is a common way of expressing a computer code's performance. The notation creates a relationship between the number of items in memory and the average performance for a function. For a set of $$n$$ items, $$O(n)$$ indicates that a particular function will operate on the set $$n$$ times on average. $$O(1)$$ indicates that the function always performs a constant number of operations regardless of the number of items. The notation only represents algorithmic complexity so a function may perform more operations but constant multiples of $$n$$ are dropped by convention.

The Node
The first data structure we look at is the node structure. A node is simply a container for a value, plus a pointer to a "next" node (which may be ).

The above is an abstraction of a structure:

In some languages, structures are called records or classes. Some other languages provide no direct support for structures, but instead allow them to be built from other constructs (such as tuples or lists).

Here, we are only concerned that nodes contain values of some form, so we simply say its type is "element" because the type is not important. In some programming languages no type ever needs to be specified (as in dynamically typed languages, like Scheme, Smalltalk or Python). In other languages the type might need to be restricted to integer or string (as in statically typed languages like C). In still other languages, the decision of the type of the contained element can be delayed until the type is actually used (as in languages that support generic types, like C++ and Java). In any of these cases, translating the pseudocode into your own language should be relatively simple.

Each of the node operations specified can be implemented quite easily:

// Create a new node, with v as its contained value and next as // the value of the next pointer function make-node(v, node next): node let result := new node {v, next} return result end // Returns the value contained in node n function get-value(node n): element return n.value end // Returns the value of node n's next pointer function get-next(node n): node return n.next end // Sets the contained value of n to be v function set-value(node n, v) n.value := v end // Sets the value of node n's next pointer to be new-next function set-next(node n, new-next) n.next := new-next return new-next end

Principally, we are more concerned with the operations and the implementation strategy than we are with the structure itself and the low-level implementation. For example, we are more concerned about the time requirement specified, which states that all operations take time that is $$O(1)$$. The above implementation meets this criteria, because the length of time each operation takes is constant. Another way to think of constant time operations is to think of them as operations whose analysis is not dependent on any variable. (The notation $$O(1)$$ is mathematically defined in the next chapter. For now, it is safe to assume it just means constant time.)

Because a node is just a container both for a value and container to a pointer to another node, it shouldn't be surprising how trivial the node data structure itself (and its implementation) is.

Building a Chain from Nodes
Although the node structure is simple, it actually allows us to compute things that we couldn't have computed with just fixed-size integers alone.

But first, we'll look at a program that doesn't need to use nodes. The following program will read in (from an input stream; which can either be from the user or a file) a series of numbers until the end-of-file is reached and then output what the largest number is and the average of all numbers:

program(input-stream in, output-stream out) let total := 0 let count := 0 let largest := $$-\infty$$ while has-next-integer(in): let i := read-integer(in) total := total + i count := count + 1 largest := max(largest, i) repeat println out "Maximum: " largest if count != 0: println out "Average: " (total / count) fi end

But now consider solving a similar task: read in a series of numbers until the end-of-file is reached, and output the largest number and the average of all numbers that evenly divide the largest number. This problem is different because it's possible the largest number will be the last one entered: if we are to compute the average of all numbers that divide that number, we'll need to somehow remember all of them. We could use variables to remember the previous numbers, but variables would only help us solve the problem when there aren't too many numbers entered.

For example, suppose we were to give ourselves 200 variables to hold the state input by the user. And further suppose that each of the 200 variables had 64-bits. Even if we were very clever with our program, it could only compute results for $$2^{64\cdot 200}$$ different types of input. While this is a very large number of combinations, a list of 300 64-bit numbers would require even more combinations to be properly encoded. (In general, the problem is said to require linear space. All programs that need only a finite number of variables can be solved in constant space.)

Instead of building-in limitations that complicate coding (such as having only a constant number of variables), we can use the properties of the node abstraction to allow us to remember as many numbers as our computer can hold:

program(input-stream in, output-stream out) let largest := $$-\infty$$ let nodes := null while has-next-integer(in): let i := read-integer(in) nodes := make-node(i, nodes) // contain the value i, // and remember the previous numbers too largest := max(largest, i) repeat println out "Maximum: " largest // now compute the averages of all factors of largest let total := 0 let count := 0 while nodes != null: let j := get-value(nodes) if j divides largest: total := total + j count := count + 1 fi    nodes := get-next(nodes) repeat if count != 0: println out "Average: " (total / count) fi end

Above, if n integers are successfully read there will be n calls made to make-node. This will require n nodes to be made (which require enough space to hold the value and next fields of each node, plus internal memory management overhead), so the memory requirements will be on the order of $$O(n)$$. Similarly, we construct this chain of nodes and then iterate over the chain again, which will require $$O(n)$$ steps to make the chain, and then another $$O(n)$$ steps to iterate over it.

Note that when we iterate the numbers in the chain, we are actually looking at them in reverse order. For example, assume the numbers input to our program are 4, 7, 6, 30, and 15. After EOF is reached, the nodes chain will look like this:

Such chains are more commonly referred to as linked-lists. However, we generally prefer to think in terms of lists or sequences, which aren't as low-level: the linking concept is just an implementation detail. While a list can be made with a chain, in this book we cover several other ways to make a list. For the moment, we care more about the abstraction capabilities of the node than we do about one of the ways it is used.

The above algorithm only uses the make-node, get-value, and get-next functions. If we use set-next we can change the algorithm to generate the chain so that it keeps the original ordering (instead of reversing it).

program (input-stream in, output-stream out) let largest := $$-\infty$$ let nodes := null let tail_node := null while has-next-integer (in): let i := read-integer (in) if (nodes == null) nodes := make-node(i, null) // construct first node in the list tail_node := nodes //there is one node in the list=> first and last are the same else tail_node := set-next (tail_node, make-node (i, null)) // append new node to the end of the list largest := max(largest, i) repeat println out "Maximum: " largest // now compute the averages of all factors of largest let total := 0 let count := 0 while nodes != null: let j := get-value(nodes) if j divides largest: total := total + j count := count + 1 fi    nodes := get-next(nodes) repeat if count != 0: println out "Average: " (total / count) fi end

The Principle of Induction
The chains we can build from nodes are a demonstration of the principle of mathematical induction:

For example, let the property $$P(n)$$ be the statement that "you can make a chain that holds $$n$$ numbers". This is a property of natural numbers, because the sentence makes sense for specific values of $$n$$:

 * you can make a chain that holds 5 numbers
 * you can make a chain that holds 100 numbers
 * you can make a chain that holds 1,000,000 numbers

Instead of proving that we can make chains of length 5, 100, and one million, we'd rather prove the general statement $$P(n)$$ instead. Step 2 above is called the Inductive Hypothesis; let's show that we can prove it:

let bigger-chain := make-node(i, chain)
 * Assume that $$P(n)$$ holds. That is, that we can make a chain of $$n$$ elements. Now we must show that $$P(n+1)$$ holds.
 * Assume  is the first node of the $$n$$-element chain. Assume   is some number that we'd like to add to the chain to make an $$n+1$$ length chain.
 * The following code can accomplish this for us:
 * Here, we have the new number  that is now the contained value of the first link of the  . If   had $$n$$ elements, then   must have $$n+1$$ elements.

Step 3 above is called the Base Case, let's show that we can prove it:

let chain := make-node(i, null)
 * We must show that $$P(1)$$ holds. That is, that we can make a chain of one element.
 * The following code can accomplish this for us:

The principle of induction says, then, that we have proven that we can make a chain of $$n$$ elements for all value of $$n\ge 1$$. How is this so? Probably the best way to think of induction is that it's actually a way of creating a formula to describe an infinite number of proofs. After we prove that the statement is true for $$P(1)$$, the base case, we can apply the inductive hypothesis to that fact to show that $$P(2)$$ holds. Since we now know that $$P(2)$$ holds, we can apply the inductive hypothesis again to show that $$P(3)$$ must hold. The principle says that there is nothing to stop us from doing this repeatedly, so we should assume it holds for all cases.

Induction may sound like a strange way to prove things, but it's a very useful technique. What makes the technique so useful is that it can take a hard sounding statement like "prove $$P(n)$$ holds for all $$n\ge 1$$" and break it into two smaller, easier to prove statements. Typically base cases are easy to prove because they are not general statements at all. Most of the proof work is usually in the inductive hypothesis, which can often require clever ways of reformulating the statement to "attach on" a proof of the $$n+1$$ case.

You can think of the contained value of a node as a base case, while the next pointer of the node as the inductive hypothesis. Just as in mathematical induction, we can break the hard problem of storing an arbitrary number of elements into an easier problem of just storing one element and then having a mechanism to attach on further elements.

Induction on a Summation
The next example of induction we consider is more algebraic in nature:

Let's say we are given the formula $$\frac{(n)(n+1)}{2}$$ and we want to prove that this formula gives us the sum of the first $$n$$ numbers. As a first attempt, we might try to just show that this is true for 1
 * $$\frac{(1)(1+1)}{2} = 1 = 1$$,

for 2
 * $$\frac{(2)(2+1)}{2} = 3 = 1 + 2$$,

for 3
 * $$\frac{(3)(3+1)}{2} = 6 = 1 + 2 + 3$$

and so on, however we'd quickly realize that our so called proof would take infinitely long to write out! Even if you carried out this proof and showed it to be true for the first billion numbers, that doesn't nescessarily mean that it would be true for one billion and one or even a hundred billion. This is a strong hint that maybe induction would be useful here.

Let's say we want to prove that the given formula really does give the sum of the first n numbers using induction. The first step is to prove the base case; i.e. we have to show that it is true when n = 1. This is relatively easy; we just substitute 1 for the variable n and we get ($$\frac{(1)(1+1)}{2} = 1$$), which shows that the formula is correct when n = 1.

Now for the inductive step. We have to show that if the formula is true for j, it is also true for j + 1. To phrase it another way, assuming we've already proven that the sum from 1 to (j) is $$\frac{((j))((j)+1)}{2}$$, we want to prove that the sum from 1 to (j+1) is $$\frac{((j+1))((j+1)+1)}{2}$$. Note that those two formulas came about just by replacing n with (j) and (j+1) respectively.

To prove this inductive step, first note that to calculate the sum from 1 to j+1, you can just calculate the sum from 1 to j, then add j+1 to it. We already have a formula for the sum from 1 to j, and when we add j+1 to that formula, we get this new formula: $$\frac{((j))((j)+1)}{2}+(j+1)$$. So to actually complete the proof, all we'd need to do is show that $$\frac{((j))((j)+1)}{2}+(j+1) = \frac{((j+1))((j+1)+1)}{2}$$.

We can show the above equation is true via a few simplification steps:

$$\frac{((j))((j)+1)}{2}+(j+1) = \frac{((j+1))((j+1)+1)}{2}$$

$$\frac{(j)(j+1)}{2}+j+1 = \frac{(j+1)(j+1+1)}{2}$$

$$\frac{(j)(j+1)}{2}+\frac{2(j+1)}{2} = \frac{(j+1)(j+2)}{2}$$

$$\frac{(j)(j+1)+2(j+1)}{2} = \frac{(j+1)(j+2)}{2}$$

$$\frac{j^2+j+2j+2}{2} = \frac{(j+1)(j+2)}{2}$$

$$\frac{j^2+3j+2}{2} = \frac{(j+1)(j+2)}{2}$$

$$\frac{(j+1)(j+2)}{2} = \frac{(j+1)(j+2)}{2}$$

title: Data Structures/Introduction


text:
Data Structures/Graphs

Graphs
A graph is a structure consisting of a set of vertices $$\{v_1, v_2,\dots,v_n\}$$ and a set of edges $$\{e_1, e_2,\dots,e_m\}$$. An edge is a pair of vertices $$\{v_i, v_j\}\ i,j \in \{1..n\}$$. The two vertices are called the edge endpoints. Graphs are ubiquitous in computer science. They are used to model real-world systems such as the Internet (each node represents a router and each edge represents a connection between routers); airline connections (each node is an airport and each edge is a flight); or a city road network (each node represents an intersection and each edge represents a block). The wireframe drawings in computer graphics are another example of graphs.

A graph may be either undirected or directed. Intuitively, an undirected edge models a "two-way" or "duplex" connection between its endpoints, while a directed edge is a one-way connection, and is typically drawn as an arrow. A directed edge is often called an arc. Mathematically, an undirected edge is an unordered pair of vertices, and an arc is an ordered pair. For example, a road network might be modeled as a directed graph, with one-way streets indicated by an arrow between endpoints in the appropriate direction, and two-way streets shown by a pair of parallel directed edges going both directions between the endpoints. You might ask, why not use a single undirected edge for a two-way street. There's no theoretical problem with this, but from a practical programming standpoint, it's generally simpler and less error-prone to stick with all directed or all undirected edges.

An undirected graph can have at most $$\left ( \begin{array}{c}  n+1 \\ 2  \end{array}  \right )$$ edges (one for each unordered pair), while a directed graph can have at most $$n^2$$ edges (one per ordered pair). A graph is called sparse if it has many fewer than this many edges (typically $$O(n)$$ edges), and dense if it has closer to $$\Omega(n^2)$$ edges. A multigraph can have more than one edge between the same two vertices. For example, if one were modeling airline flights, there might be multiple flights between two cities, occurring at different times of the day.

A path in a graph is a sequence of vertices $$\{ v_{i_1}, v_{i_2}, \dots, v_{i_k} \}$$ such that there exists an edge or arc between consecutive vertices. The path is called a cycle if $$v_{i_1} \equiv v_{i_k}$$. An undirected acyclic graph is equivalent to an undirected tree. A directed acyclic graph is called a DAG. It is not necessarily a tree.

Nodes and edges often have associated information, such as labels or weights. For example, in a graph of airline flights, a node might be labeled with the name of the corresponding airport, and an edge might have a weight equal to the flight time. The popular game "Six Degrees of Kevin Bacon" can be modeled by a labeled undirected graph. Each actor becomes a node, labeled by the actor's name. Nodes are connected by an edge when the two actors appeared together in some movie. We can label this edge by the name of the movie. Deciding if an actor is separated from Kevin Bacon by six or fewer steps is equivalent to finding a path of length at most six in the graph between Bacon's vertex and the other actors vertex. (This can be done with the breadth-first search algorithm found in the companion Algorithms book. The Oracle of Bacon at the University of Virginia has actually implemented this algorithm and can tell you the path from any actor to Kevin Bacon in a few clicks.)

Directed Graphs
The number of edges with one endpoint on a given vertex is called that vertex's degree. In a directed graph, the number of edges that point to a given vertex is called its in-degree, and the number that point from it is called its out-degree. Often, we may want to be able to distinguish between different nodes and edges. We can associate labels with either. We call such a graph labeled.

 Directed Graph Operations    Create a new graph, initially with no nodes or edges.

  Create a new vertex, with the given value.

  Create an edge between u and v. In a directed graph, the edge will flow from u to v.

Returns the set of edges flowing from v

Returns the set of vertices connected to v

Undirected Graphs
In a directed graph, the edges point from one vertex to another, while in an undirected graph, they merely connect two vertices. we can travel forward or backward.It is a bidirectional graph.

Weighted Graphs
We may also want to associate some cost or weight to the traversal of an edge. When we add this information, the graph is called weighted. An example of a weighted graph would be the distance between the capitals of a set of countries.

Directed and undirected graphs may both be weighted. The operations on a weighted graph are the same with addition of a weight parameter during edge creation:
 Weighted Graph Operations (an extension of undirected/directed graph operations)

Create an edge between u and v with weight w. In a directed graph, the edge will flow from u to v.

Adjacency Matrix Representation
An adjacency matrix is one of the two common ways to represent a graph. The adjacency matrix shows which nodes are adjacent to one another. Two nodes are adjacent if there is an edge connecting them. In the case of a directed graph, if node $$j$$ is adjacent to node $$i$$, there is an edge from $$i$$ to $$j$$. In other words, if $$j$$ is adjacent to $$i$$, you can get from $$i$$ to $$j$$ by traversing one edge. For a given graph with $$n$$ nodes, the adjacency matrix will have dimensions of $$n \times n$$. For an unweighted graph, the adjacency matrix will be populated with boolean values.

For any given node $$i$$, you can determine its adjacent nodes by looking at row $$\left( i, \left[ 1..n \right] \right)$$ of the adjacency matrix. A value of true at $$\left( i, j \right)$$ indicates that there is an edge from node $$i$$ to node $$j$$, and false indicating no edge. In an undirected graph, the values of $$\left( i, j \right)$$ and $$\left( j, i \right)$$ will be equal. In a weighted graph, the boolean values will be replaced by the weight of the edge connecting the two nodes, with a special value that indicates the absence of an edge.

The memory use of an adjacency matrix is $$O(n^2)$$.

Adjacency List Representation
The adjacency list is another common representation of a graph. There are many ways to implement this adjacency representation. One way is to have the graph maintain a list of lists, in which the first list is a list of indices corresponding to each node in the graph. Each of these refer to another list that stores the index of each adjacent node to this one. It might also be useful to associate the weight of each link with the adjacent node in this list.

Example: An undirected graph contains four nodes 1, 2, 3 and 4. 1 is linked to 2 and 3. 2 is linked to 3. 3 is linked to 4.

1 - [2, 3]

2 - [1, 3]

3 - [1, 2, 4]

4 - [3]

It might be useful to store the list of all the nodes in the graph in a hash table. The keys then would correspond to the indices of each node and the value would be a reference to the list of adjacent node indices.

Another implementation might require that each node keep a list of its adjacent nodes.

Graph Traversals
In a perfect world we would have full knowledge of the graph's contents, letting us optimize indices for the vertices and edges for efficient look-ups. But there are numerous open-ended problems in computer science where indexing is impractical or even impossible. Graph traversals let us tackle these problems. The traversals let us efficiently search large spaces where objects are defined by their relationships to other objects rather than properties of the objects themselves.

Depth-First Search
Start at vertex a, visit its neighbour b, then b's neighbour c and keep going until reach 'a dead end' then iterate back and visit nodes reachable from second last visited vertex and keep applying the same principle.

// Search in the subgraph for a node matching 'criteria'. Do not re-examine // nodes listed in 'visited' which have already been tested. GraphNode depth_first_search(GraphNode node, Predicate criteria, VisitedSet visited) { // Check that we haven't already visited this part of the graph if (visited.contains(node)) { return null; } visited.insert(node); // Test to see if this node satisfies the criteria if (criteria.apply(node.value)) { return node; } // Search adjacent nodes for a match for (adjacent in node.adjacentnodes) { GraphNode ret = depth_first_search(adjacent, criteria, visited); if (ret != null) { return ret; } } // Give up - not in this part of the graph return null; }

Breadth-First Search
Breadth first search visits the nodes neighbours and then the unvisited neighbours of the neighbours, etc. If it starts on vertex a it will go to all vertices that have an edge from a. If some points are not reachable it will have to start another BFS from a new vertex.

title: Data Structures/Graphs


text:
Data Structures/Stacks and Queues

Stacks
A stack is a basic data structure that can be logically thought of as a linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. The basic concept can be illustrated by thinking of your data set as a stack of plates or books where you can only take the top item of the stack in order to remove things from it. This structure is used all throughout programming.

The basic implementation of a stack is also called a LIFO (Last In First Out) to demonstrate the way it accesses data, since as we will see there are various variations of stack implementations.

There are basically three operations that can be performed on stacks. They are 1) inserting an item into a stack (push). 2) deleting an item from the stack (pop). 3) displaying the contents of the stack (peek or top).

Below are some of operations a stack data type normally supports:   Operations    Adds an item onto the stack.   Returns the last item pushed onto the stack.   Removes the most-recently-pushed item from the stack.
True if no more items can be popped and there is no top item.

True if no more items can be pushed.

Returns the number of elements on the stack.

All operations except  can be performed in $$O(1)$$ time. runs in at worst $$O(N).$$

Linked List Implementation
The basic linked list implementation is one of the easiest stack implementations you can do. Structurally it is a linked list. type Stack<item_type> data list:Singly Linked List<item_type> "stack follows the LIFO (last in first out) operation" "queue follows the FIFO (first in first out) operation" constructor list := new Singly-Linked-List end constructor

Most operations are implemented by passing them through to the underlying linked list. When you want to push something onto the list, you simply add it to the front of the linked list. The previous top is then "next" from the item being added and the list's front pointer points to the new item. method push(new_item:item_type) list.prepend(new_item) end method

To look at the top item, you just examine the first item in the linked list. method top:item_type return list.get-begin.get-value end method

When you want to pop something off the list, simply remove the first item from the linked list. method pop list.remove-first end method

A check for emptiness is easy. Just check if the list is empty. method is-empty:Boolean return list.is-empty end method

A check for full is simple. Linked lists are considered to be limitless in size. method is-full:Boolean return False end method

A check for the size is again passed through to the list. method get-size:Integer return list.get-size end method end type

A real Stack implementation in a published library would probably re-implement the linked list in order to squeeze the last bit of performance out of the implementation by leaving out unneeded functionality. The above implementation gives you the ideas involved, and any optimization you need can be accomplished by inlining the linked list code.

Performance Analysis
In a linked list, accessing the first element is an $$O(1)$$ operation.The list contains a pointer that checks for empty/fullness as done here are also $$O(1)$$ (depending on what time/space tradeoff is made). Most of the time, users of a Stack do not use the  operation, and so a bit of space can be saved by not optimizing it.

Since all operations are at the top of the stack, the array implementation is now much, much better.

public class StackArray implements Stack {      protected int top; protected Object[] data; ...  }

The array implementation keeps the bottom of the stack at the beginning of the array. It grows toward the end of the array. The only problem is if you attempt to push an element when the array is full. If so

Assert.pre(!isFull,"Stack is not full."); will fail, raising an exception. Thus it makes more sense to implement with Vector (see StackVector) to allow unbounded growth (at cost of occasional O(n) delays).

Complexity:

All operations are O(1) with exception of occasional push and clear, which should replace all entries by null in order to let them be garbage-collected. Array implementation does not replace null entries. The Vector implementation does...

Applications of Stacks

Using stacks, we can solve many applications, some of which are listed below.

Converting a decimal number into a binary number
The logic for transforming a decimal number into a binary number is as follows:

* Read a number * Iteration (while number is greater than zero) 1. Find out the remainder after dividing the number by 2 2. Print the remainder 3. Divide the number by 2 * End the iteration

However, there is a problem with this logic. Suppose the number whose binary form we want to find is 23. Using this logic, we get the result as 11101, instead of getting 10111.

To solve this problem, we use a stack. We make use of the LIFO property of the stack. Initially we push the binary digit formed into the stack, instead of printing it directly. After the entire digit has been converted into the binary form, we pop one digit at a time from the stack and print it. Therefore we get the decimal number is converted into its proper binary form.

Algorithm:

1. Create a stack 2. Enter a decimal number which has to be converted into its equivalent binary form. 3. iteration1 (while number > 0) 3.1 digit = number % 2 3.2 Push digit into the stack 3.3 If the stack is full 3.3.1 Print an error 3.3.2 Stop the algorithm 3.4 End the if condition 3.5 Divide the number by 2 4. End iteration1 5. iteration2 (while stack is not empty) 5.1 Pop digit from the stack 5.2 Print the digit 6. End iteration2 7. STOP

Towers of Hanoi
One of the most interesting applications of stacks can be found in solving a puzzle called Tower of Hanoi. According to an old Brahmin story, the existence of the universe is calculated in terms of the time taken by a number of monks, who are working all the time, to move 64 disks from one pole to another. But there are some rules about how this should be done, which are:
 * 1) You can move only one disk at a time.
 * 2) For temporary storage, a third pole may be used.
 * 3) You cannot place a disk of larger diameter on a disk of smaller diameter.

Here we assume that A is first tower, B is second tower  & C is third tower.

Output : (when there are 3 disks)

Let 1 be the smallest disk, 2 be the disk of medium size and 3 be the largest disk.

Output : (when there are 4 disks)

The C++ code for this solution can be implemented in two ways:

First Implementation (Without using Stacks)
Here we assume that A is first tower, B is second tower  & C is third tower. (B is the intermediate)

Second Implementation (Using Stacks)
However complexity for above written implementations is O($$2^n$$). So it's obvious that problem can only be solved for small values of n (generally n <= 30). In case of the monks, the number of turns taken to transfer 64 disks, by following the above rules, will be 18,446,744,073,709,551,615; which will surely take a lot of time!!

Expression evaluation and syntax parsing
Calculators employing reverse Polish notation use a stack structure to hold values. Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form may be accomplished using a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are context-free languages allowing them to be parsed with stack based machines.

Evaluation of an Infix Expression that is Fully Parenthesized
Input: (((2 * 5) - (1 * 2)) / (9 - 7))

Output: 4

Analysis: Five types of input characters * Opening bracket * Numbers * Operators * Closing bracket * New line character

Data structure requirement:  A character stack

Algorithm 1. Read one input character 2. Actions at end of each input Opening brackets             (2.1)  Push into stack and then Go to step (1) Number                       (2.2)  Push into stack and then Go to step (1) Operator                     (2.3)  Push into stack and then Go to step (1) Closing brackets             (2.4)  Pop it from character stack (2.4.1) if it is opening bracket, then discard it, Go to step (1) (2.4.2) Pop is used three times The first popped element is assigned to op2 The second popped element is assigned to op                                           The third popped element is assigned to op1 Evaluate op1 op op2 Convert the result into character and push into the stack Go to step (2.4) New line character           (2.5)  Pop from stack and print the answer STOP

Result: The evaluation of the fully parenthesized infix expression is printed on the monitor as follows:

Input String:  (((2 * 5) - (1 * 2)) / (9 - 7))

C Program

Output of the program:

Input entered at the command line: (((2 * 5) - (1 * 2)) / (9 - 7))

Evaluation of Infix Expression which is not fully parenthesized
Input: (2 * 5 - 1 * 2) / (11 - 9)

Output: 4

Analysis: There are five types of input characters which are: * Opening brackets * Numbers * Operators * Closing brackets * New line character (\n)

We do not know what to do if an operator is read as an input character. By implementing the priority rule for operators, we have a solution to this problem.

The Priority rule we should perform comparative priority check if an operator is read, and then push it. If the stack top contains an operator of prioirty higher than or equal to the priority of the input operator, then we pop it and print it. We keep on perforrming the prioirty check until the top of stack either contains an operator of lower priority or if it does not contain an operator.

Data Structure Requirement for this problem: A character stack and an integer stack

Algorithm:

1. Read an input character 2. Actions that will be performed at the end of each input Opening brackets             (2.1)  Push it into stack and then Go to step (1) Digit                        (2.2)  Push into stack, Go to step (1) Operator                     (2.3)  Do the comparative priority check (2.3.1) if the character stack's top contains an operator with equal or higher priority, then pop it into op                                             Pop a number from integer stack into op2 Pop another number from integer stack into op1 Calculate op1 op op2 and push the result into the integer stack Closing brackets             (2.4)  Pop from the character stack (2.4.1) if it is an opening bracket, then discard it and Go to                                           step (1) (2.4.2) To op, assign the popped element Pop a number from integer stack and assign it op2 Pop another number from integer stack and assign it                                           to op1 Calculate op1 op op2 and push the result into the integer stack Convert into character and push into stack Go to the step (2.4) New line character           (2.5)  Print the result after popping from the stack STOP

Result: The evaluation of an infix expression that is not fully parenthesized is printed as follows:

Input String:  (2 * 5 - 1 * 2) / (11 - 9)

C Program

Output of the program:

Input entered at the command line: (2 * 5 - 1 * 2) / (11 - 9)

Output: 4

Evaluation of Prefix Expression
Input: x + 6 * ( y + z ) ^ 3

Output:' 4

Analysis: There are three types of input characters * Numbers * Operators * New line character (\n)

Data structure requirement: A character stack and an integer stack

Algorithm:

1. Read one character input at a time and keep pushing it into the character stack until the new line character is reached 2. Perform pop from the character stack. If the stack is empty, go to step (3) Number                       (2.1) Push in to the integer stack and then go to step (1) Operator                     (2.2)  Assign the operator to op                                            Pop a number from  integer stack and assign it to op1 Pop another number from integer stack and assign it to op2 Calculate op1 op op2 and push the output into the integer stack. Go to step (2) 3. Pop the result from the integer stack and display the result Result: The evaluation of prefix expression is printed as follows:

Input String:  / - * 2 5 * 1 2 - 11 9

C Program

Output of the program:

Input entered at the command line: / - * 2 5 * 1  2 - 11  9

Output: 4

Conversion of an Infix expression that is fully parenthesized into a Postfix expression
Input: (((8 + 1) - (7 - 4)) / (11 - 9))

Output: 8 1 + 7 4 - - 11 9 - /

Analysis: There are five types of input characters which are: * Opening brackets * Numbers * Operators * Closing brackets * New line character (\n)

Requirement: A character stack

Algorithm:

1. Read an character input 2. Actions to be performed at end of each input Opening brackets             (2.1)  Push into stack and then Go to step (1) Number                       (2.2)  Print and then Go to step (1) Operator                     (2.3)  Push into stack and then Go to step (1) Closing brackets             (2.4)  Pop it from the stack (2.4.1) If it is an operator, print it, Go to step (1) (2.4.2) If the popped element is an opening bracket, discard it and go to step (1) New line character           (2.5)  STOP

Therefore, the final output after conversion of an infix expression to a postfix expression is as follows:

Problem Description
It's a very nice application of stacks. Consider that a freight train has n railroad cars, each to be left at a different station. They're numbered 1 through n and a freight train visits these stations in order n through 1. Obviously, the railroad cars are labeled by their destination.To facilitate removal of the cars from the train, we must rearrange them in ascending order of their number (i.e., 1 through n). When cars are in this order, they can be detached at each station. We rearrange cars at a shunting yard that has input track, output track & k holding tracks between the input & output tracks (i.e., holding track).

Solution Strategy
To rearrange cars, we examine the cars on the input from front to back. If the car being examined is the next one in the output arrangement, we move it directly to output track. If not, we move it to the holding track and leave it there until it's time to place it to the output track. The holding tracks operate in a LIFO manner as the cars enter and leave these tracks from the top. When rearranging cars, only the following moves are permitted: The figure shows a shunting yard with k = 3, holding tracks H1, H2 and H3, and n = 9. The n cars of the freight train begin in the input track and are to end up in the output track in order 1 through n from right to left. The cars initially are in the order 5, 8, 1, 7, 4, 2, 9, 6, 3 from back to front. Later cars are rearranged in the desired order.
 * A car may be moved from the front (i.e., right end) of the input track to the top of one of the holding tracks or to the left end of the output track.
 * A car may be moved from the top of the holding track to the left end of the output track.

A Three-Track Example
The requirement of rearrangement of cars on any holding track is that the cars should be preferred to arrange in ascending order from top to bottom. Car 4 is moved to the output track. No other cars can be moved to the output track at this time.
 * Consider the input arrangement from the figure, here we note that car 3 is at the front, so it can't be output yet, as it is to be preceded by cars 1 and 2. So car 3 is detached and moved to holding track H1.
 * The next car 6 can't be output and it is moved to holding track H2. Because we have to output car 3 before car 6 and this will not be possible if we move car 6 to holding track H1.
 * Now it's obvious that we move car 9 to H3.
 * So car 2 is now moved to holding track H1 so that it satisfies the previous statement. If we move car 2 to H2 or H3, then we've no place to move cars 4, 5, 7, or 8.The least restrictions on future car placement arise when the new car λ is moved to the holding track that has a car at its top with smallest label Ψ such that λ < Ψ. We may call it an assignment rule to decide whether a particular car belongs to a specific holding track.
 * When car 4 is considered, there are three places to move the car: H1, H2, and H3. The top of these tracks are 2, 6, and 9.So using the aforementioned Assignment rule, we move car 4 to H2.
 * Car 7 is moved to H3.
 * The next car 1 has the lowest label, so it's moved to the output track.
 * Now it's time for cars 2 and 3 to output which are from H1 (in short, all the cars from H1 are appended to car 1 on the output track).
 * The next car, car 8, is moved to holding track H1.
 * Car 5 is output from the input track. Car 6 is moved to the output track from H2, so is car 7 from H3, car 8 from H1, and car 9 from H3.

Quicksort
Sorting means arranging a group of elements in a particular order. Be it ascending or descending, by cardinality or alphabetical order or variations thereof. The resulting ordering possibilities will only be limited by the type of the source elements.

Quicksort is an algorithm of the divide and conquer type. In this method, to sort a set of numbers, we reduce it to two smaller sets, and then sort these smaller sets.

This can be explained with the help of the following example:

Suppose A is a list of the following numbers:

In the reduction step, we find the final position of one of the numbers. In this case, let us assume that we have to find the final position of 48, which is the first number in the list.

To accomplish this, we adopt the following method. Begin with the last number, and move from right to left. Compare each number with 48. If the number is smaller than 48, we stop at that number and swap it with 48.

In our case, the number is 24. Hence, we swap 24 and 48.

The numbers 96 and 72 to the right of 48, are greater than 48. Now beginning with 24, scan the numbers in the opposite direction, that is from left to right. Compare every number with 48 until you find a number that is greater than 48.

In this case, it is 60. Therefore we swap 48 and 60.

Note that the numbers 12, 24 and 36 to the left of 48 are all smaller than 48. Now, start scanning numbers from 60, in the right to left direction. As soon as you find lesser number, swap it with 48.

In this case, it is 44. Swap it with 48. The final result is:

Now, beginning with 44, scan the list from left to right, until you find a number greater than 48.

Such a number is 84. Swap it with 48. The final result is:

Now, beginning with 84, traverse the list from right to left, until you reach a number lesser than 48. We do not find such a number before reaching 48. This means that all the numbers in the list have been scanned and compared with 48. Also, we notice that all numbers less than 48 are to the left of it, and all numbers greater than 48, are to its right.

The final partitions look as follows:

Therefore, 48 has been placed in its proper position and now our task is reduced to sorting the two partitions. This above step of creating partitions can be repeated with every partition containing 2 or more elements. As we can process only a single partition at a time, we should be able to keep track of the other partitions, for future processing.

This is done by using two stacks called LOWERBOUND and UPPERBOUND, to temporarily store these partitions. The addresses of the first and last elements of the partitions are pushed into the LOWERBOUND and UPPERBOUND stacks respectively. Now, the above reduction step is applied to the partitions only after its boundary values are popped from the stack.

We can understand this from the following example:

Take the above list A with 12 elements. The algorithm starts by pushing the boundary values of A, that is 1 and 12 into the LOWERBOUND and UPPERBOUND stacks respectively. Therefore the stacks look as follows:

LOWERBOUND: 1                   UPPERBOUND:  12

To perform the reduction step, the values of the stack top are popped from the stack. Therefore, both the stacks become empty.

LOWERBOUND: {empty}                UPPERBOUND: {empty}

Now, the reduction step causes 48 to be fixed to the 5th position and creates two partitions, one from position 1 to 4 and the other from position 6 to 12. Hence, the values 1 and 6 are pushed into the LOWERBOUND stack and 4 and 12 are pushed into the UPPERBOUND stack.

LOWERBOUND: 1, 6                   UPPERBOUND: 4, 12

For applying the reduction step again, the values at the stack top are popped. Therefore, the values 6 and 12 are popped. Therefore the stacks look like:

LOWERBOUND: 1                      UPPERBOUND: 4

The reduction step is now applied to the second partition, that is from the 6th to 12th element.

After the reduction step, 98 is fixed in the 11th position. So, the second partition has only one element. Therefore, we push the upper and lower boundary values of the first partition onto the stack. So, the stacks are as follows:

LOWERBOUND: 1, 6                   UPPERBOUND:  4, 10

The processing proceeds in the following way and ends when the stacks do not contain any upper and lower bounds of the partition to be processed, and the list gets sorted.

The Stock Span Problem
In the stock span problem, we will solve a financial problem with the help of stacks.

Suppose, for a stock, we have a series of n daily price quotes, the span of the stock's price on a particular day is defined as the maximum number of consecutive days for which the price of the stock on the current day is less than or equal to its price on that day.

An algorithm which has Quadratic Time Complexity
Input: An array P with n elements

Output: An array S of n elements such that S[i] is the largest integer k such that k <= i + 1 and P[j] <= P[i] for j = i - k + 1,.....,i

Algorithm:

1. Initialize an array P which contains the daily prices of the stocks 2. Initialize an array S which will store the span of the stock 3. for i = 0 to i = n - 1 3.1 Initialize k to zero 3.2 Done with a false condition 3.3 repeat 3.3.1 if (P[i - k] <= P[i]) then Increment k by 1 3.3.2 else Done with true condition 3.4 Till (k > i) or done with processing Assign value of k to S[i] to get the span of the stock 4. Return array S

Now, analyzing this algorithm for running time, we observe:

 * We have initialized the array S at the beginning and returned it at the end. This is a constant time operation, hence takes O(n) time
 * The repeat loop is nested within the for loop. The for loop, whose counter is i is executed n times. The statements which are not in the repeat loop, but in the for loop are executed n times. Therefore these statements and the incrementing and condition testing of i take O(n) time.
 * In repetition of i for the outer for loop, the body of the inner repeat loop is executed maximum i + 1 times. In the worst case, element S[i] is greater than all the previous elements. So, testing for the if condition, the statement after that, as well as testing the until condition, will be performed i + 1 times during iteration i for the outer for loop. Hence, the total time taken by the inner loop is O(n(n + 1)/2), which is O($$n^2 $$)

The running time of all these steps is calculated by adding the time taken by all these three steps. The first two terms are O($$ n $$) while the last term is O($$n^2 $$). Therefore the total running time of the algorithm is O($$n^2 $$).

An algorithm that has Linear Time Complexity
In order to calculate the span more efficiently, we see that the span on a particular day can be easily calculated if we know the closest day before i, such that the price of the stocks on that day was higher than the price of the stocks on the present day. If there exists such a day, we can represent it by h(i) and initialize h(i) to be -1.

Therefore the span of a particular day is given by the formula, s = i - h(i).

To implement this logic, we use a stack as an abstract data type to store the days i, h(i), h(h(i)) and so on. When we go from day i-1 to i, we pop the days when the price of the stock was less than or equal to p(i) and then push the value of day i back into the stack.

Here, we assume that the stack is implemented by operations that take O(1) that is constant time. The algorithm is as follows:

Input: An array P with n elements and an empty stack N

Output: An array S of n elements such that P[i] is the largest integer k such that k <= i + 1 and P[y] <= P[i] for j = i - k + 1,.....,i

Algorithm:

1. Initialize an array P which contains the daily prices of the stocks 2. Initialize an array S which will store the span of the stock 3. for i = 0 to i = n - 1 3.1 Initialize k to zero 3.2 Done with a false condition 3.3 while not (Stack N is empty or done with processing) 3.3.1 if ( P[i] >= P[N.top)] then Pop a value from stack N                     3.3.2 else Done with true condition 3.4 if Stack N is empty 3.4.1 Initialize h to -1 3.5 else 3.5.1 Initialize stack top to h                        3.5.2 Put the value of h - i in S[i] 3.5.3 Push the value of i in N        4. Return array S

Now, analyzing this algorithm for running time, we observe:

 * We have initialized the array S at the beginning and returned it at the end. This is a constant time operation, hence takes O(n) time
 * The while loop is nested within the for loop. The for loop, whose counter is i is executed n times. The statements which are not in the repeat loop, but in the for loop are executed n times. Therefore these statements and the incrementing and condition testing of i take O(n) time.
 * Now, observe the inner while loop during i repetitions of the for loop. The statement done with a true condition is done at most once, since it causes an exit from the loop. Let us say that t(i) is the number of times statement Pop a value from stack N is executed. So it becomes clear that while not (Stack N is empty or done with processing) is tested maximum t(i) + 1 times.
 * Adding the running time of all the operations in the while loop, we get:

 * $$\sum_{i=0}^{n-1}t(i) + 1$$

 * An element once popped from the stack N is never pushed back into it. Therefore,

 * $$\sum_{i=1}^{n-1}t(i)$$

So, the running time of all the statements in the while loop is O($$n$$)

The running time of all the steps in the algorithm is calculated by adding the time taken by all these steps. The run time of each step is O($$n$$). Hence the running time complexity of this algorithm is O($$n$$).

Related Links

 * Stack (Wikipedia)

Queues
A queue is a basic data structure that is used throughout programming. You can think of it as a line in a grocery store. The first one in the line is the first one to be served.Just like a queue.

A queue is also called a FIFO (First In First Out) to demonstrate the way it accesses data.

  Operations

Adds an item onto the end of the queue.

Returns the item at the front of the queue.

Removes the item from the front of the queue.

True if no more items can be dequeued and there is no front item.

True if no more items can be enqueued.

Returns the number of elements in the queue.

All operations except  can be performed in $$O(1)$$ time. runs in at worst $$O(N).$$

Linked List Implementation
The basic linked list implementation uses a singly-linked list with a tail pointer to keep track of the back of the queue. type Queue<item_type> data list:Singly Linked List<item_type> data tail:List Iterator<item_type> constructor list := new Singly-Linked-List tail := list.get-begin # null end constructor

When you want to enqueue something, you simply add it to the back of the item pointed to by the tail pointer. So the previous tail is considered next compared to the item being added and the tail pointer points to the new item. If the list was empty, this doesn't work, since the tail iterator doesn't refer to anything method enqueue(new_item:item_type) if is-empty list.prepend(new_item) tail := list.get-begin else list.insert_after(new_item, tail) tail.move-next end if end method

The front item on the queue is just the one referred to by the linked list's head pointer method front:item_type return list.get-begin.get-value end method

When you want to dequeue something off the list, simply point the head pointer to the previous from head item. The old head item is the one you removed of the list. If the list is now empty, we have to fix the tail iterator. method dequeue list.remove-first if is-empty tail := list.get-begin end if  end method

A check for emptiness is easy. Just check if the list is empty. method is-empty:Boolean return list.is-empty end method

A check for full is simple. Linked lists are considered to be limitless in size. method is-full:Boolean return False end method

A check for the size is again passed through to the list. method get-size:Integer return list.get-size end method end type

Performance Analysis
In a linked list, accessing the first element is an $$O(1)$$ operation because the list contains a pointer directly to it. Therefore, enqueue, front, and dequeue are a quick $$O(1)$$ operations.

The checks for empty/fullness as done here are also $$O(1)$$.

The performance of  depends on the performance of the corresponding operation in the linked list implementation. It could be either $$O(n)$$, or $$O(1)$$, depending on what time/space tradeoff is made. Most of the time, users of a Queue do not use the  operation, and so a bit of space can be saved by not optimizing it.

Related Links

 * Queue (Wikipedia)

Deques
A Deque is a homogeneous list of elements in which insertions and deletion operations are performed on both the ends.

Because of this property it is known as double ended queue i.e. Deque

Deque has two types:
 * 1) Input restricted queue: It allows insertion at only one end
 * 2) Output restricted queue: It allows deletion at only one end
 * Deque (Double-Ended QUEue)

title: Data Structures/Stacks and Queues


text:
Data Structures/Min and Max Heaps

Some definitions of a heap follow:

A heap is an array, where there are parent child relationships, and the index of a child is 2 * parent index, or 2* parent index + 1 , and a child has an order after the parent, in some concrete ordering scheme injected by a client program of a heap. There is importance in maintaining the ordering n variant after the heap is changed. Some ( Sedgewick and Wayne), have coined the term "swim" and "sink", where maintenance of the invariant involves a invariant breaking item swimming up above children of lower ordering, and then sinking below any children of higher ordering, as there may be two children, so one can swim above a lower ordered child, and still have another child with higher ordering.

A heap is an efficient semi-ordered data structure for storing a collection of orderable data. A min-heap supports two operations: INSERT(heap, element) element REMOVE_MIN(heap)

(we discuss min-heaps, but there's no real difference between min and max heaps, except how the comparison is interpreted.)

This chapter will refer exclusively to binary heaps, although different types of heaps exist. The term binary heap and heap are interchangeable in most cases. A heap can be thought of as a tree with parent and child. The main difference between a heap and a binary tree is the heap property. In order for a data structure to be considered a heap, it must satisfy the following condition (heap property):

 * If A and B are elements in the heap and B is a child of A, then key(A) ≤ key(B).

(This property applies for a min-heap. A max heap would have the comparison reversed). What this tells us is that the minimum key will always remain at the top and greater values will be below it. Due to this fact, heaps are used to implement priority queues which allows quick access to the item with the most priority. Here's an example of a min-heap: A heap is implemented using an array that is indexed from 1 to N, where N is the number of elements in the heap.

At any time, the heap must satisfy the heap property array[n] <= array[2*n]  // parent element <= left child and array[n] <= array[2*n+1] // parent element <= right child whenever the indices are in the arrays bounds.

Compute the extreme value
We will prove that  is the minimum element in the heap. We prove it by seeing a contradiction if some other element is less than the first element. Suppose  is the first instance of the minimum, with  for all , and. But by the heap invariant array, : this is a contradiction.

Therefore, it is easy to compute : MIN(heap) return heap.array[1];

Removing the Extreme Value
To remove the minimum element, we must adjust the heap to fill. This process is called percolation. Basically, we move the hole from node i to either node  or. If we pick the minimum of these two, the heap invariant will be maintained; suppose. Then  will be moved to  , leaving a hole at, but after the move  , so the heap invariant is maintained. In some cases,  will exceed the array bounds, and we are forced to percolate. In other cases, is also outside the bounds: in that case, we are done.

Therefore, here is the remove algorithm for min heap:

 * 1) define LEFT(i) (2*i)

 * 1) define RIGHT(i) (2*i + 1)

REMOVE_MIN(heap) {      savemin=arr[1]; arr[1]=arr[--heapsize]; i=1; while(i<heapsize){ minidx=i; if(LEFT(i)<heapsize && arr[LEFT(i)] < arr[minidx]) minidx=LEFT(i); if(RIGHT(i)<heapsize && arr[RIGHT(i)] < arr[minidx]) minidx=RIGHT(i); if(minidx!=i){ swap(arr[i],arr[minidx]); i=minidx; }        else break; } }

Why does this work? If there is only 1 element ,heapsize becomes 0, nothing in the array is valid. If there are 2 elements, one min and other max, you replace min with max. If there are 3 or more elements say n, you replace 0th element with n-1th element. The heap property is destroyed. Choose the 2 children of root and check which is the minimum. Choose the minimum between them, swap it. Now subtree with swapped child is loose heap property. If no violations break.

Inserting a value into the heap
A similar strategy exists for INSERT: just append the element to the array, then fixup the heap-invariants by swapping. For example if we just appended element N, then the only invariant violation possible involves that element, in particular if $$array[floor(N/2)] > array[N]$$, then those two elements must be swapped and now the only invariant violation possible is between array[floor(N/4)] and  array[floor(N/2)] we continue iterating until N=1 or until the invariant is satisfied. INSERT(heap, element) append(heap.array, element) i = heap.array.length while (i > 1) {       if (heap.array[i/2] <= heap.array[i]) break; swap(heap.array[i/2], heap.array[i]); i /= 2; }

TODO
Merge-heap: it would take two max/min heap and merge them and return a single heap. O(n) time. Make-heap: it would also be nice to describe the O(n) make-heap operation Heap sort: the structure can actually be used to efficiently sort arrays

Make-heap would make use a function heapify

//Element is a data structure// Make-heap(Element Arr[],int size) {       for(j=size/2;j>0;j--) {               Heapify(Arr,size,j); }   }

Heapify(Element Arr[],int size,int t)   { L=2*t; R=2*t+1; if(L<size ) {           mix=minindex(Arr,L,t); if(R<=size) mix=minindex(Arr,R,mix); }       else mix=t; if(mix!=t) {           swap(mix,t); Heapify(Arr,size,mix); }   }

minindex returns index of the smaller element

Applications of Priority Heaps
In 2009, a smaller Sort Benchmark was won by OzSort, which has a paper describing lucidly how to use a priority heap as the sorting machine to produce merged parts of large (internally) sorted sections. If a sorted section took M memory and the sorting problem was k x M big, then take sequential sections of each of the k sections of size M/k, at a time, so they fit in M memory ( k * M/k = M ), and feed the first element of each of k sections to make a k sized priority queue, and as the top element is removed and written to an output buffer, take the next element from the corresponding section. This means elements may need to be associated with a label for the section they come from. When a M/k-sized section is exhausted, load in the next M/k sized minisection from the original sorted section stored on disc. Continue until all minisections in each of the k sections on disc have been exhausted.

(As an example of pipelining to fill up disc operational delays, there are twin output buffers, so that once an output buffer is full one gets written the disc while the other is being filled.)

This paper showed that a priority heap is more straightforward than a binary tree, because elements are constantly being deleted, as well as added, as a queuing mechanism for a k way merge, and has practical application for sorting large sets of data that exceed internal memory storage.

title: Data Structures/Min and Max Heaps


text: Template:Data Structures/Hash Tables

title: Template:Data Structures/Hash Tables


text:
Data Structures/Sets

Sets are helpful tools in a software application where, just as in mathematics, similar abstract objects are aggregated into collections. A mathematical set has a fairly simple interface and can be implemented in a surprising number of ways.

  ADT    True if test-item is contained in the Set.   Adds new-item into the set.   Removes item from the set. If item wasn't in the set, this method does nothing.
Removes the item referred to by item-iter from the set.

Allows iteration over the elements in the Set.

Also allows iteration over the elements in the Set.

Returns a set containing all elements in either this or the other set. Has a default implementation.

Returns a set containing all elements in both this and the other set. Has a default implementation.

Returns a set containing all elements in this but not the other set. Has a default implementation.

True if no more items can be popped and there is no top item.

Returns the number of elements in the set.

All operations can be performed in $$O(N)$$ time.

List implementation
There are several different ways to implement sets. The simplest, but in most cases least efficient, method is to simply create a linear list (an array, linked list or similar structure) containing each of the elements in the set. For the most basic operation, testing membership, a possible implementation could look like function contains(List<T> list, T member) for item in list if item == member return True return False

To add new members to this set, simply add the element to beginning or end of the list. (If a check is done to ensure no duplicate elements, some other operations may be simpler.) Other operations can be similarly implemented in terms of simple list operations. Unfortunately, the membership test has a worst-case running time of $$O(n)$$ if the item is not in the list, and even an average-case time of the same, assuming the item is equally likely to be anywhere in the list. If the set is small, or if frequently accessed items can be placed near the front of the list, this may be an efficient solution, but other options can have a faster running time.

Assuming elements can be ordered and insertions and deletions are rare, a list guaranteed to be in sorted order with no duplicate elements can be much more efficient. Using an ordered list, the membership test can be efficient to the order of $$O(log n)$$. Additionally, union, intersection and subtraction can be implemented in linear time, whereas they would take quadratic time with unordered lists.

Bit array implementation
For certain data, it may be more practical to maintain a bit array describing the contents of the set. In this representation, there is a 1 or 0 corresponding to each element of the problem domain, specifying whether the object is an element of the set. For a simple case, assume that only integers from 0 to n can be members of the set, where n is known beforehand. This can be represented by a bit array of length n+1. The contains operation is simple: function contains(BitArray array, Int member) if member >= length(array) return False else if array[member] == 1 return True else return False

To add or remove an element from this sort of set, simply modify the bit array to reflect whether that index should be 1 or 0. The membership runs in exactly $$O(1)$$ (constant) time, but it has a severely restricted domain. It is possible to shift the domain, going from m to n with step k, rather than 0 to n with step 1 as is specified above, but there is not much flexibility possible here. Nevertheless, for the right domain, this is often the most efficient solution.

Bit arrays are efficient structures for storing sets of Boolean variables. One example is a set of command line options that enable various run-time behavior for the application. C and similar languages offer bit-wise operators that let the programmer access a bit field in a single machine instruction, where array access would normally need two or three instructions including a memory read operation. A full-featured bit set implementation includes operators for computing a set union, set intersection, set difference, and element values.

Associative array implementation
Associative arrays—that is, hash tables and binary search trees, represent a heavyweight but general representation of sets. Binary trees generally have $$O(log n)$$ time implementations for lookup and mutation for a particular key, and hash tables have a $$O(1)$$ implementation (though there is a higher constant factor). Additionally, they are capable of storing nearly any key type. The membership test is trivial: simply test if the potential set member exists as a key in the associative array. To add an element, just add the set member as a key in the associative array, with a dummy value. In optimized implementations, instead of reusing an existing associative array implementation, it is possible to write a specialized hash table or binary tree which does not store values corresponding to keys. Values are not meaningful here, and they take up a constant factor of additional memory space.

title: Data Structures/Sets


text:
Data Structures/Tradeoffs

It is important to fully understand the problem you need to solve before choosing a data structure because each structure is optimized for a particular job. Hash tables, for example, favor fast lookup times over memory usage while arrays are compact and inflexible. Other structures, such as stacks, are optimized to enforce rigid rules on how data is added, removed and accessed throughout the program execution. A good understanding of data structures is fundamental because it gives us the tools for thinking about a program's behavior in a structured way.

[TODO:] Use asymptotic behaviour to decide, most importantly seeing how the structure will be used: an infrequent operation does not need to be fast if it means everything else will be much faster

[TODO:] Can use a table like this one to compare the asymptotic behaviour of every structure for every operation on it.

* singly-linked lists can push to the back in O(1) with the modification that you keep a pointer to the last node

 * Please correct any errors

[TODO:] Can also add a table that specifies the best structure for some specific need e.g. For queues, double linked. For stacks, single linked. For sets, hash tables. etc...

[TODO:] Could also contain table with space complexity information (there is a significative cost in using hashtables or lists implemented via arrays, for example).

title: Data Structures/Tradeoffs


text:
User:Ckelsh

I'm a recent Wikipedia import. Nothing to see -- I just couldn't stand my link to be red.

title: User:Ckelsh


text:
User talk:Ckelsh

I'd love some boilerplate welcome text!

title: User talk:Ckelsh


text:
User:Khaosworks

From Wikimedia Commons

See http://en.wikipedia.org/wiki/User:Khaosworks

title: User:Khaosworks


text:
Template:Data Structures/ChapNav

 Data Structures Introduction - Asymptotic Notation - Arrays - List Structures & Iterators Stacks & Queues - Trees - Min & Max Heaps - Graphs Hash Tables - Sets - Tradeoffs

title: Template:Data Structures/ChapNav


text:
Talk:Italian/Grammar/Verbs

Untitled
The structure of the Italian verb system is very coherent and intelligible. If one understands that the structure can be perceived as a chart of interrelated concepts, a great deal of the mystery about Italian verb structure disappears. In order to gain an understanding of the structure of the system, one should determine answers to the following questions: What is the congugation category of the verb (1st, 2nd or 3rd)? What is the behavior of the verb (regular or irregular)? What is the voice category of the verb (Active or Passive)? What is the mood category (Indicative, Subjunctive, Conditional, or Imperative)? What is the tense category (Any of 17 tenses assigned to the various moods)? What is the number category (Singular or Plural)? What is the person category (1st, 2nd, or 3rd)?

(To be continued)

title: Talk:Italian/Grammar/Verbs


text:
Data Structures/Asymptotic Notation

Introduction
There is no single data structure that offers optimal performance in every case. In order to choose the best structure for a particular task, we need to be able to judge how long a particular solution will take to run. Or, more accurately, you need to be able to judge how long two solutions will take to run, and choose the better of the two. We don't need to know how many minutes and seconds they will take, but we do need some way to compare algorithms against one another.

Asymptotic complexity is a way of expressing the main component of the cost of an algorithm, using idealized (not comparable) units of computational work. Consider, for example, the algorithm for sorting a deck of cards, which proceeds by repeatedly searching through the deck for the lowest card. The asymptotic complexity of this algorithm is the square of the number of cards in the deck. This quadratic behavior is the main term in the complexity formula, it says, e.g., if you double the size of the deck, then the work is roughly quadrupled.

The exact formula for the cost is more complex, and it contains more details than we need to understand the essential complexity of the algorithm. With our deck of cards, in the worst case, the deck would start out reverse-sorted, so our scans would have to go all the way to the end. The first scan would involve scanning $$52$$ cards, the next would take $$51$$, etc. So the cost formula is $$52 + 51 + \dots + 2$$. Generally, letting $$N$$ be the number of cards, the formula is $$2 + \dots + N$$, which equals $$N \times \frac{N + 1}{2} - 1 = \frac{N^2 + N}{2} - 1 = \frac{1}{2} \times N^2 + \frac{1}{2} \times N - 1$$. But the $$N^2$$ term dominates the expression, and this is what is key for comparing algorithm costs. (This is in fact an expensive algorithm; the best sorting algorithms run in sub-quadratic time.)

Asymptotically speaking, in the limit as $$N$$ tends towards infinity, $$2 + 3 + \dots + N$$ gets closer and closer to the pure quadratic function $$\frac{1}{2} \times N^2$$. And what difference does the constant factor of $$\frac{1}{2}$$ make, at this level of abstraction? So the behavior is said to be $$O(n^2)$$.

Now let us consider how we would go about comparing the complexity of two algorithms. Let $$f(n)$$ be the cost, in the worst case, of one algorithm, expressed as a function of the input size $$n$$, and $$g(n)$$ be the cost function for the other algorithm. E.g., for sorting algorithms, $$f(10)$$ and $$g(10)$$ would be the maximum number of steps that the algorithms would take on a list of $$10$$ items. If, for all values of $$n \ge 0$$, $$f(n)$$ is less than or equal to $$g(n)$$, then the algorithm with complexity function $$f$$ is strictly faster. But, generally speaking, our concern for computational cost is for the cases with large inputs; so the comparison of $$f(n)$$ and $$g(n)$$ for small values of $$n$$ is less significant than the "long term" comparison of $$f(n)$$ and $$g(n)$$, for $$n$$ larger than some threshold.

Note that we have been speaking about bounds on the performance of algorithms, rather than giving exact speeds. The actual number of steps required to sort our deck of cards (with our naive quadratic algorithm) will depend upon the order in which the cards begin. The actual time to perform each of our steps will depend upon our processor speed, the condition of our processor cache, etc., etc. It's all very complicated in the concrete details, and moreover not relevant to the essence of the algorithm.

Definition
The $$O$$ (pronounced big-oh) is the formal method of expressing the upper bound of an algorithm's running time. It's a measure of the longest amount of time it could possibly take for the algorithm to complete. We can assume that it represents the "worst case scenario" of a program.

More formally, for non-negative functions, $$f(n)$$ and $$g(n)$$, if there exists an integer $$n_{0}$$ and a constant $$c > 0$$ such that for all integers $$n>n_{0}$$, $$f(n) \le cg(n)$$, then $$f(n)$$ is big O of $$(g(n))$$. This is denoted as $$f(n) = O(g(n))$$. If graphed, $$g(n)$$ serves as an upper bound to the curve you are analyzing, $$f(n)$$.

Note that if $$f$$ can take on finite values only (as it should happen normally) then this definition implies that there exists some constant $$C$$ (potentially larger than $$c$$) such that for all values of $$n$$, $$f(n) \le Cg(n)$$. An appropriate value for $$C$$ is the maximum of $$c$$ and $$\max_{1\le n\le n_0} \frac{f(n)}{g(n)}$$.

Theory Examples
So, let's take an example of Big-O. Say that $$f(n) = 2n + 8$$, and $$g(n) = n^2$$. Can we find a constant $$n_{0}$$, so that $$2n + 8 \le n^2$$? The number $$4$$ works here, giving us $$16 \le 16$$. For any number $$n$$ greater than $$4$$, this will still work. Since we're trying to generalize this for large values of $$n$$, and small values $$\{ 1, 2, 3 \}$$ aren't that important, we can say that $$f(n)$$ is generally faster than $$g(n)$$; that is, $$f(n)$$ is bound by $$g(n)$$, and will always be less than it.

It could then be said that $$f(n)$$ runs in $$O(n^2)$$ time: "f-of-n runs in Big-O of n-squared time".

To find the upper bound - the Big-O time - assuming we know that $$f(n)$$ is equal to (exactly) $$2n + 8$$, we can take a few shortcuts. For example, we can remove all constants from the runtime; eventually, at some value of $$n$$, they become irrelevant. This makes $$f(n) = 2n$$. Also, for convenience of comparison, we remove constant multipliers; in this case, the $$2$$. This makes $$f(n) = n$$. It could also be said that $$f(n)$$ runs in $$O(n)$$ time; that lets us put a tighter (closer) upper bound onto the estimate.

Practical Examples
$$O(n)$$: printing a list of $$n$$ items to the screen, looking at each item once.

$$O(\log_2{n})$$: taking a list of $$n$$ items, cutting it in half repeatedly until there's only one item left.

$$O(n^2)$$: taking a list of $$n$$ items, and comparing every item to every other item.

Big-Omega Notation
For non-negative functions, $$f(n)$$ and $$g(n)$$, if there exists an integer $$n_{0}$$ and a constant $$c > 0$$ such that for all integers $$n>n_{0}$$, $$f(n) \ge cg(n)$$, then $$f(n)$$ is $$\Omega(g(n))$$. This is denoted as $$f(n) = \Omega(g(n))$$.

This is almost the same definition as Big Oh, except that $$f(n) \ge cg(n)$$, this makes $$g(n)$$ a lower bound function, instead of an upper bound function. It describes the best that can happen for a given data size.

Theta Notation
For non-negative functions, $$f(n)$$ and $$g(n)$$, $$f(n)$$ is theta of $$g(n)$$ if and only if $$f(n) = O(g(n))$$ and $$f(n) = \Omega(g(n))$$. This is denoted as $$f(n) = \Theta(g(n))$$.

This is basically saying that the function, $$f(n)$$ is bounded both from the top and bottom by the same function, $$g(n)$$.

The theta notation is denoted by Q.

Little-O Notation
For non-negative functions, $$f(n)$$ and $$g(n)$$, $$f(n)$$ is little o of $$g(n)$$ if and only if $$f(n) = O(g(n))$$, but $$f(n) \ne \Theta(g(n))$$. This is denoted as $$f(n) = o(g(n))$$.

This represents a loose bounding version of Big O. $$g(n)$$ bounds from the top, but it does not bound the bottom.

Little Omega Notation
For non-negative functions, $$f(n)$$ and $$g(n)$$, $$f(n)$$ is little omega of $$g(n)$$ if and only if $$f(n) = \Omega(g(n))$$, but $$f(n) \ne \Theta(g(n))$$. This is denoted as $$f(n) = \omega(g(n))$$.

Much like Little Oh, this is the equivalent for Big Omega. $$g(n)$$ is a loose lower boundary of the function $$f(n)$$; it bounds from the bottom, but not from the top.

How asymptotic notation relates to analyzing complexity
Temporal comparison is not the only issue in algorithms. There are space issues as well. Generally, a trade off between time and space is noticed in algorithms. Asymptotic notation empowers you to make that trade off. If you think of the amount of time and space your algorithm uses as a function of your data over time or space (time and space are usually analyzed separately), you can analyze how the time and space is handled when you introduce more data to your program.

This is important in data structures because you want a structure that behaves efficiently as you increase the amount of data it handles. Keep in mind though that algorithms that are efficient with large amounts of data are not always simple and efficient for small amounts of data. So if you know you are working with only a small amount of data and you have concerns for speed and code space, a trade off can be made for a function that does not behave well for large amounts of data.

A few examples of asymptotic notation
Generally, we use asymptotic notation as a convenient way to examine what can happen in a function in the worst case or in the best case. For example, if you want to write a function that searches through an array of numbers and returns the smallest one:

function find-min(array a[1..n]) let j := $$\infty$$ for i := 1 to n: j := min(j, a[i]) repeat return j end

Regardless of how big or small the array is, every time we run find-min, we have to initialize the i and j integer variables and return j at the end. Therefore, we can just think of those parts of the function as constant and ignore them.

So, how can we use asymptotic notation to discuss the find-min function? If we search through an array with 87 elements, then the for loop iterates 87 times, even if the very first element we hit turns out to be the minimum. Likewise, for $$n$$ elements, the for loop iterates $$n$$ times. Therefore we say the function runs in time $$O(n)$$.

What about this function:

function find-min-plus-max(array a[1..n]) // First, find the smallest element in the array let j := $$\infty$$; for i := 1 to n: j := min(j, a[i]) repeat let minim := j // Now, find the biggest element, add it to the smallest and j := $$-\infty$$; for i := 1 to n: j := max(j, a[i]) repeat let maxim := j // return the sum of the two return minim + maxim; end

What's the running time for find-min-plus-max? There are two for loops, that each iterate $$n$$ times, so the running time is clearly $$O(2n)$$. Because $$2$$ is a constant, we throw it away and write the running time as $$O(n)$$. Why can you do this? If you recall the definition of Big-O notation, the function whose bound you're testing can be multiplied by some constant. If $$f(x) = 2x$$, we can see that if $$g(x) = x$$, then the Big-O condition holds. Thus $$O(2n) = O(n)$$. This rule is general for the various asymptotic notations.

title: Data Structures/Asymptotic Notation