I came across this interesting problem of coming up with an algorithm that would compute, for each element of an array, the product of all other elements in that array, in linear time without using the division operator (or implementing a division algorithm.)

A solution is to traverse left to right computing the growing product, and then traverse right to left computing the growing product and multiplying it with the result from the previous traversal. I.e.,

P     Q    R    S

1     P    PQ   PQR
x     x    x    x 
QRS   RS   S    1
-------------------
QRS   PRS  PQS  PQR  

Implemented in python,

def elProd( A ):
        result = []
        prod = 1

        # for i from 0 up to len(A) - 1
        for i in range( len( A ) ):
                result.append( prod )
                prod = prod * A[ i ]
        prod = 1
        
        # for i from len(A) - 1 down to 0
        for i in range( len( A ) - 1, -1, -1 ):
                result[ i ] = result[ i ] * prod
                prod = prod * A[ i ]

        return result

The Art of Computer Programming Reading Group is for those of us who suffer from the perpetual procrastinate-reading-knuth syndrome. Starts June 1st'05. Subscribe to the mailing list here.

While I am not particularly proud of this LL(1) hack, nor am I completely sure it works 100%, I still want to see how this blog handles code posts. This is available in my cvs repository under the module "regexll". I'll post a LR(1) parser after Thursday.

Here's a link to some Microsoft Interview Questions.

Check this link out...

Robert W Floyd, In Memoriam.

Sorting in general refers to various methods of arranging or ordering things based on criterias (numerical, chronological, alphabetical, heirarchial etc.). In Computer Science, due to obvious reasons, Sorting (of data) is of immense importance and is one of the most extensively researched subjects. It is one of the most fundamental algorithmic problems. So much so that it is also fundmental to many other fundamental algorithmic problems such as search algorithms, merge algorithms etc. It is estimated that around 25% of all CPU cycles are used to sort data. There are many approaches to sorting data and each has its own merits and demerits. This article discusses some of the common sorting algorithms.