I am reviewing material for the upcoming CSE638 exam, and here is a great lecture by Charles Leiserson on Universal Hashing & Perfect Hashing.

Chernoff Bounds is a great tool that we learnt in CSE638. The foundation for which was laid with the great Balls-and-Bins stuff we did in CSE548.

Here are some exercises for Chernoff Bounds and Probability.

We know that we can solve this problem using Suffix Arrays and Suffix Trees in Linear Time, but its not all that nice. I will probably like to implement the components of those some time. But there is a much nicer and simpler algorithm, called “Manacher’s Algorithm” that I had known, but never bothered reading up on. Dhruv, today shared a link which explained it brilliantly. Here it is.

I will try to solve NUMOFPAL on SPOJ using Manacher’s. I might also do EPALIN, which I already did earlier using an approach similar to Karp-Rabin.

Update: I solved NUMOFPAL using Manacher’s.