# Moore's Law v. a Better Algorithm

> Editing notes: The title is ~slightly misleading -- let's consider a better
> title?

Abstract:

Around 1992 I wrote a program to help me decide which anagrams were most
interesting, by examining the structure of the words and computing a score.
I used a brute-force algorithm, which was pretty slow; the program took a
few hours to run.

This year I learned a more sophisticated algorithm and implemented it. the
new program was super fast! But wait, is it fast just because it's a better
algorithm, or because I ran it on a 25-years-better computer?

I'll explain both algorithms and reveal the surprising results!

Timeline:

I'll spend a minute or two explaining the problem I wanted to solve, of
finding words that are anagrams of other words. It's very easy to do this,
but unfortunately most of the examples are boring. For instance, “hackles”
and “shackle”, or “hungover” and “overhung”. I will explain what is wrong
with these examples and the method I thought of to rule them out.

Then I'll briefly discuss the brute-force algorithm I implemented in 1992.
This is simple so it'll only take a minute.

I'll spend a few minutes explaining the better algorithm, which is fun: the
anagram problem can be transformed into a problem about finding a maximal
independent set in a certain graph. Explaining maximal independent sets
will take much less time than it might sound.

I'll reveal the results of the new algorithm. Then I'll reveal what
happened when I dug up the old code and ran it on new hardware.

Then I will philosophize for a minute or two about what we can learn from
all this.

I will also reveal the top-scoring anagrams.

----------------------------------------------------------------

2. Automatic Classification of Quilt Block Patterns

> Editing notes: Add an exclamation point!!

Abstract:

To make a quilt, you take a lot of small patches of fabric and sew them
together into larger patterns called blocks. Long ago I had the computer
generate every representative of a certain set of blocks, because I
suspected that there would be some cool blocks in the set that were rarely
seen. I was right! The set looks super cool.

Some of the blocks were very easy to tell apart, but the differences
between others were very subtle. I wondered if there was a way to get the
computer to classify the blocks into families where the blocks in each
family looked similar.

This is a very nebulous problem, underspecified and vague. Just the kind of
problem I like! The first thing I tried didn't work, but the second thing
did, and I will explain how it works, with many cool illustrations, and
explain some of the general problem-solving techniques that I use to solve
vague and poorly-specified problems like this one.

Timeline:

First I'll introduce quilt blocks and explain the family that I was
interested in, and show some pictures. I'll point out how some blocks have
common features, and others have so many common features that they are hard
to tell apart unless you look closely. This will take a couple of minutes.

I'll spend a minute talking about my first approach, which didn't work well.

Then I'll spend several minutes on my second idea: the abstract idea of the
strategy, and then how I fleshed out that abstract idea into an algorithm,
and then how I implemented the algorithm.

I'll spend the last couple of minutes showing the results, which I think
are successful: the computer successfully identifies blocks that humans
would consider similar looking.