### 5 Kitchener-Waterloo Coffee Mini-Reviews

30Dec13

Some information that I can share from my itinerant wifi-migrant existence over the past couple of days:

• Matter of Taste: Wins for being local and making good espresso. Weak in the baked goods department.
• Balzac’s: Wins for design aesthetic, nice typesetting. Good pastries. Is colocated with Google and other tech companies. Looks like a hipster paradise.
• Death Valley’s Little Brother: Actually is a hipster paradise. Best place to get coffee and whiskey. Good muffins. Plain espresso is a little sketchy.
• City Cafe: Wins for honor-system payments, wood-fired pizzas and bagels, and great donuts and tarts. No espresso. Hippies, not hipsters.
• Misty Mountain Coffee: After DVLB, second-comfiest chairs. Strengths: not as bad as Coffee Culture across the street.

Happy caffeinated holidays!

### Delicious Faal / فال گرفتن

28Nov13

I have been taking a Farsi class (کلاس فارسی) this semester at Princeton, gradually learning enough of the alphabet and grammar that when I go to Iran, I won’t be completely illiterate!

On Monday, we learned about faal, which is opening the famous book of poetry by Hafez to a random page and using it as your fortune. Then on Tuesday, the last day before break, our teacher brought in pomegranates (anaar, انار) with poems written on it for our own fal. Definitely much more tasty than the usual medium of paper for these poems!

Learning Farsi has been challenging and interesting. In increasing order of difficulty, some of the steps are:

• writing right-to-left (simple enough, I like symmetry)
• learning a new alphabet (ok, at least there’s only 32 letters, and I don’t have to learn capitals)
• unpronounceable letters like ﻉ (sounds like the hyphen in uh-oh)
• leaving out most of the vowels when you write.

Later I’m hoping to create a short Farsi pangram (sentence using all the letters of the alphabet). Wikipedia already knows one:

بر اثر چنین تلقین و شستشوی مغزی جامعی، سطح و پایه‌ی ذهن و فهم و نظر بعضی اشخاص واژگونه و معکوس می‌شود

Maybe I can find a shorter one using only vocabulary from the course. Anyway, I’m thankful both for pomegranates and for written vowels in English. Happy Thanksgiving and Chanukah!

### Pascal’s rule for Beta functions

27Oct13

Recently I became acquainted something called the Beta function. It is defined in terms of the Gamma function (a continuous generalization of the factorial function):

$\displaystyle \mathsf{B}(x, y) = \frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}$

The first thing I’m tempted to do here is try to write this in terms of a binomial coefficient. If we replace each $\Gamma(x)$ by the (equivalent for integers) $(x-1)!$, then we get

$\displaystyle \mathsf{B}(x, y) = \frac{(x-1)!(y-1)!}{(x+y-1)!}$

$\displaystyle = \binom{x+y-2}{x-1}^{-1}(x+y-1)^{-1}$

Now I’m more happy since I see an expression in terms of things I understand. But I would also like to know: is there a simple recurrence relation between the Beta function values, similar to Pascal’s rule $\tbinom{n+1}{k+1} = \tbinom{n}{k+1}+\tbinom{n}{k}$? It seems a little hopeless, since these guys are not only reciprocals, but they have the additional term $(x+y-1)$ complicating things.

Surprisingly, these two complications work with each other in some way and permit a really beautiful recurrence relation

$\displaystyle\mathsf{B}(x,y)=\mathsf{B}(x,y+1)+\mathsf{B}(x+1,y)$

which is even symmetric! You can prove this using the same simple algebraic approach that you can use to prove Pascal’s rule:

$\displaystyle\mathsf{B}(x,y+1)+\mathsf{B}(x+1,y)$

$\displaystyle=\frac{\Gamma(x+y+1)}{\Gamma(x)\Gamma(y+1)}+\frac{\Gamma(x+y+1)}{\Gamma(x+1)\Gamma(y)}$

$\displaystyle = \frac{y}{x+y}\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}+\frac{x}{x+y}\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}$

which is just the definition of $\mathsf{B}(x, y)$ when you group the terms.

When you learn about Pascal’s rule in a combinatorics class, you learn not only the simple algebraic proof in the above vein, but also the combinatorial “proof from the book:” the number of ways to pick k+1 things from n+1 involves the initial choice of including the initial item (leaving k things to pick from n things) or excluding the initial item (leaving k+1 things to pick from n things). Is there a similarly slick proof of this Beta function identity?

### Quote from Turing

30Aug13

I am slowly making my way through Andrew Hodges’ biography of Alan Turing, which I bought electronically last year (the Turing centennial year). It’s a great book, and is simultaneously teaching me about the history of computing machines, the history of cryptography, and World War 2, as well as about the title character. Here’s a part that I read today:

In general the arrangement of the memory on an infinite tape is unsatisfactory on a practical machine, because of the large amount of time which is liable to be spent in shifting up and down the tape to reach the point at which a particular point of information required at the moment is stored. Thus a problem might easily need a storage of 3 million entries, and if each entry was equally likely to be the next required the average journey up the tape would be through a million entries, and this would be intolerable. One needs some form of memory with which any required entry can be reached at short notice. This difficulty presumably used to worry the Egyptians when their books were written on papyrus scrolls.

This is part of a talk by Alan himself, from February 1947.

### CS Circles is Open-Source!

29Aug13

Computer Science Circles is now fully open-source! Over the summer, we put the backend code up on GitHub and provided links to the lesson and exercise definitions on the website. A SIGCSE Special Projects grant made this work possible, for which we’re very grateful.

One thing we learned as a result is that open-sourcing has surprising applications. We found that there is an educational service running in a correctional facility that wanted to run CS Circles but could not provide internet access to their users. It is now up and running!

Over the summer we also integrated the work of George Okeowo to provide more meaningful hints for the most common error messages, we upgraded the awesome CodeMirror and OnlinePythonTutor libraries, and we integrated better management tools for teachers and administrators.

Using WordPress as our base content management system has been extremely helpful. The fact that it is open-source and fully hackable has helped in many ways, since you can fully debug things at any level you choose, and see how the internals are put together to learn from them. I’ve mostly found that when we want to add something new there is a built-in hook for it, and even if not we often can exploit the fact that JavaScript is transparent to permit new code to fix old code in arbitrary ways (for example, to fix a spacing bug in the Visual and Text editors).

WordPress also “just works” for a good fraction of what we need it to do, for example it was able to export and import page content without any hassles (except it had a problem with backslashes! but happily a patch for this is making its way through the bug trac system).

Where is WordPress flaky? It doesn’t allow square brackets in the shortcodes that it uses to extend HTML functionality, so we had to write sweetcodes to make up for it. It is sort of a pain to write admin pages since the API seems to have changed several times and all of the versions are mangled together in the documentation. And it uses PHP, the fractal of bad design.

It is worth the flakiness though, to get things like the awesome polylang plugin that seamlessly let us work with translators to publish the site in French and German. I would not have wanted to write translation code by myself!

If you are interested in seeing how CS Circles works, writing content, or running your own version, visit

http://cscircles.cemc.uwaterloo.ca/source/

Now that this is launched, I will be getting back into Java-mode as I start to coordinate, teach, and develop software for the introductory programming course here at Princeton. The Java visualizer is still up and running but my next goal is to create online fill-in-the blank exercises that mirror paper handouts currently in use.

### Doodlr and SPE

07Aug13

I spent some time earlier this summer mentoring two undergraduates, Pallavi Koppol and Joanna Wang, who built a really cool HTML-based drawing program called Doodlr. Its main features are (1) simultaneous drawing by multiple users, (2) opacity/transparency, and (3) support for Wacom tablets. If you check it out now at

http://doodlr-spe.herokuapp.com/

you can even see a vampire moose that I made on the demo day. See the about us! button there for more information.

Joanna and Pallavi used several technologies that I did not know about before this summer:

• HTML5 canvases; they are very flexible in terms of transparency and compositing operations (like erasing)
• Node.js, a tiny web server that uses JavaScript for the server-side language
• websockets, which are persistent client/server connections for a website, in which the major technological advance is that the server can push information to the client.

It was a pleasure to work with both of the students and it was really amazing to see how much could be accomplished from concept to working code in only 6 weeks. Check out the source code here on GitHub.

### Nice Quote

06Aug13

Paraphrased from a paper by Eglash, Gilbert and Foster about software education tools:

We should caution that it is largely the teacher and students who create the learning environment; the simulations are simply tools to facilitate these connections.

As someone who makes a lot of software for education, I was glad to see someone mention this crucial fact!