Monday, April 2, 2007

Thursday, March 29, 2007

NP Complete

I in one of my moods realized all real life problems are NP-Complete problems and the only way to solve them is to use techniques that are known to work with NP Complete problems:
1. Reduction: Reduce it to NP problem with known heuristic
2. Heuristic: Solve using what works most of the time
3. Approximation: Approximate the solution

If we realized that there is no perfect solution or the perfect solution to the problem is not worth the cost, we would be much faster in making decisions and moving on to another NP-Problem. If we are stuck into not accepting the complexity as inherently insolvable and persist on solving it for perfection, in more cases than less we would not get anywhere.

Formal Defintion from Wikipedia

A decision problem C is NP-complete if it is complete for NP, meaning that:

  1. it is in NP and
  2. it is NP-hard, i.e. every other problem in NP is reducible to it.

"Reducible" here means that for every problem L, there is a polynomial-time many-one reduction, a deterministic algorithm which transforms instances l ∈ L into instances c ∈ C, such that the answer to c is YES if and only if the answer to l is YES. To prove that an NP problem A is in fact an NP-complete problem it is sufficient to show that an already known NP-complete problem reduces to A.

Tuesday, March 20, 2007


Book Review:

Innumeracy : Mathematical Illiteracy and Its Consequences ... John Allen Paulos

The book talks about our ignorance to the fact that in mathematics contrary to common perceptions problems or observations do not add up or scale always in the same way. For example:-

  1. If there are 50% chances of raining on Saturday and 50% chances of raining on Sunday then we might conclude that there is 100% chance it is going to rain on the weekend.
  2. In other cases we misread because of psychological impact of numbers e.g. 280 people died in such and such incidence would take away the focus from the fact that 280 in a population of 200M are insignificant. Also, when it comes to numbers don’t put personal face to them e.g. one of the 280 was just a kid such and such. People with innumeracy problems will always refute mathematical arguments with case like what if you were one of the 280, which if you were to compute probability, the chances of you being one of 280 would be minuscule.
  3. Another such oddity is with small numbers, so if something impacts us by only 0.0001% then would tend to ignore it, but if we have a lot of such small things, they do compound to huge numbers, typical case being in computing each individual instruction is cheap to compute but if we put a lot of them together it could be the cause of big bottleneck or cost.

In summary:

Look at numbers, percentages and other statistics in perspective. You can make huge miscalculations if you take number without understanding the context and interplay of other factors.

Tuesday, March 13, 2007

सोच २.0

पहले हिंदी टाईप करना इतना मुश्किल था। पर इस ब्लोग में तो बहुत आसन हैं टाईप करना। टेक्नोलॉजी को मानना पड़ेगा, मैंने कभी भी नहीं सोचा था की मैं इतनी आसानी से हिंदी में लिख सकूंगा । बहुत सही ।

अच्चा अब कुछ कहता हूँ ... छोडो फिर कभी :)


IT architects are visionaries, coaches, team leaders, business-to-technical liaisons, computer scientists, and industry experts.

The following is effectively a job description for an IT architect:

"The architect has a responsibility for ensuring the completeness (fitness-for-purpose) of the architecture, in terms of adequately addressing all the pertinent concerns of its stakeholders; and the integrity of the architecture, in terms of connecting all the various views to each other, satisfactorily reconciling the conflicting concerns of different stakeholders, and showing the trade-offs made in so doing (as between security and performance, for example).

The choice of which particular architecture views to develop is one of the key decisions that the IT architect has to make. The choice has to be constrained by considerations of practicality, and by the principal of fitness-for-purpose (i.e., the architecture should be developed only to the point at which it is fit-for-purpose, and not reiterated ad infinitum as an academic exercise)."

The role of the IT architect is more like that of a city planner than that of a building architect, and the product of the IT architect is more aptly characterized as a planned community (as opposed to an unconstrained urban sprawl), rather than as a well-designed building or set of buildings.

An IT architect does not create the technical vision of the enterprise, but has professional relationships with executives of the enterprise to gather and articulate the technical vision, and to produce the strategic plan for realizing it। This plan is always tied to the business plans of the enterprise, and design decisions are traceable to the business plan.


Monday, March 12, 2007


The economist needs the three great intellectual faculties, perception, imagination and reason: and most of all he needs imagination, to put him on the track of those causes of visible events which are remote or lie below the surface, and of those effects of visible causes which are remote or lie below the surface. - Alfred, Marshall