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

Pivot Query in Oracle

I recently revamped some stored procedures I wrote before and found a case where I can apply pivot query to simplify the code. Though I have seen the technique demonstrated in Tom Kyte' Expert One-on-One Oracle(ch.12), this is just another evidence that to know is one thing, to know where to apply is another.

The code I maintained read buy and sell trades from trade table
and sum them into position table for each symbol. Originally, I sumed
buy orders first and then sell orders and stored the results into position table. By using DECODE function, I can finish the task in fewer lines of code. Here is how.

Assuming my trade table and pos table are as follows.
(clieck to enlarge)
  
I want to sum records in trade table and store the summations in pos table. Using Pivot query as the sql in red square, I can get it done this way.
(clieck to enlarge)


This is what I want.
(clieck to enlarge)

Book - Release It!: Design and Deploy Production-Ready Software

I came across the book from the announcement of 2008 Jolt Productivity Award. This book talks about what could go wrong (antipatterns) once a system go into production and what we could do about it (patterns). The focus of the book is not about what's in the spec but about what's not in the spec. There are 4 parts in the book, stability, capacipity, general design issues and operations. I listed below several points which impressed me most.

• Timeout - "Any resource pool that blocks threads must have a
  timeout to ensure threads are eventually unblocked whether resources become available or not".
• Conway's law - "Organizations which design systems are constrained to produce designs which are copies of the communication structures of these organizations." It's communication structure that matters, not hierarchical structure.
• Multiplier effect - For a webpage containing only 40kb of useless data, if that page is hit 1000 times a day, it means 40mb of bandwidth is wasted per day.
• Multihomed Servers - Server sockets of an application should bind to the networks they listen to. For a server socket handling administrative requests, it should bind to the administration network, not backup network or production network.
• Protocol Versioning - No matter what protocol systems use to interact, it will change. So having the version be part of the message exchange will help ease the chage of protocols.