Insert Title Here

Since we moved into our new place in July 2007, we’ve had problems with the wireless network. We have a slightly unorthodox setup with the cable modem and wireless router in the back room with my desktop and a wireless bridge/repeater in the living room next to the TV. The repeater is necessary because the walls are made of something totally opaque to radio signals, and the signal from the router will not reach the front of the house, where we use our laptops.

The problem has been that, with the walls and interference from the 10 other wireless networks near our house, even the repeater doesn’t get enough signal to reliably connect to the Internet. Using our laptops in the living room has always been a frustrating experience, with frequent dropouts and low throughput.

I have been thinking about how to fix this for a long time. One option would have been to run an Ethernet cable from the back room to the living room, but that would be a pain in the ass and would also look terrible. I considered having an electrician do the work, but decided it would be too expensive.

Another option is powerline Ethernet. You buy a pair of adapters that plug into normal power jacks and route network traffic over them. A great idea in theory, but in practice they are subject to interference from appliances on the same circuit and poor wiring, both of which I’m sure we have in this house.

While Googling the other day, I came across an article describing Ethernet over coax. These adapters route a network signal over the same coaxial cable used for television signals. There is usually no interference on those cables, and in our house there happen to be coax jacks in both rooms where we need network connectivity. It sounded like a great solution, except no one seemed to be selling the devices. Searches at Amazon and Newegg turned up nothing.

Further Googling revealed an unlikely source for these devices: Motorola NIM100 boxes previously used in Verizon FIOS installs. Apparently, the FIOS set-top boxes use Ethernet over coax to download guide data and on-demand shows. Early versions of the boxes did not have the feature built it, and you had to connect a separate box (the NIM100) to get it to work. This changed sometime in the last two years, and the old Motorola NIM100s have flooded Ebay. They can be had for roughly $30 apiece, cheaper than a powerline Ethernet adapter. I purchased a pair, which arrived today.

Everything is set up and working, and I’m seeing a solid 25 Mbits across the coax link. Other people report throughput close to 100 Mbits, so I might play with the configuration a bit, but overall I’m very pleased with the performance. It’s a major improvement just to have a reliable signal for our laptops.

I’ve been waiting for the new Ubuntu release to install on my new T400 laptop. Because the T400 is so new, the previous Ubuntu and Fedora releases did not support the wireless card or the integrated graphics adapter. I also decided to try Ubuntu this time around after a brief experience with it in a virtual machine. I found Ubuntu handles restricted software much better than Fedora; nearly everything you could want (Sun Java, Adobe Flash, NVIDIA drivers, etc.) is available from a built-in repository and is properly packaged. No more futzing around with Livna or JPackage or whatever.

So I spent the past couple of days installing Ubuntu 8.10. This page on Thinkwiki has been a great help in getting everything working.

Here are some problems and solutions I encountered:

• Problem: Thinkpads have a recovery partition that can be accessed with the Thinkvantage button on boot. This recovery partition can be used to recover to the factory state, run diagnostics, etc. However, if you allow GRUB to overwrite the MBR to install the bootloader, you can no longer access the recovery partition with the Thinkvantage button.

  Solution: Follow these directions on ThinkWiki to install the GRUB bootloader on the boot partition (*not* on the MBR), then modify the Windows bootloader to boot Linux directly. With Windows Vista, the process for adding an entry to the boot menu has changed. Follow these directions to add a Linux entry to the boot menu. Don’t follow the main directions; look at Falcon006’s second comment for an example of exactly how to do this.

• Problem: Ubuntu does not provide a way to automatically partition the free space on a drive and use it for Ubuntu. There is a menu option that sounds like it is supposed to do that, but the graphic during the installer indicates that it will overwrite the Windows partition. I think the graphic is wrong, but I didn’t want to take the chance.

  Solution: Partition the drive manually. You want to create three partitions: /boot, /, and swap. First, create the /boot partition. Set the file system to ext3, size to 200 MB, and type to primary. Second, create the / partition. Type can be logical, and size can be whatever you want. Finally, create the swap partition. This can also be a logical partition, and the size should be somewhere between your RAM size and twice your RAM size. If you want to use hibernate, it needs to be at least your RAM size.

• Problem: The screen resolution is set too low initially, and the Change Screen Resolution tool does not allow the LCD’s native resolution (1440×900). The xorg.conf file doesn’t seem to be used anymore, so you can’t change this there.

  Solution: This is related to dual monitor outputs, even when are you using only one monitor. I believe the default is to mirror displays, and the VGA output is detected as not supporting the 1440×900 resolution. If you use the Change Screen Resolution tool to disable the second monitor (make sure Mirror Displays is unchecked first), 1440×900 will become available. This will fix the problem in your user account, but I still haven’t figured out how to fix this in the login screen.

• Problem: System does not wake up from sleep. It goes to sleep, but when you wake it up it hangs and then reboots.

  Solution: This appears to be a concurrency bug. Petri K from Ubuntu Forums suggests a workaround, which works for me.

I will continue to update this list as I come across further problems and solutions.

I received my new Lenovo T400 laptop a few days ago, and I’ve been setting it up for the past few days. I have some first impressions to share.

First, this laptop is solid. It feels very sturdy, and the keyboard has that legendary Thinkpad feel. There have been some reports that the keyboard flexes more than previous models, but I can’t tell any difference compared to Catherine’s T61. It feels more solid than my previous Dell Inspiron 700m.

This is a 14.1″ laptop, and I chose this size because it’s a good compromise between portability and usability. I think it was a good choice. With my 6-cell battery, the T400 weighs 5 1/4 lbs., and I find it to be a reasonable weight for carrying around. I do wish the 6-cell battery didn’t extend so far from the back of the machine, but after suffering through 4 years with a laptop whose battery lasted less than 2 hours, I’ll take that tradeoff for the reported 5-6 hour battery life.

With previous computers, I’ve always removed all the utilities installed by the manufacturer. But in this case Lenovo has done a good job with their utilities. Their power management utility is especially impressive. It lets you set power options at a much finer grain than Windows. It also provides an almost excessive amount of information about your battery, including allowing you to set specific charge thresholds (did you know that lithium-ion batteries degrade faster at 100% charge than at 40%?) to extend battery life. After quite a bit of research on various Lenovo forums, I ended up keeping most of the Lenovo utilities.

One minor complaint I have is that current Linux distributions don’t support some of the hardware on this laptop, particularly the Intel X4500 integrated graphics and the Intel Wifi Link 5100 wireless card. This isn’t Lenovo’s fault: the T400 is built on the brand-new Centrino 2 platform, and these Linux distributions had been released before Centrino 2 came out. Word on the street is that the current alphas of Ubuntu and Fedora already support the new hardware. I’ll just have to wait until those alphas become the final releases in a few months.

So far I’m most impressed with the design and attention to detail in this machine. It has many nice proprietary features that I think I will actually use. It’s a very nice machine, and I’m excited to use it for real work.

After many months of waffling, I finally pulled the trigger on a new computer. The surprise is that I’ve gone with a laptop as my primary machine instead of a desktop. I thought about it a bit and realized that I use my laptop most of the time at home, sitting on the couch and browsing the Internet. I’ve also been looking enviously at Catherine’s new Lenovo T61 laptop that replaced her broken T40. I’ve been watching prices, and recently I found I could get a solid business-class Lenovo T400 laptop for a very reasonable price. So I pulled the trigger and ordered one last week.

Now I am very impatiently checking my order status, hoping it will ship soon. I am very excited to be moving into the brave new world of dual-cores, LED-backlit screens, and Windows Vista. I’m also planning to install Fedora Linux on it, though I might wait until version 10 is released in November.

A few years ago, I bought a copy of Motorola Phone Tools so I could copy photos and MP3s to my phone. At the time, I was able to update the software with the built-in update functionality all the way to the latest version. I recently reformatted my computer and had to reinstall the phone software, and the update functionality no longer worked. I emailed Motorola to see if they could send me a patch. Here was their reply:

The reason these older versions of Motorola Phone Tools aren’t able to update any longer is because we have noticed that a large number of updates coming from these versions haven’t been sold by Motorola since 2004-2005. We recommend you to contact our sales department, so you may purchase a new legitimate copy of Motorola Phone Tools.

So basically they accused me of pirating their software. Great, except I remember researching it at the time, noticing that it was available for download everywhere, yet I specifically purchased a legitimate copy because I would have felt bad downloading it. I bought it from Amazon, so I can still print a receipt from their website. I exported the receipt to PDF and attached it to my reply, saying I had already purchased that copy and had no interest in purchasing another one. I also said that I did not appreciate being accused of stealing. We’ll see what happens now.

This is the kind of thing that pushes people to pirate software. I legitimately purchased the thing, and they won’t let me update. Yet I could easily go to a torrent site and download the latest version. Nice job, Motorola.

Update: They gave me a download of the latest version. Yay.

Recently I’ve become addicted to solving math problems at Project Euler. Yes, I know this is incredibly dorky, but I am a computer science grad student, and it is probably a good sign that I am doing math problems in my spare time.

Project Euler keeps a list of math problems to which there is a numeric solution. You register on the web site, and then you can submit an answer for a problem. If your answer is correct, then you are given access to an official solution and also a forum where others have posted their solutions.

The problems get increasingly difficult, from (relatively) simple questions like “What is the largest prime factor of the number 600851475143 ?” (solved by brute-force factorization) to much more difficult problems.

I got hooked on this by a post at a programming forum I frequent. The poster could not find a solution to problem 185 and was looking for suggestions. His initial idea was to basically try guess-and-check with some hill climbing to look for local solutions. I didn’t think that would work because the search space is too large (10^16). My idea was to use the hints to construct the number.

Let’s look at the hints. Given the hint with 0 digits correct, you can eliminate each of those digits from the possible answers. Now look at a hint with 1 digit correct. We don’t know which digit is correct, so let’s assume it’s the first. Then we know the first digit and can eliminate another possible digit for the remaining digits. Now look at the next hing. Again, assume the first digit is correct. If it is the same as the first one, then this is an OK guess and we can continue. If not, then we assume the second digit is the correct one and continue our search.

So basically we want to construct a search tree using all the hints, looking for a consistent set of assumptions about which digits in each hint are correct. The depth of the tree is the number of hints given, and the fan-out depends on the number correct in each hint — if n is the number correct, then the fan out for that level is 16 choose n. We short circuit a branch if we encounter an inconsistent assumption. If we ever reach a leaf node and have a fully constrained assumption, then that should be our answer.

The worst-case running time of this algorithm is horrendous because of the fan out. The fan-out for the sample problem can be as bad as 16 choose 3 = 560, so if you actually have to explore every path, you’re looking at a running time of at worst 560^22 steps. In reality it’s not nearly that bad, partly because not every hint causes a fan-out of 560, but mostly because you can skip large parts of the tree because they lead to inconsistent assumptions early on.

I coded this algorithm up in Java, but not without some difficulty. Specifically, I don’t think I chose good representations for my guesses and for my the combinations of possible correct digits. Regardless, my program chugged away for 4 hours and finally spit out the correct answer. Success!

There’s a lot of optimization I could do. One thing I didn’t exploit was ordering the hints to reduce the search space. I tried to do this by ordering the hints from least to most digits correct, but I think a better strategy would be to choose the hint that constrains the problem the most. That way you will have to explore less of the lower part of the tree.

I’ve been thinking about this problem for several days now, and I’m very pleased to have solved it. I’ll be working on more Project Euler problems, and if I come across any particularly interesting ones, I will post my solution here.

I thought I would document the process of installing Fedora Core 7 on my Dell Inspiron 700m laptop. I’ve installed it several times on desktops, but this was my first time setting it up on a laptop.

1. Enable the NetworkManager and NetworkManagerDispatcher services. These allow you to choose which wireless network you want to connect to, enter encryption keys, etc. You can do this by typing “setup” at the command line and enabling the services through the interface. Or you can follow these instructions.
2. Set the screen resolution to the native 1280×800. First, go into the display settings and change your display type to generic LCD 1280×800. Then switch X from the “i810″ driver to the experimental “intel” drive. You can do this in gnome-config-display or by editing xorg.conf. Other people suggest using 915resolution with the i810 driver instead, but the i810 driver doesn’t work with suspend, which is important in a laptop IMO.
3. I find Compiz too slow on this particular machine, but it does work. You can enable it from the Desktop Effects control panel in the Gnome menus.
4. Set it so that you don’t have to enter a keyring password every time you boot and connect to an encrypted wireless network. Instructions here.
5. I’m seeing lots of error messages from NetworkManager about “Error getting killswitch power.” These are clogging up my log files, and I know that my laptop doesn’t support the kill switch. Do a “locate rfkill” and you should find a file with a “.fdi” extension and also “dell” in the filename. Rename this with a “.bak” extension, reboot, and no more messages. As far as I can tell, this doesn’t hurt anything.

I will keep adding to this list as I come across other problems/solutions.

I just installed a 120 GB hard drive in my laptop, replacing the old 30 GB one. I was kind of wary of operating on my laptop, since I’ve never done a laptop upgrade before, but this was probably the easiest upgrade I’ve ever done. Dell did a good design job with my machine, an Inspiron 700m, and the hard drive was easily accessible under a panel. It even had a pull tab to pop the old drive out. Very well thought out and easy to upgrade.

My goal with this upgrade was to allow for a Linux partition on that machine, so I can use it for working remotely. I’ve created a 75 GB Windows partition and a 40 GB Linux partition. I’ve only installed Windows so far, but tomorrow I’ll probably put Fedora Core 7 on the other partition.

I have no business building a new computer right now. My old one works fine for everything I need it for, and I even recently added a 500 GB hard drive so that I could use it as a DVR. Really, if I were to get a new machine, it would make more sense to have it at work, where I could actually use the extra performance of a dual core. On the other hand, my computer is 4 years old (around 100 in computer years), and these Core 2 Duos people are getting at work make me envious.

So, just as an exercise, here is what I would buy if I were building today. Again, just an exercise, I have no intention of buying a new computer.

• Intel Core 2 Duo E6750 2.66 GHz – $212
• Intel DP35DP motherboard – $112
• Crucial 2 GB DDR2-800 RAM – $85
• EVGA GeForce 8600GTS video card – $145
• Pioneer DVD burner, SATA interface – $34
• Cooler Master Centurion 5 case – $50
• Fortron 450W power supply – $53

Total cost: $691 + shipping

Some points about this build:

• Processor-wise, I’m fairly convinced that dual-core is the way to go for the near future, since few programs are multithreaded and with the dual-core you get a higher clockspeed for the same price (i.e. single-threaded performance is higher). Plus you get the smoothness and responsiveness that only multicore can give you. But if apps and games start showing significantly better performance on quad core, I might consider a Q6600 instead.
• The motherboard is up for grabs. I picked the Intel because I have always used Intel, and they are stable and compatible with everything. Compatibility is especially important since I plan to run Linux on this machine. However, most people seem to recommend the Gigabyte P35 motherboard. I would consider using that instead, but I need to research it to see what the benefits are.
• I’m also unsure on the video card. I picked the 8600GTS because I want something that is DX10 compatible. However, people recommend a fast DX9 card if you don’t want to spring for the 8800GTS, thinking the 8600GTS won’t be powerful enough to run DX10 games. I guess I need to decide how much gaming I plan to do on this PC. Right now I’m leaning toward “very little,” since I currently spend all my gaming time on the 360, but I’m still hesitant to go with a really cheap video card.
• I plan to reuse my monitors and 500 GB Seagate SATA hard drive from my current machine. I also have a legal copy of Vista Business from my work’s MSDN subscription, so I also don’t need an OS, though Vista Home Premium is tempting for the Media Center features.
• Notice the optical drive is SATA. Along with the SATA hard drive I would bring over from my old machine, that means there would be no PATA drives in this system. Thank God! No more fooling around with jumpers, master/slave settings, and giant ribbon cables. And no more worrying about having two devices on the same IDE channel.

I’m thinking in reality I may build a new system sometime in the first half of next year. Wait for Vista SP1 and the new 45 nm Core 2 Duos to come out.