Geeking out: Quad Core Tower of Power Yumminess

I've needed to upgrade my P4 3Ghz Dell Dimension desktop for awhile -- it's been 2+ years since I got a new computer. Once Apple went x86, I always knew my next computer would be a Mac. I've been using Unix for the last 16 years as a development environment, but I never really liked any of the Unix desktops (except NeXT), so I always kept a PC around as my main terminal and connected remotely to Unix boxes. Not so much for applications per se, but mostly for games, multimedia, and Java performance (remember the bad ole days of no Hotspot for Linux and old JDKs?)

Mac OS X gives me the environment I'm most comfortable in: Unix and the Unix command line, as well as a fabulous desktop. My only dilemma was: MacBook Pro or Mac Pro? Last year, I traveled alot for work, so it would be a no brainer, but given that I rarely travel now, and I'm replacing a PC Desktop that also acts as a gaming rig, the Mac Pro became alot more desirable.

The only worry was I haven't seen the Merom based notebooks and Clovertown based Mac Pros on the horizon, with supposedly a new case design for the Mac Pro by an internationally famous designer. Should I wait till January or longer? The next-gen NVidia and ATI DirectX10 video cards would be out by then as well. The problem with waiting is that there is *always* something new and great in the pipeline 6 months later. If you wait for the next big thing, you'll always be paralyzed.

I decided that the Mac Pro was so much better than my current setup, it doesn't matter what's coming 6 months from now. The Mac Pro case, before redesign, is already very very nice, especially the RAM and SATA connections. But once I saw how Anandtech was able to just plug Clovertown engineering samples into a Mac Pro and turn it into a Octo-Core monster, it clinched it -- this baby's CPU is upgradable too. In any case, I need to do lots of video editing, and 4 easily accessible SATA drive bays + 4 cores is good for the task.

So last Friday, I pulled the trigger. Mac Pro, 2.667 Ghz, minimum sized HD, ATI X1900XT, 2Gb FB-DIMM RAM, Bluetooth = $3003. I did not get the 3Ghz version because I think a 12% gain in serial performance is not worth $800. I expect that when Clovertown is released, Xeon 5160 prices will drop radically, and I'll upgrade later if I need to, and it will be far cheaper. Moreover, Apple charges $400 for 500Gb HDs when I can buy them online for $170. I'll use the 160Gb that comes with it as my Windows XP Bootcamp drive for gaming. I'll also have 4 empty FB-DIMM slots to upgrade RAM later if I need more, when the price is cheaper.

Now goddamn it, hurry up and deliver my machine Apple!

P.S. Parallels announced that they will support DirectX acceleration near the end of the year, which would effectively eliminate the need for Boot Camp for gaming in most cases. Yay!

As for my old Dell PC, I've got another 1TB RAID sitting in the house and I've been itching to run ZFS, so I'm gonna try running OpenSolaris on it. The Linux and Apple guys need to get their butts into gear and get ZFS ported ASAP!

Balanced Incomplete Block Designs, Difference Sets, Klein's Quartic Curve, Projective Planes, and lots more!

I've been busy lately and unable to provide the answer for the Extreme Programming Code Review problem posted last time. I chose this problem, because when I was taking a graduate combinatorics class in college, the underlying problem had an almost mystic relation to a large number of other areas of combinatorics and geometry, as well as producing a simple, but beautiful and symmetric structure.

Mathematical history has many examples of similar, but harder arrangement problems. Catherine The Great supposedly kicked things off by posing to Euler, The 36 Officers Problem. Later, Kirkman proposed the 15 schoolgirl problem (my oh my, a Reverend and thoughts of schoolgirls eh?). These seemingly simple problems acted as a catalyst and resulted in great advances in the field of combinatorics, which has enormous applications in many fields. One application of course, is solving the problem I posed.

The problem says, given 7 people, arrange them into 7 teams of 3 each, such that no two people are ever on the same team twice. It is probably possible to construct this design using trial and error, but there are many other ways to do it.

Let us number the programmers 0 through 6, and start off with the team {0,1,3}. If we were to add 1 to each number, it is easy to see that the new team will consist of 3 new members, no two of which are in the first team. {1,2,4} And likewise, the same will be true for each new team, for all teams {x+0, x+1, x+3} up to x=0 to 6. The first two positions will always differ by 1, the second and third by 2, and the first and third by 3. If you read down the three columns, we're just rewritten the numbers 0 through 6 shifted by 1 or 2 places. Here's our list of teams, you can also verify them by visual inspection.

{0,1,3}
{1,2,4}
{2,3,5}
{3,4,6}
{4,5,0}
{5,6,1}
{6,7,2}

It turns out that this solution is also unique except for permuting order.

Combinatorics describes this as a t-(v,k,l) design. A t-(v,k,l) design is a set P of v points, a set of subsets of P called blocks (also called lines) B containing k points, and an incidence structure I in P * B which describes the relation of P and B (which elements of P are in which blocks). For any t points, exactly l blocks are incident.

Our problem says that there are p=7 points, and it says that for any t=2 points, they are contained in only l=1 block (team), and the blocks consist of k=3 points. Therefore, our problem is to construct a 2-(7,3,1) design. Such 2-designs are called Steiner Triple Systems and denoted STS(7). One result of combinatorics is that STS(v) exists if and only if v = 1 or 3 (mod 6).

So what's so special about this problem to get so worked up about? It turns out there are many connections with STS(7) and other areas of mathematics, in addition to which I mentioned in the header, there are also connections to coding theory, latin squares, octonions, simple groups, and geometry.

And now I will show you how this problem is connected to the Balsa Wood problem, as well as to very beautiful geometry.

Recall that there are 7 teams of 3-programmers, 7 programmers, no two programmers are on the same team twice. Remember back to the defination of a 2-(7,3,1) design, the programmers are called "points" and the teams are called "lines". If no two programmers are on the same team twice, that means 2 programmers (or points) uniquely determine a line, and also, that at most, two teams can only have 1 programmer in common, which says that any two lines intersect at one and only 1 point. Hmm...

• 7 points
• 7 lines
• 2 points determine a line
• 2 lines determine a point

What would happen if we wrote down those 7 programmers and connected the dots according to teams?



We form what's called a projective plane. This plane, the projective plane of order 2 called the Fano Plane has the interesting property that there are no parallel lines. It also has a 168-fold symmetry. (another interesting property, since each line has 3 points as well as each point is incident with 3 lines, you can interchange points and lines to no effect! The Fano Plane is its own dual.)

How can we use this to solve the Balsa Wood problem? I will give a partial solution, by showing the solution for 3 successive writes.

• if you are writing X and the ram is already in state X, do nothing
  
• if the ram is empty, and you're writing I, then place a 1 in bit position I
• if the ram contains 1 bit in position I and you are writing the number J, find a line (I,J,K) and place a 1 in bit position K
• if the ram contains 2 bits in positions I, K, and you are writing value X, write 2 more bits such that 3 of the bits will be colinear on a line, and X will be a point NOT on that line. That is, if X != I or != K, then find the line (I,J,K) and place a 1 bit in position J, as well as in position X. If X == I then write two bits on the other line containing K, and if X == K, then write two bits on the other line containing I.

Step 2 and 3 work because of the inherent property of projective planes. Step 2 works because 2 points uniquely determine a line. Step 3 works, because no matter what, there are three lines intersecting any point colinear with X, therefore, you can always place 2 1-bits on one of those lines.

The rules for reading are as follows:

• if the memory is blank, nothing has been written yet
• if exactly one bit is written in position I, then the value in the memory is I
• if exactly two bits are written in position I and K, then the value in the memory is J, where J is on the line containing I and K
• if exactly 4 bits are written in positions X, I, J, K, find the 3 positions which form a colinear line, the one which is "left out" by itself is the value in the memory.

I leave the construction of the final rule for writing and reading, as well as an argument as to its correctness to the reader. There is an alternate solution to this problem by using womcode techniques, which have applications to both error correcting codes and cryptography. Sadly, Rivest and Shamir seemed to have patented it, and the solution to the Balsa Wood problem actually violates the patent.

Another related problem to look up is the Transylvanian Lottery Problem, also solved with the Fano Plane.


-Ray

The Extreme Programming Code Review Problem

You manage a team of 7 programmers and have become a recent convert to extreme programming. You have decided to use a style of pair-programing that you call the weekly triplet review.

Each day of the week, 3 programmers will be picked from the 7 available to conduct code reviews together such that no two programmers will ever be on the same team more than once in one week. (Note, these programmers work on weekends too, so you need 7 teams of 3.)

If the programmers are numbered 1 through 7, can you enumerate all the possible teams?

-Ray

P.S. It is no coincidence that this problem features 7 objects like the previous problem. Believe it or not, this is a hint: if you solve this problem, you may have some inspiration for how to solve the Balsa Wood RAM problem.

Puzzles you can't solve with Google

One of the techniques that people commonly use in interviewing software engineers is to use puzzle questions to ascertain the problem solving process of candidates. However, the problems themselves are generally drawn from commonly asked puzzle questions, some of them even famous puzzle problems, which lets candidates solve them either by search engine, or by memorization.

So what's a good source of problems to ask which are not generally available on the internet? Well, many college mathematics or computer science textbooks contain obscure and hard example problems which are not generally covered in internet discussions.

One of them, that I encountered over 12 years ago, still burns in my memory today because of connections with quite beautiful mathematical structures. I will reproduce the problem below, obfuscated from the original way it was stated, in order to avoid book searches. I have only seen this problem discussed twice by others in 20 years of internet usage. It has analogous solutions in some ACM/IEEE/CiteSeer references, but in general is not discussed in IT or Puzzle literature.

I will post the solution later in another message.

The Balsa Wood RAM Machine

You are given a computer attached to a unique memory device consisting of a number of sticks of Balsa Wood, 7 to be exact. The computer can read from this memory by checking to see whether a given stick of wood in position X is either broken or unbroken, representing a 1 or a 0 respectively. The computer can also write to this memory, but it can only write *1* bits, it cannot write a 0, that is, it can break sticks, but it cannot repair a broken stick.

The computer operates on decimal number in the range 0-6, and the question arises, how many times can the computer write a number to the RAM and read it back? What would the read and write procedures look like?

As an example, you can imagine that if the RAM is empty, if you want to write a decimal value X, you place a 1 in the Xth RAM position (break stick X). You read this value back by observing which position contains a broken stick.

The RAM however has 6 more unbroken sticks, can't we use this to support multiple writes? Yes, a second write could be supported for value Y by breaking all sticks except Y, in which the read procedure would be to observe which stick is left unbroken.

Those are the trivial procedures. What about 3 writes or 4? It turns out that 4 writes are possible. So, the question is:

Specify an algorithm for writing 4 values into the RAM and being able to read them back at each step, without foreknowledge of what was written before.

That is, your task is to produce two procedures: WRITE(BitSet current, Integer valueFromZeroToSix) -> returning BitSet and READ(BitSet current) -> returning Integer, in which the following is true:

1) WRITE returns a new BitSet produced by taking the old BitSet and changing only 0 to 1s. It also replaces the current bitset with the return value.
2) READ(WRITE(current, X)) == X
3) Any sequence of WRITE and READ operations may occur as long as the number of WRITE operations is less than 5.


I will post the solution some time in the future.

-Ray

Awe inspiring complexity and logical depth.

That's what I got watching "The inner life of a cell" a 3D visualization of some of the molecular mechanics of cell biology.

Watching this video was tantamount to a religious experience for me in the level of awe and wonder at the truly staggering and overwhelming complexity of what goes inside the cell at the level of molecular biology. I've read about the MAP/Microtubule transport before and seen diagrams of how the foot-over-foot moveement was supposed to work, but to watch it artistically portrayed recalled memories of "2001" A Space Odyssey -- beauty and science in a single package. It is surreal, almost like a Dali creation, watching those tiny feet attached to a thin strand carry a large amorphous bag of material hundreds or thousands of times larger in volume up a bean stalk.

None of the 3D visualizations of molecular biology I've seen before could convey this sense. There are videos floating around of macrophages in action, or HIV penetrating a cell, but they lack the artistry of this video. The closest I've seen have been the microphotography series of the development of the human fetus in the womb.

The video of course takes some artistic liberties, speeding up or slowing down time, making the cell look mostly empty inside instead of packed to the brim with molecules, but I can accept that these are done so that you may focus on a single mechanism at a time.

In the field of computer science, we are used to coding procedures to construct the proper output data according to guaranteed determinism and error-free execution, so to watch code execute which produces self assembling structures in the presense of error and stochastic processes is simply amazing. The amount of information and logical depth encoded in 4 billion years worth of evolution is a wonder to behold, even for an atheist.

I await the full 8 minute video. Hats off to XVIVO, HHMI and Harvard Biovision.