Friday, April 07, 2006

Being in-place

In 1988, during an evocative summer a long time ago, I slaved away shaving-off bits needed to store a finite state machine (FSM) for a compiler I did for a company in the distantly alluring city of Pune, India. The FSM had to fit into a floppy or something and I still needed to index transitions out of each state quickly. Don't ask me why. I was an undergrad and I could easily get into solving a technical problem elaborately without wondering if I could get around it. But since then, once in a while, I come across a problem that directly or indirectly connects with that summer chore long ago. Here are two questions which in some twisted way reminded me of that past. (in-place means using no more than O(1) extra words.)

P1: Is there an O(n) time in-place radix sort? [I have a solution, but would have thought this is standard.]

P2: (This is a research problem.) Given a string S[1,n] in which each S[i] is a log n bit integer, design an efficient Lempel-Ziv like algorithm that works in-place.

2 Comments:

Anonymous Anonymous said...

Really amazing! Useful information. All the best.
»

9:53 PM  
Anonymous Anonymous said...

Hey what a great site keep up the work its excellent.
»

1:29 AM  

Post a Comment

<< Home