School of Computing
Queen's University


Course Description - Fall 2015

Textbook Lecture Topics Course Description Assignments and Tests Grading


The third Test takes place during our class on Friday December 4 at 11:30 AM (in Goodwin 254).

November 20
Assignment 5 has been posted on the assignment page. Assignment 5 is due in class on December 2.

Announcements concerning the course will be posted above. Please check this page regularly.

Old announcements

Lecture times

Slot 13 Monday 1:30 Wednesday 12:30 Friday 11:30

Meeting in room GOO 254 (Goodwin Hall)


Teaching Assistant


You may be able to find a used copy of the second or first edition of the textbook Introduction to the Theory of Computation by Michael Sipser. The earlier editions should be quite well usable but may differ slightly from the current edition. The first edition has fewer exercises.

The textbook is available at the Queen's bookstore. A copy of the old edition will be placed on reserve in the Engineering and Science Library.

Lecture Topics

The course covers Part 2 and Part 3 of the textbook. Some concepts from Part 1 are reviewed.

Tentative schedule:

Topics Textbook chapter/section Notes outline Week (tentative)
Some history (Godel and Turing); Basics of Turing machines; Computability vs. Complexity
For fun: A nice mechanical/optical Turing machine implementation. (Strictly speaking, the implementation is only what we will call a linear bounded automaton.)
Ch. 3 Introduction: history and motivation Week 1
Turing machines; Extensions of TMs; Church-Turing thesis Ch. 3 Turing machines Weeks 1, 2
Decidability and undecidability; Review of formal languages concepts; Halting problem; Diagonalization; Universal TMs Ch. 4
Parts of Ch. 1 and 2
Decidability and undecidability Weeks 3, 4
Establishing unsolvability using reductions; PCP; Rice's theorem Ch. 5 Further undecidable problems
Mapping reducibility
Weeks 5, 6
Time bounded computations; Polynomial time; Classes P and NP; Time bounded reductions; NP-completeness Ch. 7 Time complexity
The class NP
Weeks 7, 8
Space bounded computations; Class PSPACE; Logarithmic space 8.1 - 8.4 Space complexity
Logarithmic space
Weeks 9, 10
Completeness; Relationships between complexity classes; Time and space hierarchy 8.5, 8.6, 9.1 Space and time hierarchies Week 10
Circuit complexity; Oracles and Turing reductions 9.2, 9.3, (6.3) Circuit complexity Week 11
Selected advanced topics; Review 10.? - Week 12

Note: The posted notes are only an outline and are intended to assist in taking notes in class. The posted notes are not a replacement for the classes.

Course Description

The objective of the course is to provide an introduction to computability and complexity, which are part of the theory of algorithms. The notion of an algorithm is fundamental in computer science, however algorithms have been studied much before the invention of modern computers. One of the oldest and, perhaps, most well known algorithms, Euclid's algorithm to compute the greatest common divisor, is over 2000 years old. The term "algorithm" comes from the Persian mathematician Mohammed-al-Kwowarizmi (9th century).

The theory of algorithms, as a topic of its own, was born only in the last century, in particular the second half of it. There are three rather separated directions in this research.

  1. Computability (which is sometimes called recursive function theory) studies which problems are in principle algorithmically decidable, that is, solvable by a computer.

    This research got started when Kurt Goedel proved that there exist algorithmically unsolvable problems. Goedel's results were formulated in terms of logical theories but later many concrete and quite innocent looking problems have been shown to be unsolvable. For example, there is no general algorithm that determines whether or not a polynomial equation with integer coefficients has a solution among the integers. Note that here we are not (yet) in any way concerned with resources used by the algorithm. For such an algorithm it would be completely fine, already for input polynomials of small size, to use more time than the age of the universe. However, it is known that there does not exist any (arbitrarily inefficient) algorithm solving the above problem. This question is the so called Hilbert's tenth problem and its unsolvability was established by Yuri Matiyasevich in 1970.

    Computability theory studies and classifies nonrecursive (unsolvable) problems, and in this classification the solvable problems form only a single (lowest) class.

  2. Theory of designing and analysing algorithms: Another direction arose in connection with the fast development of computers, starting in the 50's. It became clear that recursive problems requiring centuries of computer time for solving instances with small input data, were too difficult to be considered solvable in practice.

    This approach concentrates on developing fast computer algorithms and methods to analyse those.

  3. Classifications of complexities of problems: The third direction lies in-between the first two areas. In the 60's it was generally accepted that the class of "feasible" algorithms consists of algorithms that require computation time polynomial in the size of the input. (This classification is only an approximation and it has its own problems, as will be discussed during the course.) Polynomial time reductions were defined, and relationships between complexity classes and complete problems for the classes began to be studied.

    Thus we should distinguish the notions:

    The complexity of an algorithmic problem is the complexity of the "best" (with respect to some resource measure) algorithm solving this problem.

    Also everyday experience with computers and programming suggests the following (S. Wolfram):

    The task of determining the complexity of a given algorithm is often (but not always) a manageable problem. On the other hand, the task of determining the complexity of a given algorithmic problem is usually very difficult (hopeless). As we will see, the exact relationships of even the fundamental and most studied complexity classes (P, NP, PSPACE, LOGSPACE,...) remain unknown. If you are able to solve the "P versus NP" problem you will immediately get $1 million USD.


Assignments and Tests

There will be 5 written homework assignments.

There will be 3 in-class tests. The tests will take place during class in the regular classroom.

There will be no final exam.

Assignment due dates:

Each assignment has a weight of 8% for your total grade.
Assignment 1: PDF Due: October 7
Assignment 2: PDF Due: October 21
Assignment 3: PDF Due: November 4
Assignment 4: PDF Due: November 18
Assignment 5: PDF Due: December 2

Concerning the assignments:

In class tests

Each test has a weight of 20% for your total grade.

Test 1 October 16
Test 2 November 9
Test 3 December 4

Concerning the tests:


Your grade is calculated as follows:

5 assignments: 40%
Test 1: 20%
Test 2: 20%
Test 3: 20%
Total: 100%

Note: The components of this course will receive numerical marks that will be used to calculate a percentage final grade, as explained above. The final grade you receive for the course will be derived by converting your percentage grade to a letter grade according to Queen's official grade conversion scale.