John MacCormick

John MacCormick

Professor of Computer Science

  • B.A., University of Cambridge, 1993
  • M.S., University of Auckland, 1996
  • Ph.D., University of Oxford, 2000

Full contact information
Office hours 
Current courses: COMP492


Bio

John MacCormick’s work in computer science spans several sub-fields, including computer vision, large-scale distributed systems, computer science education, and the public understanding of computer science. He is the author of three books, including Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers and What Can Be Computed?: A Practical Guide to the Theory of Computation. Dr. MacCormick holds 19 US patents on novel computer technologies and is the author of numerous peer-reviewed articles; his Nine Algorithms book has been translated into eight languages. Dr. MacCormick has degrees in mathematics from the University of Cambridge and the University of Auckland, and a doctorate in computer vision from the University of Oxford. He was a research fellow at Linacre College, Oxford from 1999-2000, a research scientist at HP Labs from 2000-2003, and a computer scientist with Microsoft Research from 2003-2007. Since 2007, Dr. MacCormick has been a professor of computer science at Dickinson College.


Featured media

Fairness First in Artificial Intelligence. The Academic Minute featured speaker, September 8, 2023.

I unintentionally created a biased AI algorithm 25 years ago – tech companies are still making the same mistake, lead article in The Conversation, May 9, 2023


Books

New edition and audiobook of "9 Algorithms"

Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers has been re-released in a new 2020 edition for the Princeton Science Library series, together with an audio edition narrated by Quentin Cooper.

Nine Algorithms that Changed the Future

 

What Can Be Computed? A Practical Guide to the Theory of Computation

This is an undergraduate textbook for a course on Theory of Computation. The key characteristic of the book is that it is designed to be uniquely accessible to undergraduates, focussing on real computational problems using real computer programs as the computational model. Please see the official What Can Be Computed? website.

Here are direct links to ancillary materials for the book, which are released under the Creative Commons Attribution 4.0 International License

The book also has a page at Princeton University Press, and is available from the usual sources such as Barnes & Noble and Amazon.

cover of "What Can Be Computed?" by John MacCormick

Reviews and Media Coverage

Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers

Nine Algorithms That Changed the Future:
The Ingenious Ideas That Drive Today's Computers

9Algs cover

What is this book about? It explains how your cell phone, laptop, tablet, and other computers do the amazing things they do. How they can search the entire web in a fraction of a second. How they can transmit vast amounts of data over unreliable wireless connections, without making a single error. How they can recognize your speech and handwriting. And many others.

The book assumes no knowledge of computer science. It's designed to be read and enjoyed by anyone who's curious about how our computing devices manage to be so smart. Interested? Please, peek inside, or check out the table of contents. There's more good stuff at the 9 Algorithms Facebook page, and the book's official page at Princeton University Press. If you want to buy it, 9 Algorithms is available as an eBook or hardcover from all the usual suspects, including Barnes & Noble and Amazon. And of course there's a YouTube video:

Some people were kind enough to say nice things about the book; here are two of them:

  • Chuck Thacker, winner of the 2010 Turing Award—the highest award in computer science—said: "This book is for those who have wondered, 'What actually goes on in my computer?' MacCormick clearly explains some of the algorithms used by hundreds of millions of people daily. Not the simple algorithms like arithmetic and sorting, but more complex things such as how to determine the importance of web pages, if and when we are justified in trusting a computer-mediated conversation with another person, and the puzzling issue of what cannot be computed. I recommend it highly."
  • Andrew Fitzgibbon, who created the Emmy-award-winning camera software boujou, said: "It's been a long time since any book has given me the excitement I remember from reading Hawking and Feynman in my teens. This book does exactly that. It reminds me why I love computer science. MacCormick's explanations are easy to understand yet they tell the real story of how these algorithms actually work. This is a book that deserves not just to be admired, but celebrated."

Award from the Association of American Publishers

9 Algorithms received an Honorable Mention for the 2012 Award for Best Professional/Scholarly Book in Computing & Information Sciences, awarded by the Association of American Publishers.

Translations

9 Algorithms has been translated (or in some cases, is currently being translated) into the following eight languages: traditional Chinese, simplified Chinese, Japanese, Korean, Russian, Italian, Greek, and Turkish.

Media coverage

Media coverage of the book includes:

Stochastic Algorithms for Visual Tracking

 

Stochastic Algorithms for Visual Tracking: Probabilistic Modelling and Stochastic Algorithms for Visual Localisation and Tracking

Springer, 2002. 174 pages.

This technical monograph describes a mathematical and computational framework for implementing algorithms that track moving objects in video. The approach emphasizes the use of probability distributions to model knowledge of the object state. A key consideration is how to approximate, store, and efficiently update such distributions when the dimensionality of the object state is large.


Recommended books about algorithms

It's one of my goals in life to help anyone and everyone understand computer science and algorithms. So please check out my list of recommended books about algorithms for people who know nothing about algorithms, on shepherd.com.


Teaching

Courses

Spring 2024:

Fall 2023:

Spring 2023:

Fall 2022:

Spring 2022:

Fall 2021:

Spring 2021:

Fall 2020:

Spring 2019:

  • SCIE300: Science and Society [global study course for the Dickinson Sciences Program, based at the University of East Anglia in Norwich, England]

Fall 2018:

Spring 2018:

  • SCIE300: Science and Society [global study course for the Dickinson Sciences Program, based at the University of East Anglia in Norwich, England]

Fall 2017:

Spring 2017:

Fall 2016:

Spring 2016:

Fall 2015:

Spring 2015:

Fall 2014:

Spring 2014:

Fall 2013:

Spring 2013:

Fall 2012:

Spring 2011:

Fall 2010:

Spring 2010:

Fall 2009:

Spring 2009:

Fall 2008:

Spring 2008:

Fall 2007:

Information for students

Research

Research overview

My computer science research is motivated by the fundamental questions at the heart of artificial intelligence and computational theory: what problems can computers solve, and to what extent can computer programs exhibit the type of intelligence we recognize as human? I am currently working on modern reinterpretation of these questions based on the phenomenal advances we have seen in AI during the 21st century. This project takes the form of a book manuscript targeted at a general audience, entitled AI Alive: Minds, Brains, and the Modern Revolution in Artificial Intelligence.

In recent years, I have also investigated new approaches to teaching theory of computation to an undergraduate audience—approaches described in the book What Can Be Computed? and a 2020 article in Communications of the ACM

In addition to these recent strands of research, I enjoy working on a wide variety of problems in computer science. These include computer vision—that is, getting computers to understand images and video—large-scale distributed data storage systems, and pair programming techniques for undergraduate computer science education.

Complementing this technical research, I have another personal goal: the public understanding of computer science in general and algorithmic thinking in particular. Efforts to achieve this type of public understanding led to the book Nine Algorithms That Changed the Future.

Here are a few of the questions my research has attempted to address over the years:

  • How can we track a person's finger accurately enough with a video camera to allow fluent human-computer interaction without using any type of touchscreen, mouse, or pointing device? (This is work from my PhD thesis, later published as chapter 7 of the book Stochastic Algorithms for Visual Tracking, and in the conference paper Partitioned sampling, articulated objects, and interface-quality hand tracking.)
  • When undergraduate students work in pairs on programming assignments in an introductory computer science course, how should pairs be assigned? Randomly? Or is it better to pair strong students with other strong students and less able students with other less able students? Or do pairs of mixed ability lead to better outcomes? (This question is tackled in a SIGCSE conference paper, The Benefits of Pairing by Ability.)
  • Suppose you are trying to store, in a data center, millions of files on behalf of thousands of customers. To guard against data loss, each file should have, say, three copies stored on different computers in the data center. How do you decide where to store the copies of each file, in such a way that the file can be efficiently retrieved later, while keeping the load on each computer balanced? (A possible solution is provided by an article in the ACM Transactions on Storage, Kinesis: A New Approach to Replica Placement in Distributed Storage Systems.)
  • These days it's not uncommon to use video chat software such as Skype with two cameras, such as the front and back cameras on a tablet or cell phone. But can we enhance the experience using more cameras? If so, is this technically possible on commodity hardware? Is the conversation further enhanced by giving the remote viewer the ability to control the viewpoint? These questions are addressed by the MultiCam research project and MultiCam software. The results appear in a conference paper and a technical report.

To get a more complete picture of my research, please take a look at my publications and patents. You may also be interested in the list of talks I have given, and a separate section describing research with undergraduate students below.

Research with Undergraduate Students
Publications

Books

Peer-reviewed conference and journal papers

Book chapters

  • Needles in the World's Biggest Haystack: The Algorithm that Ranked the Internet.
    John MacCormick.
    In "You Are Not Expected to Understand This": How 26 Lines of Code Changed the World. Edited by T. Bosch. Chap. 17, pp. 108-112. Princeton University Press, 2022.
  • Statistical models of shape and motion.
    A. Blake, M. Isard, and J. MacCormick.
    Sequential Monte Carlo methods in practice, ed. A. Doucet, J.F.G. de Freitas and N.J. Gordon, pages 339-357. Springer, 2000.
    Earlier version available as a journal article.
  • A geometrical approach to calculating determinants of Wiener-Hopf operators.
    J. MacCormick and B. Pavlov.
    In A. Bohm, H. Doebner, and P. Kielanowski, editors, Irreversibility and causality: semigroups and rigged Hilbert spaces, pages 333-42. Springer, 1998.
    Full version available as a technical report.

Other publications and media

John MacCormick's ACM publications

Talks
  • Would you like a checksum with that? Guest lecture for AP computer science principles course, May 2021. Video.
  • Undecidability and more, using real computer programs. Computer science seminar, Open University, UK. 11/1/18. PDF.
  • Algorithms do change the world. Conference on Mathematics for the 21st Century, Fondation Helvetica Educatio, Geneva. 5/25/18. details; video; PDF.
  • Strategies for basing the CS theory course on non-decision problems. SIGCSE 2017 (Baltimore). 2/23/17. PDF.
  • Practical approaches to teaching the CS theory module: nondecision problems and real computer programs. Colloquium talk, School of Computing Sciences, University of East Anglia. 10/4/17. PDF.
  • Some Reasons Why Computer Scientists Should Study Math, and Mathematicians Should Study Computer Science. Math and Computer Science Majors' Dinner, Dickinson College, April 2017. (This is an updated version of the 2011 majors' dinner talk.) PDF.
  • The Science of Search Engines. 9 Algorithms Workshop, Defence Institute of Advanced Technology, India (delivered via video link) 1/21/17. PDF.
  • Why are password rules so annoying? (Dickinson college FaculTea talk, presented as part of cybersecurity month.) 10/28/15. PDF.
  • Some ideas about computer programming, for the Dickinson College Idea Fund, 4/13/2015. PDF.
  • A few connections between Dickinson College, privacy, and security. Thoughts for a "contemporary moment" discussion between Dickinson College students, 11/13/2013. PDF.
  • The magic of error-correcting codes. Gettysburg College CS Colloquium, 10/3/13. PDF.
  • 9 Algorithms that Changed the Future, Microsoft author talk series, Microsoft Corp., Redmond, WA, 10/16/12.
  • A Brief Overview of Some of the Most Interesting Cutting-Edge Research on Computer Systems: highlights from the 2011 Symposium on Operating Systems Principles (SOSP). Informal departmental seminar, Dickinson College, 12/8/11. PDF.
  • How does the Kinect work? Dickinson College Math/CS Chat, 9/6/11. PDF.
  • Some Reasons Why Computer Scientists Should Study Math, and Mathematicians Should Study Computer Science. Math and Computer Science Majors' Dinner, Dickinson College, 4/26/11. PDF.
  • Did Alan Turing analyze the Halting Problem? Microsoft Research Silicon Valley Lab, July 2010. PDF.
  • The Benefits of Pairing By Ability. SIGCSE 2010 (Milwaukee). PDF.
  • The Coolest Theorem in Computer Science: Computers Can't Do Everything. Dickinson College Math/CS Chat, 4/6/10. PDF (fragmentary).
  • What should a scientist know about computer science? Dickinson College Rush Hour interdisciplinary seminar, 10/13/09. PDF (fragmentary).
  • How to keep a secret, even on the Internet. Dickinson College Math/CS Chat, 11/4/08. PDF (fragmentary). Similar talks were given at Princeton (3/3/10, as part of Princeton's Lunch and Learn series) and Messiah College (11/31/09).
  • Retrospective on leaving Silicon Valley Lab of Microsoft Research. July 2007. PDF (fragmentary).
  • The Need for Polite Software. Microsoft Research Silicon Valley Lab, July 2007. PDF.
  • Can Computers See? Dickinson College Math/CS Chat, 2/2/07. PDF.
  • The Science of Search Engines. Dickinson College Math/CS Chat, 11/14/06. PDF.
  • The Online Index-Merging Problem. Princeton Computer Science Colloquium, 10/14/05. PDF.
Patents
  • A platform for distributed modeling of network service behavior.  Paul Barham, Moises Goldszmidt, Rebecca Isaacs, John MacCormick, Richard Mortier.  Filed 2006.
  • Searchable Storage System. Bill Hoffman, Marcus Jager, John MacCormick, Kristof Roomp, Chandu Thekkath. Filed 2006, issued 2010.
  • Replica placement using r-out-of-k hash functions for cost-effective, fast, and reliable distributed storage systems.  John MacCormick, Nick Murphy, Venugopalan Ramasubramanian, Udi Wieder, Junfeng Yang and Lidong Zhou. Filed 2006, issued 2008.
  • Dynamic activity model of network services. Paul Barham, Richard Black, Moises Goldszmidt, Rebecca Isaacs, John MacCormick, Richard Mortier. Filed 2006, issued 2011.
  • Relocating item in distributed storage system. Marcus Jager, John MacCormick, Douglas McCulloch. Filed 2007, issued 2013.
  • Automatic discovery of service/host dependencies in computer networks. J MacCormick, P Barham, M Goldszmidt. Issued 2010.
  • Network flow for constrained replica placement. John MacCormick. Issued 2010.
  • Data Replication In A Distributed System.  Bill Hoffman, Marcus Jager, John MacCormick, Kristof Roomp, Chandu Thekkath, Lidong Zhou.  Filed 2006, issued 2009.
  • Scheduling of index merges.  John MacCormick and Frank McSherry.  Filed 2005, issued 2010.
  • Efficient Recovery of Replicated Data Items. John MacCormick, Chandu Thekkath, Lidong Zhou. Filed 2004, issued 2010.
  • Systems and methods for structuring distributed fault-tolerant systems. John MacCormick, Chandu Thekkath, Lidong Zhou. Filed 2005, issued 2006. 
  • Method and system for renaming consecutive keys in a B-tree.  John MacCormick. Filed 2004, issued 2009. 
  • Distributed detection with diagnosis. Paul Barham, Richard Black, Moises Goldszmidt, Rebecca Isaacs, John MacCormick, Richard Mortier. Filed 2006.
  • Balanced prefetching exploiting structured data. C. A. Thekkath, John MacCormick, Lidong Zhou, Nicholas Murphy. Filed 2005, issued 2009.
  • Method and system for estimating the three dimensional position of an object in a three dimensional physical space.  Adrian E. Broadhurst, John P. MacCormick, Donald Tanguay, Michael Harville. Filed 2005, issued 2015. 
  • Method and apparatus for estimating time delays in systems of communicating nodes.  Marcos K. Aguilera, John MacCormick. Filed 2004, issued 2006. 
  • Method and system for managing access control.  Marcos K. Aguilera, Minwen Ji, Mark Lillibridge, John MacCormick, Oerwin Oertli, Dave Anderson, Mike Burrows, Tim Mann, Chandu Thekkath. Filed 2003, issued 2004. 
  • Method and system for securing block-based storage with capability data.  Marcos Aguilera, Minwen Ji, Mark Lillibridge, John MacCormick, Oerwin Oertli, Dave Anderson, Mike Burrows, Tim Mann, Chandu Thekkath. Filed 2003, issued 2004.
  • System and method for preventing replay attacks.  Marcos K. Aguilera, Mark Lillibridge, John MacCormick. Filed 2003, issued 2011.