Yesterday, I came to know about this wonderful git command. What it allows you to do, is to track who wrote a particular section of a file.

1
2
3
4
5
6

reddragon@reddragon-laptop:~$ git blame -L 150,+5 decaf.yy
24d48281 (Gaurav Menghani 2012-03-21 19:28:31 -0400 150) ClassDeclarations:
efe4b77c (Dhruv           2012-03-28 18:08:03 -0700 151)     ClassDeclarations C
d25802c5 (Gaurav Menghani 2012-03-28 21:17:15 -0400 152)         $1->push_back($
efe4b77c (Dhruv           2012-03-28 18:08:03 -0700 153)         $$ = $1;
efe4b77c (Dhruv           2012-03-28 18:08:03 -0700 154)     }

I would scribble some project / research - worthy ideas. That may or may not yield much benefit, but I would probably like to travel down that path some time.

• Concurrent Linked Lists Linked Lists that can be operated on concurrently. There has been some work done on Lock-Free Linked Lists etc, probably worth checking out, and implementing.

• Bloom Filters / Quotient Filters Definitely worth implementing an efficient Bloom Filter / Quotient Filter. An exciting research area is to design a Bloom-Filter type data structure to efficiently answer the query - “Is there an element in the range [p,q]?”, with a NO (which is guaranteed), or MAYBE (the false-positive rate should be adjustable).

• Persistent / Temporal Data Structures See Prof. Erik Demaine’s lecture.

• Sorting / Searching Practical In-Place Merge-Sort [PS]

• Dynamic RMQ / LCA in O(1) time. Simplify what Cole and Hariharan did for LCA in this paper. And/or devise a dynamic RMQ mechanism which can be done in O(log n) / O(1).

• Fractional Cascading This is a really cool idea. Read about it here. It helps speed up bounded-box queries by a log factor.

Please feel free to suggest ideas.

Professor Bender mentioned this thing called ‘Competitive Analysis’ in class.

It is basically analysing the performance of your algorithm in difficult scenarios, with the optimal performance in easier scenarios. For example, it is easier to do Off-line scheduling than On-line scheduling. One could compare how bad one’s algorithm performs in the on-line version, by looking at its performance relative to the optimal / good schedule in the off-line case.