This is a guest post by my brilliant friend Jeremy Kun, author of Math ∩ Programming. I would not have passed that geometry/topology prelim without him. Also, hello world! I’m in France!
I’ve always thought a recipe is kind of like an algorithm. And since I’m a theoretical computer scientist, you might imagine I’m a great cook (you’d be wrong!). So where’s the difference between algorithms and recipes? Let’s make baklava and find out.
Loosely speaking, an algorithm is a description of steps that can be used to take some input, like a number, and produce some output, like whether the number is prime. While algorithms seem a lot like recipes, there are some discrepancies between the two. The most apparent difference is that humans follow recipes and computers follow algorithms. Actually, this is a murky issue. The term “computer” originally referred to a human being who crunched numbers by hand. But even ignoring that, there is a programming language called Chef, in which every program takes the form of a recipe for a usually disgusting and often uncookable meal (try this recipe for fibonacci numbers). But even ignoring that there are many machines out there that do cook. Fast food chains will remove as much human intervention as possible to achieve uniformity, although they might not enjoy that image. I’ve even heard they add sugar to the salt they put on their French fries, but it’s a mystery how much (if you really wanted to find out, you could just do a binary search on the proportion of sugar used and compare tastes).
The real difference is that algorithms must be meticulously precise while recipes can be as vague as they like. “Beat the eggs,” “Let the meat rest,” “Microwave times may vary,” it’s all so arbitrary! When a recipe says “julienne the carrots,” what’s a poor computer like myself to do but print the following error message?
Traceback: File "salad-for-dummies.py", line 12, in <recipe> NameError: name 'julienne' is not defined
You’d be surprised how much time I spend trying to understand undefined variable bindings in conversation. It’s my curse and my finest weapon.
You see, the truth is that a recipe doesn’t always turn out the same every time. Even if you follow the recipe really closely, it’s tricky to time everything precisely, a lot of the operations are based on experiences which may differ by chef, and fresh ingredients will almost certainly be slightly different. That’s not to mention external factors like where you’re cooking or what tools you’re using.
An algorithm in the wild (on a physical computer) may suffer from the same problems, but algorithms exist outside reality. You don’t need a physical machine to come up with or follow an algorithm. But even in theory, algorithms don’t always work the same every time. One calls an algorithm that always produces the same result given the same input deterministic. Otherwise the terms are a bit varied. If the algorithm uses coin flips (random numbers) to help it make decisions then it’s called randomized. If you imagine an algorithm making all possible choices at any given step, it’s called nondeterministic. A nondeterministic algorithm “succeeds” if any of its branches of computation (some way to trace out which decisions are made in order) results in a successful result. For example, if I want to nondeterministically find a path from Chicago to Boston by road, at any intersection I could let my algorithm go straight and turn right and turn left. It should be clear that this algorithm will always find a path to Boston if there is one. It’s quite an interesting concept.
You might wonder whether nondeterminism actually adds any power to a computer. That is, are there any problems that can be solved using nondeterministic algorithms that can’t be solved with an old fashioned deterministic algorithm? Perhaps surprisingly the answer is no, but this depends on what one means by “power.” Indeed, if the power of a machine to compute stuff includes a notion of efficiency, for example how fast it finishes, then the question of whether nondeterminism gives us any more power than vanilla determinism is the biggest open problem theoretical computer science. You may have heard of it; it’s most common incarnation is called the P versus NP problem.
Unfortunately for me, I can’t nondeterministically follow a recipe in real life, or else I would always end up with at least one delicious meal. How many seconds do I let the meat rest? k seconds for all ! No, a recipe is more like a randomized algorithm in which I flip coins and guess how brown is brown enough.
In any case, today we’re going to make Torus-Knotted Baklava, and we’re going to do our best to make it as deterministic as possible.
To make Torus-Knotted Baklava, you’ll need the following ingredients:
- 1 (16 oz) package of phyllo dough, thawed overnight in the refridgerator or 2-3 hours before use.
- 2 damp hand towels.
- A 9×13 glass or metal baking dish.
- 1 lb chopped nuts (walnuts, or pick the nuts at random)
- 1 cup melted butter
- 1 cup sugar
- 1 cup water
- 1 tsp vanilla extract
- ¾ cup honey
- A paper and pencil
- 1 copy of The Knot Book
- 1 Wikipedia article on flood fill algorithms. For a purer taste, a text on graph search algorithms will do.
Start by chopping the nuts. Since nuts vary by weight, here is the volume of nuts I used.
The nuts should be chopped relatively finely, and you should aim for each piece in the end to be about the size of one eighth of a walnut.
Pour the nuts into a mixing bowl and add 1 tsp cinnamon. Cover and shake well.
Melt the butter and use it to grease the bottom of the baking dish. Open the pack of phyllo dough and unroll both rolls (usually there are two). Place one damp towel on the counter, and cover with the other damp towel. This will keep the phyllo dough from drying out and cracking as you work with it.
The process of layering the dough, butter, and nuts works as follows. I recommend having a sous chef help, because it takes a long time to do it alone. First, if needed, cut the phyllo dough so that each layer has the same dimensions as the baking pan. First place 7 +/- 1 layers on the bottom and, using your fingers, spread butter lightly on top of the dough. Then repeat the pattern of place two layers of phyllo dough into the pan at a time, alternating adding butter and nuts and just butter. The nuts should be layered sparingly, as in the diagram below. The top-most layer should have an additional 7 +/- 1.
Here’s the first layer:
Then a layer of nuts:
And the completed layering
To be completely clear, if b represents butter and n represents nuts, then the pattern is
7b, 2bn, 2b, 2bn … 2b, 2bn, 7b
Now comes the knotty part. Preheat the oven to 350 (check) and get out your pencil and paper. What we need to do is cut the baklava into pieces in the pan before baking it. Most boring people (non-mathematicians) would just cut horizontally and vertically, and maybe add some diagonals to make little triangle pieces. As a diagram it might look like this
How dreary. What we’re going to do is cut our baklava using two torus knots. For those non-topologists out there, this surface is a torus:
And a torus knot is just a closed loop on a torus. Here are two examples, the first provided for maximum coolness and the second for clarity.
There is a nicer way to draw a torus knot, and that’s by recognizing the torus as a quotient of a square. In particular (and we won’t do any hardcore math here), I can draw this square:
and glue the left and right edges together, and glue the top and bottom edges together as indicated by the colored arrows in the diagram. If I allow myself to stretch and bend the material, and I squint really hard, what I just described will give me back the torus. But then we can think of the square before gluing as the torus where we can walk to the top and teleport down to the bottom, and same for the left and right sides.
In particular, drawing a line which follows those teleoprtation rules and eventually makes it back to where it started, will give me a torus knot.
Call the number of times the line “teleports” from left to right, and the number of times it goes from top to bottom. By a nice classification theorem of torus knots up to wiggling the lines (officially, up to homotopy), we can describe all torus knots by these two numbers . The method is to associate to each torus knot a polynomial so that two knots which are the “same” have the same polynomials. So for example, the knot in the picture above is a (3,5) torus knot. For more examples of torus knots, see chapter 5 of The Knot Book.
We can pick any two torus knots (one diagonally to the left and one to the right) and use them to cut our baklava into pieces. We chose two “mirrored” knots so that the resulting lattice of diamond makes for nicely sized pieces. First we used toothpicks to measure where the cuts would start.
And then cut one torus knot:
And the second:
One nice feature of using torus knots instead of boring lattice cuts is that we can get thirty pieces (counting each of the boundary triangles as one half of a piece), and most of the pieces can still be squares! Imagine doing this using only vertical and horizontal cuts; since thirty has weird divisibility properties, it would require 6 cuts on one axis and 5 on the other, or 10 on one and 3 on the other. In either case, we’d get some oddly shaped pieces. I made this baklava for a party of 30 guests, so it worked out perfectly (and those guests who wanted smaller pieces could take the boundary triangles; mathematics is so convenient!).
Once you’ve designed a torus-knotting scheme and cut your baklava, place it in the oven for 50 minutes. While waiting we need to make the honey sauce. Bring the water and sugar to a boil in a small pot. Add the vanilla and honey and simmer for 20 minutes. Optionally add orange peel or lemon peel.
With the remaining half hour, read up on flood-fill algorithms. Once the baklava is done baking, take it out of the oven and immediately flood-fill the pan with the honey sauce. Let it sit until it’s cool enough to eat, and enjoy!