Friday, March 25, 2011

Moderately good problems in computer science.

It seems that there is no lack of important moderately difficult problems in Computer Science that require about 1 or 2 days of thinking and about a months of implementation. Lets talk about one such example problem:
Problem 1: Find near duplicate documents?

Application: Search.
One reasonable problem definition: make hash of random points from the documents such that if x1 is a near duplicate of x2, both x1,x2 will have same hash.
A reasonable solution: Make a 128 bit MD5 of the document (better, do that for paragraphs, sentences, n-grams). Choose part of the hashes from the parts of the documents in an order to increase probability of matching near duplicates.

Broader's paper: This paper is actually a good paper since it not only provides a reasonable solution, it defined the problem nicely and gave a solution with a bound for near duplicate matching. Similar techniques are implemented in Goog and in MSFT and in many other search companies for their production near duplicate detection tasks.

You can read Broader's slides here.

Excerpts for understanding developments in Programming Languages

Last fifty years in computer science research has produced a series of fascinating innovation in programming languages. It started with Church and Turing's work on lamda calculus. In 1954 John Backus assembled a team to define and develop Fortran for the IBM 704 computer. Fortran was the first high level programming language to be put to broad use. Later John McCarthy rediscovered lamda calculus and created Lisp

In the late 1950s and 1960s, ALGOL was developed in order to allow mathematical algorithms to be more easily expressed, and even served as the operating system’s target language for some computers. COBOL (1960) and BASIC (1964) were both attempts to make programming syntax look more like English. In the 1970s, Pascal was developed by Niklaus Wirth, and C was created by Dennis Ritchie while he was working at Bell Laboratories.

The 1980s saw a rapid growth in interest in object-oriented programming. These languages were im- perative in style, but added features to support objects. The last two decades of the 20th century saw the development of a considerable number of such programming languages. Smalltalk-80, originally conceived by Alan Kay in 1969, was released in 1980 by the Xerox Palo Alto Research Center. Drawing from concepts in another object-oriented language – Simula (which is considered to be the world’s first object-oriented programming language, developed in the late 1960s)Bjarne Stroustrup designed C++, an object-oriented language based on C. C++ was first implemented in 1985. In the late 1980s and 1990s, the notable im- perative languages drawing on object-oriented concepts were Perl, released by Larry Wall in 1987; Python, released by Guido van Rossum in 1990; PHP, released by Rasmus Lerdorf in 1994; Java, first released by Sun Microsystems in 1994 and Ruby, released in 1995 by Yukihiro Matsumoto. Functional programming languages, especially purely functional ones, have largely been emphasized in academia rather than in commercial software development. However, prominent functional programming languages such as Scheme, Erlang, OCaml, and Haskell, have been used in industrial and commercial ap- plications by a wide variety of organizations. Functional programming also finds use in industry through domain-specific programming languages like R (statistics), Mathematica (symbolic math), J and K (financial analysis), and XSLT (XML). Widespread declarative domain specific languages like SQL and Lex/Yacc, use some elements of functional programming, especially in eschewing mutable values. Spreadsheets can also be viewed as functional programming languages. John Backus presented the FP programming language in his 1977 Turing Award lecture “Can Program- ming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs”. He defines functional programs as being built up in a hierarchical way by means of “combining forms” that allow an “algebra of programs”; in modern language, this means that functional programs follow the principle of compositionality. Backus’s paper popularized research into functional programming, though it emphasized function-level programming rather than the lambda-calculus style which has come to be associated with functional programming. grew. By 1987, more than a dozen non-strict, purely functional programming languages existed. Of these, Miranda was the most widely used, but was not in the public domain. At the conference on Functional Programming Languages and Computer Architecture (FPCA ’87) in Portland, Oregon, a meeting was held during which participants formed a strong consensus that a committee should be formed to define an open standard for such languages. The committee’s purpose was to consolidate the existing functional languages into a common one that would serve as a basis for future research in functional-language design. The first version of Haskell (”Haskell 1.0”) was defined in 1990. The committee’s efforts resulted in a series of language definitions. In late 1997, the series culminated in Haskell 98, intended to specify a stable, minimal, portable version of the language and an accompanying standard library for teaching, and as a base for future extensions. Following paper has a comparative study on various programming language implementations http://arxiv.org/pdf/1009.0305.

Monday, March 14, 2011

Theory, real world and two remarkable pieces of work

Theories are constructed with reasonable assumption that one or a few human brains can manage. Real world is full of noisy observations. A beautiful theory considers this noise and handles it. As an example I would like to talk about two most important contributions from two of the best scientists and engineers of the century. The first contribution was by Shanon. In his 1984's paper "A mathematical theory of communication." I would like to quote a few sentences from NASA's web page on Shanon's contribution since I could not say anything better than the article has said about this phenomenal work.

"Many concepts that seem obvious today were first introduced in his paper, "A Mathematical Theory of Communication," published in two parts in the Bell System Technical Journal. The use of the term "bit" as a unit of information first appeared in this paper. In an age in which communication took place with continuous, analog waveforms, it was a startling notion that information traveling across any communications system could be defined mathematically as some quantity of binary symbols. It was entirely new that information of any kind-- whether for use on a telegraph, telephone, radio, or television-- could be decomposed into zeros and ones, encoded, transmitted, and decoded at the other end.

That was groundbreaking, but it was only one component of his theory. He went on to present the concept of the maximum rate of transmission on a channel-- the capacity or "Shannon limit"-- which provides the benchmark against which all codes and modulations are measured. He invented adding redundancy to a transmitted signal in order to enable correcting for transmission errors at the receiving end. He provided the foundation of data compression, years ahead of any widespread implementations of digital communications or storage.

In this one paper, Shannon founded the field of information theory. In a world in which no one knew the concept of a bit, asking the question, "How many bits per second can be transmitted a channel?" and doing nothing more would have been momentous. Shannon did this and proceeded to clearly state the answer, prove it, and begin to show how to design systems that achieve the limit. He presented a clear picture of the whole field of information theory, all at once."

The second person I would like to mention is Jon Von Neumann's classic work on introducing theory of games and economic behavior. Again I would like to quote from an article from Princeton university press on his classic work.

"This is the classic work upon which modern-day game theory is based. What began more than sixty years ago as a modest proposal that a mathematician and an economist write a short paper together blossomed, in 1944, when Princeton University Press published Theory of Games and Economic Behavior. In it, John von Neumann and Oskar Morgenstern conceived a groundbreaking mathematical theory of economic and social organization, based on a theory of games of strategy. Not only would this revolutionize economics, but the entirely new field of scientific inquiry it yielded--game theory--has since been widely used to analyze a host of real-world phenomena from arms races to optimal policy choices of presidential candidates, from vaccination policy to major league baseball salary negotiations. And it is today established throughout both the social sciences and a wide range of other sciences."

The characteristic of both of these great work is keen observation to identify a simplified theory of complex systems that revolutionizes science and engineering and enormously reduces the gap between the abstract world of theory and real world.

Both information theory and game theory have been proven to be applicable in modeling many complex engineering systems till date and will continue to do so.

Sunday, March 13, 2011

Share holder's value and product quality

Optimizing a development process for quarterly gain can be quite dangerous for long term growth of a company. However, a steady growth is also important. This is not difficult when the scope of the firm is small and focused and it becomes harder when the scope increases and the company started diversifying. In a lot of articles, I found that people often correlate share holder's value with quarterly profit. It is true that finance companies optimize their portfolios that way but a share holder's value should be judged with the promise of long term sustainable growth that the firm is bringing every quarter to its share holders. Often the specific attribute that gets sacrificed for rushing for quarterly gain is the "quality". Quality of a product from a firm is actually the most important aspect that can make the firm stand out in a competitive market. Hence, a development process needs to be optimized for making high quality product. The metrics for quality should be chosen very carefully and should be fully result oriented and independent of the process.