School of Computing
CISC462 COMPUTABILITY AND COMPLEXITY
Course Description - Fall 2015
Announcements concerning the course will be posted above.
Please check this page regularly.
The third Test takes place during our class on Friday December 4
at 11:30 AM (in Goodwin 254).
- The test covers chapters 3, 4, 5, 7, 8 and section 9.1
in the textbook.
Most of the questions will deal with chapters 7, 8 and section 9.1
(that is, the material after the 2nd test). However, the material
directly relies on the previous chapters and you are expected to know
also the material from chapters 3, 4, 5.
Many algorithmic questions rely on properties of finite
and context-free grammars (chapters 1 and 2) and it is important
to know well these concepts.
- This is a closed book test. You may bring two
standard size (8.5 times 11 inch) sheets of notes
and use them during the test.
- A practice Test 3 is available in
The classes during week 12 (November 30 and December 2) will be used
for review for Test 3. On December 2 we will go through the
practice test 3 questions.
- November 20
- Assignment 5 has
been posted on the assignment page.
Assignment 5 is due in class on December 2.
|| Wednesday 12:30
Meeting in room GOO 254 (Goodwin Hall)
- Kai Salomaa
- Goodwin 545, 533-6073
- Office hours by appointment.
You can drop by office any time when I'm around.
If you prefer to make sure that
I'll be in the office, please contact me for an appointment.
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.
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.
The course covers Part 2 and Part 3 of the
Some concepts from Part 1 are reviewed.
Some history (Godel and Turing);
Basics of Turing machines; Computability vs. Complexity
For fun: A nice
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
Extensions of TMs;
|| Weeks 1, 2
Decidability and undecidability;
Review of formal languages concepts;
Halting problem; Diagonalization;
|| 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
| Weeks 5, 6
|Time bounded computations; Polynomial time;
Classes P and NP; Time bounded reductions; NP-completeness
|| Ch. 7
The class NP
| Weeks 7, 8
|Space bounded computations; Class PSPACE;
|| 8.1 - 8.4
| Weeks 9, 10
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)
|| Week 11
|Selected advanced topics; Review
|| 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.
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.
- 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
already for input polynomials of small size,
more time than the age of the universe.
it is known that there does not exist
any (arbitrarily inefficient) algorithm solving the above
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.
- 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.
- 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
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.
- complexity of an algorithm;
- complexity of an algorithmic problem.
Also everyday experience with computers
and programming suggests the following (S. Wolfram):
- The solution to a given algorithmic problem can be implemented
in many ways.
- It is often difficult to foresee what a program can do
by reading its code.
- Programs (even very simple ones) can behave in complicated
and seemingly random ways - particularly when they are not working
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
- CISC 223
- CISC 365 is useful, but not required
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:
||Due: October 7
| Assignment 2:
||Due: October 21
| Assignment 3:
||Due: November 4
| Assignment 4:
||Due: November 18
| Assignment 5:
|| Due: December 2
Concerning the assignments:
- The assignments are due at the begin of class on the
- Late assignments:
Late assignments will be accepted up to two days (48 hours) after the
due date. Assignments that are more than 48 hours late are not accepted.
- If you miss an assignment due to illness or similar reason,
you should discuss the matter with me before
the assignment due date. If I accept the reason,
we will use your mark of your next test to replace a missed assignment.
- If you have questions concerning assignment marking, you should
discuss them with the marker within one week
from the time when the marked assignments are made available.
All assignment marks are considered final after that time.
- Academic integrity:
All assignments must be based on individual work.
You are permitted to discuss
general aspects of the assignment problems with your fellow students
but you should
enter and leave from such discussions without any written notes.
The written solution you hand in must be created completely
independently by you. You are of course free to discuss the
assignment problems with the instructor or the
- Please see a
Integrity from the Arts and Science
web site posted
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:
- The tests are held during our regular class time.
- The tests are closed-book exams. You may bring
two 8.5" x 11" sheets containing notes to each test
and use them during the test.
is calculated as follows:
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