Design Patterns - Intention, Motivation and Examples

Design patterns provide a fundamental foundation to building maintainable and scalable software. Understanding how the patterns work, why they provide a benefit, and when to use them helps to ensure that software is built from reusable object oriented components. In the text below, the patterns are grouped as per software architecture tradition into three categories - structural patterns, behavioral patterns and creational patterns.

The first set of patterns described in the table below is what is coined as Structural patterns. These patterns describe how objects and classes can be combined to form larger structures.

Structural
Pattern	Info
Adapter (Wrapper)	Intent: Converts the interface of a class into another interface clients expect. This lets classes work together that couldn't otherwise because of incompatible interfaces. Example 1: In the US, electrical outlets are three-pronged. When traveling to certain countries in Europe, electrical outlets require 2-prongs. To make US electronics work in Europe you can get a set of adapters to create compliance between the two interfaces. Example 2: Commonly used to make independently developed class libraries work together.
Bridge (Handle/Body)	Intent: Decouple (separate) an abstraction from its implementation so that the two can vary independently. Example 1: A household switch controlling lights, ceiling fans, etc. is an example of the Bridge. The purpose of the switch is to turn a device on or off. The actual switch can be implemented as a pull chain, a simple two position  switch, or a variety of dimmer switches. Example 2: JDBC ODBC Bridge, where both JDBC and ODBC can change and there are no implications if one changes.
Composite (Handle/Body)	Intent: Compose objects into tree structures to represent part-whole hierarchies. Lets clients treat individual objects and compositions of objects uniformly. Example 1: Although the example is abstract, arithmetic expressions are Composites. An arithmetic expression consists of an operand, an operator (+ - * /), and another operand. The operand can be a number, or another arithmetic expression. Thus, 2 + 3 and (2 + 3) + (4 * 6) are both valid expressions. Example 2: Swing where all components are containers, allowing components to be held within components.
Decorator (Wrapper)	Intent: Attach additional responsibilities to an object dynamically. Provide a flexible alternative to sub-classing for extending functionality. Example 1: Although paintings can be hung on a wall with or without frames, frames are often added, and it is the frame which is actually hung on the wall. Prior to hanging, the paintings may be matted and framed, with the painting, matting, and frame forming a single visual component. Example 2: Java I/O where InputStream and OutputStream are standard interfaces where their capabilities can be extended by being decorated with other compatible streams.
Façade	Intent: Provide a unified interface to a set of interfaces in a subsystem. Defines a high -level interface that makes the subsystem easier to use. Example 1: Consumers encounter a Facade when ordering from a catalog. The consumer calls one number and speaks with a customer service representative. The customer service representative acts as a Facade, providing an interface to the order fulfillment department, the billing department, and the shipping department. Example 2: Web Service
Flyweight	Intent: Use sharing to support large numbers of fine grained objects efficiently. Example 1: The public switched telephone network is an example of a Flyweight. There are several resources such as dial tone generators, ringing generators, and digit receivers that must be shared between all subscribers. A subscriber is unaware of how many resources are in the pool when he or she lifts the hand set to make a call. All that matters to subscribers is that dial tone is provided, digits are received, and the call is completed. Example 2: Connection pools and loggers (java.util.logging)
Proxy (Surrogate)	Intent: Provide a surrogate or placeholder for another object to control access to it. Example 1: As shareholders in a company, you can either go to a meeting and vote, or you can place a proxy vote. The proxy vote is handled by an intermediary, but represents the actual vote. Example 2: Remote interfaces in EJB and Java’s RMI implementation.

The next pattern set is referred to as Behavioral patterns. These prescribe the way objects interact with each other. They help make complex behavior manageable by specifying the responsibilities of objects and the ways they communicate with each other. 

Behavioral
Pattern	Info
Chain of Responsibility (Handle/Body)	Intent: Avoid coupling the sender of a request to its receiver by giving more than one object a chance to handle the request. Chain the receiving objects and pass the request along the chain until an object handles it. Example 1: Mechanical coin sorting banks use the Chain of Responsibility. Rather than having a separate slot for each coin denomination coupled with receptacle for the denomination, a single slot is used. When the coin is dropped, the coin is routed to the appropriate receptacle by the mechanical mechanisms within the bank. Example 2: Event handling mechanism pre Java 1.1
Command (Action / Transaction)	Intent: Encapsulate a request as an object, thereby letting you parameterize clients with different requests, queue or log requests, and support undoable operations. Example 1: The "check" at a diner is an example of a Command pattern. The waiter or waitress takes an order, or command from a customer, and encapsulates that order by writing it on the check. The order is then queued for a short order cook. Note that the pad of "checks" used by different diners is not dependent on the menu, and therefore they can support commands to cook many different items. Example 2: Java’s Threading system                      Java’s Swing action commands                      Struts Action commands.
Interpreter	Intent: Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language. Example 1: Musicians are examples of Interpreters. The pitch of a sound and its duration can be represented in musical notation on a staff. This notation provides the language of music. Musicians playing the music from the score are able to reproduce the original pitch and duration of each sound represented. Example 2: HTML and XML Parsers
Iterator (Cursor)	Intent: Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation. Example 1: On early television sets, a dial was used to change channels. When channel surfing, the viewer was required to move the dial through each channel position, regardless of whether or not that channel had reception. On modern television sets, a next and previous button are used. When the viewer selects the "next" button, the next tuned channel will be displayed. Consider watching television in a hotel room in a strange city. When surfing through channels, the channel number is not important, but the programming is. If the programming on one channel is not of interest, the viewer can request the next channel, without knowing its number. Example 2: Java Collections API
Mediator	Intent: Define an object that encapsulates how a set of objects interact. Promotes loose coupling by keeping objects from referring to each other explicitly and it lets you vary their interactions independently. Example 1: The control tower at a controlled airport demonstrates this pattern very well. The pilots of the planes approaching or departing the terminal area communicate with the tower, rather than explicitly communicating with one another. The constraints on who can take off or land are enforced by the tower. It is important to note that the tower does not control the whole flight. It exists only to enforce constraints in the terminal area. Example 2: A Software Bus
Memento (Token)	Intent: Without violating encapsulation, capture and externalize an object's internal state so that the object can be restored to this state later. Example 1: This pattern is common among do-it-yourself mechanics repairing drum brakes on their cars. The drums are removed from both sides, exposing both the right and left brakes. Only one side is disassembled, and the other side serves as a Memento of how the brake parts fit together. Only after the job has been completed on one side is the other side disassembled. When the second side is disassembled, the first side acts as the Memento. Example 2: HTTP Sessions                       Cookies                       Serialized Objects
Observer (Dependents, Publish-Subscribe)	Intent: Define a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically. Example 1: Some auctions demonstrate this pattern. Each bidder possesses a numbered paddle that is used to indicate a bid. The auctioneer starts the bidding, and "observes" when a paddle is raised to accept the bid. The acceptance of the bid changes the bid price, which is broadcast to all of the bidders in the form of a new bid. Example 2: Most UI toolkits                 ORM Frameworks
State	Intent: Allow an object to alter its behavior when its internal state changes. The object will appear to change its class. Example 1: This pattern can be observed in a vending machine. Vending machines have states based on the inventory, amount of currency deposited, the ability to make change, the item selected, etc. When currency is deposited and a selection is made, a vending machine will either deliver a product and no change, deliver a product and change, deliver no product due to insufficient currency on deposit, or deliver no product due to inventory depletion. Example 2: Web Servers                       Real-time software
Strategy (Policy)	Intent: Define a family of algorithms, encapsulate each one, and make them interchangeable. Lets the algorithm vary independently from clients that use it. Example 1: Modes of transportation to an airport is an example of a Strategy. Several options exist, such as driving one's own car, taking a taxi, an airport shuttle, a city bus, or a limousine service. For some airports, subways and helicopters are also available as a mode of transportation to the airport. Any of these modes of transportation will get a traveler to the airport, and they can be used interchangeably. The traveler must chose the Strategy based on tradeoffs between cost, convenience, and time. Example 2: Comparator / Comparable interfaces in Java Collections.
Template Method	Intent: Define the skeleton of an algorithm in an operation, deferring some steps to subclasses. Lets subclasses redefine certain steps of an algorithm without changing the algorithm's structure. Example 1: Home builders use the Template Method when developing a new subdivision. A typical subdivision consists of a limited number of floor plans, with different variations available for each floor plan. Within a floor plan, the foundation, framing, plumbing, and wiring will be identical for each house. Variation is introduced in the latter stages of construction to produce a wider variety of models. Example 2: Template-oriented websites                      CMS
Visitor (Agent)	Intent: Represent an operation to be performed on the elements of an object structure. Lets you define a new operation without changing the classes of the elements on which it operates. Example: This pattern can be observed in the operation of a taxi company. When a person calls a taxi company he or she becomes part of the company's list of customers. The company then dispatches a cab to the customer (accepting a visitor). Upon entering the taxi, or Visitor, the customer is no longer in control of his or her own transportation, the taxi (driver) is.

Finally, the last of set of patterns we will summarize are the Creational patterns. These patterns are used when a decision must be made at the time a class is instantiated.

Creational
Pattern	Info
Abstract Factory (Kit)	Intent: Provides an interface for creating families of related or dependent objects without specifying their concrete class. Example 1: The pattern is found in the sheet metal stamping equipment used in the manufacture of Japanese automobiles. The stamping equipment is an Abstract Factory which creates auto body parts. The same machinery is used to stamp right hand doors, left hand doors, right front fenders, left front fenders, hoods, etc. for different models of cars. Through the use of rollers to change the stamping dies, the concrete classes produced by the machinery can be changed within three minutes. Example 2:  java.sql.Connection allows the creation of Statements, PreparedStatements, CallableStatements for each database flavor. javax.swing.LookAndFeel allows switching between several L&F for the components displayed.
Builder	Intent: Separate the construction of a complex object from its representing so that the same construction process can create different representations.                                                                                          Example 1: The pattern is used by fast food restaurants to construct children’s meals. Children’s meals typically consist of a main item, a side item, a drink, and a toy (.e.g., a hamburger, fires, coke, and toy car). Note that there can be variation in the contents of the children’s meal, but the construction process is the same. Whether a customer orders a hamburger, cheeseburger, or chicken the process is the same. The employee at the counter directs the crew to assemble a main item, side item, a toy. These items are then placed in a bag. The drink is placed in a cup and remains outside of the bag. This same process is used at competing restaurants. Example 2: Creating an Input Stream in Java delegates the creation of an underlying OS Specific input stream to a native library. This construction process is exactly the same from client perspective but how the object is created may differ.
Factory Method (Virtual Constructor)	Intent: Define an interface for creating an object, but let subclasses decide which class to instantiate. Lets a class defer instantiation to subclasses. Example 1: Injection molding presses demonstrate this pattern. Manufacturers of plastic toys process plastic molding powder, and inject the plastic into molds of the desired shapes. The class of toy (car, action figure, etc.) is determined by the mold. Example 2:         java.net.URLConnection – allows users to decide which protocol to use.          JDBC DriverManager.getConnection
Singleton	Intent: Ensure a class only has one instance and provide a global point of access to it. Example 1: The Singleton pattern in named after the singleton set, which is defined to be a set containing one element. The office of the President of the United States is a Singleton. The United States Constitution specifies the means by which a president is elected, limits the term of office, and defines the order of succession. As a result, there can be at most one active president at any given time. Regardless of the personal identity of the active president, the title, “The President of the United States” is a global point of access that identifies the person in the office. Example 2:  Logger                       Configuration                       Accessing resources in shared mode                       System.in, System.out, System.err   AWT Thread
Prototype	Intent: Specify the kinds of objects to create using a prototypical instance, and create new objects by copying this prototype. Example 1: Prototypes of new products are built prior to full production, but in this example, the prototype is passive, and does not participate in copying itself. The mitotic division of a cell, resulting in two identical cells, is an example of a prototype that plays an active role in copying itself and thus, demonstrates the Prototype pattern. When a cell splits, two cells of identical genotype result. In other words, the cell clones itself. Example 2:  The clone method in Java.

Computer Science Milestones (1900 - 2011)

I wanted to share with you a timeline of major events in computer science history. The milestones listed hereunder are those that I deem important and include only 20th and 21st century events. 

1900 - In a lecture to the International Congress of Mathematicians, David Hilbert asks for way to mechanize all of mathematical reasoning

1921 - Czech author Karel Capek popularizes the term ‘robot’ in his play “R.U.R. (Rossum’s Universal Robots)”

1925 - Vannevar Bush and colleagues create the first large-scale analog calculator at MIT

1931 - Kurt Gödel publishes his Incompleteness Theorem; the system of “Gödel numbering” used in the proof foreshadows computer programming

1936 - Alan Turing publishes “On computable numbers,” often considered the founding document of computer science; the paper gives an explicit construction of a universal Turing machine. Alonzo Church and Emil Post arrive at similar ideas independently

1936 - Working alone in Germany, Konrad Zuse builds the Z1, the first working stored-program computer

1937 - In his MIT master’s thesis—considered possibly the most influential master’s thesis in history—Claude Shannon proposes the application of Boolean algebra to electrical circuit design

1940 - Building on earlier breakthroughs by Polish mathematician Marian Rejewski, Alan Turing builds an improved “Bombe” at Bletchley Park, to break the German Enigma code and help the Allies win WWII

1942 - Isaac Asimov introduces his Three Laws of Robotics

1942 - At Iowa State College, John Atanasoff and Clifford Berry successfully test a special-purpose vaccum-tube computer able to solve up to 29 simultaneous linear equations; Atanasoff will later spend decades in legal disputes to establish his computer’s priority over Eckert and Mauchly’s ENIAC

1943 - Colossus, the world’s first programmable electronic computer, begins operation at Bletchley Park

1943 - During the Manhattan Project, Richard Feynman and others pioneer large-scale scientific computing, using humans and later mechanical calculators

1943 - In their paper “A Logical Calculus Immanent in Nervous Activity,” Warren McCulloch and Walter Pitts propose neural networks and finite automata

1944 - The Mark I, designed by Howard Aiken, begins operations at Harvard

1945 - In a 100-page “draft report on the EDVAC”, John von Neumann describes the architecture of a stored-program computer (henceforth called “von Neumann architecture”)

1945 - Vannevar Bush publishes “As We May Think” in the Atlantic Monthly, a now-famous article that foresees a global information network based on hypertext

1946 - At the University of Pennsylvania, J. Presper Eckert and John Mauchly complete the ENIAC

1946 - In Los Alamos, Stanislaw Ulam develops the Monte Carlo method to speed up calculations of neutron diffusion in nuclear weapons

1947 - At Bell Labs, John Bardeen, Walter Brattain, and William Shockley invent the transistor

1947 - Operators of the Mark II computer trace an error to a moth trapped in a relay. The incident, popularized by Grace Murray Hopper, stimulates wider adoption of the terms “bug” and “debugging”

1947 - George Dantzig proposes the simplex algorithm for linear programming

1948 - In his landmark paper “A Mathematical Theory of Communication,” Claude Shannon first uses the word “bit,” attributing it to John Tukey

1948 - Norbert Wiener publishes “Cybernetics: Or Control and Communication in the Animal and the Machine”

1949 - The EDSAC, built by Maurice Wilkes, begins operations at Cambridge University

1949 - Claude Shannon initiates the rigorous mathematical study of cryptography, publishing his proof that the one-time pad is unbreakable and that any unbreakable encryption system has the same basic properties

1950 - Alan Turing proposes the Turing Test for artificial intelligence; four years later, Turing will commit suicide after being prosecuted for homosexuality

1950 - CSIRAC, in Australia, becomes the first computer to play music

1951 - J. Presper Eckert and John Mauchly release UNIVAC I, the first commercial electronic computer

1951 - Grace Murray Hopper creates A-O, considered the first compiler

1951 - MIT’s Whirlwind I computer goes online. Designed by Jay Forrester, Whirlwind features magnetic core memory and vacuum tubes that last 1000 - times longer than those previously available

1952 - Based on analysis of early returns, a UNIVAC computer borrowed by CBS News predicts that Dwight Eisenhower will defeat Adlai Stevenson in the presidential election

1954 - Researchers at Birkbeck College perform the first demonstration of machine translation, with a rudimentary translation of English into French

1955 - MIT’s Whirlwind I becomes the first computer to display graphics on a video console

1956 - Dartmouth hosts the first conference on artificial intelligence, bringing the term AI into use

1956 - In a letter to John von Neumann, Kurt Gödel first poses what will later become known as the P versus NP problem

1956 - Edsger Dijkstra conceives his shortest-path algorithm, the basis for modern trip-planning software (Dijkstra also may have been the first person to list his profession as “programmer”)

1956 - Noam Chomsky proposes the Chomsky Hierarchy, linking the theory of computing to formal languages

1956 - MIT Lincoln Laboratories builds the TX-0, the first general-purpose computer to be built with transistors

1956 - Reynold Johnson at IBM introduces the hard drive

1957 - A team led by John Backus at IBM delivers a compiler for FORTRAN, the first high-level programming language

1958 - John McCarthy proposes the LISP family of functional programming languages

1958 - As part of the air-defense project SAGE, MIT Lincoln Labs links hundreds of radar stations in the first large-scale computer network

1958 - Jack St. Kilby at Texas Instruments and Robert Noyce at Fairchild Semiconductor propose the integrated circuit

1959 - In the seminal paper “Finite Automata and Their Decision Problems,” Dana Scott and Michael Rabin introduce the concept of nondeterminism into computer science

1960 - Tony Hoare invents the Quicksort algorithm, while a visiting student at Moscow State University

1960 - Irving Reed and Gustave Solomon give a systematic construction of error-correcting codes; later, Elwyn Berlekamp and James Massey will discover an efficient decoding procedure

1960 - Ray Solomonoff proposes measuring the complexity of a string by the length of the shortest program that generates it; Andrey Kolmogorov and Gregory Chaitin will later arrive at similar ideas independently\

1961 - UNIMATE, the first industrial robot, begins work at General Motors

1961 - A team led by MIT professor Fernando Corbato demonstrates the first computer time-sharing system

1961 - A team led by MIT student Steve Russell creates Spacewar!, the first computer game

1962 - While studying computer models of the weather, MIT professor Edward Lorentz discovers the phenomena that would later be popularized as “chaos theory”

1963 - At MIT, Joseph Weizenbaum develops ELIZA, the now-famous program that simulates conversation between a Rogerian psychotherapist and a patient

1963 - MIT graduate student Ivan Sutherland develops Sketchpad, the first Computer-Aided Design (CAD) software

1963 - The first edition of ASCII (American Standard Code for Information Interchange) is published

1964 - IBM releases the System/360, one of the first computers based on integrated circuits. Fred Brooks, the lead developer, later describes the lessons learned in his book “The Mythical Man-Month”

1964 - At Dartmouth, John Kemeny and Thomas Kurtz create the BASIC programming language

1964 - Seymour Cray releases the CDC 6600, the first of many record-breaking supercomputers

1964 - American Airlines and IBM debut SABRE, the first computer-based travel reservation system

1965 - AT&T debuts 1ESS, the first electronic telephone switching system, in Succasunna, New Jersey

1965 - Intel cofounder Gordon Moore enunciates Moore’s Law, that the number of transistors per integrated circuit doubles roughly every two years

1965 - At IBM, James Cooley and John Tukey rediscover and popularize the Fast Fourier Transform (versions of which were known to Gauss and others)

1965 - Juris Hartmanis and Richard Stearns prove the existence of an infinite hierarchy of harder and harder computational problems

1965 - MIT student Richard Greenblatt begins developing Mac Hack, the first computer chess program to succeed in tournament play. Mac Hack also defeats the AI skeptic Hubert Dreyfus, who had famously claimed that computers would never play high-quality chess

1965 - Edsger Dijkstra introduces semaphores, which allow multiple concurrently-running programs to share the same resource

1966 - Texas Instruments unveils the first electronic handheld calculator

1966 - The first cash-dispensing ATM is installed in Tokyo

1967 - At SRI, Douglas Engelbart and Bill English apply for a patent for the first computer mouse

1967 - Andrew Viterbi invents the Viterbi algorithm for maximum-likelihood estimation in Hidden Markov Models; the algorithm will find major applications in speech recognition, bioinformatics, and both the CDMA and GSM cellular-phone standards

1967 - In Norway, Ole-Johan Dahl and Kristen Nygaard develop Simula 67, considered the first object-oriented programming language and a major influence on Smalltalk and later C++

1968 - Donald Knuth publishes Volume 1 of “The Art of Computer Programming”

1968 - Edsger Dijkstra publishes his now-famous article “Go To Statement Considered Harmful,” igniting an acrimonious debate about programming practices

1968 - The movie “2001: A Space Odyssey” introduces the world to HAL

1968 - Work begins at MIT on Macsyma, the first computer algebra system

1969 - Victor Scheinman builds the Stanford Arm, the first electronic computer-controlled robotic arm

1969 - ARPAnet, the precursor of the Internet, links UCLA, SRI, Santa Barbara, and Utah (MIT joins in 1970)

1969 - At Bell Labs, Ken Thompson and Dennis Ritchie create UNIX, and begin developing the C programming language

1969 - Arthur Bryson and Yu-Chi Ho introduce back-propagation, a learning technique for neural networks that is largely ignored until the 1980s.  Meanwhile, Marvin Minsky and Seymour Papert publish “Perceptrons,” a book that introduces important mathematical techniques into computer science, but has also been accused of “killing” neural-net research for more than a decade

1969 - The Apollo Guidance Computer plays a crucial role in steering Neil Armstrong and Buzz Aldrin to the lunar surface

1970 - John Horton Conway invents the Game of Life cellular automaton; it is estimated that millions of dollars of computer time are wasted watching Lifeforms evolve

1970 - E. F. Codd proposes the relational database management system (RDBMS)

1970 - Yuri Matiyasevich, building on work of Julia Robinson, Martin Davis, and Hilary Putnam, shows the nonexistence of an algorithm to solve Diophantine equations, negatively resolving Hilbert’s Tenth Problem and demonstrating Turing-universality in one of the oldest parts of mathematics

1971 - Stephen Cook and Leonid Levin independently prove that the Satisfiability problem is NP-complete; a paper by Richard Karp a year later demonstrates the pervasiveness of the NP-completeness phenomenon

1971 - IBM commercially releases the floppy disk

1971 - Ray Tomlinson sends the first email message on ARPANET

1971 - Bob Thomas at BBN Technologies creates the first experimental computer virus

1972 - Atari releases Pong

1973 - At Xerox PARC, Alan Kay and collaborators create the Alto, featuring the first graphical user interface (GUI) with windows, icons, and menus

1973 - Robert Metcalfe at Xerox PARC creates Ethernet

1974 - MIT professor Barbara Liskov and students begin work on CLU, a predecessor of modern object-oriented programming languages

1976 - Kenneth Appel and Wolfgang Haken prove the Four-Color Map Theorem, the first major theorem to be proved using a computer

1975 - Bill Gates and Paul Allen adapt BASIC to the MITS Altair microcomputer

1975 - Inspired by work of Ralph Merkle, Stanford researchers Whitfield Diffie and Martin Hellman announce the first protocol for public key exchange (which had been discovered previously at the British GCHQ, but kept classified)

1975 - Robert Kahn and Vint Cerf test the new TCP/IP protocol between Stanford and University College London

1975 - At IBM, John Cocke advocates RISC processor architecture, and begins work on the 801 to implement it

1977 - Ronald Rivest, Adi Shamir, and Leonard Adleman develop the public-key encryption system that they call RSA, and announce it via Martin Gardner’s Mathematical Games column in Scientific American

1977 - Robert Solovay and Volker Strassen publish an efficient randomized algorithm for primality testing, demonstrating both the feasibility of RSA and the power of randomized algorithm; shortly afterward, Gary Miller and Michael Rabin find a more efficient such algorithm

1977 - Steve Jobs and Steve Wozniak release the Apple II

1977 - William Kahan puts forward a draft proposal for the IEEE floating-point standard

1977 - In Israel, Abraham Lempel and Jacob Ziv propose the data compression algorithm that (after improvements by Terry Welch and others) becomes the basis for PKZIP and most other general-purpose compression software

1978 - Intel releases the 8086, the first in the line of x86 processors

1978 - Donald Knuth begins developing the TeX computer typesetting system, which will eventually become the lingua franca of science

1979 - Dan Bricklin and Bob Frankston release VisiCalc, the first personal spreadsheet program and “killer app” for the Apple II

1980 - Duke University graduate students Tom Truscott and Jim Ellis create Usenet

1981 - Nintendo achieves its first video game success with Donkey Kong, designed by Shigeru Miyamoto

1981 - The IBM PC is released, running Microsoft’s MS-DOS

1981 - Richard Feynman points out the exponential difficulty of simulating quantum physics with a conventional computer, and speculates that a quantum-mechanical computer would do better; a few years later; David Deutsch will publish his construction of a universal quantum Turing machine

1982 - Work on pseudorandom generators by Manuel Blum, Silvio Micali, Shafi Goldwasser, and Andy Yao begins the modern era of complexity-based cryptography, which will lead over the next decade to notions such as zero-knowledge, interactive proofs, and probabilistically checkable proofs

1982 - Sony and Philips commercially release the compact disc 

1982 - Michael Fischer, Nancy Lynch, and Michael Paterson prove that it’s impossible to reach consensus in an asynchronous distributed system if there’s even a single faulty processor

1983 - Bjarne Stroustrup at Bell Labs develops C++, which is to become the dominant object-oriented programming language

1984 - With its iconic Super Bowl commercial, Apple announces the Macintosh, the first consumer machine with a mouse/windows interface

1984 - Robert Axelrod publishes “The Evolution of Cooperation,” a classic book that uses computer experiments with the Iterated Prisoners’ Dilemma to shed light on human nature

1984 - Leslie Valiant at Harvard proposes PAC (Probably Approximately Correct) learning, which becomes the central mathematical framework for machine learning, and helps to explain why Occam’s Razor “works”

1985 - Microsoft releases Windows

1985 - Richard Stallman publishes his GNU Manifesto, setting out the principles of the free-software movement

1986 - Thinking Machines begins shipping the CM-1 Connection Machine, considered the first massively-parallel supercomputer

1988 - While a graduate student at Cornell, Robert Morris creates a computer worm that cripples the Internet (though that wasn’t Morris’s intention)

1989 - Mike Godwin formulates Godwin’s Law: “As an online discussion grows longer, the probability of a comparison involving Nazis or Hitler approaches 1″

1990 - At CERN in Geneva, Switzerland, Tim Berners-Lee creates the World Wide Web

1990 - The IP=PSPACE Theorem, proved by Carsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan, and Adi Shamir, shows the unexpected power of interactive protocols and opens a new era in the theory of computing

1990 - The discovery of boosting—a technique for combining the predictions of different learning algorithms—by Michael Kearns, Rob Schapire, and Yoav Freund, starts a revolution in the theory and practice of machine learning

1990 - Microsoft releases its first Office application suite, consisting of Word, Excel, and PowerPoint

1991 - At Los Alamos National Laboratory, Paul Ginsparg founds the arXiv, ushering in the era of rapid online dissemination of scientific research

1991 - The Linux kernel is designed by Finnish student Linus Torvalds

1991 - Phil Zimmermann releases Pretty Good Privacy (PGP), which makes “military-grade” public-key encryption easily available. After the Customs Service opens a criminal investigation, Zimmermann becomes an Internet folk hero

1993 - A team headed by Marc Andreessen at the University of Illinois Urbana-Champaign releases NCSA Mosaic, the browser credited with popularizing the Web

1993 - Joel Furr first uses the word “spam” to mean “excessive multiple postings” (in that case, to Usenet newsgroups)

1993 - With 24 satellites in orbit, the Global Positioning System achieves “initial operational capability.”  Originally designed by the US Department of Defense for military applications, GPS quickly finds numerous civilian uses including computerized car navigation

1994 - Peter Shor proves that a quantum computer, if built, would be able to factor numbers efficiently, launching quantum computing as an active research field

1994 - Thomas Nicely discovers the Pentium FDIV bug; the ensuing controversy and costly recall by Intel underscore the need for hardware verification

1995 - Pixar releases Toy Story, the first feature film made entirely with computer-generated imagery

1995 - Lee Zehrer launches Match.com, the first major online dating service

1995 - Amazon.com is launched by Jeff Bezos and sells its first book

1995 - The Institute for Genomic Research uses whole-genome shotgun sequencing—a technique dependent on massive computer power—to sequence the genome of the first free-living organism, the bacterium Haemophilus influenza

1996 - Stanford graduate students Larry Page and Sergey Brin begin developing Google

1997 - IBM’s Deep Blue computer defeats human world champion Garry Kasparov

1997 - Rob “Commander Taco” Malda founds Slashdot, which hosts freewheeling web-based conversations of the sort that would later be commonplace on blogs

1997 - NASA’s Sojourner robotic rover moves semi-autonomously across the surface of Mars for 83 days, sending spectacular images back to Earth

1999 - Widespread fear of the “Y2K millennium bug” underscores society’s dependence on legacy computer systems. Later, many will argue the fears were overblown

2000 - The first major denial-of-service (DoS) attack is launched against CNN, Yahoo, and eBay

2000 - Putting an unexpected practical twist on Alan Turing’s ideas from 1950, Manuel Blum, Luis von Ahn, and John Langford at Carnegie Mellon articulate the notion of CAPTCHAs (Completely Automated Public Turing tests to tell Computers and Humans Apart), the challenges—usually involving reading distorted text—that are used by numerous websites to discourage spam-bots

2001 - Larry Sanger and Jimmy Wales launch Wikipedia

2001 - Bram Cohen develops BitTorrent, the controversial peer-to-peer file sharing protocol now estimated to account for 27-55% of all Internet traffic

2001 - In the wake of the 9/11 attacks, news websites continue running smoothly in part because of routing algorithms designed by Akamai Technologies. Meanwhile, former MIT student Danny Lewin, who cofounded Akamai with Professor Tom Leighton, is on American Airlines flight 11 when it crashes into the World Trade Center

2002 - At IIT Kanpur, Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena announce a deterministic polynomial-time algorithm for primality testing

2004 - Harvard sophomore Mark Zuckerberg launches Thefacebook.com

2005 - YouTube is launched, beginning an era of online video-sharing

2007 - Apple releases the iPhone

2010 - Some of Iran’s centrifuges for uranium enrichment are destroyed by the Stuxnet worm, in the first known large-scale cyberattack to target physical infrastructure

2011 - Making essential use of Facebook and Twitter as organizing tools, protesters in Egypt force the resignation of President Hosni Mubarak after 30 years of rule

2011 - IBM’s Watson computer defeats all-time human champions Ken Jennings and Brad Rutter on Jeopardy