Links for 2008-05-29

American Scientist Article:

• Accidental Algorithms
  • Polynomial time and Exponential time algorithm are introduced and distinguished. Then, the author moves on to introduce the categories of problems, i.e., P, NP(decision problems), and #P(counting problems), as well as subgroups within the categories, i.e., NP-Complete and #P-Complete.
  • Although #P problems is at least as hard as NP, for some counting problems, by transforming them into matrices and computing their determinants, some terms are cancelled out, and determinants can be computed in polynomial time. It means those counting problems, supposed to be harder than decision problems, can be solved in polynomial time.
  • Non-holographic algorithms typically rely on reductions. That is , if we can reduce problem A to problem B and if there is a solution to problem B, then we know there is a solution to problem A.
  • Holographic algorithms reduced problems in a different way. The author cited an example, using matchgrid and matchgate, to demonstrate the holographic process.

MSDN Article:

• Alphabet Soup: A Survey of .NET Languages And Paradigms
• Object-oriented programming
• Languages - C#, Visual Basic .NET
• Features
1. Type contracts
2. Polymorphism
3. Encapsulation
• Functional programming
• Languages - F#
• Features
1. Higher-order functions
2. Type inference
3. Pattern matching
4. Lazy evaluation
• Dynamic programming
• Languages - IronPython, IronRuby, Phalanger
• Features
1. Just-in-time (JIT) compilation
2. Late bound - Read Eval Print Loop (REPL)
3. Duck typing - "..., if a type looks like a duck and quacks like a duck, the compiler assumes it must be a duck."
4. Hosting APIs
• Misc.
  • LINQ
  • Inline XML in Visual Basic 9.0
  • Declarative programming - Windows Presentation Foundation and Windows Workflow Foundation
  • Logic programming - Prolog

Links for 2008-03-01

D-Bus

• D-Bus - Wikipedia, the free encyclopedia
• Get on the D-BUS
  

MapReduce Method

• MapReduce - Wikipedia, the free encyclopedia
• Distributed Programming With MapReduce
• MapReduce: A major step backwards
• MapReduce II
• MapReduce: Simplified Data Processing on Large Clusters
  
• Map-Reduce-Merge: Simplied Relational Data Processing on Large Clusters

Links for 2007-12-08

Blog:

• Measure twice, average once - Measurement is all about estimation and there is a theory behind it. The blog sheds some light on what the theory is about.

Article:

• Gödel, Escher, Bach: an Eternal Golden Braid - a pholosophical book by Douglas Hofstadter, with many subjects covered, including what i'm interested, such as artificial intelligence.
• How Many Ways Can You Spell V1@gra?
• Brian Hayes analyzed that an legible variation of Viagra has 1,843,200 possible spellings, by varying Viagra and separating the six letters by five copies of space characters. However, studying the 88,324 emails received, the author identified 113 distinct spellings. Based on the information, the author suspected that the spam scheme was not very sophisticated. It seemed a spelling once has been incorporated into a message, it is mailed out repeatedly over a period of a few months, then gave a rest.
• The techniques used to combat spam are must better known thant the methods of spam senders. Three spam-filtering approaches have been used to train a spam-ham classifier, that is, Bayesian, SVM, and HMM. However, a possible attack to Bayesian filtering, Bayesian poisoning, was discussed but could be defended by frequently retraining the filter.
  
• Introduction to Estimation Theory - The choice of error criterion and optimization heavily influences the form of estimation procedure. The estimation performance can be considered from three aspects.
• Bias - An estimate is said to be unbiased if the expected value of the estimate equals the true value of the parameter.
  
• Consistency - An estimate is said to be consistent if the mean-squared estimation error tends to zero as the number of observations becomes large.
  
• Efficiency - An estimate is said to be efficient if its mean-squared error achieves Cramér–Rao bound.
  

Count Bits in Words

How do we count the number of 1-bit in a 32-bit unsigned integer, x? A naive approach is like this.

pop = 0;
for (i = 0; i < pop =" pop" x =" x">> 1;
}

Can we do better? Yes, according to Henry S. Warren, Jr., who wrote "The Quest for an Accelerated Population Count" of Beautiful Code. There are many ways to improve the loop. For example, if x is a small number, then the loop can be improved as followed.

pop = 0;
while (x) {
pop = pop + (x & 1);
x = x >> 1;
}

The following is looped as many times as the number of 1-bit in x.

pop = 0;
while (x) {
pop = pop + 1;
x = x & (x - 1); //turn off the rightmost bit
}

Or we can trade space for time. Look up the number of 1-bit in a table.

static char table[256] = {0, 1, 1, 2, 1, 2, 2, 3, ...,
pop = table[x & 0xFF] + table[(x >> 8) & 0xFF] + table[(x >> 16) & 0xFF] + table[x>> 24];

And several non-trivial approaches are discussed in the article. The author further applied the 'population count' functions to other problems, such as comparing population counts of two words, calculating Hamming distance, computing the number of trailing 0s in a word and allowing fast direct indexed access to a sparse array. Someone even posted performance analysis of the population count functions on the Internet. It seems Google would ask this kind of questions in an interview. Though I am not sure where I can apply the population count functions in my projects, Mr. Warren's article is definitely very informative.