20 Apr 2012 - less than 1 minute read
I am reviewing material for the upcoming CSE638 exam, and here is a great lecture by Charles Leiserson on Universal Hashing & Perfect Hashing.
Read more20 Apr 2012 - less than 1 minute read
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.
Read more08 Apr 2012 - less than 1 minute read
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.
Read more