Monday, October 28, 2013

Calculating Integer Partitions

This post can serve as a nice interview question. Because some problems can be deceptively simple. Knowing the formula MAY NOT be enough to write an algorithm to compute it. Allow me to explain using the example of Integer Partitions. If you want the explanation on how this formula is derived, you can read it here.

To recap, Integer Partitions of a number, are ways the number can be expressed as sum of smaller numbers. And, P(N), the number of integer partitions of a positive integer N can be expressed as
P(N) = PP(N,1) = PP(N-1, 1) + PP(N, 2)
Where PP(N,k) is the number of partitions in which the smallest addend is at least k. And
PP(N,k) = 0 if N < k
PP(N,k) = 1 if N = k
otherwise
PP(N,k) = PP(N-k,k) + PP(N,k+1)

Here is how it can serve as an interview question to test the programming skills. The “natural” recursive solution can be easily implemented as follows.

public static int recursivePP (int N, int k) {
    if ( N <= 0 ) return 0 ;
    if ( N < k ) return 0 ;
    if ( N == k ) return 1 ;
    return recursivePP(N-k, k) + recursivePP(N, k+1) ;
}

This is grossly inefficient. Because intermediate results are unnecessarily computed multiple times. Every time the recursion reaches a particular pair (a,b) it will issue another recursion and calculate it all over again. So the code is natural, but not smart. It would take forever to compute say P(100) this way. What’s needed is a solution based on dynamic programming that builds P(i) as i goes from 1 to N. To do that we need to store the table of values for P(N,k).

Consider the following code.
public static long[][] PPvalues = new long[100][100] ;

public static long iterativePP (int N) {

    if ( N <= 0 ) return 0 ;

    // init P(N,k) for N=1, k=1
    PPvalues[1][1] = 1 ;

    for (int i = 1 ; i <= N ; i++) {
       
    // mark PP(N,k) where N == k
    PPvalues[i][i] = 1 ;

    for (int j = i-1 ; j > 0 ; j--) {

        long pp1 = ((i-j) < j) ? 0 : PPvalues[i-j][j] ;
        long pp2 = (i < (j+1)) ? 0 : PPvalues[i][j+1] ;
        PPvalues[i][j] = pp1 + pp2 ;

    } //
    } //

    return PPvalues[N][1] ;
}

Now this performs incredibly faster than the recursive solution. O(N^2) is not ideal, but it’s not bad either. This answer should usually be enough for an interview question.

Unfortunately, it’s not enough for finding out the value of P(N) for large values of N. The reason is the memory complexity of the algorithm which is also O(N^2), and our computers have a very finite memory.  For example, even with 8G of RAM I could not calculate the value of P(10000) because there is simply not enough memory to allocate the table.

That was a real bummer. There is no quick and easy way to optimize this to take less memory. Using a better data structure to store only half the table, as P(N,k) = 0 for N < k, of course won’t help much, only by a factor of 2.

One possibility is to compute only a section of the table at any given time. Note that the formula requires only the current column and the previous column, to calculate the value of any cell. You can start from last 2 (rightmost) columns, and keep computing the table leftwards. So you have to store only 2 columns (current and previous), thus significantly reducing memory. That’s a good optimization. The resulting code will be too complex for an interview question though.

Fortunately, there is a better formula for coming up with an algorithm to calculate integer partitions. It is based on pentagonal numbers. But that’s a math question, not a programming question. I will explain that in another blog post.

Monday, October 14, 2013

Boardwalk Empire

Review : Boardwalk Empire
Aired on HBO (2010, 2011, 2012, 2013)
My Rating : 8 out of 10

There was a time when I had no patience for spending many hours to watch a seemingly endless storyline of a TV series. There is always a worry that so much investment of time may not be worth it in the end. That has changed now due to the quality, as well as easy availability of the content. For a well made series, the length becomes an advantage, as characters and subplots can be fully developed, to make it a very satisfying viewing experience.

The pilot for Boardwalk Empire was directed by Martin Scorsese. It was heavily promoted and reportedly is the costliest pilot ever. It was fabulous, and I got totally hooked onto it. I have watched the first 3 seasons live, and this is a combined review for all.

It’s hard to give a concise synopsis of a story that so far has had 35 plus hours of screen-time, and it’s not even necessary. At its core, Boardwalk Empire is a gangster story. But it’s not just a long Irish version of Godfather. Stylistically it’s closer to Goodfellas. There is no one single plot here. The series revolves around ambitions and internal conflicts of every character punctuated by the ever changing alliances of convenience and double crossings.

The premise is loosely based on historical facts of prohibition era Atlantic City, and its powerful political boss of Irish origin Enoch Johnson, named Enoch “Nucky” Thompson here. Nucky (Steve Buscemi) has the complete control of the city - as the gangster boss, leader of the bootlegging operation, city treasurer and a socialite who throws lavish parties. As a help, his brother Eli (Shea Whigham) is the sheriff. A returned war veteran Jimmy Darmody (Michael Pitt) is Nucky’s lieutenant. Chalky White (Michael Kenneth Williams), leader of the local black gang, runs the bootlegging operation for Nucky. A federal agent Nelson Van Alden (Michael Shannon) comes to New Jersey to investigate the rampant violations related to sale of alcohol. Nucky meanwhile falls for the beautiful housewife Margaret (Kelly Macdonald). These are just the some of the main characters that live in the Atlantic City. There are others, from the Jewish gang of Arnold Rothstein (Michael Stuhlbarg) from New York, and the Italians from Chicago including a budding Al Capone (Stephen Graham).

The list of characters may seem rather large, but each one is fully developed. This character development, along with the superlative acting by each is reason enough to be glued to this series. But there are many other strengths. I can guarantee that you would be impressed by the smartness of the dialogues. How often do you pay attention to the music of a TV serial ? You will do that here. It is superb. The production is simply magnificent. It works quite well as a period drama too.

The central character is of course Nucky Thompson, played by Steve Buscemi, the only widely known actor in the entire cast. As an authoritative leader, Nucky is amoral but not irrational. Steve Buscemi brings out all the different shades of the character, and there are many. As the series progresses we learn more and more about him, and other characters. Every actor gives his or her best, and it’s hard to pick a favorite. I can assure you that you will like a few characters so much, that you would complain that they needed more screentime. Which ones, depends on you.

This is a great series but it’s not perfect. It suffers from the same trap every series suffers. The desire to extend it, and keep it running. That requires infusion of completely new characters, and some improbable turns. In spite of that, repetitiveness is unavoidable. In an ideal world, every good series will conclude at the right time. In this world, the temptation to squeeze more money out of the same formula trumps artistic integrity. I wasn’t happy with the 3rd season, for these exact reasons, although it was no less captivating. On the same note, I am perplexed about the current season 4. What more is left to be shown that can be called new?

I highly recommend watching this series. It feels like watching an Oscar calibre movie. I am obliged to include a strong warning. This is not for the faint of the heart. It’s about gangs, correctly rated as TV-MA. You should know what that means before you decide to watch it.

Related Posts Plugin for WordPress, Blogger...