Sunday Numbers 2.0, Vol. 5: Sorting animations.

As Donald Knuth said, "An algorithm must be seen to be believed." In some browsers, you can click on the pictures to watch an animation of some famous sorting algorithms.



Here is a video from The You Tubes of heapsort. This is a link to another animation of Heapsort, which puts in a heap sorted backwards, then takes the big values at the front of the line and moves in in exact order into the back of the line.




Here is a YouTube selection for Quicksort. Note that some of the lines are green, which means in the proper position, and some are in blue, which means not yet perfectly sorted. While the project appears to be try to set things up from left to right, you'll notice very early on a green line This is a link to another animation of Quicksort, which picks a single value, puts it in the proper position, with everything smaller than the value in front of it and everything bigger after it. This effectively splits the data set into two parts to be sorted yet again. This is called a divide and conquer algorithm.

My friend Ken sent me a link to a bunch of animating in place sort algorithms. These include Heapsort and Quicksort, as well as merge, bubble, shell and others.

Thanks to Ken. Fun stuff, if you like that sort of thing.

(Nerd puns. Tee hee!)

So, what CAN'T a computer do better than a human brain?

Much is being made of a recent project from IBM called Watson*, a computer trivia program that is set to compete with top players on Jeopardy!, the show to be aired in the middle of next month. The machine beat top champions Ken Jennings and Brad Rutter in a short practice which can be viewed already.

As a computer programmer and a former Jeopardy! champ, I am very impressed with this accomplishment.

It's nothing at all for a computer to have a massive amount of data in storage and the ability to access it at literal lightning speed. The great accomplishment here is the ability understand a sentence in spoken English a person has made intentionally tricky by employing homonyms, puns and other word play. English is by far the language with the most words of any used by humans, roughly twice the size of any other. If the data set is correctly formatted, that doubling of size means searching for words might take ten superfast decisions instead of nine.

But consider the word bat. Are we talking about the flying animal or the piece of wood used in baseball? Don't forget that it's also the name for the piece of wood in the game cricket, and in British usage, a ping pong paddle becomes a tennis table bat. When combined with the adjective "old", it's probably not a flying animal or a piece of wood used to hit a ball, but instead a somewhat outdated piece of slang for a disagreeable older woman.

"He was disgusted when the old bat batted her eyes." There are two ways this can be disgusting, one much more likely than the other. How do you fill a computer with all the possible permutations of word play? What about an audio Daily Double or a video Daily Double? We are used to pulling the human voice out the many sounds in a song. How well can a computer do that?

*As you might have already guessed, this program Watson is named for Thomas Watson, the man who in 1924 renamed Computing Tabulating Recording Corporation to International Business Machines and became the president of the newly named company, which would dominate the tabulating machine industry for many decades to come.


IBM is building on a track record of making software that excels at brain games. Their greatest previous victory was the chess software that defeated legendary world champion Garry Kasparov in a six game match in 1997 by compiling a record of two wins, one loss and three draws. When it comes to speed chess, computers have dominated humans for decades, but this set of matches was played using the regulation time limits for the top professional tournaments, two hours a piece for each player to complete 40 moves and if the game is still undecided, the position is sealed and play begins later with less times allotted. Kasparov wanted a rematch but IBM refused and accusations of cheating were thrown around. Still, the final score was Deep Blue 2.5, Kasparov 1.5, and it is still considered a watershed moment in the history of software development.


On the other hand, there are some brain games that do not have particularly good software opponents available. Most notably the great Asian game known as Go in Japanese (Weiqi in Chinese and Baduk in Korean), a game whose rules are somewhat simpler than chess since pieces never move once put on the board unless they are captured. Many fans of Go say it does not have a good algorithm a computer can follow because it is so much more subtle than chess, but it seems more likely that the problem of making a strong computer opponent lies in the fact that no one has decided to put in the resources necessary to develop such a program. Go is a great game and very subtle, but it is nowhere near as subtle as understanding the spoken English language, and Watson has shown it can do that remarkably well.


As for great games that also involve the element of chance, some have been the focus of very intensive software research and others have not. A computer backgammon program beat the World Champion Luigi Villa back in 1979, and by using backgammon software to analyze positions exhaustively, some players consider the game close to "solved", such that the best plays are known and it just comes down to luckier dice.

On the other, bridge software is still in its infancy. Again, I am willing to concede bridge is more complex than backgammon, but I don't think bidding and playing bridge properly is as tough as understanding natural language, especially natural language where word play is the norm instead of the exception.

Yet again, hating on the Mac.

Yesterday, the Yahoo! fantasy football league run by my nephew Adam had its draft, and that was an enjoyable way to spend a couple hours. The Mutant Mercenaries drafted first, so I have last year's best running back Chris Johnson on my team, and I am also happy with several other picks. What I am not happy with is how the software that ran the draft worked on my Mac.

I used my usual browser Firefox, and of course it let me choose players and sort through the data in several ways, but there was a chat window that had no accompanying text box, so I could could read the stuff other people were writing, but could not comment myself. It's possible another Mac browser would have worked better, but this is just another way my Mac does not give me options that were readily available on even the most out of date PC that will connect to the Internet.

Grr.

p.s. I will keep a sidebar up on this blog showing the progress of the Mutant Mercenaries this year. My first game is two weekends from now against my nephew Adam's team, Condoms R 4 Sailors.

Don't buy a Mac.

Yes, I'm an old fart, but I'm a tech savvy old fart. Yes, I bought a Mac when it had 128k of RAM. Yes, I figured out that an external hard drive was NOT a luxury but a necessity. Even so, in the early 1980's, Macs were better than PCs and the ideas that moved the personal computer forward were almost all from Apple and later stolen by Microsoft.




That was then, this is now. Back then for example, the San Francisco 49ers were the best franchise in professional football. Nowadays, not so much. Things change.

Don't buy a Macintosh computer. I bought a Mac Mini earlier this year, and it's a mistake I can't afford to fix, so I'm stuck with it for awhile.

I expected less crashes, but I've already had several bad freeze-ups when using the Internet, so I don't see a big improvement in terms of software reliability or speed. The only plus so far is that I've had no issues with iTunes like I did on Windows based platforms.




The software isn't as good. For example, I was really getting good with the latest version of Excel on the PC before my old computer gave up the ghost. There are a LOT of useful features on the PC version of Excel the programmers at Microsoft decided users of Macs didn't need. I know that means people at Microsoft are being dicks, but if you own a Mac, you are the one who suffers.



The command key makes your life worse. If you buy software specific to the Mac, anything that will be Ctrl-C in other software will be command-C instead. So far, so good. The problem is that a lot of the software I use is designed to be used on the 'Net, and some Netware understands the command key and other Netware only understands the control key. The software I use to write my blog posts understands the command key in some instances and the control key in others. Really annoying and a time waster.



And whatever you do, don't buy a Magic Mouse. It looks cool, it means less wires to get tangled, I thought it was a win-win when I was at the Apple Store.

IT SUCKS UP BATTERIES WORSE THAN A WALKMAN USED TO.

I'm keeping track of battery usage with this piece of crap. The first set of batteries lasted exactly one month. The second pair crapped out this morning, so they lasted three weeks. Even when you put fresh batteries in, it will take a while before the computer reads the connection to the mouse consistently.

It pains me to write this. I had expected a much better experience than this with my new computer. I like the Mac ads and seriously dislike the PC/Microsoft ads going back for years if not decades.

I'm not a Mac. I'm not a PC. I'm a human being and more importantly in this case, I'm a human being who has written software and knows how it's supposed to work. Using a computer shouldn't this much of a struggle in 2010. A lot of people are realizing the "nice" tech companies like Apple and Google are becoming just as evil as Microsoft as they get bigger. Most people who whine about Apple are hating on the iPhone. Let me start a trend of hating on their computers, both the dumbed down software and and glitchy hardware.

Wednesday Math, Vol. 113: MergeSort

Last week, the topic was sorting lists quickly, a problem one runs into regularly in the field of computer science, and I showed the first pass of the algorithm QuickSort, which uses a general method known as divide and conquer. This week, I'll show all the steps of the MergeSort method, which also works on average at the rate of nlogn operations, much faster than the brute force methods that work at ½n² operations. A standard sorting method that works at the slower speed is to search the list to find the smallest thing and put it at the front of the list, then find the second smallest and put it in position #2, etc. until completed.

Let me give an example of MergeSort from my real life. I have two sets of graded papers from the same class and both sets are alphabetized. If I want to merge the two piles into one, I don't have to start all over again, I can use the work that's already been down alphabetizing them separately. The first paper on the merged list has to be either the top paper from list #1 or the top from list #2. I take that paper and put it on a new stack face down. Now I make the comparison between the new two papers on top of the stacks and put it face down on the new stack, again and again, until all the papers are on the new stack face down. Once one of the original stacks is depleted, there are no more comparisons to be made and I can put the rest of the remaining stack face down on top of the merged stack, turn it back face up and it is completely sorted.

If we start with a list that hasn't been sorted at all, our first step is to split it into sublists that are sorted from lowest to highest. I underlined in red those lists, and the algorithm is to start a new list if the thing on the list is less than the previous entry. It looks like this.

Sublist #1: 31 94

Sublist #2: 69

Sublist #3: 62

Sublist #4: 25

Sublist #5: 9 20

Sublist #6: 13

Sublist #7: 11 37

Sublist #8: 5

We then look for consecutive sublists that have only one thing, lists known as singletons. For example, if we take Sublists #2 through #4 we have 69 62 25. If we switch the order to 25 62 69, this is a new Sublist in ascending order 25 62 69. We now have six sublists instead of eight.

Sub list #1: 31 94

Sub list #2: 25 62 69

Sub list #3: 9 20

Sub list #4: 13

Sub list #5: 11 37

Sub list #6: 5

The algorithm now is to merge the adjacent lists, #1 with #2, #3 with #4, #5 with #6, etc. So after this pass, we should have exactly half as many lists as we did before if we had an even number of lists, and one more than half if there were an odd number of lists. We do that again with the new lists, effectively cutting the number of lists in half every time, which means we should be down to one list in relatively few passes. For example, let's say we had 10,000 things on our list and on our first pass we had 3,257 ascending sublists, which means on average we have about three things on a list before a small thing comes after a larger thing. Even with this very unordered mess, it should only take 12 passes before we are down to a single list, and every time we go through a single pass we make slightly less than 10,000 comparisons.

After pass 1: 1,629 sublists, about 10,000 total comparisons.

After pass 2: 815 sublists, about 20,000 total comparisons.

After pass 3: 408 sublists, about 30,000 total comparisons.

After pass 4: 204 sublists, about 40,000 total comparisons.

After pass 5: 102 sublists, about 50,000 total comparisons.

After pass 6: 51 sublists, about 60,000 total comparisons.

After pass 7: 26 sublists, about 70,000 total comparisons.

After pass 8: 13 sublists, about 80,000 total comparisons.

After pass 9: 7 sublists, about 90,000 total comparisons.

After pass 10: 4 sublists, about 100,000 total comparisons.

After pass 11: 2 sublists, about 110,000 total comparisons.

After pass 12: 1 list, about 120,000 total comparisons.

To be fair, there are the 10,000 comparisons we do the first time through on Pass 0, when we count the number of sublists, so this algorithm in this made up instance needs to go through about 130,000 comparisons. That seems like a lot to a human, but a computer will do that work in a blink of an eye, and it's a lot more elegant than the brute force method finding the smallest thing, then the next and the next, etc. Doing it that way will take fifty million comparisons, much slower than the few hundred thousand we need when doing MergeSort.

Yay, computer science!

Wednesday Math, Vol. 112: Quicksort

It's common though misleading to think of computers as smart. They are phenomenally good at two parts of the way we often measure intelligence, they move at crazy fast speeds and they never make a mistake, which is to say they will do what they are told. But a computer has no gift for original thought, so presented with a problem in a form it has never seen before, a computer program has no way of moving forward unless the programmer was clever enough to consider the possibility beforehand.

Computer science became a major branch of mathematics in the 20th Century, and it now rivals older parts of math like calculus in terms of importance. Much of the field involves finding ways to do tasks that are more efficient than the "common sense" approach a human might naturally take.

We don't think that much about our methods of doing simple tasks. For example, let's say I have a pile of quizzes on my desk and I want to sort them alphabetically. What method do I use? Personally, I sort the papers first into three piles, A through I, J through Q, R through Z, then I sort the piles of papers one by one, taking a quiz from the unsorted pile and putting it into its correct position in the sorted group of papers I hold in my hand. Once I sort A-I, I sort J-Q and put that sorted stack after, then sort R-Z and put that stack at the end. If there are n papers in the stack, this should take n²/6 + n comparison operations. In computer science, we would say this is a method that works in the order of n².

Coming up with faster ways to do things on a computer can pay big dividends. A British mathematician named Tony Hoare invented an algorithm called Quicksort, a method nearly no human would use for sorting on his or her own but which fits a computer's skills very well.

Let's start with a list of numbers we want to sort.

31, 94, 69, 62, 25, 9, 20, 13, 11, 37, 5

The idea of the first pass of Quicksort is to put 31 in its proper position on the list, to put everything bigger than 31 behind 31 and everything smaller than 31 in front of it.

We start count from the front and from the back simultaneously, marked with a green star and a red star. When we find a number smaller than 31 at the back we stop and look for numbers bigger than 31 near the front. In this case, we have a 94 at the front and a 5 at the back. Switch them. Move the green star forward and the red star backward. As you can see we make several switches, 69 for 11, 62 for 13, until the green star and red star are at the same position, the number 20. Since 20 is less than 31, we now switch those two. The list has been split into three parts: The numbers less than 31 in front, followed by 31 itself, followed by the numbers bigger than 31. This is called a divide and conquer strategy. We will do the same divide and conquer on the two smaller lists and on each split after that. Instead of having an algorithm that works in the order of n² operations, Quicksort should sort the list in about n × logn comparisons.

Here come the big payoffs. If the list has 100 things in it, a standard sorting method will make about 5,000 comparisons, while Quicksort will make about 800 comparisons. If the list had a million things in it, which is not an impossible size for a computer, sorting it "normally" will take about 500 billion comparisons, while Quicksort would expect to do only about 30 million comparisons. The time savings get better in terms of percentage as the lists get longer.

You might think of both 30 million and 500 billion as being numbers too large to deal with, but if you have a computer on your desk that is less than ten years old, it can probably perform many millions of such operations in a second, so the 30 million operation program might run in no more than a few seconds, while the 500 billion operation program could take hours to finish, maybe even half a day.

Yay, computer science! Yay, Tony Hoare! You are so cool, I won't even make any obvious jokes about your last name.

A newbie old timer's view of the Mac.

It's hard to believe that I've only been using the Mac for a single week now. It seems faster than my old PC and I'm getting used to a lot of the functions. But a week into the process, I find that the 2010 version of the Mac has forgotten a lot of the ideas that made the 1984 version good, unique and revolutionary.

OSX comes with a few art programs, most notably Preview and Photo Booth, but it does not have a simple to use program that updates the features of the original MacPaint. Oddly enough, Windows XP has exactly a program that fits that description called Paint, simply enough.

I used Paint on my PC all the time. Let's say, for some odd reason, I decided to write a post comparing Richard Nixon to Joe Namath. Since I like to have a picture with most posts, I would go to the web, grab a Namath picture, grab a Nixon picture, open up Paint and using no tools more clever than cut, paste, crop and resize, both for the picture and the canvas, I'd have a picture with Namath on the left and Nixon on the right in considerably less than fifteen minutes.

Nothing I've used on the Mac makes this an easy process. I tried downloading a few free software packages like Paintbrush and MacPaint X, but they don't do what I want them to do, or at least not easily.

Part of what makes these programs clumsy is they have gotten away from the original Macintosh focus, which was a very heavy emphasis, some would even say too heavy, on the great new toy of 1984, the mouse. The original Mac keyboard did not have arrow keys, so the users were forced to use the mouse. That may have been overboard, but the idea that the mouse could let users click and drag to move a window, resize it and perform other useful functions is what made it interesting and relatively easy to learn. Paint on the PC stays with that theme. The paint software on Mac or the free download stuff has forgotten that idea.

I would tell the people in charge of the software at Mac nowadays to get in contact with the ghost of Bill Atkinson, but that's not necessary. Bill Atkinson is still alive. Think about making a simple Paint program as good as the one on Windows XP a standard app. Think of your design template as a color version of the original MacPaint.

I don't want to go overboard in praise of Mr. Atkinson, genius that he his. I don't think we need an update of HyperCard, for instance. But I hate to say that the PC has the upper hand in terms of easy-to-use software in this instance, not because they have innovated more cleverly than Apple but because they remember Apple's history better than Apple does.

Abu Scooter FOR THE WIN.

Several of my nerdy friends sent ideas for how to solve my Mac problems, but the first guy to get it right is Abu Scooter, which means Father of Scooter for those of you with limited Arabic vocabulary. He made some suggestions and damned if they didn't work. This is the first post written on my shiny new Mac Mini.

Yay, nerds! The most helpful people on the planet if you ask nice.

This is a picture of Scooter, not his daddy. Also, though his blog is called The Ghost Grey Cat, these colors are washed out some. The real Scooter is not this pale. Getting pictures pulled off the Internets to work properly is going to be a learning curve.

Still, not to complain. My new computer works in all the important ways and life is good.

To reiterate. Yay, nerds!

More troubles with this whole "insanely easy to use" concept.

So what's the worst thing that can happen when your brand new computer doesn't work and the nice people on the customer support line tell you to take it into the shop?

Well, I suppose the worst thing that could happen is an 8.8 earthquake, but given that I live in California and not Chile, the worst thing that can happen is to take it into the shop and everything works just fine, then to take it back home and it still doesn't work.

AAAAAAARRRRRRRGGH, as an opponent of Spider-Man might say.

I'm open to suggestions. Taking the computer out and shooting it is not a suggestion I am willing to entertain, because I'd have to buy a gun at considerable expense, and then I'd be out the price of the gun, the bullets and the computer. And then there's the whole waiting period for a firearm... No. Taking the computer out and shooting it is not on the list.

Any other suggestions?

Moving forward in a backward sort of way.

So I went out yesterday and bought my first new computer in several decades. I was worried about how many chowderheads were claiming that Windows 7 was their idea, so I decided to buy a computer from a company that admits they write their own operating system.

I got the Mac Mini from the Apple Store in Emeryville. The purchasing process was fairly straightforward and it took me less than a half hour to set the thing up. Transferring over data took a little longer and currently the Mac Mini doesn't recognize the modem because it doesn't have the Earthlink software. I'll make a call today to get that situation rectified.



When I say I bought my first new computer in decades, it's not like I've still been using something from the Stone Age all this time. Friends have bought me computers or given me hand me downs, and the laptop I'm using to write this post was part of my pay for writing the Pascal's Triangle website about six years ago.

I'm not sure it's the most recent computer purchase I made, but the last computer I distinctly remember buying was a Mac 128K back in 1984. I probably spent $2,000 for it, and then I had to pony up for a second floppy drive port. Remember when companies thought one floppy drive was enough external memory, or 128 K of RAM was enough internal memory?

If you do, you are both old and a nerd. I don't mean to be harsh, but there it is.

I will keep you posted on my first impressions of the modern day Mac. I am full of fun facts about it already. For instance, did you realize that the screen is now separate from the rest of the machine and it's in color? Golly, it's like living in the future.

Sorry, technical difficulties. Please cry again later.

My computer is still in the shop, and there it will remain. They tell me they can't fix it but they can get the data onto a CD. The problem is, they have lied to me before. I'll believe it when I see it.

I won't update this blog until the new computer is in place, unless there's something that can't wait. I will keep updating It's News 2 Them™, because it's easier.

I think I'm about to become a Mac user again. The last one I bought was 25 years ago, and I hear they've made some improvements.

If I were to pray to the God of Machines...

today would be as good a day as any and better than most.

Friday afternoon, my computer crashed. I usually don't turn the machine off, just put it in sleep mode, but Friday morning I shut it down and when I came home from class, it wouldn't turn back on. I took it to the shop and they said they'd have a look at it, but some of their equipment was on the fritz, so there won't be any word until today.

The good news is that the data appears to be retrievable, and if the problem is just the power supply the fix will be fairly easy.

If not, I may be in the market for a new computer. I haven't bought a computer in probably 20 years, maybe more. The one I used back in the 1990's was a gift from my friend Kevin; it still works for writing homework and quizzes, but is way too slow to hook up to the Internet today. My upgrade was a laptop I got as part of my payment for writing the Pascal's Triangle website, and that's what I'm using to write this post. It's slow and there are keys that don't work, like the Ctrl key, which slows work down considerably. The computer in the shop was a second hand computer from my friend Alan, a major upgrade over the seven year old laptop. I'm thinking about what I will buy if the news is bad today, but I'll wait for the verdict before deciding my next step.

As you can see, the illustration is from a O-L-D science fiction story about a computer-reliant alien race. Those wacky SF writers! Where did they get their crazy ideas? A race reliant on computers indeed! It sure would suck to be them.