Think Complexity

Preface

Why I Wrote This Book

This book is inspired by boredom and fascination: boredom with the usual presentation of data structures and algorithms, and fascination with complex systems. The problem with data structures is that they are often taught without a motivating context; the problem with complexity science is that it is usually not taught at all.

In 2005, I developed a new class at Olin College where students read about topics in complexity, implement experiments in Python, and learn about algorithms and data structures. I wrote the first draft of this book when I taught the class again in 2008.

For the third offering, in 2011, I prepared the book for publication and invited the students to submit their work in the form of case studies for inclusion in the book. I recruited nine professors at Olin to serve as a program committee and choose the reports that were ready for publication. The case studies that met the standard are included in this book. For the next edition, we invite additional submissions from readers (see Appendix A).

Suggestions for Teachers

This book is intended as a scaffold for an intermediate-level college class in Python programming and algorithms. My class uses the following structure:

Reading

Complexity science is a collection of diverse topics. There are many interconnections, but it takes time to see them. To help students see the big picture, I give them readings from popular presentations of work in the field. My reading list and suggestions on how to use it are in Appendix B.

Exercises

This book presents a series of exercises; many of them ask students to reimplement seminal experiments and extend them. One of the attractions of complexity is that the research frontier is accessible with moderate programming skills and undergraduate mathematics.

Discussion

The topics in this book raise questions in the philosophy of science, and lend themselves to further reading and classroom discussion.

Case studies

In my class, we spend almost half the semester on case studies. Students participate in an idea generation process, form teams, and work for 6–7 weeks on a series of experiments, which they then present in the form of a publishable 4–6 page report.

An outline of the course and my notes are available at https://sites.google.com/site/compmodolin.

Suggestions for Autodidacts

In 2009–10, I was a Visiting Scientist at Google, working in their Cambridge office. One of the things that impressed me about the software engineers I worked with was their broad intellectual curiosity and drive to expand their knowledge and skills.

I hope this book helps people like them explore a set of topics and ideas they might not encounter otherwise, practice programming skills in Python, and learn more about data structures and algorithms (or review material that might have been less engaging the first time around).

Some features of this book intended for autodidacts are:

Technical depth

There are many books about complex systems, but most are written for a popular audience. They usually skip the technical details, which is frustrating for people who can handle it. This book presents the mathematics and other technical content you need to really understand this work.

Further reading

Throughout the book, I include pointers to further reading, including original papers (most of which are available electronically), related articles from Wikipedia,^[1] and other sources.

Exercises and (some) solutions

For many of the exercises, I provide code to get you started, and solutions if you get stuck or want to compare your code to mine.

Opportunity to contribute

If you explore a topic not covered in this book, reimplement an interesting experiment, or perform one of your own, I invite you to submit a case study for possible inclusion in the next edition of the book. See Appendix A for details.

This book will continue to be a work in progress. You can read about ongoing developments at http://www.facebook.com/thinkcomplexity.

Allen B. Downey

Professor of Computer Science

Olin College of Engineering

Needham, MA

Contributor List

If you have a suggestion or correction, please send an email to [e-mail]. If I make a change based on your feedback, I will add you to the contributor list (unless you ask to be omitted).

If you include at least part of the sentence the error appears in, that makes it easy for me to search. Page and section numbers are fine, too, but not quite as easy to work with. Thanks!

• Richard Hollands pointed out several typos.

• John Harley, Jeff Stanton, Colden Rouleau, and Keerthik Omanakuttan are computational modeling students who pointed out typos.

• Muhammad Najmi bin Ahmad Zabidi caught some typos.

• Phillip Loh, Corey Dolphin, Noam Rubin, and Julian Ceipek found typos and made helpful suggestions.

• José Oscar Mur-Miranda found several typos.

• I am grateful to the program committee that read and selected the case studies included in this book: Sarah Spence Adams, John Geddes, Stephen Holt, Vincent Manno, Robert Martello, Amon Millner, José Oscar Mur-Miranda, Mark Somerville, and Ursula Wolz.

• Sebastian Schöner sent two pages of typos!

• Jonathan Harford found a code error.

• Philipp Marek sent a number of corrections.

Conventions Used in This Book

The following typographical conventions are used in this book:

Italic

Indicates URLs, email addresses, filenames, and file extensions.

Bold

Indicates new terms.

Constant width

Used for program listings, as well as within paragraphs to refer to program elements such as variable or function names, databases, data types, environment variables, statements, and keywords.

Constant width bold

Shows commands or other text that should be typed literally by the user.

Constant width italic

Shows text that should be replaced with user-supplied values or by values determined by context.

Tip

This icon signifies a tip, suggestion, or general note.

Caution

This icon indicates a warning or caution.

Using Code Examples

This book is here to help you get your job done. In general, you may use the code in this book in your programs and documentation. You do not need to contact us for permission unless you’re reproducing a significant portion of the code. For example, writing a program that uses several chunks of code from this book does not require permission. Selling or distributing a CD-ROM of examples from O’Reilly books does require permission. Answering a question by citing this book and quoting example code does not require permission. Incorporating a significant amount of example code from this book into your product’s documentation does require permission.

We appreciate, but do not require, attribution. An attribution usually includes the title, author, publisher, and ISBN. For example: “Think Complexity by Allen B. Downey (O’Reilly). Copyright 2012 Allen Downey, 978-1-449-31463-7.”

If you feel your use of code examples falls outside fair use or the permission given above, feel free to contact us at [e-mail].

Safari® Books Online

Note

Safari Books Online is an on-demand digital library that lets you easily search over 7,500 technology and creative reference books and videos to find the answers you need quickly.

With a subscription, you can read any page and watch any video from our library online. Read books on your cell phone and mobile devices. Access new titles before they are available for print, and get exclusive access to manuscripts in development and post feedback for the authors. Copy and paste code samples, organize your favorites, download chapters, bookmark key sections, create notes, print out pages, and benefit from tons of other time-saving features.

O’Reilly Media has uploaded this book to the Safari Books Online service. To have full digital access to this book and others on similar topics from O’Reilly and other publishers, sign up for free at http://my.safaribooksonline.com.

How to Contact Us

Please address comments and questions concerning this book to the publisher:

O’Reilly Media, Inc.

1005 Gravenstein Highway North

Sebastopol, CA 95472

800-998-9938 (in the United States or Canada)

707-829-0515 (international or local)

707-829-0104 (fax)

We have a web page for this book, where we list errata, examples, and any additional information. You can access this page at:

http://shop.oreilly.com/product/0636920022480.do

To comment or ask technical questions about this book, send email to:

[e-mail]

For more information about our books, courses, conferences, and news, see our website at http://www.oreilly.com.

Find us on Facebook: http://facebook.com/oreilly

Follow us on Twitter: http://twitter.com/oreillymedia

Watch us on YouTube: http://www.youtube.com/oreillymedia

---

^[1] Some professors have an allergic reaction to Wikipedia, on the grounds that students may depend too heavily on an unreliable source. Since many of my references are Wikipedia articles, I want to explain my thinking. First, the articles on complexity science and related topics tend to be very good; second, they are written at a level that is accessible after you have read this book (but sometimes not before); and finally, they are freely available to readers all over the world. If there is a danger in sending readers to these references, it is not that they are unreliable, but that the readers won’t come back! (See http://xkcd.com/903.)