Half-baked Inspiration

The Computer Science Circles project that I’m working on has a lot of exercises and content, but has not had very much practical information in terms of debugging and design. Today as a partial remedy, I wrote a lesson called Design, Debugging and Donuts and added it to the site. It was an excellent excuse to go to Tim Hortons for research purposes, which was certainly necessary to ensure that the pricing in the lesson was accurate. The lesson uses a couple of nice Creative Commons photos from flickr (by thisisbrianfisher and looking_and_learning):

If you are interested in giving your brain a minor workout, go check out the lesson and see if you can debug the sample code.

Tales of Tails

My colleague Adrian from Berlin has been visiting the University of Waterloo this month, and I was delighted this Friday to get to bring him to Hog Tails BBQ in Waterloo for a taste of something new. It’s new both for him, and for me! Real slow-smoked BBQ is a cuisine that didn’t exist at all in the Kitchener-Waterloo region until a couple of years ago and this is actually the first time that I’ve eaten it here… the closest that I’ve had is the venerable Phil’s Original BBQ in Toronto.

Hog Tails has itself. Tails of hogs, I mean. I have never seen them on a menu before so it seemed like a prudent idea to order some, just to be scientific. I also ordered ribs and wings, with sides of onion rings and collard greens… it’s pretty important to get your vegetables. Here is an animated .gif showing my order; look at the altitude on those rings!

In the picture above there are two tails on the bottom left-hand side of the plate. When eating the tails, which was a little weird, I had to put them in a mental category alongside ribs and wings: delicious meaty morsels which will be yours only after you put up a good fight against bone and cartilage. Here’s a close-up of the tails:

The taste and mouthfeel are very similar to ribs, but both of the tails also had a lump or two of fat that I had to pull away to get to the goodness underneath. The tails bent in a way that reminds me of asparagus, but the most unique part is that after eating them, you’re left with a string of miscellaneous pig bits that looks like this:

You can see at the top it looks almost like a spinal cord (and the second tail is just below). Overall, I would highly recommend the place; every component of our meals was very delicious, and the service and price were good too. It is an excellent dining experience if you want to feel like Fred Flintstone!

New Computer and the End of an Era

I bought a new laptop last month. A couple of criteria were important for me. First, I wanted my screen to be matte instead of glossy; second, I wanted an integrated video card that was pretty fast, let’s hypothetically say fast enough to play StarCraft 2. It was pretty helpful to use newegg for most of my searches, and notebookcheck for information about graphics card performance, but checking matte/glossy screens seemed possible only through a single website notebooksbilliger, which as maybe you could guess, is in German.

There weren’t any Lenovo machines that really met both of these criteria, my usual go-to brand; my searching brought me to Acer and Asus machines. I checked out some Asus machines in the store but found that they were pretty jangly: the form factor was plastic-feeling with a strange body shape.

I ended up buying an Acer machine called the TravelMate TimeLineX 6495TG-6818. It seems only to exist in Canada. I ordered from ca.buy.com which seemed to be known for their bad customer service… but I could only find a handful of retailers selling the machine at all. Well, it turns out the company does deserve their bad ratings, although in short I did eventually get the laptop. A lot of the trouble they caused with shipping has to do with the fact that they don’t actually ever keep the item in physical stock, rather they directly order the machine from a “drop-shipper.” In fact, when I ordered my machine  it looked like the “in stock” count from every seller I found in the country dropped from 5 to 4. Another bite of bad news is that the company only has a 1 year warranty and no possibility of an extended warranty.

So, although I am knocking on wood, the laptop is really pretty good and handles all of my work and non-work tasks very well. The battery life, when 3D graphics acceleration is not used, is around 5 hours! There was a fair amount of pre-installed crapware, but nothing difficult to remove. It’s my first-ever laptop to have an ISO keyboard, as shown in the photo above. I don’t have a clue how to access all of the five symbols \|}<> on a single key.

The photo above is the whole laptop. This brings me to the second part of my post. On my laptop I am looking at Cook’s Illustrated, a fantastic cooking magazine. I saw it for the first time last Fall, and read two issues of it so far. The coolest aspects of it, in my opinion, are that

1. it has absolutely no advertisements (other than for itself),
2. the illustrations are very attractive, hand-drawn (or at least, photoshopped to look hand-drawn? I can’t tell),
3. the recipe instructions are pretty meticulous and methodical, but focusing on getting good results rather than starting from fancy ingredients,
4. the tone and style of writing is extremely varied: it’s not all cut-and-dry imperative “Sift the flour.” but rather most of the recipes have a history/narrative and an overview of the experimenting the writer used to get it right.

In fact, items #1, #3, #4 remind me a lot of Good Eats, my favourite TV show of all time. It’s from Good Eats that I learned all sorts of day-to-day useful things about food, like making a steak or how to keep lettuce and herbs in your fridge. I thought today to look up whether there were any good new episodes, since I last caught up a couple of years ago. Tragedy of tragedies, the series is now finished! The last couple of specials were aired earlier this year. I am grateful for the host Alton Brown’s hard work on the series but I’ll miss it a lot!

Can Cook’s Illustrated be a suitable replacement? On the one hand, you can watch TV “in the background” of your living room while you’re doing something else. On the other hand, there is a more traditional way of multitasking with magazines, and it thankfully doesn’t involve bringing your TV into the bathroom.

Here are a few of my favourite recipes from the show.

• Meatloaf
• Sweet Potato Pie
• Hash Browns
• Corn Dogs

Thanks Alton, for making things that some shows treat as mundane, into delicacies in their own right!

holidays.happy()!

It has been great to be back in Toronto for the holidays! I have seen a lot of sorely-missed old friends and got great presents from my family (props to my brother’s megaman magnets). So far with Sara (who got me a wonderful coffee grinder) we have made:

• open-face apple pies… it was supposed to be topped but we had enough apples to fill two pies, and two bottomless ones worked out very well
• cinnamon rolls, from a great recipe my sister found years ago
• next planned baked good: biscochitos!

Foreground: Kindle DXG with myts-6 terminal. Background: Lebowski pants.

I also have had an opportunity to hack around a lot on my Kindle DXG (DX Graphite), which I got a few months ago. It is not one of the newest (e.g. ‘fire’) versions of the device, but it’s the most recent one of the large-screen versions, which for me is essential so that I can read my .pdf papers with ease. It has a great e-ink screen and displays grayscale beautifully.

I was pretty happy with the Kindle, but the thing that made me want to keep it for certain rather than possibly return it was that it has free internet access all over the world! Sort of. There is a browser, which can display text and basic images pretty competently. It supports a few aspects of JavaScript and CSS but mostly not. It has problems displaying pages that are larger than 1 MB. It’s best if I’m looking for a restaurant nearby, or trying to read my emails on the bus.

I previously installed the Duokan operating system, which has a much-improved .pdf reader (especially for 2-column documents) and lots of cool-looking Chinese text that I cannot read (but it’s not important). But, this week, I installed a new set of tools which are very neat:

• first, the ability to telnet into the kindle’s linux operating system over USB
• second, some cool screensavers of Samus and Megaman instead of the original bunch of famous authors
• third, a ‘launchpad’ to add custom commands (and make Duokan easier to use)
• finally, a terminal!

The terminal is really pretty amazing. It took a couple days’ worth of trial-and-error before I found the right version that actually works on the DXG, since there are about a dozen different types of kindles out there. I can’t say it has been very useful yet, but definitely playing with this computer was a great christmas toy.

For accessing the web, this opens a limited set of new possibilities. When you access the web with the normal browser, you can go to any web page you like, but you cannot download files like .pdfs and .mp3s to your machine. Through the command-line, it seems you can now actually download anything that you like so long as it is on an Amazon server. The photo of my kindle shows me after I successfully downloaded this pdf, this jpg of Kim-Jong Il looking at stuff, and this mp3. Note that both “amazon.com” and “s3.amazonaws.com” are fair game, but I don’t know of any connections that are possible.

So what possibilities are there other than downloading pictures of dead dictators from tumblr? I’m not really sure. But I have grown more fond of my Kindle over time. Having the ability to play .mp3s has helped, any my friend Mariel’s suggestion to use it in place of a magazine while on gym machines has been great. It’s been a pretty handy way to carry .pdf recipes around. Now that I can access linux, maybe I should install LaTeX on it? An old-school version of Maple?

Thanksgiving Turkeys Times Two

This post is a shout-out to several good friends who hosted me for thanksgiving. As such, I looked up the background on a well-known story: Canadian thanksgiving happens earlier than the American one because it’s colder and therefore the harvest happens earlier.

Wikipedia corroborates this but I was more interested in a link to Canada’s list of all previous individual dates of Thanksgiving. The strangest part to me is that between 1816 and 1849, it was celebrated by both Lower and Upper Canada exactly four times, both on the same years. I guess somebody was copying someone else’s good idea? The timing was a bit different back then, sometimes in February and May, and it was for a variety of different officially festive reasons, such as the “cessation of cholera” or the end of wars between Britain and France.

Although no government-sponsored reasons were so interesting this year, I did give thanks twice! Here are the stats:

	Canadian Thanksgiving	American Thanksgiving
I was in	Boston (America)	LA (America)
well technically,	Medford	Huntington Beach
visiting	Mike and Kathleen.	Jaime and Christina.
We ate	turkey	turkey
pictured being sliced by	Mike (above).	Jaime (below).
I contributed	whiskey	sweet potato pie, sweet potato pie casserole
and for the first time tried	crème brulée beer.	green bean casserole.
I got to see, for the first time,	Bohnanza.	an electric knife-saw.
Everything was	delicious!	delicious!

Thanks from Sara and me to all of you ladies and gentlemen for the edible hospitality! I have never cooked any bird larger than a chicken, but when I do I hope it flies as well as these two!

Better Know A Theorem: Online Matching

I saw a nice result sketched a few weeks ago, on the “online matching” problem. Below I try to re-explain the result, using some idiomatic (and as a bonus, inoffensive) terminology which I find makes it easier to remember what’s going on.

Online Matching. There is a set of items, call them Lunches, which you want to get eaten. There is a set of people who will arrive in a sequence, call them Diners. Each Diner is willing to eat certain Lunches but not others. Once a Diner shows up, you can give them any remaining Lunch they like, but that Lunch cannot be re-sold again. The prototypical problem is that a Diner might show up but you already sold all of the Lunches that they like. Your task: find a (randomized) strategy to maximize the (expected) number of Lunches sold, relative to the maximum Lunch-Diner matching size.

This is an online problem: you don’t have all the information about Diner preferences before the algorithm begins, and you need to start committing to decisions before you know everyone’s preferences in full.

Consider the following strategy:

Algorithm: pick a random ordering/permutation of the lunches; then when a diner arrives, give her the first available lunch in the ordering that she likes.

How does this perform? In expectation at least M*(1-1/e) lunches are sold, where M is the maximum (offline) matching size in the Lunch-Diner graph. But proving so is tricky. (This ratio 1-1/e turns out to be the best possible.) Birnbaum and Mathieu recently gave a simpler proof that this ratio is achieved. Amin Saberi, whose talk sketched this, rightly pointed out that it feels like a “proof from The Book!”

With a small lemma (e.g. Lemma 2 in Birnbaum-Mathieu), we may assume that the number of diners and lunches are equal, and that there is a perfect matching between diners and lunches. Let the number of diners and lunches each be n, and so M=n.

Let x_t be the probability that in a random lunch permutation, upon running Algorithm, the lunch in position t is eaten.

Experiment 1. Take a random lunch permutation. Score 1 if the lunch at position t is not eaten, 0 if it is eaten. The expected value of this experiment is 1-x_t.

Experiment 2. Take a random lunch permutation, and a random diner. Score 1 if that diner eats a lunch in one of the first t positions, 0 otherwise. The expected value of this experiment is (x₁ + … + x_t)/n.

The key is to show that the second experiment has expected value greater than or equal to the first one, then we are done via an easy calculation. We do this with a joint experiment, similar to “coupling” arguments.

Joint experiment. Let t be fixed. Take a random lunch permutation π₁, and look at the lunch L in position t. Let D be matched to L in the perfect matching. Obtain π₂ from π₁ by removing L and re-inserting L in a random position.

Key claim: π₂ and D are independent, uniformly distributed random variables. This implies that we can run both experiments at the same time using this joint distribution on π₁, π₂, L, D. Moreover,

Deterministic Lemma. For any π₁, and for an uneaten lunch L at position t in π₁, obtain π₂ from π₁ by removing L and re-inserting L in any position. Let D be matched to L in the perfect matching. Then in π₂, D eats one of the first t lunches.

This implies that whenever experiment 1 scores a point, so does experiment 2. So taking expectations,

(x₁ + … + x_t)/n ≥ 1-x_t.

This equation is the crux. Let x_≤t = x₁+…+x_t, then we see x_≤t ≥ (ⁿ/_n+1)(1+x_≤t-1). This recursion is easy to unravel and it gives a lower bound of n(1-(ⁿ/_n+1)ⁿ) ≥ n(1-1/e) on x_≤n, the expected size of the matching!

Best Food in Lausanne

I am very grateful to have got to live in Lausanne for the last year and a half. There are a lot of great people who I have met, and fantastic sights. But I would be negligent not to point out

The Best Food I Ate in Lausanne

Special events: Manneke Kris waffles. Cooked fresh to order, chewy on the inside, with a nice yeasty taste and Liège-style embedded sugar bits. One was bejeweled with cheese, ham and olives at the Montreux jazz festival this year!

Street food: hot dogs from Bretzelkönig. A delicious portable trio: a pretzel-dough bun, impaled to make a hole, with mustard squirted inside, and a hot dog plopped in.

Coffee beans: Pappy John’s (who also has amazing loose tea). If you are without equipment, a fine cup can be had at P’tit Bar by the cathedral.

Best sandwiches: paninis from Monopole in Place Chauderon. The chicken paninis are made from actual chunks of real roasted chickens, not processed meat! (Pro: tasty skin, con: occassional bones.)

Best restaurant: Nandanam Indian restaurant by the train station.

Best brunch, best fondue: Café de Grancy has fantastic ambiance in a surprisingly peaceful sous-gare location. Café de l’Éveche also had a great fondue without being too greasy.

Best burger: l’Étoile Blanche if you want to sit down for a meal, The Great Escape if you want to hang outdoors on a patio with ample beer, Holy Cow for a guilty pleasure at lunch.

Best beer: Brasserie du Château is the best brewpub and has the best late night food, while Mise en Bière is the best bottle store. Satellite at EPFL is also pretty fantastic in the limited hours that they are open. Docteur Gab is a very good local brewery. I discovered Bar Tabac on my last evening, which has a great selection of Belgian beers.

Best ice cream: Veneta; I visited two of their locations, on the Ouchy pier and in the town of Gruyères. Fleur du Lait is made from the crème de la crème of crème, and they have a Swiss specialty flavour “Lackerli” which was especially good, with cinnamon and other spice flavours.

Best chocolate: Villars (see last post); for an actual restaurant in Lausanne, have spoonfuls of “hot chocolate” (chocolat chaud épais) at La Barbare.

Best bakery/patisserie: tragically my two favourite ones shut down while I was here, replaced by non-pastry stores… but Fleur de Pain is pretty good, it has locations in Ouchy, Morges, and sometimes a truck at EPFL.

Unavoidable and unforgettable: Les Brasseurs, with its metre-high columns of beer, plus Röstis and flammenkuchen of every imaginable variety. This place I will mainly miss since I got to share the offerings with many great companions… the friends make the meal here.

Click here for the map of edible Lausanne!

Fribourg

This was my last full weekend in Switzerland, and I used part of it to visit nearby Fribourg. The main reason: chocolate! My favourite Swiss chocolate company, Villars, was founded, operates, and offers their only boutique/café in Fribourg. (It is not a chocolate factory, no oompa-loompas, for that you have to go to la Maison Cailler in nearby Broc-Fabrique.) I was not disappointed: they had chocolate-covered marshmallow goo (pictured at left), 2.5-kilogram bags of napolitain bite-size bars, saffron ganache pralines (also basil, star anise, and others), chocolate bread, hot chocolate, chocolate cows, books on chocolate, et cetera et cetera. It was very tasty… the reason which I first got into Villars is that they had the shortest list of ingredients out of the major brands, so I think it tastes more like true chocolate and not finely-tuned chemicals… not that I am an expert at that.

At right, you can see they used to have some chocolate cross-promotion with the United Nations! See more pictures in my Picasa album here. It also gave me a good excuse to edit the wikitravel websites in English and French for Fribourg, as shamefully, neither one previously mentioned the Villars boutique.

In the rest of the city, the main landmark is St. Nicolas’ church, which you can see from every point in the city. I didn’t know anything non-chocolatey about the city upon arrival but the sight of this towering behemoth in the distance made me walk towards it. In fact you can climb ~75m to the top, which was exhausting and rewarding in terms of the view. Even after leaving the church, the day was filled with ups and downs, since the city’s topography consists of hills, cliffs, valleys and deep rivers. I have always thought that Lausanne was a uniquely 3-dimensional city (you can see where you want to go, but not be able to get there since the graph is non-planar) but Fribourg is perhaps even more 3D. Compared to these two, the North American cities where I have lived feel like this:

I had some very tasty crepes (bacon, cheese, spinach) before heading back to Lausanne, enjoying my remaining partially-melted (but completely-delicious) chocolates on the way.

The Lazy Gourmet

In the last year, I have learned two excellent recipes that are amazing in terms of their deliciousness and simplicity. The internet being a great place to share great ideas, I hereby present you with:

• No-Knead Bread. Mix flour, salt, water, and yeast in the evening. Overnight the yeast will do the hard work. In the morning, transfer to a pan. Bake and enjoy.
• Cold-Brewed Coffee. Mix coffee grounds with water. Let sit overnight and strain. Gives a batch of concentrated brew. Add to cold/hot water/milk for tasty coffee.

Salivating? Here are the more detailed recipes.

No-Knead Bread

1. Mix 3 cups of flour (pictured: 50% white, 50% whole wheat) with 1/2 tsp of yeast and 1 tsp of salt.
2. Add between 350 and 450 mL of water, stirring. Stop once it is quite wet, yet possible for you to pick up and hold together in one piece.
3. Sit overnight, covered with a clean kitchen cloth, 12 to 18 hours.*
4. Move in one piece to a well-oiled loaf pan and let sit 2 more hours.
5. Cover top loosely with foil and bake in a pre-heated 460F/240C oven.
6. Remove foil and cook approx 15 more minutes or until solid with a hard dark top, but not burnt.
7. Important: Let cool for 30 min-1 hr to solidify. (This is the hardest step.)

*: The bread sits. You lay down and sleep, covered with a clean blanket.

Cold-Brewed Coffee

1. Put 170g (about 1 cup) of normal or coarse-ground coffee in a 1L french press / bodum / glass jar.
2. Add room temperature water half-way and stir until everything is saturated. Fresh grounds may bubble; let sit 5 minutes.
3. Fill to top with room temperature water and stir again.
4. Cover and let sit overnight, about 12 hours.
5. In the morning, press / strain out the goodness.
6. Store the resulting concentrate in the fridge. Use about an ounce per coffee. Keeps for 1-2 weeks.

According to online info about cold-filtering, some people say there is less acidity in cold-filtered coffee. Some claim that it makes the cheapest possible store grounds taste great. I am not sure about this but I think in general it’s hard to mess up. Be aware that the concentrate will probably have some silt at the bottom after sitting in the fridge all week, unless you have used a hard-core filter.

My potatoes have a chance!

Could my Julia Child number become finite? I have a recipe in an online contest, with voting until Sunday June 26:

http://www.chow.com/food-news/84327/vote-now-for-the-chow-recipe-challenge-best-picnic-side/

I previously saw some contest on their website about muffins, and I was glad to enter this one since it gave me an excuse to test-drive the recipe at a BBQ last week. In particular if you have not tried tarragon very much, this is a nice salad to see how it behaves.

If you’re reading this by Sunday June 26 you can vote for the recipe via the link above.