The Knapsack problem

I found the Knapsack problem tricky and interesting at the same time. I am sure if you are visiting this page, you already know the problem statement but just for the sake of completion : Problem : Given a Knapsack of a maximum capacity of W and N items each with its…

Quicksorting - 3-way and Dual Pivot

It's no news that Quicksort is considered one of the most important algorithms of the century and that it is the defacto system sort for many languages, including the Arrays.sort in Java. So, what's new about quicksort? Well, nothing except that I figured just now (after 2 damn years…

Evaluating Infix expression - multiple digits

If you are looking for evaluating an infix expression with parantheses, don't waste your time here. Visit my other fresh write up here [http://rerun.me/2012/10/17/evaluating-infix-expression-with-parentheses-in-groovy-multiple-digits/] These images have been running around Facebook for a while now. Though it is eye-damaging primary level arithmetic [http://www.…

Find Continuous subarray with maximum sum problem - Kadane's algorithm

Update : Previous version of the code failed for some inputs, as pointed out by @Thinker in the first comment. Changes to the program and the presentation were made. Tested to satisfy most conditions that I could google for. In a desperate attempt to increase my sad looking stackoverflow reputation, I…

Quicksort - the easy way

-------------------------------------------------------------------------------- Note : For 3-way partition and Dual Pivot Quicksort (with programs to trace the sort process), please refer to this recent post [http://rerun.me/blog/2013/06/13/quicksorting-3-way-and-dual-pivot/]. -------------------------------------------------------------------------------- Quick sort is the fastest known non-hybrid comparision sort for arrays which has no knowledge of the data beforehand.…