Archive for the 'Computing' Category
A recent slashdot.org thread discussed how a programmer at Microsoft incorrectly implemented a random shuffle algorithm. The discussion was prompted by an article Rob Weir wrote in which he presented a comprehensive analysis of the problem and provided a correct algorithm. Along the way, he named the botched implementation the “Microsoft shuffle.”
The following points are salient:
- One can use Pearson’s Chi-squared test to determine if the results are non-random. In Weir’s analysis, the probability that the results were random (the probability that the null hypothesis was true) was p < 2.2e–16, given 10,000 repetitions of the algorithm.
- Random shuffle algorithms are so commonly used that this is often an interview question for a programmer.
- The Fisher-Yates shuffle is an excellent random shuffle algorithm of time complexity O(n).
- The programmer who implemented the Microsoft shuffle did not understand how a sorting algorithm works.
As usual with discussions on slashdot, there were quite a few posters who didn’t understand the problem and why it required an accurate solution.
February 28 2010 | Computing | 2 Comments »
Yesterday Apple Inc. introduced its new tablet computer, the iPad. The best summary of the iPad that I have read is, not surprisingly, written by Adam Engst at tidbits.com. I provide here notes about the features that interest me.
The iPad is a computer for content consumers, not content creators. It is ideal for casual web browsing, watching television and movies, reading digital books, and playing games. The touted battery life of 10 hours, although undoubtedly exaggerated, is still long enough for a coast-to-coast flight. (It is not so ideal for listening to music, because I don’t have a pair of pants with pockets wide enough to hold it, unlike an iPod.)
For content creators, Apple has created new versions of its iWork suite for the creation of text-based documents (Pages), spreadsheets (Numbers), and slide presentations (Keynote). I am interested in learning how well this actually works without a keyboard and mouse.
The iPad has several shortcomings. Surprisingly, it has no camera. Other commentators have wondered whether Steve Jobs couldn’t decide where the camera should be located. The iPad really needs two cameras, one facing toward the user, for video conferencing, and one on the back for taking stills and videos.
The iPad operating system, which seems to be a variant of the iPhone OS, doesn’t allow multitasking. This is an annoyance, but I think we can anticipate that a future version of the OS will overcome this limitation.
Like the iPhone and the iPod touch, the iPad doesn’t support Adobe Flash. This means there is some material on the web that we won’t be able to view on an iPad. I’m not a big fan of Flash, because I hate how processor-intensive Flash is. If I want to bog down my old PowerBook G4, I just need to open two or three web pages with Flash animations.
I plan to buy one for use at home and to take with me when I travel. I already use my iPod touch as much as or more than my MacBook Pro when I’m at home. Other than listening to music and podcasts, I use it to check the weather, Facebook, Twitter, and email, watch movies, and read books. Movie watching and book reading will be more pleasant on the iPad. One thing I’m eager to test is whether I can read PDFs of scientific papers on an iPad.
January 28 2010 | Computing | No Comments »
Yesterday I finished reinstalling Vista Business on my MacBook Pro. I say finished, because the reinstallation required two days. I needed to reinstall Vista after I had updated Mac OS X to Snow Leopard (10.6), at which time I had wiped out my old Vista partition, which at 25 GB was too small.
I used Boot Camp Assistant to create a 32-GB partition and reboot my MacBook Pro from the Vista installation DVD. I installed Vista Business from the DVD and then began applying software updates. I should have counted these, but I estimate there were six separate operating system updates that I estimate required six hours to apply. The first update applied 93 individual patches to my system, and I let this run while I slept. If I remember correctly, it reported that it took 90 minutes to complete the update. Later updates updated Vista to SP1 (Service Pack 1) and SP2 (Service Pack 2). (I discovered that I couldn’t get the SP2 and later updates until I remembered to activate Vista.) One of the updates installed Internet Explorer 8; that one took a long time because I didn’t realize that it had displayed a dialog window for accepting the EULA. The problem was that the dialog was hidden under the main update window, where I couldn’t see it.
My question at this point is, why can’t Microsoft combine all these updates into a single update? Why do I have to install SP1 before I can install SP2? Why can’t SP2 contain all the changes already in SP1?
After installing Vista, I installed Office 2007 Professional, after which at least two more updates were required to bring it up to date, taking another two hours.
I want to contrast that experience to what happened last fall when I wiped clean my old PowerBook G4 and performed a fresh install of Leopard (Mac OS X 10.5). My install disk installed OS X 10.5 (which you would think would be called version 10.5.0, but Apple doesn’t begin adding the third numeric field until the first revision is released). When I ran software update, there was a single (massive) update that rolled all changes from 10.5 to 10.5.7 into a single update.
So the Microsoft Experience was six hours of time spent reinstalling Vista, and the Apple Experience was two hours of time spent reinstalling OS X 10.5. If I were doing this for a living, I would bill $75 per hour for my time — $450 for reinstalling Vista, $150 for reinstalling Leopard. The Microsoft Experience cost me an extra four hours of my time or $300 equivalent. This is the primary reason I prefer OS X over Vista — it is less expensive to install and maintain.
Note: What I really wanted to do was install Windows 7, but Apple has been slow in releasing the drivers necessary for full support. Having originally promised the new drivers by the end of 2009, Apple now provides a much more vague estimate of when the drivers will be available.
January 10 2010 | Computing | 1 Comment »
For the past two or three weeks, I’ve been reading Neal Stephenson’s Cryptonomicon, a novel published in 1999. Much of the story in the novel concerns cryptography, and page 480 contains a Perl script that can be used to encrypt and decrypt messages using the Solitaire cryptosystem.
As published in the novel, the Perl script is gibberish, impossible to read and understand. Fortunately, the “verbose version” of the script is available on Bruce Schneier’s web site at www.schneier.com/code/sol.pl. Bruce Schneier provides an explanation of the Solitaire Encryption System at www.schneier.com/solitaire.html. And Neal Stephenson himself discusses the novel and the Perl script at web.mac.com/nealstephenson/Neal_Stephensons_Site/cypherFAQ.html.
Cryptonomicon is a brilliant novel, and it reminds me in many ways of Gravity’s Rainbow by Thomas Pynchon, one of my favorite books. It is a book I know I’ll have to read more than once, because I’m certain I’m missing important clues and subtexts in the story that will become apparent only on a rereading.
January 09 2010 | Books and Computing | No Comments »
Fourteen months ago I traded in my old iPod mini for a new 8-GB iPod touch. I think the price at the time was about $230, but I got a 10% discount for exchanging the old iPod mini.
Six weeks later, I dropped the iPod touch from waist height onto brick pavement and broke it; the impact created a dent in the metal back and apparently crushed some of the electronic components inside. (These things are surprisingly delicate.) I took it to the Apple store on Boylston Street in Boston and asked if they could fix it. The answer was no, but they offered me a refurbished unit in exchange for the broken unit and a little under $130. I have been using the refurbished iPod for over a year now.
Since I live in an urban area, I usually have wifi connectivity. (For example, when I’m waiting for the bus in Kendall Square, I get a good connection to MIT Guest wifi.) This means I don’t need to buy a smart phone such as the iPhone; I get nearly iPhone-equivalent functionality from two devices, my minimal cell phone ($40 a month with Verizon) and my iPod touch, saving me roughly $40 per month that I can spend on books or music.
I was slow to take advantage of all of the iPod touch’s capabilities, using it initially for listening to music, podcasts, and audiobooks. I usually commute to work by walking, a 45-minute trip each way. I can listen to two audiobooks per month plus quite a few podcasts during my commuting time.
The first apps I added were news-, information-, and book-related: New York Times, Bloomberg, Yahoo Finance, WeatherBug Elite, Stanza, and Shakespeare Pro. I find that the iPod touch makes for a great electronic book reader (although I still haven’t found a good app for reading PDFs of research papers).
Lately I’ve been taking advantage of the iPod touch’s abilities to act as a small pocket computer. I purchased the American Heritage Deluxe dictionary app ($35), and I feel like I’ve already gotten my money’s worth for that app alone because now I have an unabridged dictionary in my pocket and I use it all the time. I also installed the Facebook, LinkedIn, TweetDeck, and WordPress apps for managing my Web 2.0 presence. And recently I set up two new email addresses that I use primarily from the iPod touch with the Mail app.
Lately, I’ve begun buying movies and TV shows from the iTunes store. The TV shows are, in my opinion, an incredible bargain. I bought the first season (twelve episodes, 10 hours) of HBO’s Rome for only $20. Recently, I taught myself how to use Handbreak and VLC to copy my DVDs to mpeg files formatted for the iPod touch.
The result is that my little 8-GB iPod touch is feeling cramped for space. First of all, the 8-GB iPod touch actually has 7.66 GB of storage capacity. (Is the remaining 0.34 GB used for the operating system and included apps?) Second, I have almost 2 GB of apps installed, the dictionary being the largest. Third, I like to carry one or two TV shows or a movie with me, and each of these is roughly 0.6 GB in size. Fourth and finally, I like to carry plenty of music and audiobooks.
Consequently, I’m ready to buy a new iPod touch. The bigger models have 32 GB and 64 GB of storage and list for $300 and $400, respectively. However, rumor has it that the next model of the iPod touch will include a camera for stills and video, and I would find a camera quite useful. And rumor has it that Apple is about to announce its new tablet computer, allegedly named the iSlate. So I’ve decided to bide my time to see what Apple might announce in the next few months.
January 03 2010 | Computing | 1 Comment »
I put off upgrading the operating system on my MacBook Pro from Leopard (Mac OS X 10.5) to Snow Leopard (Mac OS X 10.6) until I had free time over the holidays. These are my brief notes about how I performed the upgrade.
I needed to clean up the cruft that had accumulated in my system, and I needed to repartition my internal hard drive to remove a Windows partition and expand the partition devoted to OS X to the entire drive. Because repartitioning my internal drive was going to wipe out all data, I wanted to be very careful in having a complete copy of my old system before performing the upgrade.
I followed the upgrade instructions provided in Take Control of Upgrading to Snow Leopard, written by Joe Kissell. This e-book is well worth the $10 because it provides detailed advice on every step of upgrading to Snow Leopard.
In brief, I performed the following steps:
- I cleaned up my directories and files.
- I removed software that I no longer use.
- I made a record on my backup computer of all license keys in case something went wrong and I needed to completely reinstall my applications.
- I made a complete bootable backup of my entire internal drive using Carbon Copy Cloner, and I tested the backup by booting from it.
- I booted my MacBook Pro from the install DVD and used Disk Utility from the DVD to remove the old partitions and create a partition spanning the entire internal drive.
- I installed Snow Leopard.
- I used the installer’s Migration Assistant to transfer my old applications and files from the backup drive.
- I ran Software Update to update the system to OS X 10.6.2.
- I created a fresh backup from Snow Leopard using Time Machine, preserving my Leopard backup for the time being on a separate partition of my external drive.
The result was an upgrade to Snow Leopard that is, so far, working with zero problems.
My biggest difficulty was in getting a complete backup of my internal drive onto my external drive. I have a Western Digital My Passport Studio 320 GB external drive, and during the weeks I have owned the drive, I have experienced many failures in the backup process where the computer loses its connection with the external drive. Yesterday, I experienced this problem using either the FireWire 800 or the FireWire 400 cable that came with the drive. I decided to try the USB 2.0 cable, and that has worked well so far, with no noticeable loss in speed writing to the disk. In case the problem was caused by bad sectors on the external drive, I erased the 120-GB partition I had created on the drive by writing zeros once using Disk Utility. If I remember correctly, this step will identify bad sectors on the drive and cause the drive to mark them not to be used.
Carbon Copy Cloner was so useful that I made a $25 contribution.
December 28 2009 | Computing | No Comments »
I own a Western Digital My Passport Studio 320 GB external hard drive, which I purchased a few weeks ago as a backup drive for my MacBook Pro. The drive came with three cables, a FireWire 800 cable, a FireWire 400 cable, and a USB cable. The drive obtains its power through the cable from the FireWire or USB bus. CNET has a review of an older model of this drive.
I used Carbon Copy Cloner to create a complete backup of my MacBook Pro to the external drive. Unlike Apple’s Time Machine, Carbon Copy Cloner creates a bootable backup. I checked that I could boot my Mac from the external drive by restarting while holding down the option key. However, my external drive did not appear in the list of bootable drives. Perplexed, I performed a google search to see if other people had experienced this problem, and I found this solution at macosxhints.com.
The solution is to shut down my MacBook Pro and unplug the external drive, then boot while holding down the option key. Once the Mac presents the list of available boot drives, I plug in my external drive, whereupon the Mac adds the external drive to the list of boot drives. I use the arrow keys to select the drive and press the return key to boot from that drive.
After booting, I verified that my external drive had been used as the boot drive by checking that special icons were used for my System, Applications, and other folders. (Generic folder icons are used for these folders when they are present on a drive that was not the boot drive.)
December 27 2009 | Computing | No Comments »
Next »
