School of Computing
Queen's University
CISC462 COMPUTABILITY AND COMPLEXITY
Course Description  Fall 2018
NEWS
 Sept. 10
 Assignment 1 has been posted
on the assignments page.
Assignment 1 is due in class on September 27.
 Sept. 10
 The office hours have been posted. The office hours begin
the week of Sept. 17.
 Sept. 3
 Welcome to the course!
Announcements concerning the course will be posted above.
Please check this page regularly.
Old announcements
Lecture times
Slot 2 
Monday 9:30 
Wednesday 8:30 
Thursday 10:30 
Meeting in room
Jeffery Hall 101.
Instructor
 Kai Salomaa
 Goodwin 545, 5336073
 ksalomaa at cs dot queensu dot ca
 Office hour: Tuesday 12:30  1:30 PM Goodwin 545
You can drop by my office also at other times when I'm around.
If you prefer to make an appointment,
please talk with me after class.
Teaching Assistant
 Taylor Smith
 tsmith at cs dot queensu dot ca
 Office hour: Wednesday 2:30  3:30 PM, Goodwin 241. (The TA office
hours begin the week of Sept. 17.)
Textbook
You may be able to find a used copy of the second
or the first edition
of the textbook
Introduction to the Theory of Computation by Michael Sipser.
The earlier editions should be usable but may
differ slightly from
the current edition.
The first edition has fewer exercises.
The
textbook is available at the Queen's bookstore.
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;
ChurchTuring 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; NPcompleteness 
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
MohammedalKwowarizmi (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
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.
 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 inbetween 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:
 complexity of an algorithm;
 complexity of an algorithmic problem.
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 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
properly.
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.
Prerequisites and Academic Policies
 CISC 223
 CISC 365 is useful, but not required
Learning
outcomes can be found at
http://www.cs.queensu.ca/students/undergraduate/CLO.php#CISC462.
Information on Faculty of Arts and Science policies on Academic integrity,
accommodations and copyright can be found at
http://www.cs.queensu.ca/students/undergraduate/syllabus/
and
www.queensu.ca/artsci/sites/default/files/academic_regulations.pdf.
Assignments and Tests
There will be 4 written homework assignments, a midterm test
and a final exam.
Assignment due dates:
Each assignment has a weight of 10% for your total grade.
The assignments are due at the beginning of the class on the due date.
Assignment 1:
PDF 
Due: Thursday Sept. 27 
Solution 
Assignment 2:
PDF 
Due: Thursday October 11 
Solution 
Assignment 3:
PDF 
Due: Monday November 5 
Solution 
Assignment 4:
PDF 
Due: Monday November 26

Solution 
Concerning the assignments:
 The assignments are due at the begin of class on the
due date.
 The assignments must be submitted in paper copy. Assignments
sent by email are not accepted.
 Late assignments:
Late assignments will be accepted up to two days (48 hours) after the
time they are due.
Assignments that are more than 48 hours late are not accepted.
 The penalty for a late assignment is 10% of the maximum mark.
 If you miss an assignment due to illness or similar reason,
you should discuss the matter with the instructor before
the assignment due date. If the instructor accepts the reason,
we will use your midterm test mark to replace a missed assignment 1 or 2,
or your final exam mark to replace a missed assignment 3 or 4.
 If you have questions concerning assignment marking, you should
discuss them with the teaching assistant 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
teaching assistant.
 Please see a
Statement
on Academic
Integrity from the Arts and Science
web site posted at
http://www.queensu.ca/artsci/studentsatqueens/academicintegrity.
Midterm and Final Exam
There will be a 50 minute closed book midterm test
held during the class hour and
a 3 hour closed book final exam.
 Midterm test time: Thursday October 18, 10:30 AM.
 The final exam
will be scheduled during the December final examination period.
 The midterm and the final are closedbook exams. You may bring
one
standard size 8.5" x 11" sheet containing notes to each test
and use it during the test. The sheet can be written/printed on
both sides.
Grading
Your grade
is calculated as follows:
4 assignments: 
40% 
Midterm exam: 
20% 
Final exam: 
40% 
Total: 
100% 
 If you do better on the final exam than on the midterm, we will
replace your midterm mark by the final exam mark (as a percentage).
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.