Prof. Michael Bender showed us a neat trick when presenting graphs in talks.

Often, we do experiments with Data-Structures and Algorithms, and we want to show that the cost of doing blah with the foo bar data structure, is $O(n)$ (which means that if we plot the actual cost against the value $n$, we should get a straight line).

Okay. What intuition do you have for something which costs $O(n\log{n})$. I would say its slope is somewhere between a line and a parabola. But how does the audience visually verify this instantly when seeing the graph?

On the y-axis, you do not plot the actual cost, but plot the ratio of the actual cost to the value that you expected, and show that the ratio is constant.

This is how we plotted something that we expected to be $O(n\log\^2{n})$:

It was perfectly clear that the ratio is almost constant, and hence our hypothesis was correct.

Prof. Bender calls Data Structures as Crystallized Algorithms, and Algorithms as Defrosted Data Structures :)

Problem: I need to maintain state for a function. In simpler and analogous terms, what static member variables do for a class, I want something to do the same for functions.

Solution: See the JavaScript code below:

1
2
3
4

function foo() {
    var x = 0;
    return function () { return ++x; };
}

I tried this in nodejs, and here is the output:

1
2
3
4
5
6
7
8

> bar = foo()
[Function]
> bar()
1
> bar()
2
> bar()
3

The function foo returns a function which returns an incremented value of x. At first glance, to C/C++ programmers, this looks weird, because x, is a variable declared in foo, so how would the returned function have access to x?

Firstly, in JS, a variable continues to live, as long as there is a reference to it. So, as long as the returned function is referenced by someone, its copy of x is referenced, and it continues to live.

Secondly, what we are doing, is a concept called a Closure.

Quoting the Wikipedia article verbatim here:

A closure allows a function to access variables outside its immediate lexical scope. An upvalue is a free variable that has been bound (closed over) with a closure.

This is pretty clear. The upvalue here is x.

The referencing environment binds the nonlocal names to the corresponding variables in scope at the time the closure is created, additionally extending their lifetime to at least as long as the lifetime of the closure itself.

So, the copy of x that the function refers to, lives on.

When the closure is entered at a later time, possibly from a different scope, the function is executed with its non-local variables referring to the ones captured by the closure.

This is what is happening when I execute the returned function.

This was an introductory post to Closures in JS, here is a much better and well-motivated post.

Again, the Nirvana is courtesy Dhruv :-)