Yesterday night during the workout suddenly I thought about what will happen if we encode the t-vector {-1,0,1}in the Four Russian algorithm as an integer.....the idea was a BOOM! I really felt like EUREKA! just like Archimedes thought when he discovered the law of flotation, I felt that suddenly I speedup the edit-distance dynamic programming algorithm which is O(n^2) by a factor of O(log^2(n)), it was really great I spend working on the details all special cases and written up every thing was great till then. I discussed the solution with Dr.Wu and found that it was actually solution to some exercise problem in Gusfield's book which says that in a RAM based computation model the copy of vector 't' can be done in O(log(t)) time.
How do you feel when you know some thing which you are exited just slips from you ? its very painful and its like killing you, but thats the way the world is its full of SMART people and any path which you are taking might have been taken before........
No comments:
Post a Comment