Donnie’s Blog

The summer break is finally here, and I for one am very excited about this summer. This year I have a SURF student helping me out with the implementation of my “educational database system” in Java. The working name is currently NanoDB, although I am certainly open to other suggestions.

(more…)

A few days ago there was this Slashdot article about a serious Linux kernel security hole. Since I was running a version of Linux that had the issue, I thought I had better patch it on my server ASAP.

My machine basically has nobody on it, so I am really not worried about somebody using the exploit directly. But, I do have a number of network services, like my mailserver, webserver, SSH server - and if any of those has a vulnerability, I sure don’t want somebody using that to get root access on my box!

So, last night I manually patched my kernel source, rebuilt my kernel, and rebooted the machine. It was exciting and nerve-wracking; since it’s been so long since I built a kernel myself (2000? 2001? It was at DALi I am sure…), I didn’t know if I would get it right! Then there’s the fact that I am running RAID1 on my boot partition, and I wasn’t sure how the kernel update would go with that.

But, everything went fine. The machine rebooted fine, and when I tried the exploit on the patched system, nothing bad happened. All my services started back up without a hitch.

It was kind of exciting!

Saturday, November 10 was the ACM regional programming contest. Caltech won yet again… Go Caltech!

This year was definitely one of the least intentional wins. There was little interest in an ACM programming contest track for CS11, so we just didn’t have one. Then, two weeks before the contest was scheduled, some all-star students expressed interest in going, so we arranged it. And they won! Caltech rocks.

Anyway. Hopefully we won’t do it this way ever again. Next year I want to really try to drum up interest in the contest and actually get 3 or 4 teams out there. But at least we were able to land the win this year!

I just added a new programming note about a project I have been tinkering with lately. The project is a Buddhabrot image generator. Right now I am still working on generating some images so I will add those tomorrow, but tonight I wrote up a page about some of the interesting things I learned from this little project. So, check it out. Hopefully you will find it interesting too.

One of the software projects I have been working on over the summer required the software to be built for MacOS X, but not just any old version - it had to be built for MacOS X 10.3.9, and it had to run on the PowerPC.

This was an interesting challenge. Especially since I didn’t have a Mac!

(more…)

This is an interview question I had at Microsoft, from when I was interviewing for my very first internship. That would have been way back in early 1996.

“You are given an integer n, and you need to write a function to count how many bits in n are set to 1.”

As most reasonably savvy programmers would do, I wrote a function that shifts n to the right, counting the times that the least-significant bit is set to 1, until n is 0. Something like this:

  int countBits(int n) {
    int count = 0;
    while (n != 0) {
      if (n & 1)
        count++;

      n = n >> 1;
    }

    return count;
  }

In general, this function will take O(b) time to complete, where b is the bit-width of n. This is fine; it’s a constant, so we are all happy with that.

But it turns out that there’s a faster way!

Question 1: Do you know what the faster way is?

Question 2: Do you know how it works?

I will admit up front that my interviewer showed me, way back in 1996, the faster way. But I just figured out how it works this weekend.

(more…)

I wrote a fun little program for computing the closure of a set of functional dependencies this week. Functional dependency theory is the foundation for Third Normal Form and Boyce-Codd Normal Form, and a variety of other neat things you can do with relation schemas. An interesting and powerful set of ideas, but I think that most database designers don’t really use functional dependency theory so much. But it is fun to play with!

Anyway, a lot of the problems are very simple in that they work with abstracted schemas, such as R(A, B, C, D, E), and if you take a set F of functional dependencies against the relation R, you would like to compute things like “What is the closure of F?” or “What is a canonical cover of F?” Then you can answer questions like “What are the candidate keys of R, given F?”

(more…)

I have been thinking for a long time about what language would be best to use for implementing a relational database system. Keep in mind that this is not for any serious use; I want to implement this as an educational platform for the students in my database systems course, so that they can have some of the grungier details all nailed down for them. So, a clean, modular architecture is the number one focus, and performance is a rather distant concern.

(This is also why I have generally ruled out open-source database systems as a teaching aid. Although most open-source databases are quite impressive in their capabilities and performance, they just don’t have the modularity and the simplicity that an effective teaching tool would need.)

(more…)

The last post I wrote about C++ was about an unfortunately too-common programming practice of writing a class so that it provides a direct reference to an internal data-member. Here is the offending code, yet again:

class Widget {
private:
  double m_distance;

public:
  double & distance() { return m_distance; }
  const double & distance() const { return m_distance; }
};

I showed this kind of approach in my Advanced C++ track last night, and here is something that one of my students thought of: Can you grab a reference to Widget’s m_distance data-member, and hang on to it?

In other words, what does this code print:

  Widget w;
  w.distance() = 5;

  double &evil = w.distance();
  evil = -2;

  cout << w.distance();

(more…)

This is the first time that my computer has ever been too fast for me!

I needed to come up with a good programming problem that would be easily parallelizable. So, I fell back on the old standard, the Mandelbrot set. I got the single-threaded version working yesterday, and much to my dismay, it was really fast. What’s the point in parallelizing a fast program?

Nonetheless, I love the Mandelbrot set. Here are some pictures I generated:

Most of these images only took a few seconds to generate. Back in 1995 when I wrote my first Mandelbrot viewer in CS3, it took several minutes to generate images this large. The parallelized version would still take 30-45 seconds.

So, since this is no longer challenging enough for modern computers, I’ll have to find something else. Volumetric rendering sounds pretty good…