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.