John MacCormick

John MacCormick

Associate 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


John 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. 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 has filed over a dozen 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's work spans several sub-fields of computer science, including computer vision, large-scale distributed systems, computer science education, and the public understanding of computer science.


Books

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

 

 

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:


Teaching

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:


Research

My main area of research is computer vision—that is, getting computers to understand images and video—but I enjoy working on a wide variety of problems in computer science. For example, I've also worked on large-scale distributed data storage systems, and pair programming techniques for undergraduate computer science education. 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.

Books

Peer-reviewed conference papers

Book chapters

  • 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.

Journal articles

Other publications

  • 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.

Distributed Detection With Diagnosis.
Paul Barham, Richard Black, Moises Goldszmidt, Rebecca Isaacs, John MacCormick, Richard Mortier. Filed October 2006.

Data replication in a distributed system.
William R. Hoffman, Marcus J. Jager, John P. MacCormick, Kristof Roomp, Chandramohan A. Thekkath, Lidong Zhou. Filed June 2006.

Searchable storage system.
William R. Hoffman, Marcus J. Jager, John P. MacCormick, Kristof Roomp, Chandramohan A. Thekkath. Filed June 2006.

Scheduling of index merges.
John P. MacCormick, Frank D. McSherry. Filed January 2006, issued March 2010.

Balanced prefetching exploiting structured data.
John P. MacCormick, Nicholas Charles Murphy, Chandramohan A. Thekkath, Lidong Zhou. Filed September 2005.

Method and system for estimating the three dimensional position of an object in a three dimensional physical space.
Adrian E. Broadhurst, Michael Harville, John P. MacCormick, Donald O. Tanguay. Filed in April 2005.

Systems and methods for structuring distributed fault-tolerant systems.
John MacCormick, Chandu Thekkath, Lidong Zhou. Filed January 2005.

Efficient Recovery of Replicated Data Items.
John MacCormick, Chandu Thekkath, Lidong Zhou. Filed December 2004, issued June 2010.

Method and apparatus for estimating time delays in systems of communicating nodes.
Marcos K. Aguilera, John MacCormick. Filed in October 2004, issued April 2006.

Method and system for renaming consecutive keys in a B-tree.
John MacCormick. Filed in April 2004.

System and method for preventing replay attacks.
Marcos K. Aguilera, Mark Lillibridge, John MacCormick. Filed in June 2003.

Method and system for securing block-based storage with capability data.
Marcos K. Aguilera, Minwen Ji, Mark David Lillibridge, John Philip MacCormick, Erwin Oertli, David Godbe Andersen, Michael Burrows, Timothy P. Mann, Chandramohan A. Thekkath. Filed May 2003.

Method and system for managing access control.
Marcos K. Aguilera, Minwen Ji, Mark David Lillibridge, John Philip MacCormick, Erwin Oertli, David Godbe Andersen, Michael Burrows, Timothy P. Mann, Chandramohan A. Thekkath. Filed May 2003.