Streaming Algorithms using Finger Printing Technique

Algorithms working on large data(say of size n) should be both space and time efficient. Any algorithm has to see atleast the whole data once, so time required has to be atleast n(see sublinear time algorithms for exceptions). Also it should use space much less than n(ie. o(n)). We will see a good technique for designing such algorithms and use it to solve two problems. First will be checking whether a string x can be derived from a grammar and the second one is to check whether a sequence of n numbers are exactly the out degrees of the corresponding vertices in an n vertex graph. Furthermore we will prove that the algorithms are optimal in their space usage(ie. being more space efficient is a mathematical impossibility) using techniques from communication complexity (joint work with Ajesh Babu and Nutan Limaye and is going to be presented next Monday at TAMC 2010).