Putting the magic in the machine since 1980.

Wednesday, April 30, 2008

Marriage Problem

In the marriage problem we have an equal number of men and women who we want to pair up (it is presumed they are all heterosexual). Each one has an ordered list of their prefered mates. The goal is to find the set of marriages such that no two people would rather get divorced and marry each other. That is, not two prefer each other over their assigned mates.

This problem can be solved with a simple algorithm where all the men propose to the women. Then, each woman with more than one proposal rejects all but her most preferred which she temporarily accepts. The bachelors then repeat the process by asking their most favorite woman who has not rejected them. The process continues until all women have a partner. I have a NetLogo implementation of the marriage problem that illustrates this process.

It is interesting to notice that while the women are the ones that get to turn down the men, the men do overwhelmingly better than the women. I mentioned this to my wife and she said that is why she proposed to me. Of course, in the end it is always the women who propose to us.

I am interested in finding distributed algorithms that arrive at stable solutions, that is, those where no two people would rather be married to each other than to their partner. Here is a link to a set of slides that goes into more detail on the marriage problem, in case you want to learn a bit more.

Monday, April 28, 2008

Trading Houses

Imagine that all students are assigned dorm rooms in some ad-hoc way. After each one has a room, two students might find that they both prefer the room the other one has, thus they could switch rooms and both be happier. Similarly, three students (A,B, and C) might find that A prefer's B's room, B prefers C's room, and C prefers A's room. These three students might also trade rooms in a cycle. This can go on for even larger cycles. But, how do we find these cycles?

A very simple algorithm, proposed back in the seventies, is to have each agent point to its most preferred choice. If the resulting graph has any loops (it will) then all the agents in the loops exchange rooms and drop out of the game. The remaining agents then point to their most preferred room and we repeat the process until there are no more agents left.

I have implemented a simple demonstration of this top trading cycle algorithm using a simple distributed cycle detection protocol. Its fun to watch!

Thursday, April 24, 2008

My Programming Languages History

As faculty members in Computer Science and Engineering we often discuss the pros and cons of languages and which ones we should teach. The Tiobe software index shows us how the popularity of certain languages ebbs and flows. I think it is clear that it does not really matter which specific language you learn first or second, what matters is that you learn how to think clearly. And that you learn how to learn new languages.

As a demonstration, I thought I'd take a trip back memory lane and list the languages I learned (and forgotten) while still in school:

  1. BASIC - Freshman year in high school I took a summer class on Basic programming using the old Tandy PET (I also had the Atari 2600 basic programming cartridge, but it kinda sucked). Next year, my new Apple IIe had basic built in. I should also mention that back then it was common for high schools to teach Basic programming, Power Point and Excel did not yet exist.
  2. 6052 Assembly language - Of course, I wanted to write games and the only way to get any kind of animation in the Apple IIe was to progran in assembly.
  3. APL - I only worked with this extremely strange language for two weeks.
  4. Pascal - Somehow I got a hold of a copy of a Pascal compiler for the Apple IIe. I was surprised to learn that you could write programs without line numbers and GOTO/jmp statements.
  5. Scheme - I used it in my freshman year at college. Scheme is the simplest language I have seen. It is beautiful.
  6. CLU - In college we had to do our software projects using CLU. It is a pre-cursor to object-oriented languages.
  7. Emacs Lisp - I learned it for a summer job. This rss feed will be turned into HTML automatically by an Emacs Lisp function I wrote.
  8. C - Learned it for an OS class in graduate school.
  9. Lisp - thesis work.
  10. Tcl/tk - thesis work.
  11. C++ - thesis work.
  12. Java - I wanted to write some applets, for fun.
Those are just the major programming languages I encountered while still a student (pre 1998), I also learned bits and pieces of countless scripting languages (awk, sed, bash) or special purpose languages (latex, um-prs, sql). The point is, my experience is not uncommon. A good computer scientist or software engineer will learn at least one new language every year or so. After a while, one notices how they are all not that different but how each one teaches us something about the way we think, the way we solve problems. Writing software is about how we think, and how we translate these thoughts to meet the capabilities of the machine at our fingertips.

Thus, there is no need to get too hung up on which programming language you should learn first. If you choose software as a career, you will likely learn over 100 languages over your lifetime. I can only imagine what we will be using 10 years from today!

If you also have fun writing programs then maybe you would like to try to solve some of my programming questions.