A great textbook on mathematical foundations for Computer Science

I have been using James Hein's Discrete Structures, Logic, and Computability for studying first order logic and automatic reasoning. Its an excellent textbook which introduces these concepts very lucidly with proper motivation, very comprehensively and without too much of abstract formulate. There are many examples worked out too, which is a great aid to get started with many problem solving techniques.

This is not a book about logic alone - it covers the entire mathematical foundations of computer science:

• Discrete Structures
• Set Theory
• Complexity Analysis
• Logic
• Automata Theory
• Group Theory

James Hein is Professor Emeritus at Portland State University, whose current interest in his own words is  "Finding ways to help students learn about the mathematical foundations of computer science (discrete mathematics, logic, and computability)." This book is surely the result of that passion and vision. 

Thanks to Rajen for pointing this textbook. 

printf("Adieu Ritchie, McCarthy and Jobs");

In the last two weeks, the world of computing has lost three of its stalwarts - Dennis Ritchie (the inventor of C and Unix), John McCarthy (the father of AI and Lisp) and Steve Jobs (of Apple). 

For me and for basically everybody I know of, the introduction to programming came through C. I still admire C for its simplicity and orthogonality. The notions of elegant and efficient programming can probably not be taught better in any language other than C. Unix, of course, is a boon to the world - an operating system so simple and elegant that every OS of note essentials follows its design principles. Ritchie, Brian Kerninghan and Ken Thompson were first class hackers who changed the world  forever. 

The very term 'Artificial Intelligence' was coined by John McCarthy and he along with Marvin Minsky, Claude Shannon laid the foundations of this branch of computer science that I now happen to be associated with. AI is now the darling of the computing world, though the challenges McCarthy had set for us is still far away. And who can forget Lisp - the language that has spawned the functional paradigm of programming that every programmer of note will appreciate for its elegant style.     

Unlike Ritchie and McCarthy, Jobs was no technical whiz or geek - but the idea that drove him was the same - beauty and elegance. Its a word not normally associated with CEO - but it is his insistence of aesthetics that has seen Apple build the sleekest products that just do what they are supposed to do with no feature crap that is the bane of all software. 

R.I.P

Python is great!

Recently, I learnt Python mainly in the course of doing some web programming, not wanting to jump into the jargon laden Java technology stack. Also, I wanted to learn a language for quickly coding out things, yet be able to manage and organize code as well as in Java. Quite a lot of people have taken to Python for these reasons, and it surely doesn't disappoint. Coding feels like a breeze, yet I can write well organized and structured code. The language is powerful and expressive and the list manipulation facilities are a breeze. There is a hint of functional programming too with 'map', 'reduce', 'filter' functions. It has a good collection of libraries too, and almost every functionality has Python APIs. So there is little reason to be stuck with Java because of non-availability of libraries. The only odd thing is that the language has no braces, and relies on indentation for defining scopes. Enjoying Python for now, hope to use it heavily in times to come !

The disposable Ph.D

The Economist recently carried an article about how and why Ph.D degrees were losing their sheen. In summary, its argument was basically this:

• Designed to be a programme for preparing candidates for an academic career, there is now an oversupply of Ph.D holders, with the US itself handing 64,000 doctorates every year.
• Given the low stipends/scholarships that bright Ph.D candidates are given, they have become "cheap, highly motivated and disposable labour" that is driving most of the research today, and are being taken for a ride with promises of a better future for the present struggles. The so-called "postdocs" are also victims of this infrastructure, the post itself being a result of an attempt to fix the demand-supply mismatch.
• Does having a Ph.D add value to your career? The Economist says its definitely better than a bachelor's degree, but not much value-addition over a master's - in fact you may be disadvantaged. The Ph.D skills of deep analysis, research are not what today's fast moving markets are looking for. The more qualified a candidate is, the more likely he is to be dissatisfied and de-motivated with the work at hand.

Now, here's what I think on the Economist's viewpoint:

• The demand-supply mismatch argument does not hold in India, since there is a large shortfall of qualified, well-versed academic staff today, while the number of Ph.Ds joining the pool is very small. For example, India produces just about a 100 Ph.Ds in Computer Science today. With globalization, the Indian educational institutions have to achieve higher benchmarks to maintain relevance. This explains the sprouting of new higher educational institutions like the new IITs,IIITs, IISER, and others trying to match them. These have to be manned by qualified faculty. So, we need to have more students pursuing Phds.
• Yet, we don't see too many people pursuing doctorates in India. Why? One, there is no monetary benefit for the long struggle. But that will always be the cost of pursuing anything different, hence that will never deter the really committed. Secondly, there is government apathy of which the zillions of pages have already been written. More importantly, we are not contextualizing and localizing the problems we are solving. We are solving problems defined and relevant to the West, hence neither the potential candidates nor the Indian society at large feels any affinity to the kind of problems tackled as part of the candidate's thesis. So, even the demand exists, the supply doesn't inspire enough confidence in the society. This chain of thought naturally leads to preference for the West by many wannabe candidates.
• Of course, the PhD syllabus needs to reformed. In a fast moving and dynamic world, the course needs to be more flexible. There could be intermediate exit points in the course, for instance.
  
• This seems to be part of the conservative agenda (of which the Economist is the vanguard), that wants to spend lesser and lesser on free and open education, and make the work force pay for job oriented skills. Of course, societies don't run only on markets and there should always be a place for intellectual and artistic pursuits that don't necessarily yield the market any pay-off. Society must always support such endeavours.
  

What Ph.D candidates need to do to weather this storm:

• Information is now ubiquitous, it is not a premium; hence, the days of the informed teacher being highly regarded are gone. However, with the deluge of data, the ability to analyze information, think deeply and synthesize ideas are needed more than ever. Hence Ph.D candidates have to focus more on developing their faculties in this direction. This is anyway part of their brief, but being satisfied with low-hanging fruits like being an authority of a subject will not work in future.
• They must not become super-specialists, limiting their thinking to some restricted domains of thought. After all, it is a doctorate of philosophy, and the spirit of philosophy is to think openly with no restrictions. Creativity depends a lot on cross pollination of ideas from many disciplines.
• There has to be an irreverence to authority and a commitment to be fiercely independent.
  

"Many scientists are scientists because they are afraid of life"

This quote by John Backus, the creator of FORTRAN and the Backus-Naur form inspires this post. This is what Backus had to say in his later years about science and life:

"Many scientists are scientists because they are afraid of life. It's wonderful to be creative in science be use you can do it without clashing with people and suffering the pain of relationships and making your way through the world. It's sort of this aseptic world where you can do exciting things with your faculties, and not encounter any pain. The pain in solving problems is small potatoes compared with the pain you encounter in living.
Introspection is not a scientific activity, it is not repeatable, there are no good theories about how to repeat it, what you expect to find. It's strange that by looking into yourself you really get an appreciation of the mystery of the universe. You don't by trying to find the laws of physics."

Wise words from an old hand, and they ring true. The central idea of any modern science is abstraction, the process of drawing out the essential features that describe and system, while leaving out those which are irrelevant to the goal. Through this abstraction a system is simplified, and the abstraction becomes the basis for a lot of creativity. For eg. Newton abstracted mechanical motion to precisely three laws and this spawned the modern industrial revolution and all its inventions. We now know that Newton's laws cannot explain all phenomena, neither can relativity. The uncertainty principle is a partial acceptance of the fact that everything cannot be explained through abstraction and reason. It's a messy dynamic world out there, at the level of sub atomic particles, where our clean abstractions of matter and energy, wave and particle, force and particle break down. Even our intellect is based on this kind of learning through discrimination, categorisation, and abstraction.

But abstraction is beautiful, which is why the greatest of scientists cherish these abstractions, and adjectives like 'beautiful', 'elegant', 'simple' are applied to great works of science. It is then easy to mistake the abstraction for the 'perfect' and the real for the 'impure'. In essence, one is being afraid, running away from reality - the justification of perfection is only an alibi. This belief in the 'perfection' of abstraction can become fanatical, with disastrous consequences - especially in the social sciences. And so the communist and social Darwinian ideas brought disaster to millions, as the processes of globalisation driven by a fanatical belief in the infallibility of the markets are homogenising an inherently diverse human society.

Can Eucalyptus be the "Lucene" of cloud computing?

Eucalyptus is an open source cloud platform which can be used to create private clouds. It came out of a research project at the Computer Science Department at the University of California, Santa Barbara. The good thing about it is that it has an open and modular architecture, which means it is perfect for experimenting with different kinds of innovations in cloud computing platform development.

Sounds like Lucene, the open source text search engine that with its extensible design became a vehicle for a lot of innovation in search - leading to innovations like Solr, Nutch, Hadoop, HDFS, etc.Whenever a platform is made open, and its design made modular, extensible - it becomes the hotbed of innovation. That happened with Unix, Linux, and is now happening with Android. Will Eucalyptus take cloud computing there?

PS: Cross-posted from my Peepaal blog post

Blog on organizing information

Organizing and extracting information from unstructured data is an area that excites me tremendously. I have started learning the tricks of the trade in the last couple of years, and there is still a long way to go. Dhaval shares the interest too, and we thought of writing a blog on the things we do, things we read and our learnings. We call it 'On Organizing Information', and this post should give you sense of what we intend to write about.