School of Computing
Queen's University
CISC462 COMPUTABILITY AND COMPLEXITY
Course Description  Fall 2015
NEWS
 Reminder:

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
automata
and contextfree 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
PDF format.

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.
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)
Instructor
 Kai Salomaa
 Goodwin 545, 5336073

 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.
Teaching Assistant
Textbook
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;
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
 CISC 223
 CISC 365 is useful, but not required
Assignments and Tests
There will be 5 written homework assignments.
There will be 3 inclass 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:
 The assignments are due at the begin of class on the
due date.
 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
teaching assistant.
 Please see a
Statement
on Academic
Integrity from the Arts and Science
web site posted
here.
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 closedbook exams. You may bring
two 8.5" x 11" sheets containing notes to each test
and use them during the test.
Grading
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.