CISC462 COMPUTABILITY AND COMPLEXITY

NEWS

Dec. 8

I'm holding office hours on Monday Dec. 10, 2:00 - 4:00 PM, Goodwin 545.

Nov. 30

The tutorial is on Friday December 7, starting at 10:00 AM in Goodwin 521.
Note:The tutorial should take about 90 minutes and at 11 AM we move to Goodwin 544. (We have the original room only for one hour.)

Nov. 25

• Most of the last two classes (on November 28 and 30) will be used for review.
• Information concerning the final exam is posted here. The exam is on December 11.
• A practice final exam is available in PDF format. We will schedule a tutorial going over solutions to the practice exam questions. The time for the tutorial will be decided during the last class (and posted here).

Nov. 16

The fifth assignment has been posted on the assignments page. The fifth assignment is due in class on November 28.

Oct. 31

The fourth assignment has been posted on the assignments page. The fourth assignment is due in class on November 14.

Old announcements

Lecture times

Meeting in room JEF 319 (Jeffery Hall)

Instructor

• Kai Salomaa
  • Goodwin 545, 533-6073
  • 
  • Office hours: Tuesday 10:00 - 11:00
    I will be glad to meet with you also at other times when I'm in my office. You can just drop by, or if you prefer to make sure that I'm in the office, you may contact me for an appointment.

Teaching Assistant

• Ming Yi Zhang
  • myzhang [at] cs [dot] queensu [dot] ca
  • Office hours: Monday 2:30 - 4:30 in Walter Light 310

Textbook

• Introduction to the Theory of Computation, Second Edition
• Author: Michael Sipser
• Thomson Course Technology, 2006

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.

Prerequisites

• CISC 223
• CISC 365 is useful, but not required

Assignments and Exams

Assignment due dates:

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 midterm mark for a missed assignment before the midterm and the final exam mark for an assignment after the midterm.
• 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.
• Ethical conduct:
  • 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.

Midterm and Final Exams

• Midterm exam time: October 24, Wednesday, 7:00 - 9:00 PM, room Goodwin 247.
• The final exam will be scheduled during the December final examination period.

Grading

• If you do better on the final exam than on the midterm, we will replace your midterm mark by the final exam mark.

Lecture Topics

Tentative schedule:

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 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:

   • 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.