{"id":326,"date":"2007-02-27T22:02:15","date_gmt":"2007-02-27T22:02:15","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/02\/27\/basics-algorithm\/"},"modified":"2007-02-27T22:02:15","modified_gmt":"2007-02-27T22:02:15","slug":"basics-algorithm","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/02\/27\/basics-algorithm\/","title":{"rendered":"Basics: Algorithm"},"content":{"rendered":"

A kind reader pointed out that I frequently mention algorithms, but that I haven’t defined them in the basics posts. To me, they’re so fundamental to the stuff I do for a living that I completely forgot that they’re an interesting idea.<\/p>\n

It’s really pretty simple: an algorithm is description of a mechanical procedure for performing a mathematical task. But that’s actually a fairly sophisticated idea – the general concept of things<\/em> that describe a procedure, and which can be discussed, described, and reasoned about as entities in their own right is something quite different from nearly anything that came before it.<\/p>\n

<\/p>\n

The term algorithm has an interesting and humorous origin. Most people believe that it’s named after a Persian mathematician named “Al-Khwarizmi”. That’s actually not quite true. While the term is<\/em> derived from Al-Khwarizmi’s name, it’s actually an accident. In fact, what happened was that Al-Khwarizmi wrote a book about how to perform calculations using the Hindi numbering system (which is what we know as arabic numerals). Several hundred years later, the text was translated into Latin, and in the process of transliterating the name “Al-Khwarizmi” into Latin, the title of the book became “Algorithmi on Indian Numbers”. “Algorithmi” looks<\/em> like a latin plural noun – and so many European mathematicians interpreted the title of the book not as “Al-Khwarizmi talking about mathematical procedures using Indian numbers”, but “Mathematical Procedures using Indian Numbers”. And the term stuck.<\/p>\n

So – an algorithm is a description mathematical procedure – and it’s possible to reason about an algorithm as an entity itself. Let’s look at a simple example, just to get the sense of it.<\/p>\n

Suppose I have a list of N numbers in random order. I want to get the list into
\nincreasing order – smallest first, largest last, ever number smaller than the number that comes after it.<\/p>\n

One of the simplest algorithms for this is called bubble sort<\/em>:<\/p>\n

\nGiven: a list L1<\/sub>...LN<\/sub> of N numbers in random order.<\/b>\nProduce: a list of those N numbers in increasing order<\/b>\nDo:<\/b>\nrepeat the following until the list no longer changes:\nlook at each pair of adjacent numbers Li<\/sub> and Li+1<\/sub>:\nif Li<\/sub> > Li+1<\/sub> then swap Li<\/sub> and Li+1<\/sub>\n<\/pre>\n
 This will<\/em> produce a sorted list. Let’s run through a quick example: the list [3,5,2,1,4].<\/p>\n
    \n
  1.  First pass through the list:\n
      \n
    1.  Compare 3 and 5. 3<5 so move on to the next pair.<\/li>\n
    2.  Compare 5 and 2. 5>2, so swap. List becomes [3,2,5,1,4]<\/li>\n
    3.  Compare 5 and 1. 5>1, so swap. List becomes [3,2,1,5,4]<\/li>\n
    4.  Compare 5 and 4. 5>4, so swap. List becomes [3,2,1,4,5]<\/li>\n<\/ol>\n
    5.  The list changed, so we take another pass. Second pass:\n
        \n
      1.  Compare 3 and 2. 3>2, so swap. List becomes [2,3,1,4,5]<\/li>\n
      2.  Compare 3 and 1.3>1, so swap. List becomes [2,1,3,4,5]<\/li>\n
      3.  Compare 3 and 4. 3<4, so move on.<\/li>\n
      4.  Compare 4 and 5. 4<5, so move on.<\/li>\n<\/ol>\n
      5.  The list changed, so we do another pass. Third pass:\n
          \n
        1.  Compare 2 and 1. 2>1, so swap. List is now: [1,2,3,4,5].<\/li>\n
        2.  Next four comparisons are (2,3), (3,4), (4,5), none of which cause swaps.<\/li>\n<\/ol>\n
        3.  The list changed, so another pass. Fourth pass, everything is in order – each pair compares without causing changes. So the result is [1,2,3,4,5].<\/li>\n<\/ol>\n
           What can we say about this algorithm? Well, for one thing, it’s slow. Given a list of N elements, we might need to do up to N passes over the list, each of which will do N-1 comparisons, each of which might cause a swap. So in the worst case, this will require N2<\/sup>-N comparisons and swaps to get the list into order. Our example wasn’t even a worse case, and it ended up needed to do 16 comparisons (4 passes, 4 comparisons per pass), and 6 swaps. In the best case – the list is already in order – this algorithm will take one pass – N-1 comparisons, 0 swaps.<\/p>\n
           There are even some tricks using Kolmogorov-Chaitin information theory where we can show that on average, Bubble-sort will tend more towards the worse end of its possible performance than the best – but that’s beyond the scope of a basics post, except to point out that we can apply interesting mathematical analyses to the algorithm itself<\/em> to figure out what it’s average performance should be, even without running it.<\/p>\n","protected":false},"excerpt":{"rendered":"
          A kind reader pointed out that I frequently mention algorithms, but that I haven’t defined them in the basics posts. To me, they’re so fundamental to the stuff I do for a living that I completely forgot that they’re an interesting idea. It’s really pretty simple: an algorithm is description of a mechanical procedure for […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[74],"tags":[],"class_list":["post-326","post","type-post","status-publish","format-standard","hentry","category-basics"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-5g","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/326","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=326"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/326\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=326"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=326"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=326"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}