Announcements | | Course information | | Important dates | | Assignments and tests | | Lecture notes |

- 23/5/2018 The updated source file now includes an example of a table for the TM transition function.
- 21/5/2018 To make 2c on the assignment simpler, print your resulting number on the output tape (but do move to the first symbol on that tape). Also, you can assume that tapes are two-way infinite, and that in addition to L and R, there is also a transition "S" (for "stay in place").
- 21/5/2018 Here is a tool for drawing finite automata which generates LaTeX code (copy just the part from \begin{center} to \end{center} into your file). Many thanks to Vineel for the link!
- 17/5/2018 Assignment 1 is now posted. Due Wednesday, May 30, 10pm. Type it up (in LaTeX) and upload pdf to Brightspace (former D2L); here is the LaTeX source,
- 7/5/2018 For the next little while, our lectures will be from 2pm to 4pm. This is to cover more material early on; we will skip lectures later in the semester.
- 7/5/2018 On May 23rd, there is a useful workshop at MUN: Introduction to HPC with ACENET & Compute Canada / Introduction to Linux , followed by Introduction to Shell Scripting on May 24th. As the time on May 23rd overlaps with our class (2pm-4pm), we will cancel the class that day to allow everybody to attend these sessions. In particular, Introduction to Linux and Shell Scripting would be useful for you even if you don't use the clusters.

** older announcements...**

- 14/5/2018 The next lecture, on May 16th, will be in the seminar room (EN-2022). Note that there is an exam there before us, so we might have to wait a little.
- 29/4/2018 The first lecture is Monday, May 7th. If you need me to sign your course add form, please bring it to class.

Assignment 1. (LaTeX source) Due May 30, 2018. |

For typesetting please use LaTeX. I will post source files for the assignments. If you need a LaTeX compiler, the simplest way is to use an online one, such as ShareLaTeX. Just load the source file and start adding your solutions. A good, though outdated, introduction to LaTeX is "Essential LaTeX" .

** Policy on collaboration: ** The work you submit must
be your own. You may discuss problems from assignments with each
other; however, you should prepare written solutions alone.
Plagiarism is a serious academic offense and will be dealt with
accordingly.

**Reference books:**

Mathematics and Computation by Avi Wigderson

* Introduction to the Theory of Computation"* by Michael Sipser

Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.

We will also use lecture notes from similar courses (to be posted later).

** Marking scheme: ** 3 assignments 15% each,
a project %25, and a test 30%.

** Description: **
The goal of this course is to help students develop an intuitive feel
for hardness of computational problems, and an ability to prove that
intuition. What does it mean that a given problem is "hard"? In which
sense is it "hard": is it memory-intensive, computation-intensive; how
are these notions related? How expressive are various languages used
in databases and AI, and what does it mean computationally? These are
some of the questions we will explore in this course.

In particular, we will cover the classical P vs. NP problem (is
checking a solution easier than finding a solution? Nobody knows!), as
well as classes of higher complexity (polynomial-time hierarchy),
space classes, counting classes, randomized and circuit complexity,
and descriptive and proof complexity. We will also review some
computability theory and, time permitting, cover a range of advanced
topics such as PCP, natural proofs (why it is hard to resolve the P
vs. NP question), hardness of approximation, etc.

(this picture is from the cover of the book
"Descriptive Complexity" by
Neil Immerman)

For now, please see lecture notes from the previous run of this course and notes on computability and NP-completeness from an undergraduate course I taught before. I will try to post updated notes if there are sufficient changes from before, new material, etc.

- Lecture 1 (May 7): Four problems, sorting lower bounds
- Lecture 2 (May 9): Finite automata and Turing machines
- Lectures 3 (May 14) and 4 (May 16): Computability and undecidability
- Classic papers on computability and complexity:
- Turing "On computable numbers". (Undecidability, Turing machine).
- Edmonds "Paths, trees and flowers". (Discusses polynomial time as capturing the notion of efficient)
- Cook "The complexity of theorem-proving procedures" (NP-completeness).
- Karp "Reducibility among combinatorial problems" (Shows that a number of well-known problems are NP-complete)
- Impagliazzo's "A personal view of average-case complexity" (Describes 5 possible "worlds" for different resolutions of P vs. NP question)