Some citizens of Königsberg
Were walking on the strand
Beside the river Pregel
With its seven bridges spanned.

“O Euler, come and walk with us,”
Those burghers did beseech.
“We’ll roam the seven bridges o’er,
And pass but once by each.”

“It can’t be done,” thus Euler cried.
“Here comes the Q.E.D.
Your islands are but vertices
And four have odd degree.”

William T. Tutte
    

Overview

The course aims to cover many portions of the book "The Nature Of Computation" by Cristopher Moore and Stephan Mertens. This nearly 1000-page text is a comprehensive study of computers, physical experiments and their underlying mathematical ideas. It is a well-balanced, in-depth introduction to modern computing, covering about every aspect of what one needs in order to effectively apply computers to problem solving. The central theme of the book is understanding computational complexity of various problems, starting with the 18$^{th}$ century problem of "The Bridges of Königsburg" and ending with current problems, such as systems exhibiting "artificial intelligence" or "machine learning", and quantum computing. An interesting chapter "When Formulas Freeze: Phase Transitions in Computation" explains how a computer program may "freeze" or "thaw", as if it were a pot of water subjected to temperature changes. Exploring this analogy allows applying methods of statistical mechanics to analyzing computer programs. The course will cover a number of selected topics from the book. The emphasis will be on a clear presentation of a wide variety of topics representative of the computing revolution we are experiencing. The target audience is students of mathematics, computer science and related fields who will use applied computing in their research and future work.

Book:

"The Nature Of Computation" by Cristopher Moore, Stephan Mertens. (ISBN-13: 978-0199233212, ISBN-10: 0199233217). Additional course materials will be provided by the instructor in electronic form as needed.

Description:

The specific topics may include:
  • Measuring complexity (1 week).
  • Dynamic programming and greedy algorithms. Discrete vs. continuous optimization (1 week).
  • Review of graphs and NP-hard problems, e.g. finding Hamiltonian paths, cliques, etc. (2 weeks).
  • Solving problems by message passing. Belief propagation (2 weeks).
  • Ising-type models. Sampling. Partition function (2 weeks).
  • Graphical models (2 weeks).
  • Counting (1 week).
  • Phase transitions in computing (2 weeks).
  • Basics of quantum computing (2 weeks).

Prerequisites:

Basic programming skills are required. Familiarity with MATLAB is useful, as the instructor will use it as means of illustrating fundamental ideas.