Thursday, September 14, 2006

Historical Algorithms?

So I recently found myself doing some readings on algorithms. I found this lesson pretty interesting, if a little rudimentary. I thought that the principle characteristics of a good algorithm were well explained, but the lessons themselves involved a little too much guiding by hand. Luckily, the good ol' intraweb has the resources to help me read more about the topic. One thing that did interest me comes from the page on worst case scenarios. What caught my eye was how the authors skipped doing all of that summation work for the selection and instertion sorts by recognizing the trend seen in the first order of magnitude analyzed. However, how would they have solved the equations: (n-1)+(n-2)+(n-3)+...+1 if they did not have the simple sort to compare with?

After a quick Google search with "math" and "summation" as my principle search terms. The first result returned was for the title "the algebra of summation notation". I found that the site was fascinating.

Although the site did not explain exactly where some of the "well-known" summation rules came from, I could see that the (n*(n-1))/2 shortcut used in the algorithm lesson was based on rule #2, where S(n)(i:n)= (n*(n+1))/2. I could also appreciate that rule #2 could be derived from rule #1...now, rule #3 and #4 are a little difficult to appreciate. Where do the 6 and 4 come from?

I guess that I will have to figure that one out on my own...

The sorting algorithm strikes me as an essential tool for anyone doing research that involves collecting pieces of data. However, it is significant as a stochastic tool, as I believe that it will not return sorted data in a way that is meaningful to historians. Of course, this last point is certainly up for debate...

1 comment:

samantha said...

You have a wonderful site, although it can be improved by adding in the resources. There are two resons off the top of my head, which are:- young children, such as myself, to do their homework. The second reson is:- for adults to proof read about it, so they are knowing what they are reading about. (as my mother likes to do!).

sighned... Samantha L Howell.