Powered by glolg
Display Preferences Most Recent Entries Chatterbox Blog Links Site Statistics Category Tags About Me, Myself and Gilbert XML RSS Feed
Saturday, Aug 29, 2009 - 17:43 SGT
Posted By: Gilbert

Algo Brüno Championleagueo

(N.B. Ph.D. Taxi driver blogger identity confirmed - the blog is legit)


Algo

Been spending a bit of time with algorithms recently, in particular basic asymptotic analysis, which I'm informed is a math module too (ulp). Before that, what is an algorithm?

While the word "algorithm" may conjure up visions of complex oodles of code, at its heart an algorithm is simply a collection of instructions that aim to complete some task. For example, babies eventually discover the algorithm for walking as:

1. Put one foot ahead of the other.
2. Put the other foot ahead of the first foot.
3. Repeat.

 (N.B. Computer Science [CS] people call it an "algorithm" instead of simply "steps" or "a plan" to justify their existence)

Algorithms are important in CS as computers are, despite being very fast and very loyal, also gloriously stupid. Say that an executive has a file containing 1000 account numbers, and wants them in ascending order. One possible solution is to tell a personal assistant, "Sort these accounts in ascending order before lunch." The other is to let a computer do it.

Unfortunately, computers today are generally not very good at human languages (we're still a way from C-3PO of Star Wars fame), and have to be told how to do every tiny thing - threatening to fire them won't help. How might our executive instruct a computer to do the sorting? Well, he could order his PA to tell the computer the individual steps involved in sorting. The PA then sits in front of the computer, sighs, and comes out with a plan:

1. Pick the lowest account number out of all unsorted account numbers.
2. Put this account number at the bottom of the list of sorted account numbers.
3. Repeat while there are still unsorted account numbers.

This isn't quite detailed enough for the computer, and might be expanded as follows:

1a. Check the next unsorted account number is lower than the current lowest unsorted account number.
1b. If it is, it becomes the current lowest unsorted account number.
1c. Repeat while there are still unsorted account numbers.
2a. Exchange this lowest (sorted) account number with the next unsorted account number.
2b. Increase the number of sorted account numbers by one.
3. Repeat while there are still unsorted account numbers.

Better, except that the computer still doesn't understand English and has no plans to pick it up, forcing the PA to translate his plan into one of the many computer languages:

$sorted = 0;
$maxi = 1000;

while ($sorted < $maxi) {

    while ($i = $sorted; $i < $maxi; $i++) {
        if ($i == $sorted) {
            $lowest = $U[$i];
            $lowi = $i;
        }
        if ($U[$i] < $lowest) {
            $lowest = $U[$i];
            $lowi = $i;
        }
    }
    $U[$lowi] = $U[$sorted];
    $U[$sorted] = $lowest;
    $sorted = $sorted + 1;
}

And we are done.

This particular (pretty natural) method of sorting is called selection sort, because at every iteration, the smallest (or largest/cutest if desired) item is selected. Although selection sort is completely correct, we might ask if there are faster ways to go about doing our sorting. As it happens, there are!

Unfortunately, better/faster algorithms are often more complicated (otherwise the obvious algorithm would be the best). For example, consider quicksort. The idea behind it would be to first pick any element as a "pivot", and then move all elements smaller than (or equal to) the pivot to its left, and all elements larger than the pivot to its right.

For example, for the following list, taking 5 as the pivot:

5 9 7 1 3 2 10 4 8 6

we would get something like this:

1 3 2 4 5 9 10 7 8 6

by going through all 10 elements exactly once. Looks better, but it's not quite right yet.

How do we continue? Well, we repeat the same process on the two lists to either side of the pivot. Each time we do this to a list, the problem is reduced to that of sorting two lists of at most half the size of the original. Eventually, we end up with lists of a single element, which are of course sorted by default.

This algorithm clearly works too, but why is it better than the simpler selection sort? Here's a rough idea:

At the top level, there is a list of n items. Let us say each item takes 1 second to process, then the list takes n seconds to process.

After the lists are halved, at the next level there are two lists of n/2 items, which also take n seconds to process in total.

We see that at the third level, there are four lists of n/4 items taking n seconds in total also, and so on for each level, until each list contains a single element. How many levels are there? After L levels, each of the L lists will have n/2(L-1) items, so the last level is when n/2(L-1) = 1, or with a bit of algebraic manipulation, L = (lg n/lg 2)+1. Put into perspective, for n = 1 million (i.e. a list with a million elements), there are just 21 levels. The total time taken is thus about 21 million seconds.

What about selection sort? For the same list, the first iteration would need to check all one million elements. The second iteration would check 999 999 elements, the third 999 998 elements, and so on for one million iterations in total. Using the summation formula that 1 + 2 + ... + (n-1) + n = n(n+1)/2, the total number of checks and therefore the total number of seconds required, would be (1 000 000)(1 000 001)/2, or over 500 billion seconds, more than 20 000 times longer than quicksort! By trying larger figures for n, we easily see that the larger n is, the better quicksort performs compared to selection sort.

In Big Θ notation, we say that selection sort takes Θ(n2) time, while quicksort takes Θ(n lg n) time... on average. Why is this so? Consider a list that is already sorted. Then quicksort, taking the first element of a list as a pivot each time, has to go through a total of n lists, and would be no better than selection sort. However, that is a pretty rare case, and in general we are justified in saying that quicksort is faster, since even when the lists aren't divided perfectly evenly, the effect is still to diminish the size of the lists very rapidly.

This is what asymptotic analysis is all about: Stating which algorithms are faster than others as the number of elements to be inspected grows. In ascending order (lousiness), some of the orders are Θ(1) [constant time], Θ(lg n), Θ(n), Θ(n lg n), Θ(nk) and Θ(kn).

While it is not set in stone that an algorithm with a lower order is always better in practice [an algorithm that takes n2 time is faster than one that takes 1001000(lg n)10000 time unless the value of n is truly stupendous - note that the number of particles in the entire universe is estimated to be somewhat less than 10100, and 264 (about 1018) grains of rice is already more than what the Earth could produce in centuries], the order nevertheless is an invaluable rule of thumb, since in practice huge constants and exponents are rather uncommon.

Again, in practice, computer programmers seldom (re)implement such code themselves - programming languages worth their salt would include prewritten subroutines that can be called upon for almost all purposes, and trying to code one's own version for greater efficiency is for most part not worth it. Remember, a programming language, even assembly code, is to an extent an abstraction or algorithm to generate the bits that constitute true machine language. In real life, our long-suffering personal assistant as seen in the example above would probably have just dumped the data into Microsoft Excel.

From personal experience, great algorithms often seem very obvious once they are learnt. Having the imagination to discover them is another thing altogether, I suppose. Some examples: Given a number of tasks scheduled for a fixed time period, and given that you can only do one task at any one time, how would you select the maximum number of achievable tasks? Given a huge map of thousands of intersecting roads, how would you find the shortest route between two points? Hint: Both problems can be solved in a time nearly proportional to the number of tasks/roads.

A third interesting problem is the stable marriage problem, or how to match up an equal number of men and women (or students and advisors, etc) such that all the pairings hold, by making sure that there are no circumstances where a husband and a wife currently in different marriages are willing to leave their spouses for one another (assuming that their preferences do not change over time). Yes, it can always be done, and there's an algorithm to do it. Don't let the SDU get wind of it!

Things are not always so simple, of course. Consider board games like Power Grid (played last Saturday with colin & triceo). While it is certainly to compute all possibilities on the last turn, when someone has the funds to build the maximum number of power stations, it is often too late to affect the outcome by then. A more classic example is chess, which has a finite number of piece configurations, and therefore must be solvable by examining all possible configurations and their transitions (i.e. by brute force); the practical issue is that there are about 1040 such possibilities.

I will delve into more applications of algorithms sporadically in the future, and for now introduce a puzzle site called [wu:riddles], which has been around for some time. Strangely, I have managed to come across a few of the puzzles in the course of taking modules (particularly in algorithms, game theory and psychology)

My pick for today is one of the "medium-difficulty" questions (though the ratings are quite subjective, and may not be applicable to those with particular strengths):

WORLD SERIES BETTING

You dare not offend nor disappoint Great Uncle Willy lest he disown you. He has placed $2000 in your hands to bet on the outcome of the World Series, which is a baseball contest won by whichever of two teams first wins four games. Willy's $2000 was given to you in advance of the series. At the end of the series he expects you to return to him either $4000 if the team he chose wins, or nothing if it loses.

But you can find nobody who will accept bets on the entire World Series. However, there are wagerers who will take on even-odds bets, in any amount(s), on each game individually. What strategy for placing bets on individual games will achieve the cumulative result Willy expects?

Note: This task was reputedly set before job-seekers at a Wall Street brokerage in 1994.

Clearly this would be trivial if Willy's nephew had money to spare (in which case he could just take on the bet himself), but the intention of the puzzle is that he is flat broke. Also, the actual abilities of the baseball teams are irrelevant. Honorary AAAAA up for grabs!


Brüno

Checked out what was possibly my first R-21 rated film, Brüno, with occ and alvin at Cine. Hamstrings still ached slightly after Tuesday's badminton session with occ and law, likely due to not stretching. And Mr. Ham assures me that his strings never hurt. Bah!

Sadly, the movie was a notch less funny than I had expected. As one reviewer said, it has exactly one trick up its sleeve, and repeats it over and over again. There are some priceless moments, such as when some parents are willing to let their babies land any sort of acting gig, even if it involves operating antiquated heavy machinery while dressed as a Nazi.

Another gripe is that it is hard to believe that all the scenes were unscripted, for example the reviewer comments, which had to be quite specific to support the continuation of the plot (unless Cohen played it by ear). Still, it is a special kind of talent that manages to get Paula Abdul to speak about humanitarian work while using a Mexican as a chair, and a special kind of bollocks that indulges in terrorist-baiting - "I want to be famous. I want the best guys in the business to kidnap me. Al-Qaeda is so 2001..."

In the final accounting, Brüno is probably a disservice to the more well-behaved gays (which is just about the rest of them), despite raising awareness, but as Kazakhstan found out with Borat, you takes what you gets.

One thing that struck me was that Brüno looked slightly familiar, and lo and behold:


On the left, Liverpool star Fernando Torres
On the right, comedy genius Brüno
(Sources: Buzznet.com & Ekolay.net)


The resemblance hasn't been lost on his teammates (okay, News of the World isn't the most reliable source, but...). Well, having another celebrity spearheading their forward line won't affect them much, seeing that they have Kevin Spacey as their manager.

Okay, I confess, I matched the colours of the two images (and touched up Brüno's eyebrows some, or was it Torres?) to heighten the similarity, using Photoshop's Match Color (what else?) tool. Protip: The Computer Vision and Pattern Recognition module I'm currently taking teaches one how to do that... with MATLAB.


Championleagueo

And we return to footy, in a week that saw Liverpool surprised 1-3 by Aston Villa (Brüno netting their consolation goal), and United rout Wigan 5-0, but it's still early days. Memories are short in football, and if United beat Arsenal later tonight they'll be regarded as lock-ons for four titles in a row, and if they lose it's time for Ferguson to leave. Part and parcel of the game.

What shouldn't be part of the game are the scenes at West Ham vs Millwall a few days ago, with large-scale fights, though fortunately no fatalities. Quite by coincidence I had just borrowed The Football Factory some days ago, which gives a man-on-the-groud perspective on such clashes between hooligan "firms". Kind of an odd feeling to see locations I've been to (e.g. King's Cross, Seven Sisters) referenced.

The major motivation appears to be a sense of belonging (tribalism/brotherhood), and the sheer adrenaline rush, and perhaps a touch of Fight Club-style psychological support. The Football Factory follows a Chelsea fan, who coincidentally is badly injured near the end of the book after getting outnumbered against Millwall supporters.

Mass brawls such as these were far more common in the Eighties, and usually took place some distance from the stadium itself to avoid police presence. Weapons were not compulsory but far from prohibited, and there appears to be no real motive - participation and not getting beat up too badly seemed to be the key goals. Not a bad way of letting off steam, except for the property damage and people possibly getting disabled or killed.

[N.B. Speaking of participation, Usain Bolt is a relief in a world where technology seems to be taking over sports, e.g. super-swimsuits in the pool and various doping procedures of dubious legality in cycling (and atheletics to a lesser extent)]

More trivia: one area where football hooliganism might not have been expected to impact is fashion, but it did. Leather jackets and work clothes were a real police magnet, and the obvious solution was to adopt a more affluent and respectable look. Such apparel was more expensive, and again an obvious solution presented itself - just steal it. And one didn't even have to skulk about in the process; with sufficient numbers, less scrupulous supporters could just flood a store and walk out with what they wanted!


Materazzi: "Football, bloody game, eh?"
Rui Costa: "Indeed, indeed."
(Sources: Lordcolus on Flickr)


Returning to the business of football proper, the Champions League group stage draw took place on Thursday night, and was nowhere to be seen on Starhub presumably thanks to Singtel buying up the Champions League rights. United drew CSKA Moscow, Beşiktaş and Wolfsburg, a decent group but with a lot of travelling.

An observation from the draw was that the person choosing the groups might have reasonably easily chosen his desired group, since there were a maximum of eight balls in his transparent bowl, and an assistant always placed the balls two at a time in order into the bowl, i.e. knowing which ball contained which group letter is straightforward. Of course, having the assistant deliberately mix the balls about first might impugne on the drawer's integrity...

Virtual punting: $174/$200 after City failed to oblige with a second goal in the second week. Since I haven't got a copy of The New Paper with me, odds will be from Singapore Pool's website:

$50 on Man City (-1.5) vs Portsmouth (at 2.45)
$25 on Everton (-1.5) vs Wigan (2.70)
$25 on Man Utd to draw Arsenal (3.10)



comments (0) - email - share - print - direct link
trackbacks (0) - trackback url


Next: Ham, Thy Name Is Fame


Related Posts:
Clearing a Virtual House
Spot The Bug (Not The Dog)
Mega Bonus Post
Takeoff Imminent
Weekend B-activities
Back to top

Copyright © 2006-2025 GLYS. All Rights Reserved.