Sorting Quickly

Merge sort and heap sort both run in O(nlgn), which is where the lower limit lies in comparison sort algorithms.

Merge sort is intuitive and fairly straightforward. Heap sort has the advantage of being able to be used in priority queues efficiently.

Then there is quick sort. Quick sort also runs in O(nlgn), but only for its average and best case scenarios. In the worst case, quick sort runs in O(n^2). However, quick sort is preferred over merge sort and heap sort. Why? Because other than the worst case, quick sort runs faster in practice due to its tighter loops. But what about the worst case? The good news is that there is only 1 worst case sequence, which is if at each iteration, we choose the largest number as the pivot. If we use a randomized algorithm of quick sort, the chances of hitting the worst case is 1/n!, which is very low. Hence, in practice, it's worth the risk of hitting the worst case.

Here's my code for quick sort and a test file.
https://gist.github.com/wmwong/6758508#file-quicksort-rb
https://gist.github.com/wmwong/6758508#file-quicksort_test-rb

Fun with Heaps!

It's been a while since my undergraduate and I've forgotten how fun my Computer Science degree was.

I'm re-reading Introduction to Algorithms and having quite a lot of fun with it.

The latest chapter I went over was the chapter on heaps. So I decided to implement some of the data structures and algorithms.

Here is my code for creating heaps (both max and min-heaps) and heap sort.
https://gist.github.com/wmwong/6747122#file-heap-rb

I also created a test file.
https://gist.github.com/wmwong/6747122#file-heap_test-rb

Also introduced along with heaps are priority queues as they go really well together. Here are my implementations for a max and min-priority queue.
https://gist.github.com/wmwong/6747122#file-priority_queue-rb

And of courses tests!
https://gist.github.com/wmwong/6747122#file-priority_queue_test-rb

Code Kata 6: Anagrams

For this one, we get to play with anagrams! Anagrams are words with the same letters. An example is "read" and "dear".

The task is to take a list of words and find all the anagrams in the list.
http://codekata.pragprog.com/2007/01/kata_six_anagra.html

Being honest, I have to tell you that I originally misread the task. I thought that I was supposed to generate all possible anagrams for each word in the list. Instead, you're supposed to find all words that are anagrams within the list. More on my folly later.

For this task, the link to the word list is broken. I happened to find it after Googling, so I included it in my Gist.
https://gist.github.com/wmwong/6724712#file-wordlist-txt

My solution was fairly simple. I used a hash function which basically took each word and sorted the letters in alphabetical order. I then used the sorted word as the key to my hash and stored the original word as the value. Because of the nature of anagrams, all words that are anagrams of each other will generate the same sorted word.
https://gist.github.com/wmwong/6724712#file-6_anagrams-rb

There is one issue with this solution though. It is not optimal. We need to sort each word. If we let n be the number of words, and m be the average number of letters in a word, our running time is O(nmlogm) if we use merge sort.

I cannot take credit for coming up with a better solution, but I will share it here. There is a theorem called the Fundamental theorem of arithmetic. This gives rise to two things: that all integers greater than 1 can be represented as a product of primes and that those primes are always the same (although you can order them any way you like).

How does this help us? Well, that means we can assign each letter in the alphabet a unique prime number. When we get a word, we take each letter, map it to its prime number, and multiply it all together. This generates a unique integer. In order to get the same integer, you must multiply the same set of primes, which maps to the same set of letters, which means we found an anagram! What's more important is that this hash function takes O(m), which was better than our hash function based on sorting which was O(mlogm).

With this new hash function, that brings the algorithm to O(nm) which is an improvement over O(nmlogm). In reality though, m could probably be considered a constant because the average length of a word doesn't really change and so either solution would be just as good.

I didn't write example code for this as the code is straight forward.

Instead, I'll dive into what I thought was the task.

After reading the task, I thought that we were given a list of words, and for each word, we were to find all anagrams of that word. This task was actually harder than the original task as I had to generate possible anagrams of a word and then check them against a dictionary.

Here is my solution to this task. I stopped after I noticed I was working on the wrong task so it's not fully thought through. My first attempt tries to reduce the number of permutations checked by disregarding duplicate letters. Further optimizations could be made by memoizing each set of letters we come across. This also does not massage the word to only contain alphanumeric characters, so this solution may not be 100% correct.
https://gist.github.com/wmwong/6724712#file-6_anagram-rb

And here is the test file I used to check the solution.
https://gist.github.com/wmwong/6724712#file-6_anagram_test-rb

Lastly, here is the file I used to run the small example given in Code Kata 6. This is where I found out my list looked different than his, and that I was actually solving the wrong task.
https://gist.github.com/wmwong/6724712#file-6_anagram_generator-rb

Code Kata 5: Bloom Filters

In this one, we learn about bloom filters and implement a spell checker.
http://codekata.pragprog.com/2007/01/kata_five_bloom.html

Here's my version.
https://gist.github.com/wmwong/6695303

Code Kata 4: Data Munging

This one is about reading data from a file and retrieving relevant data.
http://codekata.pragprog.com/2007/01/kata_four_data_.html

Solutions

• Part One: Weather Data
• Part Two: Football Data
• Part Three: DRY

Kata Questions

• Deciding to use regular expressions made the refactoring much more easy.
• When I wrote the second program, I definitely followed many of the things I did in the first program. This made refactoring much more easy too.
• Refactoring code to rip out common code is usually a good practice. This helps in maintainability especially when you have to change the piece of code. If it wasn't refactored, you would have to change the code in two different places and test them separately. It also becomes a candidate for reuse when you come across the same scenario. If done right, it helps with readability because it breaks code into smaller chunks. This way, you can hold less in your head. There is, however, one scenario where I find refactoring out common code is a downfall: when future requirements cause slight differences in the common code. Because we don't know all the cases we will ever handle when we refactor out common code, it is hard to account for this. However, there have been several times where future changes cause slight differences in the common code and it turned out that refactoring was a bad idea.

Code Kata 3: How Big, How Fast?

This one helps you quickly estimate sizes and speed.
http://codekata.pragprog.com/2007/01/kata_three_how_.html

How Big?

How many bits?

For this one, the way I thought about it is that 10 bits is roughly 1000 (2^10).

11 bits gives you roughly 2000 (2^11).

A pattern emerges as such: 2000 = 1000 * 2 ~ 2^10 * 2^1 = 2^(10+1).

Hence, you can quickly figure out a rough approximation by seeing how many multiples of 1000 there are and then figure out the leftovers.

• 1,000 ~ 2^10
• 1,000,000 ~ 2^20
• 1,000,000,000 ~ 2^30
• 1,000,000,000,000 ~ 2^40
• 8,000,000,000,000 = 1,000,000,000,000 * 8 ~ 2^40 * 2^3 = 2^43

How much space?

For a town of 20,000 residences, to store their names, addresses, and phone numbers, we can assume that we need about 200 characters per resident. This gives us 20,000 * 200 which is 4,000,000 characters. If each character takes up a byte, then we end up with roughly 4MB of data.

Binary trees!

Storing 1,000,000 integers in a binary tree will require 1,000,000 nodes. In the best case (balanced), the number of levels will be log2(1,000,000). Using our approximation technique from above, that would be roughly 20 levels. Any worse then a balanced tree would have more levels up to 1,000,000 levels. The space required to hold a tree like this would be calculated by noticing what data each node needs to hold. Each node needs to hold its own value, a pointer to the left child, and a pointer to the right child. If each piece of data requires 32 bits (4 bytes), then each node requires 12 bytes. This totals 12,000,000 bytes or 12MB of data.

How fast?

How long?

Assuming that each page in the book has roughly 200 characters. Each character takes up a byte. This means we have roughly 240,000 bytes to send. A 56kb/s modem translates to a 7,000B/s modem. This means it would take roughly 350 seconds which is roughly 6 minutes.

Binary search!

It takes 4.5mS to search 10,000 entries and 6mS to search 100,000. There is 10x more to search and it was done in 1.5mS more time. Hence, for 10,000,000, it should take roughly 9mS.

Brute force

There are 96^16 possible passwords.

A rough estimation would be 100^16 = (10^2)^16 = 10^32.

Since we can do 1000 searches per second, this would take 10^32 / 10^3 = 10^29 seconds to perform.

There are 86,400 seconds in a day which is roughly 100,000 seconds. This gives us 10^24 days.

Dividing by 365 is a little hard to do but dividing by 1000 is "close enough". This gives us 10^21 years.

Brute force is definitely not a viable approach.

Code Kata 2: Karate Chop

This kata challenges you to implement binary search in 5 different ways and to document things you had trouble with, like "off by one errors" and fencepost errors.
http://codekata.pragprog.com/2007/01/kata_two_karate.html

Here are my attempts in Ruby.
https://gist.github.com/wmwong/6662429

Got any other ideas on how else to solve this? Or feedback for my code? Let me know down below in the comments!

Rusty

Over the years, I've been working on several different products, all of which has allowed me to practice building products and shipping code. However, I haven't had much time to experiment and play. I feel I've lost many things that I've learnt from my CS degree.

So starting from today, I will start practising and learning again.

To start off, I'm going to work my way through Code Kata. I'll be posting my solutions on Gist.

I also plan on going through my Introduction to Algorithms book again. I'll try to summarize what I learn as I go.

Well, time to get started!

Ubuntu: Out of Disk Space

Problem

When I first installed Ubuntu on my desktop, I had decided I would like to partition my /home directory from the rest of my filesystem. This way, if an Ubuntu upgrade fails, I can always perform a clean install without having to backup my data. Or, theoretically, I could install another OS and my data would all still be there. When I partitioned the / directory, I decided that 10 GB should be enough.

Well, recently, I've been hitting up against that 10 GB limit. Every day when I boot up my computer, I get a warning that I only have a few hundred MB of space left. Well, today, I'm at 100% usage. I couldn't even send an email out from Thunderbird.

So, I tried clearing space. I tried running

sudo apt-get autoremove

Unfortunately, there was nothing left to autoremove.

I then browsed through /usr/local as that's where I store any applications I need to compile and run. Again, nothing extra to remove.

My last resort was heading to /tmp to clear anything there. However, it didn't make much of a difference.

I was still stuck.

Solution

Suddenly, a thought came to me. I've gone through several Ubuntu updates where it installed Linux kernel headers. Maybe that's what was taking up space. After a quick Google search, I came upon a post that would delete all unused Linux headers.

Just to be safe, before running this, restart your machine.

dpkg -l 'linux-*' | sed '/^ii/!d;/'"$(uname -r | sed "s/\(.*\)-\([^0-9]\+\)/\1/")"'/d;s/^[^ ]* [^ ]* \([^ ]*\).*/\1/;/[0-9]/!d' | xargs sudo apt-get -y purge

This ran in the terminal for some time while it cleaned out all my unused Linux kernel headers. I ended up getting rid of 3 GB of data.

I was free again!

So next time you're running out of room, make sure it isn't some old Linux headers taking up space.

References

http://ubuntugenius.wordpress.com/2011/01/08/ubuntu-cleanup-how-to-remove-all-unused-linux-kernel-headers-images-and-modules/

Ubuntu 12.04: No Root File System Is Defined

Problem

I got this error when trying to do a fresh install of Ubuntu 12.04 from USB. I get past the screen that asks if you want to download updates and install third party software, then I get stuck on the "Installation Type" screen.

The installer only sees /dev/sdb which is my USB and shows nothing in the partitions table. All the buttons are disabled. Clicking continue gives me the error "No root file system is defined".

Instead of installing, I went to "Try Ubuntu". This loaded up the Ubuntu desktop. Checking gparted and fdisk, I was able to find /dev/sda. Great! Unfortunately, trying to install gives me the exact same problem.

Solution

When you "Try Ubuntu", open up a terminal and type

sudo apt-get remove dmraid -y

It gave me some errors, but I ignored them. I ran the installer from the desktop and voila! The installer sees /dev/sda and I could install Ubuntu 12.04

References

http://askubuntu.com/questions/111926/installation-stuck-on-installation-type-screen

Ubuntu: Automating Locking and Suspending

Locking and Suspending from the Terminal

The first thing to note is that suspending the computer does not lock the computer. They are separate actions.

To lock the screen.

gnome-screensaver-command --lock

To suspend the computer, check out this article on How To Suspend Ubuntu from the Terminal. If you're simply running this from the terminal either by typing or using a script, I would suggest method 3 as it does not require sudo.

gnome-screensaver-command --lock
dbus-send --print-reply --system --dest=org.freedesktop.UPower /org/freedesktop/UPower org.freedesktop.UPower.Suspend

Locking and Suspending from cron (Problems)

Note: If you don't care about the problems and just want the solution, skip down to the next section.

If you had the above in a script that you could run from the terminal, it follows that you could run this script from a cron. Perhaps the scenario is that you wanted to lock down and suspend a particular computer at work every day at 5pm.

The script would look like this.

#!/bin/sh
gnome-screensaver-command --lock
dbus-send --print-reply --system --dest=org.freedesktop.UPower /org/freedesktop/UPower org.freedesktop.UPower.Suspend

Let's say it was stored in ~/bin/lock-suspend.sh. Remember to make sure that it's executable.

chmod +x ~/bin/lock-suspend.sh

When you run this in the terminal, your computer locks and suspends. Everything is fine.

Next, you would edit your crontab.

crontab -e

And place the following in it. The output from standard out and error is logged to a log file.

0 5 * * * /home/user/bin/lock-suspend.sh > /home/user/logs/lock-suspend.log 2>&1

You then wait for 5pm to come around and lo-and-behold, nothing happens.

Knowing that cron logs to /var/syslog/log, you go and check it and find that the cron job ran, but an error occurred.

Since the script was logged to /home/user/log/lock-suspend.log, you check it out and find the following errors.

** Message: Failed to get session bus: Command line `dbus-launch --autolaunch=364dc0936e296ffa0881a3e90000000a --binary-syntax --close-stderr' exited with non-zero exit status 1: Autolaunch error: X11 initialization failed.\n
Error org.freedesktop.UPower.GeneralError: not authorized

What does this mean?

After much Googling, I came across this thread. It explained that the first message came about because cron does not have access to the same environment as the terminal. More specifically, it is missing the environment variable DBUS_SESSION_BUS_ADDRESS.

I did not look much further into the second error though. I assume it is because cron does not have access to the dbus. This was easily solvable though as there are several methods to suspend, for instance method 2.

sudo pm-suspend

Locking and Suspend from cron (Solution)

In order to solve the first problem, we need to figure out what should go into the environment variable DBUS_SESSION_BUS_ADDRESS.

When you first login, DBUS_SESSION_BUS_ADDRESS is set for you. We can grab this and write it to file. Add the following to your .bashrc file.

set | grep DBUS_SESSION_BUS_ADDRESS > ~/.DBUS_temp

Now we need to modify the lock-suspend.sh script. However, before we do that, we need to think about the solution to the second problem. Since we'll be using sudo to run pm-suspend, the cron job must be run as root instead of as the current user. We will need to modify the script expecting root to be running the script.

Note that in order to set the DBUS_SESSION_BUS_ADDRESS environment variable, we use source. However, in order to use source, we must use bash instead of sh.

The full script.

#!/bin/bash
source /home/user/.DBUS_temp
export DBUS_SESSION_BUS_ADDRESS
su -c "gnome-screensaver-command --lock" user
/usr/sbin/pm-suspend

Now modify the root's crontab.

sudo crontab -e

And add the following.

0 5 * * * /home/user/bin/lock-suspend.sh > /home/user/log/lock-suspend.log 2>&1

Come 5pm, the computer locks and suspends gracefully and you can relax knowing that your data is safe and you're saving the planet by reducing power usage.

SSH Key Fingerprinting

After GitHub got hacked, I received an email informing me that my SSH keys may have been compromised. I needed to login to GitHub and confirm each SSH key.

The thing is, the SSH keys were being shown using their fingerprints. I've seen this before when logging into a server through SSH, but I've never actually had to generate one before.

Thank goodness for Google. Here's how.

ssh-keygen -lf 

References

• SSH fingerprinting

Ubuntu: Install from USB

Apparently, you can install Ubuntu through a USB stick if your BIOS can boot from USB. I though this was pretty neat and wouldn't have to deal with throwaway media like CDs and DVDs. Unfortunately, each time I tried, the computer would not boot from the USB. It just kept booting from the harddrive no matter what I did in the BIOS.

I finally managed to figure this one out. The first 2 computers just didn't boot from USB. No hints. Nothing. Googling this problem brought up nothing. The solutions were to re-download Ubuntu, check your USB, use a CD, try on another computer, etc.

Fortunately, the 3rd computer I used gave me "Missing Operating System". Bingo! I found something searchable. This brought up a nice blog article. A solution! And it works! Basically, the problem was in the creation of the bootable USB. I was using Ubuntu's Startup Disk Creator. Apparently, it doesn't properly wipe out the USB and repartition appropriately. This caused havoc. The idea is to wipe out the USB stick and repartition before using Startup Disk Creator. This solved my problem.

Check out the solution here: http://ubuntuliving.blogspot.com/2008/11/missing-operating-system-step-by-step.html

Ubuntu + iPhone: Upgrade/Restore

It's no secret. Ubuntu + iPhone is a pain in the ass! However, it just got a little less painful for me.

You see, the way I've been approaching this is to never plug my iPhone into my computer. If the two don't meet, there can't be any problems. Don't solve your problems. Get rid of them!

Unfortunately, I've been losing reception the last two weeks and it's been annoying me to no end. I called my service provider and they determined it's probably because I'm still on 3.1.3. Great. I need to upgrade my iPhone. iPhone, meet Ubuntu. Ubuntu, meet iPhone. Now PLEASE play nice.

Of course, that was too much to ask for. I installed VirtualBox and got Windows XP installed. I then added the iPhone as a USB connection in the settings. I then proceeded to plug in my iPhone. iTunes detects my iPhone. Yay! A small triumph. I decided to restore instead of upgrade. I wanted to start from scratch anyways.

After iTunes wiped out my data, it started to prepare for the restore. At which it hung. After a few minutes, it gave me a 1602 error. I tried everything I could think of: reboot iPhone, reboot VirtualBox, reboot Ubuntu, re-plug in iPhone, etc. The best I got out of all this was a different error: 1604. At this point, my iPhone is permanently in Recovery Mode and now, I couldn't even select the iPhone USB connection in VirtualBox.

I thought to myself, "Screw this. I'm fixing you even if it takes all night!" And so, I did. Thanks to this post.

Follow it. It works.

Here are the keypoints and some added tips from the comments.

• Add yourself to both the vboxusers and audio groups.
• Change the USB filter settings so that only Name and Vendor ID have values. DELETE EVERYTHING ELSE. It's not recommended. It's mandatory!
  

After all this, I was able to restore my iPhone without problems. Booyah!

Rails 3.0: RSpec 2 + Machinist + ActiveRecord

RSpec 2 usually cleans up after itself if you set config.use_transactional_fixtures to true. However, if you use Machinist 2, this isn't the case. Apparently Machinist likes to keep around a cached version to speed things up. This is bad when trying to run independent tests.

To prevent this from happening, add this to config/environments/test.rb.

Machinist.configure do |config|
  config.cache_objects = false
end

References

http://blog.angelbob.com/posts/315-RSpec-not-clearing-database-when-you-use-machinist---published-rails

Rails 3.0: PostgreSQL

If you're starting fresh, getting a Rails application running on PostgreSQL can be rather involved.

Install PostgreSQL on Ubuntu.

sudo apt-get install postgresql libpq-dev pgadmin3 -y

Create a new Rails application with PostgreSQL.

rails new <project name> -d postgresql

If this is an old project, install the gem in Gemfile.

gem 'pg'

Create the PostgreSQL user. The username will be the same name as your project which can be found in config/database.yml.

sudo su postgres -c psql
# Enters the psql console.
create user "<username>" with [superuser] password "<password>";
# Outputs CREATE ROLE.
\q

The superuser keyword is optional but makes things easier in development.

If you get the error "FATAL: ident authentication failed", edit /etc/postgresql/8.4/main/pg_hba.conf.

local all all ident

to

local all all md5

Restart PostgreSQL.

sudo service postgresql restart

Create the development and test databases through the terminal.

createdb <project name>_development -U <username> -W
createdb <project name>_test -U <username> -W

References

http://olmonrails.wordpress.com/2008/08/12/switching-rails-to-postgresql/

Ubuntu 11.04: Window Docking Shortcuts

I stumbled upon some new shortcuts in Natty Narwhal to dock a window in a certain position.

Try out Ctrl+Alt+<Number Pad Key>. This will dock your window according the position of the number in the number pad. Note that it doesn't work with the numbers along the top of the keyboard.

1: Bottom left corner
2: Bottom
3: Bottom right corner
4: Left
5: Middle (but not maximized)
6: Right
7: Top left corner
8: Top
9: Top right corner
0: Maximize

If you press the same number several times, it will change the size of the window.

I found this super handy when I needed to fit things inside my monitor, such as having 2 terminals side-by-side.

Try it out and let me know what you think down below in the comments!

Ubuntu 11.04: Redshift

Redshift is a program that changes the temperature of your monitor according to the time of day. It basically emulates sunset and encourages your body to sleep earlier. Something that I desperately need to do.

I recently upgraded to Ubuntu 11.04 Natty Narwhal, and was happy to find that Redshift had made it into the repositories! Unfortunately, after installing both the application and its GUI counterpart, it did not start.

I tried it in the terminal and to my dismay, I got the following:

> redshift
No clock applet was found.
Initialization of gnome-clock failed.
Trying next provider...
Latitude and longitude must be set.

So what's going on? Well, as of Ubuntu 11.04, Gnome is no longer the default. It's Unity. Hence, there is no gnome-clock.

Luckily, Ubuntu uses Redshift v1.6. In this version, a configuration file can be added! Just create the file ~/.config/redshift.conf with the following:

[redshift]
location-provider=manual

[manual]
lat=49.3
lon=123.06

After saving the file, you can now restart Redshift from the GUI.

Enjoy and sleep early!

Logging Bootup/Startup Scripts

I was writing some startup scripts in /etc/init.d/ to be run during bootup. However, there was a problem and the scripts weren't running properly. Unfortunately, there were no logs anywhere.

System Wide Logging

I found a solution in Ubuntu which was to open up /etc/default/bootlogd and set the option to yes. You supposedly see the boot logs in /var/log/boot. However, I found it was writing to /var/log/boot.log. Sort of. I got partial output (about 6 lines). The file was never fully written to.

Script Specific Logging

I found a workaround. Instead of using a system wide log, use a script specific log. Add this to your script. It will log all output.

exec > /tmp/debug-my-script.txt 2>&1

References

• Ubuntu boot log
• Logging to file

Automatic Server Bootup on Power Failure

Imagine a power failure where your servers are running. Of course, they should be plugged into a UPS, but what if that goes down too? Your server will power off.

When the power comes back, your server will remain quiet unless you tell your servers to come back to life by themselves.

There are 2 things you must do in the BIOS to make this happen.

1. Tell the server to bootup after a power failure. This is the AC Power Loss Restart option in the BIOS. This should be set to On.
2. Ignore a missing keyboard. There is an area in the BIOS that handles halting on errors. It should be set so that it ignores keyboard errors. If this is not ignored, the server will wait for the user to press F1.