Monday, September 03, 2012

Algorithms beyond school

I was working on a list of algorithms a new college graduate ought to know to either

  • Do well in an interview
  • Make quick progress through the learning curve

Here is the list I have so far, I would appreciate comments on what else to add

  1. Population Counting
  2. Multi-precision Arithmetic
  3. Fast Fourier Transform
  4. Fast Prime Number Generation
  5. Quicksort
  6. Union-Find
  7. String searching (KMP, Regular Expressions)
  8. Polynomial Multiplication
  9. Calculation of Pi
  10. 8 Queens Problem
  11. Instance of a turing machine simulation
  12. Tries
  13. Radix Tree
  14. Red Black Tree
  15. Huffman's algorithm
  16. Graphs - DFS, BFS
  17. Graphs - Bipartite
  18. Minimum Spanning Tree
  19. Hashing algorithms
  20. Linear programming?
  21. Classes of problems - P/NP/?
  22. Vertex Cover?
  23. Synchronization (locks/mutex/spin locks)
  24. Lockless algorithms
How does the list look?

Thursday, April 19, 2012

A night that stole more than just my sleep

What a night.. I lost all useful data on my desktop due to (a) lack of sleep (b) eagerness to install Fedora 17 Beta. How this happened is a long story, but here is the sequence of events

  1. I saw Fedora 17 Beta (got excited with the new release features)
  2. Got excited and upgraded my Fedora 15 (that I had maintained since Fedora 10 and kept doing upgrades) to Fedora 17
  3. Neither ATI proprietary nor the open source drivers work
  4. I decide to reinstall Fedora - Except that I used my home partition as root partition. I've lost all my scanned documents, my open source repositories (so many of them) :(. My programming, my SDK's, my projects, my articles, my documents, my downloads... I am going to cry. Moral of the story, backup is not for dummies, it is for everyone! Anyway, I am too arrogant to backup, even now :) Leave me alone!
  5. On the reinstalled partition, I am back to (c)
  6. Today, after extensive debugging I find out all my xorg.conf hacks don't work -- why? Apparently X has gotten smarter and needs additional options to enable specific monitor sections in xorg.conf to a specific output. By default all my configuration was being applied to my HDMI output.
  7. I figure it out, fix the display and now I am back to starting off from lot of empty space and this post.
  8. Thank god, I use some tools to keep my web data in sync and have backup of some key things (Oh! come on, everyone knows I was lying.. I do maintain backups on USB sticks once in a while, but not enough to stop complaining, yes I still lost all my data). Confused?

There you have it, thanks for reading my rant.. now back to work!

Saturday, March 31, 2012

Poem of Physics

Oh! I hope you see my plight
Why does light travel at the speed of light
Which almost seems infinite!
When I think of infinite, I think of god
Does he hide,
Like the infinite?
Hidden in corners, exposed by the equations right
I can see the infinite, but not his might
In a circle so beautiful, like the zero
But, yes sometimes I wish I never know
For its the unknown that makes us go

-- Balbir Singh

Saturday, February 11, 2012

Wish list of books - need suggestions

I've got a big list of books that I own. Here is what I intend to purchase in the next set. I am looking for suggestions on what would make useful reading? I am open to all categories of fiction/non-fiction/technical books. It would help if you point me to a review or provide me your own review comments

Enumerative Combinatorics - volume 1 (second edition)

The second edition is out and available at

The book is extremely well written, although I've forgotten and probably never read a few of the topics mentioned in chapter 1, like one dimensional complete local ring. From where I stand at the moment, completing chapter 1 and understanding the twelve fold way will be quite an accomplishment :)

Do checkout the book. The first chapter is 221 pages with 203 exercises at the end.

Dynamic programming for the binomial coefficient

More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don'...