School of Computing
Queen's University
CISC462 COMPUTABILITY AND COMPLEXITY
Course Description - Fall 2018
NEWS
- Nov. 27
- Office hours before the exam:
- Recall the tutorial takes place
Tuesday December 4, 2:00 - 4:00PM in Kinesiology 107
- see information below.
- The instructor has an additional office hour
Thursday November 29, 1:30 - 2:30 PM.
The instructor will be away the week Dec. 3 - 7.
- The TA holds the regular office hour on
Wednesday Dec. 5, 2:30 - 3:30 PM in Goodwin 241.
- Nov. 21
-
- The final exam is on Monday December 10 at 7:00 PM.
The final is a three hour closed book exam. Information
on the final exam is posted here.
- The last two classes on Nov. 28 and 29 will be used
for review for the final exam. The Wednesday class reviews the
first half of the course (Computability) and the Thursday class
reviews the second half (Complexity).
- A practice exam is
posted here.
Solutions can be found
here.
A tutorial going through the practice exam questions
will be held on Tuesday December 4, 2:00 - 4:00PM
in
Kinesiology 107. The tutorial will be held
by the TA Taylor Smith.
- Nov. 16
- In class on Monday Nov. 19 we discuss the timing of the
tutorial for the final exam. The tutorial will be scheduled for
Dec. 3, 4, or 5, based on a poll we conduct in class on Monday.
- Nov. 14
- Marked assignment 3 papers will be returned in
class tomorrow Thursday. Comments from the TA have been posted on
the assignments page.
- Nov. 7
- Assignment 4 has been posted
on the assignments page.
Assignment 4 is due in class on
Monday November 26.
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, 533-6073
- 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;
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.
- 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 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:
- 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.
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/students-at-queens/academic-integrity.
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 closed-book 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.