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 math.mit.edu/~rstan/ec/ec1.pdf


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.

Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...