ariels's New Writeups

Buffon's Needle (thing)

2007-11-18T03:58:43Z

Sewing without Calculus

Buffon's needle is deeply unsatisfying: a question with only a passing relationship to circles (the needle can fall in any orientation -- but there's still the small matter of lateral motion!) ends up connected to π. Why?

The standard proof -- above in devout's writeup, with integrals -- does little to explain the mysterious appearance of π. Calculation is often like that.

Geometric measure theory offers a "clean" proof, one that almost does explain where π comes from. And it goes like this.

We are interested in the probability "p_L" that a needle of length L, randomly dropped on a surface ruled with lines at interval 1 from each other, will intersect a line. Suppose L≤1. Then almost always the needle can intersect at most 1 line, so either it intersects 1 line (with probability p_L) or it intersects 0 lines (with probability 1-p_L).

…

generic programming (thing)

2007-08-25T21:02:46Z

Introduction

Generic programming is a philosophy of programming that emphasizes the algorithm, invented/discovered by Alexander Stepanov. Its most famous incarnation is in the STL of C++; however it is quite distinct. Best to say that C++, as a multi-paradigmatic language, also supports generic programming.

At work we have a fairly complex Message class. There are at least two different possible views of the contents of Message, neither of which exists in contiguous memory. Just last week I got asked...
"Do we have a substring find algorithm on Messages? And what about regular expressions? Do we have algorithms for those? I looked and couldn't find any relevant method in class Message."

Algorithms

Algorithms are a sequence of steps. For example, an algorithm for finding a minimal…

Proof of Sperner's theorem (thing)

2007-07-30T06:36:38Z

This is about the only proof I can come up with for Sperner's theorem (which see). It's an interesting question whether other, structurally different, proofs exist. In particular, a truly probabilistic proof (not just rephrasing the counting argument below in terms of probability) would be desirable (to me, at least).

Proof.

Suppose we have some antichain F on {1,...,n}. Consider all ordered permutations a₁,a_n∈{1,...,n} (that is, all orderings of the numbers 1,...,n). There are n! such orderings. Now, the sequence of sets

{a₁} ⊆ {a₁,a₂} ⊆ ... ⊆ {a₁,a₂,...,a_n}

contains at most one element of F (otherwise F is no antichain).

Suppose f∈F has k elements. Then there are exactly k!(n-k)! orderings that intersect…

Sperner's theorem (thing)

2007-06-28T15:17:12Z

Sperner's theorem

(Combinatorics, finite set theory:)

Sperner's theorem is an important example of extremal problems in finite combinatorics. It establishes a bound on the largest possible size of a (hopefully interesting) configuration.

What is the size of the largest possible antichain on {1,2,...,n}? As the antichain writeup shows, the set of all subsets of size k is an antichain. The size of this antichain is C_k,n=n!/(k!⋅(n-k)!). The largest such antichain (for even n) is attained when k=n/2. It turns out that this is, in fact, the largest possible antichain.

Theorem. The size of the largest possible antichain on {1,2,...,n} is
C_⌊n/2⌋,n = n!/(⌊n/2⌋!⋅⌈n/2⌉!)

Proofs of…

antichain (thing)

2007-06-21T08:45:41Z

(Combinatorics, Set Theory, Logic:)

In the combinatorics of sets, especially finite sets, an antichain is a family F of sets such that no member contains any other member:

∀x,y∈F. ¬(x⊂y)

More generally, we can define antichains whenever (P,<) is a poset (a partially ordered set). A subset F⊆P is an antichain if no two elements of F can be compared:

∀x,y∈F. ¬(x<y)

The definition for sets is a special case of the definition for posets (when the family F is a set): take the poset (F,⊂).

Examples.

Let S be a set and k a natural number. The set
F_k(S) = {x⊆S: |x|=k}
of all subsets of S of size k is an antichain.

…

virtual destructor (thing)

2007-06-04T12:40:16Z

(C++, and most likely only C++:)

A destructor that is virtual

In C++, a virtual destructor is a destructor that happens to be a virtual function (which see, if you'd like a recap of why member functions sometimes like to be virtual) . So, it gets called with (run time) polymorphism.

Why bother?

To apply run-time polymorphism in C++, you need to hold the object itself, via pointer or reference. If ever you copy an object to a variable of a base class, object slicing takes place and your new copy has that class.

Now suppose you want to write code like this:

      class X { /* ... */ };
      class Y : public X { /* ... */ };

      X* make_a_new_X(int);

      void f(int t) {
        X* px = make_a_new_x(t);
        // do stuff with px
        delete px;
      }

This code works…