When others find that my wife and I have decided to homeschool our children inevitably they ask, "Why?" I've always tried to answer this question with tactful precision and achieved a varying degrees of success. Today I discovered a description that defines how I feel about what's wrong with public schooling in a wonderfully clear and precise way. It's found in The Cambridge Handbook of the Learning Sciences and authored by R. Keith Sawyer:

By the twentieth century, all major industrialized countries offered formal schooling to all of their children. When these schools took shape in the ninetieth and twentieth centuries, scientist didn't know very much about how people learn. Even by the 1920s, when schools began to become the large bureaucratic institutions that we know today, there still was not sustained study of how people learn. As a result, the schools we have today were designed around commonsense assumptions that had never been tested scientifically.

Sawyer goes on to outline these problematic "commonsense assumptions" as follows:

• Knowledge is a collection of facts about the world and procedures for how to solve problems. Facts are statements like "The earth is titled on its axis by 23.45 degrees" and procedures are step-by-step instructions like how to do multidigit addition by carrying to the next column.
• The goal of schooling is to get these facts and procedures into the student's head. People are considered to be educated when they possess a large collection of these facts and procedures.
• Teachers know these facts and procedures, and their job is to transmit them to students.
• Simpler facts and procedures should be learned first, followed by progressively more complex facts and procedures. The definitions of "simplicity" and "complexity" and the proper sequencing of material were determined either by teachers, by textbook authors, or by asking expert adults like mathematicians, scientists, or historians - not by studying how children actually learn.
• The way to determine the success of schooling is to test students to see how many of these facts and procedures they have acquired.

This traditional vision of schooling is known as instructionism (Papert, 1993). Instructionism prepared students for the industrialized economy of the early twentieth century. But the world today is much more technologically complex and economically competitive, and instructionism is increasingly failing to educate our students to participate in this new kind of society. Economists and organizational theorists have reached a consensus that today we are living in a knowledge economy, an economy that is built on knowledge work (Bereiter, 2002; Drucker, 1993). In the knowledge economy, memorization of facts and procedures is not enough for success. Educated graduates need a deep conceptual understanding of complex concepts, and the ability to work with them creatively to generate new ideas, new theories, new products, and new knowledge. They need to be able to critically evaluate what they read, to be able to express themselves clearly both verbally and in writing, and to be able to understand scientific and mathematical thinking. They need to learn integrated and usable knowledge, rather than the sets of compartmentalized and decontextualized facts emphasized by instructionism. They need to be able to take responsibility for their own continuing, lifelong learning. These abilities are important to the economy, to the continued success of participatory democracy, and to living a fulfilling, meaningful life. Instructionism is particularly ill-suited to the education of creative professionals who can develop new knowledge and continually further their own understanding; instructionism is an anachronism in the modern innovation economy. (R.K. Sawyer, The Cambridge Handbook of the Learning Sciences, Cambridge University Press, 2006.)

It's not that instructionism isn't good, it's that it's incomplete. It was never designed to be more than an instantiation of, and a response to, these fundamental "commonsense assumptions" about what it means to be educated.

I believe there are probably as many different approaches to education as there are people, but this approach, embodied in instructionism is the problem. As long as any educational pursuit approaches learning from this perspective alone, young people will continue to enter the global workforce unprepared for the demands of the modern economy.

I want my children's minds to be factories for new ideas, not just warehouses of facts and procedures.

This year marks the 40 year anniversary of the Xerox Palo Alto Research Center, usually called Xerox PARC, or now just PARC. Ethernet, Laser printers, the mouse, the Graphical User Interface (GUI) and even the Dynabook all came out of this uncommonly innovative place, and then promptly left the building. In many ways, Xerox PARC is more famous for the innovations that it couldn't hold onto, than the ones it could retain and capitalize on. Today, PARC will celebrate the start of their fifth decade at its Palo Alto headquarters, and I think it's worth looking back to see what can be learned.

What Left

The Dynabook started as a concept created by Alan Kay in 1968, just a few years before PARC was established on July 1, 1970. While the focus of the Dynabook was to give children access to computing, the Dynabook proved to be the forerunner to both the laptop and now the super-successful iPad. In 1973 Xerox released the Xerox Alto which some say was originally called the interim Dynabook.

When the Xerox Alto was released with it came Ethernet, a Graphical User Interface and the novel mouse used for pointing and clicking instead of the then popular command line user interface. This was the beginning of what we think of as modern computers. Surprisingly, it wasn't until 1981 that these amazing inventions were put into a commercial product: the Xerox Star. In fact, the Alto was never intended to be a commercial product! Ethernet has now become the hardware layer of the Internet and a bit-mapped display and graphical interface the standard for modern human-computer interaction. If that wasn't enough, the Alto included the first WYSIWYG document preparation systems, new advanced programing language, Smalltalk, and one of the first network-based multi-person computer games! Of all those iPhone and iPod touch games everyone is playing these days, almost every one of them is largely written in Objective-C which was an attempt to bring Smalltalk like constructs to the C programming language. All these inventions in one place, at one time!

On the bright side, about 1 year before PARC was founded, Gary Starkweather (Mac greybeards will know him as the father of Colorsync 1.0) modified a Xerox copier and invented the first laser printer. Eight years later, in 1977 the Xerox 9700 was released and this technology quickly became a multi-billion dollar business for Xerox. Leading up to this, a legal misstep led to Xerox being forced to license their entire patent portfolio to competitors. Xerox's market share of the U.S. photocopier market was said to drop from almost 100% to around 14% in 4 years. While certainly a problem for Xerox, I count the laser printer on the bright side of things because they were actually able to see the future and produce something commercially viable. For laser printers at least, Xerox was able to take the idea and make it reality.

All this background should convince you that when it comes to taking the future of technology to the masses, the stakes are high and yet still this company found it difficult to capture the brilliance of their ideas and make them into actual products. There are probably many and multifaceted reasons as to why Xerox PARC fumbled, but I'd like to focus on one particular facet, that of transferring knowledge from one human to another.

The Social Side

In 2000, John Seely Brown published a book entitled, The Social Life of Information with his colleague Paul Duguid. Brown was a director of Xerox PARC for 10 years. Now, I've watched and enjoyed the melodramatic Pirates of Silicon Valley. I've worked at Microsoft in the Macintosh Business Unit for 10 years. Currently, I'm an iOS consultant and developer. I've read and experienced part of the Mac folklore. But his explanation for why Xerox lost their crown jewels to Apple and others was both new to me and very applicable to everyone in the tech industry.

If Only Xerox Had Known What It Knew...

Brown begins the argument that in tumultuous times, moving knowledge in a company is critical. In fact, much of the knowledge a firm needs to stay ahead of competitors already exists in the firm! Sadly, this knowledge can not always be found, and when it is, it is often impossible to move it to where it can make a difference. In contrast, other firms find that their problem isn't finding the knowledge already present, but keeping it from moving out the door! Sometimes knowledge is sticky and sometimes knowledge is slippery. To quote Brown, "What knowledge the firm can hold on to, it can't use. And what it might use, it can't hold on to."

A side note: For most of the time that I worked at Microsoft the MacBU was located in building 115 which was next door to a huge part of the Microsoft Research facilities. I often took advantage of this by attending the tech talks and technology demonstrations open to all employees. It was a wonderful experience to just talk to those brilliant engineers and have them show me "their baby" and enjoy their enthusiasm. It wasn't until the years brought with them the realization that so much of what I saw, would never make it into any product from Microsoft. When ever I saw another company, big or small, bring to market something the likes of which I had already seen in MS Research I would ask my self, "Why? Why can they do it and we can't?" I never discovered a satisfactory answer to this question, but continued to watch billions and billions more of Microsoft's money be poured into Research. To this day, I think Microsoft's core competency is throwing money at problems and hoping the planets align and something comes out of it.

Now to the part about Xerox and Apple:

Yet most of the extraordinary knowledge generated at PARC never crossed the boundary between the scientist in Palo Alto and the development engineers in Dallas or the management in Stamford. The engineers found the scientists arrogant and almost unintelligible. Management found them naïve and unrealistic. The scientists, for their part, regarded almost everyone in the corporation outside their own community as "toner heads" -- unable to think of the world beyond photocopiers.

The story and the knowledge, as everyone knows, did not end here. For the essence of what had been invented by Xerox in Palo Alto ended up being put into production by Apple down the road in Cupertino. In 1979, Xerox managers invited Steve Jobs, one of Apple's founders, to PARC. Once inside, Jobs was able to see what Xerox management could not, the potential of what PARC had generated. So Apple licensed what it could and replicated what it could not. The knowledge that stuck within Xerox leaked readily through its front door.

Who to blame?

So was it that the management had no vision or that they couldn't work with the brilliant scientists? Was it that the manufacturing engineers couldn't "speak" the language of the scientists? Was it the arrogance, naïveté and unrealistic expectations of the scientists? Of course the answer is: Yes. But the answer could just as easily be, that the folks at Apple understood the folks at Xerox in a deep and fundamental way because they were working on the same problems! For the Xerox scientists, they were dying for someone who understood them, and when they found that the Apple engineers "spoke their language" the knowledge flowed freely. It was a social thing.

The point isn't so much recognizing that people make mistakes and often find others difficult to work with. The point is that developing something new, harnessing knowledge and transforming it into a product is just as much a social challenge as it is a technical one. Getting the right people technically is just part of it, and in many ways Microsoft and now Google are living proof that a high-density collection of brilliant people do not innovation make. The social chemistry between the people is at least as important as their raw intellectual horse power.

But things get really tricky, really quick. Anyone with a modicum of experience knows that Engineering is the study and application of trade offs, but how do you know what to trade and what to off? I've been in meetings where a new and "naïve" developer has proposed massive and sweeping changes to a large code base. The old guard, for good reason, had plenty of ammunition and experience to shoot down the new ideas, but what if? What if the changes turned out to be critical? What if, the short run loss would be far outweighed by the long run gain? The Xerox manufacturing engineers in Dallas I'm sure had many good and intelligent reasons to stand by the successes of the past against the uncertain possibilities of the future. But what if...

It's not just that technical judgement is tricky, it's judging people too. My coworkers who have found me hard to work with might enjoy this story. I was 18 when I first started working at Microsoft. Gary English, a former manager on Apple's QuickTime team had been hired at Microsoft and was looking for another Quality Assurance Engineer, to use Apple's parlance. Grant George over on the Office team had seen my resumé and sent it to Gary. He looked at it, brought me in for an interview and I was hired. A few months later, he, my Dad and I were having lunch and my Dad asked, "Why did you hire my son?" (I never quite know what my Dad is going to say...) I'll never forget Gary's answer, "Well, he had about half of the technical qualifications, but when I found out he was an Eagle Scout and understood the patrol method and came from a large family I knew he would get along with people, and more than half of my problems are people problems, so I knew I'd come out ahead." Now, I'm not about to defend Gary's logic in every case, but the point is that he was making a decision based largely on the social dynamics of the candidate, not on just the technical capability alone. What can I say? I'm glad he did. :-)

Since then as I have been in a position to hire people on my team and observe team chemistry in other teams. All I can say is that the social environment has been for me the number one factor in my personal job satisfaction as well as the explosive X-factor in both success and failure on the teams I have had the opportunity to closely observe. I'd go one step further and say that for an engineer, one hires very often for technical ability not just because the job requires it, but because there's an internal desire to have one who can "speak the language" and really relate to. This socially driven sub-text cannot be ignored in the hiring process. You've got to belong too.

There's yet another problem, and that is that so much of organizational theory set to attack just these sort of knowledge transfer and team problems have as their unstated premise that the people in the firms are homogeneous in nature. Talk of "cross functional teams" ignore the reality of the deep social impact these kinds of teams cause, and therefore, more often than not, the "cross" becomes dysfunctional. I have worked with and stood in awe of brilliant engineers and I can tell you from first hand experience, there is a huge range in the quality of engineers. But it's not just the range, but that the best are so much better than the rest. However, if you have found a few rock stars, a sure way to lose them is to put them on a team where the chemistry is wrong. When rock star engineers leave, their knowledge goes with them. Managing team dynamics is way more important than assigning and organizing the work.

Specialization and Silos

Brown makes the point that, as Adam Smith emphasized, division of labor leads to specialized teams developing specialized improvements to their processes and jobs. But as these teams focus, that very focus often causes them to "develop away from other groups" creating problems of coordination. Management then steps in to "solve" the coordination problems with "process" which in turn often has the unintended side-effect of quelling the creativity! If at this point, you haven't witnessed this kind of behavior in an organization first-hand, well, I'm happy for you, and you haven't been at your current job long enough. ;-)

Tightening controls for coordination almost always leads to reduced creativity, except maybe at Apple. ;-) Certainly their "skunk works" project to develop the Macintosh was an example of loosening control to encourage creativity, but I speak of the current Apple. Apple's organizational secrets are just that, secrets, but one thing I have continued to hear over the years is how organizationally siloed they are. Each team has very little knowledge of the other teams and only a select few interface between the teams and can see the "big picture." While this design might be simply a result of Apple's penchant for secrecy, it might also be one of the key factors in Apple's ability to bring to market new ideas successfully.

The downsides of this super-siloed organizational design is of course that all coordination must be managed by a few and those few will take an extraordinary amount of heat as a result of the friction between groups. On the other hand, over time this very friction could develop into a set of defined boundaries and expectations that leave the several groups fully able to innovate and be creative without the overhead of internal group process. Their process then is their people who skillfully manage the teams both technically and socially. Of course only a few know a great deal about what makes Apple a place where knowledge and creativity can stay and flourish. But who knows, maybe Apple learned one more thing from Xerox way back then, and that one more thing wasn't technical at all, it was the social nature of ideas and development.

Environment

A major reason Xerox lost what they did to Apple was that the Xerox PARC scientists found in the Apple engineers people who looked at the world in a similar way. This similarity in practice and desire to conquer similar problems created an instant social bond and identity between the two groups. It was this social acceptance and mutual understanding centered around a common practice that made it work. But, keep in mind, all it did was make the knowledge transfer happen, there was still a long way to go to turn invention to product innovation. Apple saw the future in 1979, but it wasn't until 1984 that they could actually begin to make the ideas reality. Speaking of this delay Brown says:

This is not a criticism of Apple. Rather, it is an acknowledgment of the organization required to take even something as appealing as the GUI to the marketplace. Within Apple there were many bridges between communities and practices to build. The Macintosh was for a while something of a pariah. The larger Lisa and the older Apple II drew most resources. There are accounts of pitched battles between the old and the new, where the lines of confrontation resemble those between the photocopier stalwarts and PC visionaries within Xerox.

In these conditions, the journey from new invention to robust innovation required hard work, tough decisions, contentious resource allocation, power struggles, hard-won organizational commitment, leadership, and a great deal of trust. It took an organizational leap of faith to build the multidirectional, cross-communal links from R&D, through engineering, manufacturing, sales and marketing, to the market itself. Nothing was preordained. Indeed, the organizational effort was significant enough that developing the knowledge redeveloped the corporation. In all, moving from initial idea to market involved much more than taking it from PARC to Cupertino.

It's easy to sit back and observe large corporations succeeding and failing and take time to opine as to why and what they should have done. The social angle that Brown takes on this interchange between Xerox and Apple brings so much more richness and color to the challenges of any corporation trying to take an invention to market. Certainly, as Brown says, nothing is preordained. When we see successes and failures in the tech industry, the lesson of Xerox is that there is more than meets the eye. This world turns on very small hinges. So many small, but significant things have to go right, so frequently, that it's a wonder to me that anything makes it at all. I suppose maybe that's why you have to love this stuff so much to keep at it. The challenge is so difficult, that only those who love it, stick at it long enough to begin to sense the subtle signs of success.

When designing any kind of product it's important to be able to "get into the head of the user." A key to this kind of thinking is learning to observe how you and others interact with things. Donald Norman often used this approach in his classic book, The Design of Everyday Things. When I first read his book it changed the way I looked at things. Every once in a while, I'm particularly amazed by designs around me. Recently I recognized a few and what follows are three real world objects that I think are interesting from a usability perspective.

How can you ruin the usability of a pen? It's easy: make it so the user can't get to the ink-dispensing mechanism. Here's a picture of the Uni-ball Jetstream pen:

It looks innocent enough, but when I hand this pen to someone, they do the following, almost always in this order:

1. Try to write with it, only to discover there's no pen tip exposed.
2. Try to press the clip end with their thumb in hopes it will "click" to expose a pen tip. It doesn't.
3. Try to twist the clip end hoping this will reveal the pen tip. It doesn't.

At this point, they will do one of two things: Look at me with an expression that says, "Okay, how does this work?" or they will try to pull the pen apart. If they pull hard enough, the cap will come off revealing the writing end and annoyed they will try to remember what they needed the pen for in the first place. Here's what the pen looks like without the cap on:

The user could be a child or adult anyone who wants to write or draw, but to succeed, they must discover the end which dispenses ink. Over time and through our experience with pens we have learned to identify which end of a pen is the writing end. This pen fails because the end without the tip looks like it should write and it doesn't. I think it's the metallic look and cone shape that suggest that it is the end you write with. These 2 simple design choices: shape and material provide a subtle hint that is strong enough to cause significant confusion if not failure in using the pen for its intended purpose.

How could this problem be fixed? The fix is to make the end that doesn't write look like it doesn't write. A change to the color so that it's not sliver would work. Another option would be to make the end cylindrical rather than conical. Either of these would fix the problem. I recently went to the store to see if I could get another pen like this one and I discovered they had changed their design, here's the new look:

A marginal success is something that the targeted user is likely to be successful using, but due to various constraints, it is not living up to its potential. The awesomely named "In-Sink-Erator" disposal in my kitchen falls into this category.

A kitchen disposal is used to grind up bits of food that might plug up your kitchen sink drain or worse: the pipes leading to the sewer. During the normal use of a kitchen sink, leftover food inevitably ends up in the sink. Without the disposal, the user must carefully remove the messy food scraps and throw them into the trash by hand. Because a disposal is composed of mechanical blades that move at high speed, it is a dangerous device. An arrant utensil sent "down the drain" while the disposal was running could harm the machine or user or both. Care must be taken because almost all family members--children and adults--could be interacting with the device.

The drain plug rotates either left or right to turn on and off the disposal. When it's on, there is only a small opening around the plug that lets water through. The plug has 3 functions: 1) turn on and off the disposal, 2) keep hands, utensils, etc. out of the device while it is on, and 3) plug the drain entirely so you can fill the sink with water. All of these are fairly easy to discover and accomplish with rotation of the plug at different levels.

The real advantage of this plug-activated design is that it is impossible to turn on the device and accidentally drop anything into it while it is running. This is a great safety feature, but it comes at a cost. First, the user must reach down into the wet sink to turn on the unit at the very least getting his or her hand wet. This means that before going onto another task, hands will need to be washed and dried again. Second, the opening on the plug is small, which means it gets clogged, filling up the sink. To fix this the user must reach down, turn the plug and pull it out to allow the water to drain. As the water rushes in the disposal cavity the air must escape and as it does, it sprays the user with dirty water. Using this disposal is always safe, but potentially very messy.

Certainly the user doesn't want to lose a finger or bend a fork in the disposal blades, but neither does the user want to get dirty while rinsing dishes in the sink. This device does its job, but the constraint of ultimate safety is at odds with the users immediate goals and makes the device less enjoyable to use.

An alternative solution would be to, have the switch that turns on and off the disposal without the need to reach down into the murky water. For additional safety the switch could be located in a place that requires the user to step away from the sink just enough that if something was ejected from the disposal, like a spoon that had escaped down the drain, the user would be out of range. A single purpose plug could be provided to fill the sink when needed. Rubber baffles around the drain could minimize splashing. This is a compromise on safety, but I think it's the better compromise since the users goals are more focused on cleaning and draining the sink.

This example shows how important it is to design with the context of the user in mind. Their context can expose their goals and desires. It also shows that in an effort solve one problem, you can create secondary and unintended side effects that can be worse than the original problem being solved. Great restraint must be used to avoid this pitfall. Not every problem is worth fixing.

Finding a "Runaway Success" in usability can be difficult because they tend to be invisible. They are so easy to use that it is difficult to imagine that they could be designed in any other way. My Grand Caravan door handles fall into this hall of fame category.

Obviously the external door handle is used to open the door. That is the user's goal. Young or old, tall or short, all who want to enter the car must first open the door.

This is a successful design for several reasons. First it's simple. You see the door and you know how to use it: you pull and it opens. The handle that you grab onto hinges out mimicking the way the door opens. The keyhole is placed next to the handle and relates to and inhibits the handle hinge movement when locked. You can operate the door from below, for example in a wheel chair or a child's height or standing. In a rescue situation a solid handle provides a clear place to securely pull on the door. When in the dark because the door handle material is a different color and is not flush with the door, you can easily find the handle, and once you have found the handle, you have also found the keyhole for unlocking the car. Also, because the handle is a durable plastic, your constant opening of the door minimizes scratched the paint.

There is one thing that could be better in the sliding door handles. The sliding doors slide back away from the front door, but the hinge on the handle swings forward, not back. This makes sense for when closing the door, but not for opening the door and closing the door is easier than opening it in most cases and often done from the inside of the vehicle. My children regularly can't get the door handle open because they are pulling back toward the rear of the car and are not able to achieve sufficient outward pull on the handle. If the hinge on the handle would follow the opening of the door like in the front doors, this problem would be eliminated.

We can learn from the good and bad all around us, but we must take the time to observe. This skill of careful observation is a key to better understanding, compassion and humility when designing something truly usable. Great usability begins with what we see.

In college I was first introduced to this definition for algorithm:

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.¹

An algorithm is a defined process for getting something done. Algorithms are all around us. Recipes are common algorithms. Driving directions can be algorithms. Your morning routine might be an algorithm. How we do the things we do can often, but not always, be described as an algorithm.

In the study of algorithms, we often consider the analysis of how a process scales. That is, as inputs to the process grow to incredibly large sizes, we ask and answer the question: "What factors dominate in determining the cost, both in time and resources, of this process?" The answers to this question often take the form of common mathematical growth functions shown in the diagram below:

As you move across the x-axis you can see that each of these functions grows or increases along the y-axis. While they all grow, they do so at different rates. For example, the linear growth rate is greater than the logarithmic growth rate. In fact you can visually compare each of these curves rather easily for these small values of x, but doing this visual comparison for small values isn't where algorithm analysis normally starts. Remember the point of all this is to answer the question, "But how does it scale?" or "For very large inputs (values of x), which function increases the least?" If an algorithm's representative growth function can scale well, there's profit to be made.

For example, below is a basic chart of possibly the worst of all algorithms for sorting a list of items, namely, Bubble sort.² Imagine a machine you pay to sort items using Bubble sort. The amount you'll have to pay depends on the number of items you ask the machine to sort. The x-axis shows the number of items to sort and the y-axis shows what it will cost, in dollars.

As you can see, the cost of this algorithm grows rapidly. With only 35 items to sort, this Bubble sort machine would cost you well over $1,000 to do the work! You might recognize this graph; it is the graph of an n² function. Any algorithm that grows its cost in a way that follows the general form of an n² function we call an n² algorithm.

The "cost" of an algorithm depends on what you count. In the previous example we counted dollars spent on sorting the items. For computer algorithms the costs normally counted are space and time. Time measures how long the algorithm takes to complete as the number of items increases. Space measures how much extra memory or disk space is needed to complete the algorithm. In other fields, an algorithm's "cost" might refer to other things like money, people required or even distance traveled.

There are only a handful of general functions that are used to represent an algorithm's cost. Here they are:

It is important to note with these functions that when the number of items to process is very small, the cost difference is also relatively small. For example, consider the relative cost of processing 5 items using different algorithms, each with a different efficiency type or class. Of course, the dollar costs shown below are fictional, but it should help you compare the different kinds of algorithms. The cost difference between each class of function follows:

This table orders the function types from least expensive to most expensive at large-scale, that is, when the number of items to process is much larger than five. Even so, some of the more costly functions (Exponential for example) are actually cheaper when considered for only 5 items. Normally, algorithm analysis ignores cost at small-scale and looks at what the relative costs are when things get really, really big. Let's look at 1 million items. That's a big number, and for most people, if they sell or work with 1 million things, that qualifies as a large-scale system.

At large-scale, this kind of analysis begins to make sense. With 1 million things to process, you can really see how the order of growth changes dramatically. If you were responsible for a manufacturing plant and had a process whose cost function was an n² function and you were able to change the process to something that cost more along the lines of a "n-log-n" function, well, you'd have a competitive advantage of $999,994,000,000! That is probably enough to get you that next promotion!

Taking the time to look at your processes, or algorithms, and improving them can result in amazing economic benefits when you are working with large-scale systems. Small changes, even seemingly simple modifications in a core or costly work process can add up to huge economic returns.

What we've been discussing has a name and it is called: asymptotic complexity analysis. It's called this because as an algorithm approaches very large inputs, the cost graph "looks like" or "asymptotically approaches" one of the key functions mentioned above. For our purposes, the word complexity simply means cost.

Economics

What does this asymptotic complexity analysis have to do with Economics? Consider this definition for Economics:

Economics: the branch of social science that deals with the production and distribution and consumption of goods and services and their management.⁵

Algorithms can optimize production, distribution and consumption, and these advancements can save time and money and drive economic growth. There are large economic incentives to scale up your business and reap the rewards that come with increased size and algorithms can help you do this. Remember, algorithms define how you do what you do, and at large-scale, they really matter. The following examples should better illustrate the value of algorithms in production, distribution and consumption of goods and services.

Production

For years the US Constitution has protected manufacturing algorithms in the form of process patents. These limited monopolies began with these lines in the Constitution:

"The Congress shall have Power ... To promote the Progress of Science and useful Arts, by securing for limited Times to Authors and Inventors the exclusive Right to their respective Writings and Discoveries;"⁶

The constitutional patent protection has been further clarified as follows:

"Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement therefore, may obtain a patent therefore."⁷

The ability to secure a process patent for exclusive use has obvious economic value. If you are able to discover and patent a new, more effective process for producing a chemical, drug or other material, the process patent offers a legal protection for your algorithmic advantage. It is for this and other reasons that capturing process patents offer a significant financial incentive.

The patent protection of algorithms is not new. The first patent for a chemical process was granted in 1793 for a process used to make potash.⁸ Since then many famous chemical processes have been patented.⁹

While there are those who criticize the patent system, even some of the most ardent opponents of the current system have concluded "the patent system still appeared to offer positive innovation incentives for drug and chemical firms."¹⁰

To summarize there are at least three key ways algorithms have a significant impact on economic production:

• Better algorithms can lower production costs
• Better algorithms can allow production to scale
• Better algorithms patented can provide a competitive advantage

As companies deal with market pressures, algorithms-their discovery, improvement and protection-are an important part of doing business.

Distribution

When we think of the distribution of goods, images of trucks, trains, boats and planes crisscrossing the globe often come to mind. Certainly when you attempt to achieve large-scale distribution, the need to move goods across the globe becomes important. This kind of physical distribution is critical to many economic activities.

Overnight delivery services were largely unknown before the birth of FedEx. Yet it was an insight and an algorithm and its application to shipping that led FedEx to become a synonym for next day delivery. In his autobiographical account of starting up FedEx, Fred Smith explains how the algorithm he chose for distribution was central to his initial design for the company:

"My solution was to create a delivery system that operates essentially the way a bank clearinghouse does: Put all points on a network and connect them through a central hub. If you take any individual transaction, that kind of system seems absurd-it means making at least one extra stop. But if you look at the network as a whole, it's an efficient way to create an enormous number of connections. If, for instance, you want to connect 100 markets with one another and if you do it all with direct point-to-point deliveries, it will take 100 times 99-or 9,900-direct deliveries. But if you go through a single clearinghouse system, it will take at most 100 deliveries. So you're looking at a system that is about 100 times as efficient."¹¹

The insight was the growing need to transport goods reliably overnight and the algorithm was this "spoke and hub" delivery system. The algorithm was not new, in fact Delta was already using it when FedEx was in its infancy, but it's application to shipping and next day delivery was new.¹² For FedEx this algorithm served as their initial economic advantage.

Another example of algorithms and distribution improvements comes from UPS and their Right Turn Policy.¹³ UPS has always tried to optimize their delivery routes, but in 2005 UPS began the process of creating a new computerized route optimization system. This new system was in essence an algorithm that allowed for faster delivery of more packages while reducing costs. The new system generates delivery routes that do all they can to avoid left turns and the idling and waiting that accompany them. Ninety percent of the time, if a UPS truck is turning, it's turning right. For a company that delivers 15.8 million packages and documents around the world each day with a fleet of almost 100,000 cars, vans, tractors and motorcycles, this algorithmic improvement adds up.¹⁴

What have been the results of this optimization? In 2007 the algorithm removed 30 million miles off its delivery routes, saved 3 million gallons of gas, and reduce CO2 emissions by 32,000 metric tons, equal to removing 5,300 passenger cars from the road for an entire year.¹⁵

When it comes to distribution systems on a large-scale, the development and choice of algorithms have not only an economic impact, but an environmental one as well.

Consumption

It's hard to imagine now, but it wasn't long ago that searching for and gathering information involved travel, visiting libraries and other institutional records facilities. Google has changed all that, and at the heart of that change was an algorithm, namely PageRank.

It all began at Stanford in 1995. Larry Page and Sergey Brin met while Page was considering attending Stanford for his graduate degree.¹⁶ Part of their research was focused on a "web crawler" that would visit every web page it could find and begin to analyze the page and it's relative importance. The algorithm for determining a page's rank ultimately received the creative name of PageRank. By 1998 PC Magazine reported that Google "has an uncanny knack for returning extremely relevant results."¹⁷

How did this algorithm work?¹⁸ At the most basic level it would create a "citation graph" of the World Wide Web. Pages with more citations or links to it would be given a higher page rank. This idea was not new, but using web links and other web meta data and applying it to cataloging and judging the vast and growing data online was something new indeed.¹⁹

By August 1996, this research project part of the Digital Library Project in the Computer Science Department at Stanford had discovered roughly 75 million pages on the Internet and indexed about 30 million of them in a 28 GB database! It was obvious that the Google algorithm would need to be something that could deal with scale. This algorithm would need to deal with enormous amounts of data while still allowing instantaneous access to a constantly changing data set.²⁰

This one algorithm solved a real problem: finding relevant information when faced with the information overload online. Word spread fast and soon almost everyone was going to Google to search the web. This presented an opportunity to sell contextual and relevant ads along with the search results and the rest is, as they say, history.

In Google's case, the PageRank algorithm is perhaps one of the most useful and lucrative algorithms in recent history, but it has not come without challenges. Google has had to constantly combat those who try to game the system for profit, using the fact that a system based on an algorithm, even a "smart" one, has inherent and repeatable weaknesses.

Googlebombing is when a person or group tricks Google's algorithm to return a certain search result. Since at least 1999 people have attempted to influence the ranking of particular pages in the search results returned by Google. My first experience with googlebombing was when I was informed that the top result for the search "more evil than Satan himself" was a link to Microsoft's web page.²¹ Google resisted manually tweaking these results citing the importance of the "objectivity" of the algorithm.²² In 2007 Google changed the algorithm so that this kind of thing was more difficult,²³ but the economic incentive to be on the first page of Google's search results has continued to motivate determined hackers and business people alike.²⁴ Search Engine Optimization (SEO) is the process of changing your website's data to improve rank and relevance in the Google search results.²⁵ While there are legitimate ways to improve your rank, significant effort has been invested in finding ways to illegitimately place their website on the first page or top spot in the search results.²⁶ Additionally Search Engine Optimization scams are prevalent. It is common for a business to pay a purported SEO company for a better page rank, often with little success.²⁷

Clearly, Google's success shows that creation of a new algorithm for doing something that scales can be a critical part to business. Still, that was not enough. Google has had to continually adapt the algorithm to changes in the market. Perhaps this simply underscores the fact that the people who can invent, maintain and improve these algorithms are even more economically valuable than the algorithms themselves.

The Dark Side of Algorithms

"Not everything that can be counted counts, and not everything that counts can be counted." - Albert Einstein²⁸

One of the great things about an algorithm is the fact that it is an "unambiguous sequence of instructions." This unambiguous nature allows for repeatability and scalability, but this very strength is also a weakness. Process patents, desirable as they are, often specify in clear terms what it means to follow the process and what it means to do something different and thereby avoid infringing on the patent. Since patents are public, you are in a sense giving the competition the map to the minefield! The other and perhaps larger weakness with algorithms is that there are qualities like style, judgment, understanding and creativity that simply resist being defined algorithmically.

Clearly employing repeatable and scalable processes to produce, distribute and consume goods and services is a boon economically, but there is a dark side to this specification and reduction of all things into a "sequence of unambiguous instructions for solving a problem."

Food

Consider your personal experience with food. Have you noticed a difference between homemade meals and those produced at a fast food establishment? If you have, you probably haven't noticed that the fast food was better. McDonalds famously applied for a patent with a 55-page description of a "Method and Apparatus for Making a Sandwich" underscoring their algorithmic focus to food production.²⁹ While much of what has made McDonalds successful has been their focus on algorithmic repeatability, this has allowed for worldwide growth in scale, not deep improvements in culinary quality.

The quality of food isn't just in how it tastes, but also in how it helps us to stay healthy. Large-scale and efficient food production has been helpful in meeting the world's hunger needs, but along with the scale have come other problems. High output factory processes have created new risks for large-scale food-borne illnesses³⁰ and high yield crops can generate food of decreasing nutritional value.³¹

The Unquantifiable

"The only problem with Microsoft is they just have no taste, they have absolutely no taste, and what that means is - I don't mean that in a small way I mean that in a big way. In the sense that they, they don't think of original ideas and they don't bring much culture into their product" - Steve Jobs, 1996³²

How does one define in systematic and unambiguous terms what is original, beautiful, stylish, elegant or even culturally valuable? Some things simply resist precise definition. Additionally, there is an economic reality that often good enough is sufficient, especially on a large-scale. One can be remarkably successful without these ambiguous and intangible qualities like beauty and elegance. Certainly Jobs' assertion that Microsoft lacks taste hasn't kept the company from being phenomenally successful. Indeed taking the extra time and money to push your work to the level of art can easily be considered wasted effort from an algorithmic efficiency point of view.

On the other hand consider Steve Jobs assessment of their "system" for developing innovative products:

The system is that there is no system. That doesn't mean we don't have process. Apple is a very disciplined company, and we have great processes. But that's not what it's about. Process makes you more efficient.

But innovation comes from people meeting up in the hallways or calling each other at 10:30 at night with a new idea, or because they realized something that shoots holes in how we've been thinking about a problem. It's ad hoc meetings of six people called by someone who thinks he has figured out the coolest new thing ever and who wants to know what other people think of his idea.³³

For a company so often praised for style, beauty, innovation and elegance it's somewhat surprising that Apple doesn't have a system in place to ensure continued success along these lines. The reason for this omission is that creativity, art, style and beauty remain far outside the algorithm's grasp.

Banking

Perhaps nothing is more central to our economic system than banking. As banking operations have become more sophisticated and computer automated, the use of algorithms to make important decisions has increased.³⁴

In the past, getting a loan meant a personal visit to a loan officer of a bank and an interview. Following the interview and documented analysis of income, the loan officer would discuss the loan with a loan approval committee and make the case for issuing the loan.³⁵

Now, algorithms and risk probability models often replace this human factor. Is this better? The answer is complicated, but the underwriting of subprime loans for individuals and institutions that were unable to service the loan may not have occurred except for the powerful force of statistical algorithms and investment models suggesting it was a prudent course.³⁶ These "bad loans" contributed to the housing bubble and the current US economic climate.³⁷ We are now in the meltdown of the US residential real estate market and the beginnings of a commercial real estate depression.³⁸ Perhaps there is room for more human judgment in banking loan decisions. This brings to mind what Warren E. Buffett said about the complex securities engineered by Wall Street mathematicians: "Beware of geeks bearing formulas."³⁹

Problems of Scale

One reason to focus energy on algorithms comes from the problems associated with scale. When you grow the raw size of an organization or the customers you serve, algorithms can help you deal with that growth in a uniform way. On the other hand, this very growth can make it hard to focus. The reason that focus is often lost at scale is that a small percentage of a big number is still a big number! Even small problems are big problems when magnified by the sheer size of things. Focused efforts become more defuse, as almost any effort pales in comparison to the magnitude of the overall size of things. In this case, one's focus on size, algorithms and their efficiency are of utmost importance, but this comes at the cost of a host of smaller advancements which can be the seeds of real innovation.⁴⁰

Sometimes limiting growth can help generate profit as you focus on quality or target your product effectively. Apple has done this recently with the iPhone. While many have suggested that Apple should focus on capturing market share, Apple has been focusing on profit-share. According to a recent report, Apple made $1.6 billion in operating profit off of the iPhone in Q3 2009. In the same quarter Nokia, made $1.1 billion, but consider this: Apple owns 2.5% of the cell phone market while Nokia controls about 35% of the market! Apple's focus is on a smaller sector of the market, but a sector where they can be focused and extremely profitable.⁴¹

Apple doesn't always play only for profit share. Certainly the iTunes Music Store is a market share leader, but there is something to be learned from growth through focus rather than scale. Apple's own iPhone App Store provides another example of large-scale and the challenges of "quality vs. quantity" that often come with it.⁴²

Algorithms and Their Limitations

Thinking deeply about the core algorithms in your work can be very productive and help you gain a competitive advantage. Algorithmic complexity analysis can help you find areas where you can improve your economic returns significantly. Many great companies have at their core a collection of algorithms that form the engine of their success.

Algorithmic study makes the most economic sense on a large-scale but don't get caught up in the desire to scale. Sometimes the focus that is provided at small scale can allow you to produce things that would simply be impossible to produce in a large-scale environment. Asymptotic complexity is not everything! You can know how to do something extremely well and not be able to explain it or reproduce it at scale, yet it can still be very valuable. There are many important things that can't be succinctly described in an algorithm and this very fact may be your competitive advantage.

References

¹ Levitin, Anany V. Introduction to the Design and Analysis of Algorithms. 2nd ed. Addison Wesley, 2006. Print. ↩

² For an introduction to Bubble sort see: Bubble sort. Wikipedia: The Free Encyclopedia. Web. ↩

³ This number is very large. I used the command line tool bc, an arbitrary precision calculator, to calculate it and the result was a number 301,030 digits long! It would take 110 pages just to print this number. ↩

⁴ This number is very, very large. It's so large, in fact, I'm not sure how to calculate it. ↩

⁵ Definition of "economics." WordNet. Princeton. Web. ↩

⁶ "Transcript of the Constitution of the United States - Official." Web. 5 Dec 2009. (see Article 1, section 8, clause 8) ↩

⁷ "35 U.S.C. 101 Inventions patentable. - Patent Laws." Web. 5 Dec 2009. ↩

⁸ "BENEFICIATION OF POTASH - Google Patent Search." Web. 5 Dec 2009. ↩

⁹ Bessen, James, and Michael J. Meurer. Patent Failure: How Judges, Bureaucrats, and Lawyers Put Innovators at Risk. illustrated edition. Princeton University Press, 2008. Print. ↩

¹⁰ Ibid. ↩

¹¹ Smith, Fred. "How I Delivered the Goods." Web. 5 Dec 2009. ↩

¹² "Online Extra: Fred Smith on the Birth of FedEx." Web. 5 Dec 2009. ↩

¹³ "Right Turn at the Right Time - UPS Pressroom." Web. 5 Dec 2009. ↩

¹⁴ "UPS Fact Sheet - UPS Pressroom." Web. 5 Dec 2009. ↩

¹⁵ Right Turn at the Right Time ↩

¹⁶ "Corporate Information - Google Milestones." Web. 5 Dec 2009. ↩

¹⁷ "PC Magazine: Top 100 Web Sites (Google!)." Web. 5 Dec 2009. ↩

¹⁸ For a deeper explanation of the algorithm see the patent: "Method for node ranking in a linked database - Google Patent Search." Web. 5 Dec 2009. ↩

¹⁹ "Working Paper SIDL-WP-1997-0072." Web. 5 Dec 2009. ↩

²⁰ "Stanford BackRub Web Project." Web. 5 Dec 2009. ↩

²¹ Sullivan, Danny "Google Bombs Aren't So Scary - Search Engine Watch (SEW)." Web. 5 Dec 2009. ↩

²² "Official Google Blog: Googlebombing 'failure'." Web. 5 Dec 2009. ↩

²³ Co-written with Ryan Moulton and Kendra Carattini. "Official Google Webmaster Central Blog: A quick word about Googlebombs." 25 Jan 2007. Web. 5 Dec 2009. ↩

²⁴ "The Times (UK) Spamming Social Media Sites - Waxy.org." Web. 5 Dec 2009. ↩

²⁵ "Official Google Webmaster Central Blog: Google's SEO Starter Guide." Web. 5 Dec 2009. ↩

²⁶ "Derek Powazek - Spammers, Evildoers, and Opportunists." Web. 5 Dec 2009. ↩

²⁷ "Search Engine Optimization (SEO) - Webmasters/Site owners Help." Web. 5 Dec 2009. ↩

²⁸ Albert Einstein, a US (German-born) physicist (1879-1955). This quote is attributed to him because of sign that he had hanging in his office at Princeton. ↩

²⁹ "(WO/2006/068863) METHOD AND APPARATUS FOR MAKING A SANDWICH." Web. 5 Dec 2009. ↩

³⁰ Roberts, Paul. The End of Food. Reprint. Mariner Books, 2009. Print. ↩

³¹ Pawlick, Thomas F. The End of Food: How the Food Industry is Destroying Our Food Supply--And What We Can Do About It. 1st ed. Barricade Books, 2006. Print. ↩

³² Sen, Paul. Triumph of the Nerds. Ambrose Video, 2002. Print. Transcript. ↩

³³ "The Seed of Apple's Innovation." Web. 12 Oct 2004. ↩

³⁴ Kim, Jane J. "New FICO Credit Score Debuts." wsj.com 29 Jan 2009. Wall Street Journal. Web. 5 Dec 2009. ↩

³⁵ Clark, Kim B. Speech given at a City Club luncheon December 18, 2008 ↩

³⁶ Coy, Peter. "Why Subprime Lenders Are In Trouble." BusinessWeek: TopNews 2 Mar 2007. BusinessWeek. Web. 5 Dec 2009. ↩

³⁷ "Declaration of the Summit on Financial Markets and the World Economy." Web. 5 Dec 2009. ↩

³⁸ Foust, Mara Der Hovanesian, Dean. "Why This Real Estate Bust Is Different." BusinessWeek: Online Magazine 5 Nov 2009. BusinessWeek. Web. 5 Dec 2009. ↩

³⁹ Lohr, Steve. "Like J.P. Morgan, Warren E. Buffett Braves a Crisis." The New York Times 6 Oct 2008. NYTimes.com. Web. 5 Dec 2009. ↩

⁴⁰ Weiss, David. "Impatience and Design by Counter Example" 6 Nov 2006. Web. 5 Dec 2009. ↩

⁴¹ "While Rivals Jockey For Market Share, Apple Bathes In Profits." Web. 5 Dec 2009. ↩

⁴² Gruber, John. "Daring Fireball: Pound the Quality." Web. 5 Dec 2009. ↩

The other day I noticed one of my friends login to his laptop. I do this all the time, so that he logged in wasn't unusual, but how he did it, that caught my attention. He slid his finger on a small sensing area and after some delay he was logged in! No username and no password! This piqued my curiosity, put me on a research track. Here is what I discovered.

What are Biometrics?

When you login to your computer, security experts would say you authenticate. That is, you prove to the computer that you are indeed who you say you are. There are three ways you can normally prove who you are [2]:

1. What you know
2. What you have
3. Who you are

When you login with a password, you are using the first form, what you know. If the password is kept secret and sufficiently hard to guess, when you enter your password the computer assumes it must really be you, because no one else would know the secret password. By this logic you are authenticated. There are other ways you can prove that you are who you say you are. When you purchase something with your credit card, or unlock your car door, you are normally authenticating with something you have. When someone checks your passport picture against what you look like, this is using two forms of proof: What you are, your face and what you have, namely the passport.

So what are Biometrics? From the word you might be able to deduce some of the meaning. The "bio" part means of or pertaining to biology. The "metrics" part relates to measurement. Put together biometrics it is the measurement of biological data. For authentication purposes a biometric is a physical characteristic that can be measured and then used to identify a specific individual.

When you use a "what you are" proof, it helps that you choose an attribute that is unique. If I used my height to prove that I am who I say I am, most of you would laugh. Why? Because there are lots of other people 6 feet 4 inches tall. For a strong identification, uniqueness matters.

How do fingerprint biometrics work?

Each fingerprint contains ridges in the skin which are detectable. These ridges make patterns which you can see with the naked eye. The ridge patterns can make loops, arches or whorls. In each fingerprint there are areas where one ridge changes, these points of change are called minutia. When a ridge ends, splits into two ridge, joins another ridge or creates a island; all of these features in a fingerprint are minutia. [10]

A fingerprint scanner detects the larger ridge patterns and records the following information about the minutia:

1. Orientation - the direction the minutia is facing
2. Spacial Frequency - how far apart specific features are located
3. Curvature - the rate of orientation change
4. Position - the (x, y) location relative to some fixed point

All of these can yield up to ideally 60 or 70 minutia for a single fingerprint. [10]

When a person first configures a scanner to use their fingerprint, this is called enrollment. This is a key time where strict process must be followed so as to avoid someone enrolling another's fingerprints as his or her own. In this process several fingerprints are recorded by the system and then an averaged template of the fingerprint is stored in the system. [10]

After enrollment, when a new fingerprint is supplied to the system, a statistical match is sought. If no match is discovered, the person is denied access. If a match is found, the person is granted access. Since biometric measurement can change slightly with each scan, determining a match is a probabilistic process. There is always a possibility that a valid fingerprint is rejected or an invalid fingerprint is determined to be good. [10]

What are the advantages and disadvantages?

To compare the relative merits of fingerprint as a biometric, we can considering the following properties of a good biometric [11, 6, 3]:

1. Universality - each person has the characteristic
2. Uniqueness - the characteristic is unique per person
3. Permanence - characteristic remains the same over time
4. Collectability - how easy is it to measure the characteristic
5. Performance - accuracy, speed, and resource requirements
6. Acceptability - culturally accepted by the population
7. Circumvention - robust against fraudulent attacks

Universality

Fingerprints are largely universal. About 2% of the population can not use fingerprints due to skin damage or genetic factors.

Uniqueness

An important aspect of any biometric is that the characteristic be unique among all participants. Empirical evidence of fingerprints gathered since at least 1892, have found no two pairs of fingerprints that are identical, even between twins. [10] While this is reassuring, more recent research [13] indicates that the minutiae-based uniqueness as measured by fingerprint scanners may not be sufficient to determine individuality in every case.

Permanence

Fingerprints can be damaged and change due to manual labor or injuries.

Collectability

A key aspect of any biometric is the reliability of the measure coupled to the convenience of making the measurement. [10] Fingerprints are easy to collect and the systems today very inexpensive, around $20 per scanner if purchased in bulk.

Performance

Fingerprint recognition systems for large-scale deployments require a large amount of computational resources. For smaller populations the computational resources are smaller making this trade off allows for the current use in personal computers. Still compared with face recognition, for example, fingerprint scanners are more accurate, faster and require less computation and storage. Face recognition may seem very intuitive for humans, but the current mature computer systems are still far away from reliable face recognition in practice. [9]

Acceptability

Fingerprints are perhaps the most accepted biometric short of facial recognition. Still, the acceptance of biometric authentication technology depends on context, perceived benefit for the user and perceived privacy risks. [1]

Circumvention

Fingerprints are not impervious to attack, but using multiple finger scans can make the system harder to attack. ( see Myth Busters http://www.youtube.com/watch?v=MAfAVGES-Yc ) One method for improving the accuracy of biometric authentication systems is to enforce "two-factor authentication", that is one must authenticate by some biometric form as well as use a password or posses a token. [10] This additional factor can significantly harden the system.

Problematic Properties

Among the currently available biometrics, fingerprints have a large collection of positive characteristics. Some of the advantages of a biometric are that you don't have to remember passwords, don't have to worry about forgetting a password or smart card and it cannot be easily changed. [4] Because of these advantages systems have been developed for so called "One Touch Logon" [12] but in these systems one still makes significant trade offs between a password-based system and a fingerprint biometric based system. There are large trade offs between security and privacy [11] when using fingerprint biometrics.

Fingerprints have other problematic properties. They can be changed or damaged and some simply don't have fingerprints. Often because of these limitations fingerprint authentication systems have an alternate password based "back door" which can become the weakest link in the authentication system.

I think the biggest problem is that fingerprints are not very private, we leave fingerprints everywhere! Storing large amounts of fingerprint data in a safe way becomes a real challenge. If that data were exposed, criminals might devise a way to create fingerprints from the template data that fool fingerprint scanners. Biometrics in general are or can be unique identifiers, but they are not secrets. [7] Once a fingerprint is stolen, it's stolen for life! You can never get back to a secure situation! With a password or token system you can re-issue the token and invalidate the old token, or change the password. Not so with fingerprints! They are useful, but they are not keys. Keys need to be secret, random and easily updatable. Fingerprints are none of these things.

If fingerprint were to become the common authentication across different applications used for everything from logging onto your PC to accessing your bank account to opening your garage door, then value of stealing this information goes up significantly. At least with passwords you can spread the risk across different passwords for different services creating multiple barriers that must be overcome for full disclosure. With our fingerprints we have only ten of them.

References

[1] Heckle, R. R., Patrick, A. S., and Ozok, A. 2007. Perception and acceptance of fingerprint biometric technology. In Proceedings of the 3rd Symposium on Usable Privacy and Security (Pittsburgh, Pennsylvania, July 18 - 20, 2007). SOUPS '07, vol. 229. ACM, New York, NY, 153-154. DOI=http://doi.acm.org/10.1145/1280680.1280704 

[2] Guinier, D. 1990. Identification by biometrics. SIGSAC Rev. 8, 2 (May. 1990), 1-11. DOI=http://doi.acm.org/10.1145/101126.101127 

[3] Jain, A. K. and Ross, A. 2004. Multibiometric systems. Commun. ACM 47, 1 (Jan. 2004), 34-40. DOI=http://doi.acm.org/10.1145/962081.962102 

[4] Boatwright, M. and Luo, X. 2007. What do we know about biometrics authentication?. In Proceedings of the 4th Annual Conference on information Security Curriculum Development (Kennesaw, Georgia, September 28 - 28, 2007). InfoSecCD '07. ACM, New York, NY, 1-5. DOI=http://doi.acm.org/10.1145/1409908.1409942 

[5] Markowitz, J. A. 2000. Voice biometrics. Commun. ACM 43, 9 (Sep. 2000), 66-73. DOI=http://doi.acm.org/10.1145/348941.348995 

[6] Jain, A., Hong, L., and Pankanti, S. 2000. Biometric identification. Commun. ACM 43, 2 (Feb. 2000), 90-98. DOI=http://doi.acm.org/10.1145/328236.328110 

[7] Schneier, B. 1999. Inside risks: the uses and abuses of biometrics. Commun. ACM 42, 8 (Aug. 1999), 136. DOI=http://doi.acm.org/10.1145/310930.310988 

[8] Bergadano, F., Gunetti, D., and Picardi, C. 2002. User authentication through keystroke dynamics. ACM Trans. Inf. Syst. Secur. 5, 4 (Nov. 2002), 367-397. DOI=http://doi.acm.org/10.1145/581271.581272

[9] Zhao, W., Chellappa, R., Phillips, P. J., and Rosenfeld, A. 2003. Face recognition: A literature survey. ACM Comput. Surv. 35, 4 (Dec. 2003), 399-458. DOI=http://doi.acm.org/10.1145/954339.954342 

[10] Alfred C. Weaver, "Biometric Authentication," Computer, vol. 39, no. 2, pp. 96-97, Feb. 2006, doi:10.1109/MC.2006.47 http://doi.ieeecomputersociety.org/10.1109/MC.2006.47 

[11] Salil Prabhakar, Sharath Pankanti, Anil K. Jain, "Biometric Recognition: Security and Privacy Concerns," IEEE Security and Privacy, vol. 1, no. 2, pp. 33-42, Mar. 2003, doi:10.1109/MSECP.2003.1193209 http://doi.ieeecomputersociety.org/10.1109/MSECP.2003.1193209 

[12] Beomsoo Park, Sungjin Hong, Jaewook Oh, Heejo Lee, Yoojae Won, "One Touch Logon: Replacing Multiple Passwords with Single Fingerprint Recognition," cit,pp.163, Sixth IEEE International Conference on Computer and Information Technology (CIT'06), 2006 http://doi.ieeecomputersociety.org/10.1109/CIT.2006.128 

[13] Pankanti Sharath, Prabhakar Salil, Jain Anil K., "On the Individuality of Fingerprints (2002)," IEEE Transactions on Pattern Analysis and Machine Intelligence, http://biometrics.cse.msu.edu/cvpr2001_indiv.ps

Since the beginning of the Internet people have shared URLs with each other. Often the vehicle for sharing URLs was an email or a personal web page with favorite links. Today there are bookmarking websites where users share URLs, comment on them and rate them. [1] As the popularity of Twitter increases, more and more people are using Twitter to share URLs with each other. [2] The 140 character limit on communication with Twitter combined with the reality that many URLs are easily longer than 140 characters has given rise to more and more URL shortening services. While these services do a simple mapping, exchanging one short URL for a longer one, there are risks involved with trusting a third party to redirect you to a web page.

The basic idea for a URL shortening service is to exchange one URL that is short to another that is long. Typically the long URL is the desired destination. A person might send the short URL to a friend. When the short URL is clicked, the website looks up the longer URL and redirects the user to the longer URL. For example, suppose I just got an Amazon Kindle 2 and I wanted to share with my friends more information about it. Amazon typically has very long URLs. The URL for the Amazon Kindle 2 is as follows:

http://www.amazon.com/Kindle-Amazons-Wireless-Reading-Generation/dp/B00154JDAI/ref=amb_link_83624371_1?pf_rd_m=ATVPDKIKX0DER&pf_rd_s=center-1&pf_rd_r=0YPC2AH8155PQV3FWRPN&pf_rd_t=101&pf_rd_p=469942651&pf_rd_i=507846

That's 215 characters! I'll use this URL as the original URL with the following services to give you an ideas how they work:

bit.ly - http://bit.ly/

http://bit.ly/Z6eYE  19 characters

budURL - http://budurl.com/

http://budurl.com/bsfs  22 characters

eweri - http://eweri.com/

http://eweri.com/8rC  20 characters

hex.io - http://hex.io/

http://hex.io/ajz  17 characters

idek.net - http://idek.net/

http://idek.net/3kH  19 characters

is.gd - http://is.gd/

http://is.gd/lg7L  17 characters

lin.cr - http://lin.cr/

http://lin.cr/fvc  17 characters

POPrl - http://poprl.com/

http://poprl.com/Lm3  20 characters

snipurl - http://snipurl.com/

http://snipurl.com/cucc2  24 characters

tinyurl - http://tinyurl.com/

http://tinyurl.com/bngrky  25 characters

twurl - http://tweetburner.com/

http://twurl.nl/no316s  22 characters

urlBorg - http://urlborg.com/a/

http://ub0.cc/60/3G  19 characters

zi.ma - http://zi.ma/

http://zi.ma/65226b  19 characters

As you can see the original URL was 215 characters long, while the longest of the shortened URLs was only 25 characters long. I could post this shortened URL on Twitter and still have an expansive 115 characters left to comment on this URL. Perfect.

There are over 90 URL shortening services available online. A more complete list of URL shortening services is located at http://mashable.com/2008/01/08/url-shortening-services/.

Trusted or Untrusted

The most obvious risk associated with URL shortening is that it's difficult to know where the URL will take you, until you click it. The true destination of the URL is opaque. Often when I receive a dubious link via email, I hover my mouse over the URL, or view the HTML source to discover the real URL destination address and evaluate if I trust it enough to click. With a shortened URL, it's hard to know where it will take me, until I click it. Email Phishing scams are using URL shortening service for this very reason. [7]

Another problem with URL shortening is how it interacts with filters. A spam filter could use the URL in the past as one more hint that the email could be nefarious, but with a URL shortening service as the broker of URLs, the filter can't make any judgment about the URL. Many URL shortening services take spam complaints and will disable URLs if they are discovered to point to spam websites. [3] Some also proactively search their URLs for blacklisted websites and remove or disable these shortened URLs. [4]

Not just spam filters can be bypassed. Both Firefox and Google Chrome web browsers use Google Safe Browsing [5] a feature with warns users of malware or phishing sites. In the past using a shortened URL, instead of getting a warning message, users are sent directly to the dangerous web page. [6]

Less serious, but still problematic is using URL shortening services to hide the motive for an online review or recommendation. A seemingly objective review is tainted when readers discover that the author gets a monetary kick back for sending people to the reviewed product's site. Since shortened URLs hide the real URL they can be used to hide affiliate URLs and surreptitiously link to online stores. Most affiliate URLs are easy to spot, but when wrapped in a shortened URL, detection is more difficult. [8]

Another more remote, but still plausible problem with URL shortening is that should a URL shortening service become compromised, hacking one site would allow for redirecting popular shortened URLs to phishing or malware sites.

Getting More Transparent

Many URL shortening services have added some level of "see before you click" functionality. For example, any tinyurl can be prepended with the text "preview" in the URL and it will not redirect, but show the destination URL for inspection at tinyurl.com. Take the tinyurl above

http://tinyurl.com/bngrky

and modify it as follows:

http://preview.tinyurl.com/bngrky

While this adds characters to the URL, it allows the user to evaluate the URL before redirecting to the site. BudURL has an even more compact preview function. Just adding a '?' to the end of the URL will turn it into a preview URL.

http://budurl.com/bsfs  will auto redirect to the original URL

http://budurl.com/bsfs?  will preview the link first

Some of the services provide a little popup window that displays a picture of the webpage when you hover over the URL link.

Conclusion

A hacker or spammer is empowered by using a "benign" URL shortening service that everyone uses and everyone trusts. Once the click is made, a homographic attack may follow and will make it very difficult for a normal user to detect that they are being redirected to a phishing site. The real danger is that people have become habituated to trusting unknown links from their friends. This is dangerous because if their friend's account is compromised, it might not be their friend sending a link and the shortened URL will be clicked without concern.

An example of this propensity to click occurred 12 Feb 2009. One of my friends tweeted, "Don't Click: (link)". I was curious, but I didn't click the link. Next another posted the same thing, than another! It seemed fishy to me, and I later found out that the link presented a web page with another button that said, "Don't Click!" Naturally curious people, and trusting in their friend's recommendation, clicked the button and all of the sudden they noticed that they had in fact tweeted the same link though they never consented to doing so! It was the first socially engineered twitter virus. [9] While this virus was started as a joke, it spread extremely fast. [10] Luckily this social virus was harmless, but it reinforces how effective a socially engineered virus can be.

There are always trade off decisions to be made. In this case, the trade off is between the convenience of a short URL and the need for disclosure of a URL's destination.

References

[1] Tony Hammond, Timo Hannay, Ben Lund and Joanna Scott. - Social Bookmarking Tools (I): A General Review In: D-Lib Magazine 11, Nr. 4, 2005 http://www.dlib.org/dlib/april05/hammond/04hammond.html

[2] State of the Twittersphere - Q4 2008 Report - http://blog.hubspot.com/blog/tabid/6307/bid/4439/State-of-the-Twittersphere-Q4-2008-Report.aspx

[3] is.gd - Technical Information - http://is.gd/tech.php

[4] SURBL http://www.surbl.org/

[5] Google Safe Browsing for Firefox BETA http://www.google.com/tools/firefox/safebrowsing/  

[6] Finjan's Malicious Code Research Center, Evasive URL techniques, 25 Jan 2009. http://www.finjan.com/MCRCblog.aspx?EntryId=2153

[7] McGrath, D. Kevin, Gupta, Minaxi. Behind Phishing: An Examination of Phisher Modi Operandi. https://www.usenix.org/events/leet08/tech/full_papers/mcgrath/mcgrath_html/mcgrath_gupta.html

[8] Parker, Ryan J. Shortening (Affiliate) Links For Prettier Linking. 20 Feb 2007. http://www.ryanjparker.net/shortening-affiliate-links-for-prettier-linking/

[9] Korben. Petit cours de Twitt Jacking :-). 30 Jan 2009. http://www.korben.info/petit-cours-de-twitt-jacking.html

[10] Johnson, Clay. What is this Don't Click business? 12 Feb 2009. http://sunlightlabs.com/blog/2009/02/12/what-dont-click-business/

"Performance is the perceived measure of how fast or efficient your software is and it is critical to the success of all software. If your software seems slow, users may be less inclined to buy it. Even software that uses the most optimal algorithms may seem slow if it spends more time processing data than responding to the user. ... Remember that the perception of performance is informed by two things: The speed with which an application processes data and performs operations and the speed with which the application responds to the user." [1]

Instantaneous (0.1 to 0.2 seconds)
Immediate (0.5 to 1.0 seconds)
Continuous (2 to 5 seconds)
Captive (7 to 10 seconds)

If you address another human being, you expect some communicative response within x seconds-perhaps two to four seconds. ... In conversation of any kind between humans, silences of more than four seconds become embarrassing because they imply a breaking of the thread of communication. [2]

Especially with a code base that is mature, assumptions correctly made years ago can be terribly difficult to deal with later when the current and new assumptions reign. Writing code that lasts even 5 years and "is robust" is what everyone wants to do for sure, but the recipe for doing just that is not easy to learn and even harder to actually do. For example, you might know what changes need to be made to conform to even the most obvious object oriented design principles, but the business requirements and time to market needs dictate leaving once again old crusty code alone and racking up yet another round of technical debt. Over time, this technical debt will demand payment and the effects on your ability to hire, employee morale, design changes possible, speed of delivery, testing burden, marketing message etc. become very real and very painful. I wonder, can these concepts can be fully learned without actually experiencing pain? Could you even attempt to learn these concepts experientially in college? My experience so far makes me think that one may know something intellectually, without really knowing it. It seems like for so many, one may talk about design patterns or abstraction or low coupling, but until you actually try to build something the other way, the painful way, you just don't appreciate what you are avoiding. What's worse, junior developers who, for no fault of their own lack experience with "the hard way" have a difficult time understanding why one must "go the long way around" to do what seems like such a direct solution. Passing on the stories of the past and their consequences and lessons seems to be an unending challenge.

From my economics book comes this fictional story which I think illustrates the point:

"One Pepsi plant is managed by an economics major with an MBA and has a labor force with an average of 10 years of experience. This plant produces a larger output than does an otherwise identical plant that is managed by someone with no business training or experience and that has a young labor force that is new to bottling."

I definitely fall into the "young labor force that is new to bottling" camp. In the technology industry there is a tendency to glorify the young and bright rather than those who have the experience and have paid the price to learn the lessons that matter in the long run. Whenever I talk to some developer and we talk about where they learned some valuable lesson about software development, rarely do they refer to a book. Almost invariably, they say, "I worked with Joe on this project and he showed me x, y and z. I learned so much working with him." Smart developers, experienced developers who know how to teach and share important lessons to junior programmers seem like a key to the experience problem. Sadly, junior developers who have the presence of mind to ask, listen and apply what they hear are hard to find, and senior developers who are both willing and able to teach effectively are even more rare.

Perhaps the answer to all this is simple. Perhaps it's just he or she who writes the most code, wins. What I mean by this is simply when one writes a lot of code that increases the probability that he or she will make more of the key mistakes needed to learn how to write software with longevity. Just getting more exposure to "how bad things can get" helps bring a sober reality to each line of code written thereafter.

What's remarkable about all this, is that failures in teaching and learning are what keep us "discovering" new ideas that are 40 years old. Truly, "there is no new thing under the sun."