The goal of this course is to explain and illustrate one of the most important and fundamental facets of the world of computing - its inherent limitations. We shall see that there are problems for which no algorithmic solution will ever exist, and realizing the existence of such inherently unsolvable problems has been one of the main achievements of 20th century mathematics. Roughly speaking, the subject matter of the theory of computability is the precise definition of the informal concept of algorithm, and the characterization of those problems that can (or, perhaps more intriguingly, cannot) conceivably be solved by means of algorithms. In the process of developing such a theory, to which the bulk of the course will be devoted, we shall touch upon topics such as:

• Models for the description of algorithms (with special emphasis on Turing Machines and their equivalence,

• Church-Turing's thesis,

• Unsolvable problems.

The last part of the course will be devoted to a brief introduction to the theory of computational complexity. In a nutshell, one may say that, whereas computability theory is concerned with the class of problems that can or cannot be solved algorithmically, complexity theory aims at characterizing the problems for which efficient algorithmic solutions can conceivably be found. The key concept that we shall touch upon in this part of the course is that of NP-complete problems.

This is a THEORY Course.  As such, we will spend time working with DEFINITIONS, THEOREMS and PROOFS.  We will learn about ABSTRACT computer structures and models.  We will use mathematical tools to look at what can be computed and what cannot be computed, as well as how efficiently it might be computed.

Sipser, Michael, Introduction to the Theory of Computation, PWS Publishing Company, 1997.  ISBN 0-534-94728-X.  (Sipser)

Homework is considered an essential part of mastering the course material and will be assigned at the end of each lecture.  Selected homework problems will be graded and contribute to the overall course grade (see below).  Homework will be collected at the beginning of the lecture on the prescribed due date.

NO LATE PAPERS will be accepted.

If you foresee a conflict in your schedule which would preclude your ability to get your homework in on the date that it is due, make arrangements to submit your work before the assignment is due.

Assignments are individual efforts and not community projects.  To this end, and to make this perfectly clear BEFORE the semester begins, here is the policy that will be enforced:

Any perceived joint efforts will be documented and the alleged collaborators (copiers and copyees alike) will be confronted.  A plea of “guilty” will result in a zero score for that assignment.  A plea of “not guilty” will result in the documentation being delivered to the Dean of Student Affairs in accordance with the Academic Honesty Policy of Rensselaer at Hartford (see the handbook).  Any subsequent alleged offense will be documented and delivered directly to the Dean for handling.  The collaborators will be notified, but the will be no plea bargaining.

The grading of homework will be done with the following criteria in mind, from most to least desirable:

1.      Logical foundation with correct solution

2.      Logical foundation but incorrect solution

3.      No logical support with correct solution

4.      No logical support and incorrect solution

Occasionally, graded quizzes will be given during the lecture period.  The quizzes are closed book and closed note.

Two in-class exams will be given, a Midterm exam and a Final exam.  The exams are closed-book/closed-note tests.  Please review the institution policy on ‘cribbing’ published in the Rensselaer student handbook.  No make-up exams will be given.  If you know you have a problem with a scheduled exam date, see me and we can make arrangements for you to take an exam prior to the scheduled date.  If you miss an exam and the Dean says I must give you a make-up exam, it will be oral, in my office, and at my convenience. 

Your course grade will be determined by the distribution of Final Course Scores according to the following formula:

Final Course Score    =   10%(Quizzes + Homework)  +  45% Midterm  +  45% Final

However, in no event will a semester Final Course Score of greater than 90% be anything less than an A, greater than 80% less than a B, or greater than 70% less than a C.  This does not mean, however, that you must score at least 90% to get an A, or at least 80% to get a B, or at least 70% to get a C.

Syllabus

Schedule

Student Information Questionnaire

Question:  Some students seem to have copies of old exams and homework sets from past semesters when CSCI-6050 has been taught.  Can we use these?  How can I get copies of these materials?

Answer:  This course has been offered in the past and copies of old exams and homework solutions are floating around.  I will not distribute these.  Of course, I encourage you to study any source that helps you learn and understand the material.  BUT, that being said, plagiarism is a serious academic offense and all instances of plagiarism will be reported to the Dean.  Please don't be tempted to copy materials from any source when answering homework and exam problems; these have to be your own answers.  This warning also applies to materials you find on the web. 

Question: I got a low score on the midterm exam.  Is there some way I can makeup the points by extra credit (like writing a program or report)?

Answer:  No.  I suggest you put the energy into studying for the final.