This blog has moved to Medium

Subscribe via email


1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

Posts tagged ‘Computer Science’

My Master thesis is now locked!

I wrote my master thesis in computer science 4.5 years ago, and it was published by my universitry, the Technion. It was always very Googlable – just Google for “Ron Gross master thesis”.

Well, I happened to do this exact Google search today, and found the correct Technion webpage with my abstract, clicked on “Full Thesis Text” to download the PDF … and found that my thesis is now access-locked outside of the Technion network!

What the fuck?

I hate academic censorship. My thesis might or might not be relevant to someone out there (someone actually cited it a few years ago), but there is no reason to have it locked. I did find another technion page that provided full access, but who knows … that might be gone tomorrow as well.

Luckily, I have of course saved a full copy of my thesis in my trusty old gmail. So, for posterity, if you happen to be interested in “Invariance Under Stuttering in Branching-Time Temporal Logic“, go right ahead and download it. Free as beer, and free speach. No subscription required.

BTW, I’m a proponent of the Higher education bubble hypothesis.

Programming – The art of giving percise instructions

I have a friend that likes riddling me riddles, kind of like a sphinx.
The last riddle, out of a computer science course, asked to solve programatically the following problem:

You are in a lattice, at some position (x,y), with x>=0 & y>=0. How many different routes do you have for reaching the origin (0,0), where in each step you either go one unit down, or go one unit left?

I found three solutions, each better in time complexity than the previous one:

Solution 1 – Just translate the question

As the title of this post claims, a great deal of the magic of programming is knowing how to translate problems from human language to machine language. The first algorithm should be straight forward – just do as a human would:

public long CountWays1(int x, int y)
{
  if (x == 0 || y ==0)
  {
    // you've reached the edge of the positive quadrant
    // only one way from here - either straight down or straight left
    return 1;
  }
 
  // else, we're somewhere with x>=1 and y>=1.
  return
    // Either you go down now
    CountWays1(x, y-1) +
    // Or you go left
    CountWays1(x-1, y);
}

It’s easy to verify this solves the problem. No magic involved, just take the literal description of the problem and turn it into a language a computer will understand.

Solution 2 – Add a little cache

A quick complexity analysis will reveal actually running this program on not too large inputs will never complete. The solution is hyper-exponential (grows faster than 2^(x+y)). This is because the same sub problem is computed over and over again. When calculating CountWays1(40,40), you will calculate CountWays1(20,20) many times over again (I’m ignoring integer overflow for the sake of discussion). This can be solved by adding a cache, or memory, to our solution:

public long CountWays2(int x, int y)
{
  long[,] solutions = new long[x,y];
  return CountWays2Impl(x, y, solutions);
}
 
private long CountWays2Impl(int x, int y, long[,] solutions)
{
  if (x == 0 || y ==0)
  {
    // you've reached the edge of the positive quadrant
    // only one way from here - either straight down or straight left
    return 1;
  }
 
  // !!! Change from CountWays1 !!!
  if (solutions[x,y] != 0)
  {
    // we already know the solution for (x,y), let's not recalculate it
    return solutions[x,y];
  }
 
  // else, we're somewhere with x>=1 and y>=1, and you don't know the answer yet
  long solution =
    // Either you go down now
    CountWays1(x, y-1, solutions) +
    // Or you go left
    CountWays1(x-1, y, solutions);
 
  // !!! Change from CountWays1 !!!
  // We found the solution for (x,y), let's store the result in the array to avoid recalculations
  solutions[x,y] = solution;
  return solution;
}

In fact, this solution is so simple it can be “coded” in an Excel sheet. Just put 1 in the first row & column, put “=A2+B1” in the (2,2) cell, and copy this formula to all other cells.

The time and space complexity of this solution is O(x*y) – the size of our matrix, where filling every cell in it takes a constant amount of steps.

Solution 3 – Remember Pascal

After playing with Excel and actually calculated some values, I remembered this problem is actually equivalent to Pascal’s Triangle



An association every programmer should have for Pascal’s Triangle is combinatorics. If you think about the problem in terms of combinatorics instead computer science, you’ll see the solution is actually the total number of ways one can order a certain sequence of actions of length X+Y:

In X+Y moves, you will reach the origin (unless you step out of the positive quadrant). Every move is either Down or Left, so to get the number of ways you can calculate the total number of different orders of length X+Y, where every item is either Down or Left, and you have exactly X number of Lefts and Y number of Downs.

The number of ways to order a sequence of length X+Y is (X+Y)! Then, we divide by the number of ways to order the Left actions (X!), and by the number of ways to order the Down actions (Y!). This is because our initial number (X+Y)! counted the sequence “Left, Left, Down” twice.

So the most efficient way to answer the riddle is simply this:

public long CountWays3(int x, int y)
{
  return Factorial(x+y)/Factorial(x)/Factorial(y);
}
 
private long Factorial(int x)
{
  if (x <= 1)
    return 1;
 
  return x*Factorial(x-1);
}

(Note this is Tail Recursion, so don’t give me arguments about inefficient recursion – this can be optimized into a loop by the compiler).

How sorting works

A very cool visual demonstration how various sorting algorithms work on different inputs.

A Cartoon Proof of Löb’s Theorem

Recommended for hardcore logicians only (or just people who like to think).

Löb’s Theorem apparently states that "if it is provable that ‘if X is provable, then X’, then X itself is provable". The cartoon helps you (just a bit) to avoid getting trapped in an endless loop of logic.

There’s also a bonus exercise at the end, quite refreshing.

Thesis Complete!

Finally, after years of research, months of writing and correcting, and weeks of bureaucracy, I finished my M.Sc thesis!

Robot Dog

A bit scary, but very cool.

The On-Line Encyclopedia of Integer Sequences

I was trying to answer this question – how many labeled rooted trees with n nodes are there?

A quick search didn’t find the answer (I’m sure a more detailed search would have). Then I had this idea – find the answer for small values of n, and look in the OEIS. I typed 1,2,9,64 in the search and quickly found the answer (which is n^(n-1) for those interested). I thought about it for a couple of minutes but still hadn’t come up with an answer as to why this is true.

Google Publication Fumble

Update – it appears the link I gave is simply a table of contents of an ACM symposium. So where is the actual paper?

One of the feeds I recently subscribed to is Papers Written by Googlers, (the web version is here). Apparently every link on the page is to some Google search instead of a definite link to a paper. I wanted to check out a paper titled Towards Temporal Web Search, by Marius Pasca and got a strange result page containing totally unrelated papers. Only the focused search I ran myself for the exact title gave me the actual article.