Computer Science

The traveling salesman problem (TSP) is a very simple combinatorial optimization problem. Given a set of cities and distances between each pair, the problem is to find the tour of least distance that travels each city exactly once. Simple – as in simple to state. But from what I have seen this seems to be the hardest of the hard problems to solve. To give some background, there are these famous hard problems in Computer Science that do not have “efficient” solutions. Brute force solutions work very easily on them, but take an eternity to run. In spite of 40 years of extensive research by some very smart people, brute force seems to be the only solution. For example, the TSP can be solved by listing all possible tours covering the cities once, and picking the one with the least length. This takes an eternity as there are an exponential number of such tours (n!). These problems are the (in)famous NP-Hard problems. Stephen Cook at the University of Toronto proved that if one of them can be solved efficiently, all of them can be!!! A very intuitively pleasing fact. ...

I have never heard the Who’s music; and scientists have always wondered about the Why’s; Science mostly explains the How’s; Today’s question is the What. On first glance, the What appears to be tame compared to its illustrious peers. While beginning Jaynes’s tome on probability, I came across this quote said around 1948 and attributed to von Neumann – “For those who believe that comptuers cannot do all that we humans can; please explain in finite, precise steps, what it is that you can do; I will make the computer do precisely that.” ...

Its been a while since I have blogged anything technical. These days, I am working on the open source search engine, Nutch. Before I get into what I am doing, let me explain why, in the last sentence, I put the phrase “open source search engine” as a part of the href tag. Search engines use anchor text extensively to figure out what a page is about. For example, the home page of Tejaswi doesn’t have the phrase “home page” anywhere. So, by looking at the anchor text of all the in-links to a page, the search engine figures out what the content of the page might be about. This is a latent way of identifying the content of a page: by looking at what in-links call it. Now, when I say “the open source search engine Nutch” in the anchor text and link to nutch.org, that phrase gets associated with the site, and helps someone searching for an open source search engine, but has no clue about Nutch itself. ...