linear time sorting, or, why remedial courses are not just for dullards

I've been listening to an introductory course on algorithms from MIT OpenCourseware. Today I learned that it is possible to sort integers in linear time!! The technique I learned this morning, counting sort, only works for a particular kind of input: a list of n integers in the range 0..k. (Or any known range; map it to 0..k for convenience.) If k is much smaller than n, you can sort in Θ(n + k). That's linear time, people!
I'm 33, an Ivy League graduate, and I just discovered it's possible to sort in linear time! Where was I in (ahem) 1998 when Roberto Tamassia was teaching this? Well, it looks like this year's equivalent class at Brown (now cs0160, then cs21) doesn't counting sort in the lecture notes. Or maybe I slept through it; I was a sophomore.
My point: reviewing a subject you used to know, from a different perspective and with more experience than you had at 18, can blow your mind with mind-blowing information that you might have missed the first time through.
WE CAN SORT INTEGERS IN LINEAR TIME! (for sets of integers meeting the requirement above.)


in praise of display calibration

I've been watching tv shows and dvd's on my giant LCD monitor, and wondering why it's so dark and moody and why everyone looks feverish. Somehow I convinced myself that I just shouldn't worry about it -- absolutely ridiculous when the whole point of a giant LCD display is fantastic picture quality. So here's what finally hit me, while I'm snuggled up with the sniffles: maybe calibrating my display would help. Boom! It just so happens that Mac OS X (Leopard baby!) has an expert-mode display calibration that crafts a custom gamma profile from about a dozen data points provided by the most advanced optics on the planet: my eyes.
Now people on Studio 60 have normal skin tone and it doesn't look moody so much as, well, ebullient. Which is exactly what Aaron Sorkin and Thomas Schlamme were going for, I'm pretty sure.


naive users suffer

Yesterday I wrote about discovering that my mac became distressingly slow when paired with some peripherals I hadn't used with that particular machine before. I investigated and eventually deduced that the problem was the version of USB supported by my machine's hardware. A naive user, or even a moderately powerful software user, would not have a chance of figuring out a bus bandwidth mismatch. To determine that I only had USB 1.0 support, I looked at Apple's tech specs for this powerbook, which is in itself a challenge, because the powerbooks are differentiated by parenthetical keywords like "DVI" and "Gigabit Ethernet". Again, if I'm a naive user, there's no way I could figure out which one I have. Consulting the tech specs, I found that I had two 12 Mbps USB ports. When I do the math, that sounds slow for disk access: 1 gig = 1000 Mb = around 80 seconds if everything is cruising at top speed -- bleck. But it didn't say "USB 1.0" anywhere. Tech specs of later powerbooks explicitly said USB 2.0. Combined with the observed performance problems, I concluded that the problem was the USB version.
There's no way a naive user could have figured this out. Even if they took the machine into a genius bar, they probably would have left the peripherals home, and the genius would just say, "it's operating as well as we could expect for a machine this old; if you want it faster you'd better buy a new machine."
I'm not saying I'm such a whiz with diagnosing hardware issues; far from it! My point is that many people are subject to sub-optimal user experiences because of subtle hardware and software incompatibilities.
All of which I suppose points to a more general idea: naive users of any technology or discipline suffer from their lack of expertise. My car could be tuned better; my taxes could be lower; my house could be heated more efficiently; my cel phone probably has superpowers it's hiding from me. I'm not sure what to do about this, though. Learn everything about everything? Okay! Good thing I've got another 60 years to live.


slowed to a crawl by I/O

I'm using my PowerBook G4 Titanium as my main machine for a while -- hopefully not long, because this is insanely slow. I'm trying to understand how it was wonderful five years ago, and now painfully slow, when I'm just running a browser and iTunes and gmail notifier and not even a terminal. I figured it out: the I/O is making it seem hellaciously slow. I used to have a FireWire iPod; now I'm using a USB iPod (thank you, Marshall). I used to be satisfied with my built-in 30 gig hard disk; now I'm using an external half-terabyte disk. Here's the kicker: this machine doesn't support USB 2! It was built back when firewire seemed like it was going to win. Firewire lost, though, at least for commodity consumer peripherals, and I'm hamstrung by slow IO.
I'm picking out my next mac, and I'm having a hell of a time deciding between almost all the form factors. I need one now, can't wait until after Macworld, so buying a monster macbook pro seems like a bad idea; I'll just be kicking myself when the prices drop and a new mindblower comes out in two weeks. The iMacs have the combination of tons more computing power and disk space for less money, but I've already got a huge wonderful display. (Hmm, could I use an iMac with the built-in display and my widescreen external display? Mmm, tasty!) And of course, I adore the idea of a Mac Pro, but I got one of those a few years ago and immediately discovered I would rather have a laptop. The one that I can totally rule out is the mini; 2GB ram just isn't how I roll. Probably the thing to do is to get a Mac Pro now, and plan on getting the rumored new subnotebook as my next planned purchase. Buying components instead of all-in-one's is the most flexible, but least portable, solution.


get your backstreet boys off my network!

If you're going to use a neighbor's open wifi connection, it's probably not a great idea to share your iTunes library. I opened my network a few days ago because I was having trouble getting my Powerbook G4 online; I couldn't get it to connect using any of the password-based security schemes. I thought I turned on MAC filtering, but the netgear router adminstration page was a bit confusing -- it shows a "Wireless Card Access List" but doesn't actually do MAC address filtering unless you've checked a box above the access list. So I thought I had a closed network, but I was wrong. Fine, I deserve to have neighbors find and share my connection.
And then I launched iTunes and saw "Ernesto's LimeWire Library" under the "shared libraries" tag. (Not really his name.) Bwahhahha! Apparently Ernesto found my open network! I bet he had no idea that he was sharing his music.
I returned to the netgear router admin, actually turned on MAC addr filtering, and bye-bye Ernesto! Whee! Now he's looking around going, damn, what happened to that open wifi?
This is a nice feeling -- I did something kind of mean but I had every right to do it. That is so rare!

Page 1 ... 4 5 6 7 8 ... 51 Next 5 Entries »