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