CSCI 6120.601 (Fall 2014)

"Theory of Computation"

N. Adlai A. DePano, Ph.D.

Class Meeting Particulars

Mondays & Wednesdays, 7:30-8:45 p.m., venue TBA.

Preliminary Remarks

Welcome to CSCI 6120, "Theory of Computation." The Fall 2014 edition of this course will be just the second offering of the “revamped” one I taught back in 2005.  Even though almost a decade has passed, the theory is mature and we can still discuss material presented in the textbook we used back then (see title below).  The idea is tol build on the material covered in CSCI 3102.  We will expand or limit the coverage as time and other factors permit.

Catalogue Description

CSCI 6120  Theory of Computation  3 cr.

Prerequisites: CSCI 3102. A survey of formal models for computation. Includes Turing machines, partial recursive functions, recursive and recursively enumerable sets, the recursion theorem, Church's thesis, Godel numbering, computational complexity, uncomputability, intractability, and unsolvability.

 

Required Text

The required text for this course is Models of Computation. Exploring the Power of Computing by John E. Savage. Addison Wesley, 1998 (ISBN 0-201-89539-0).  A large part of the lecture material will be based on this text.  We will augment the material with notes from other sources such as the proceedings from the annual ACM Symposium on Theory of Computation and more recent books.   [The textbook is currently out of print but there are secondary sources, two of which are provided here:  Barnes & Noble and Amazon.]

 

Reference

We shall refer to material from other excellent textbooks such as the classic Lewis & Papadimitriou's Elements of the Theory of Computation (2nd ed), Prentice-Hall (1997) (ISBN 0-132-62478-8), which is now in its second edition.

 

Other Texts

An older edition of this course was based on the following classic text (now in its fourth edition):  Boolos, Burgess, & Jeffrey's Computability and Logic (4th ed), Cambridge Press (ISBN 0-521-00758-5).

Course Objectives

In the course of the term, successful students in CSCI 6120 should be able to:

  1. Articulate the theoretical basis of computation, including finite automata, regular expressions, push-down automata, grammars, formal languages, Turing machines, computability, and complexity.
  2. Appreciate the real limitations and opportunities in computing, including: (a) what can and cannot be computed (computability); (b) the power of different types of computational systems in terms of what they can compute; and (c) what is practically computable and the complexity of solving certain classes of problems (complexity and intractability).
  3. Appreciate and improve proficiency with rigorous methods, representations, and proof techniques.
  4. Further apply theoretical concepts to practical problems.

Course (Coarse?) Outline

The following serves as a rough guide to the material to be discussed in the term.  We shall adjust as time permits:

  1. Overview and review
  2. Logic Circuits
  3. Machines with Memory
  4. NP-Complete Languages
  5. Space-Time Tradeoffs and I/O Complexity
  6. Formal Languages and Automata
  7. Computability
  8. Reductions Between NP-Complete Problems
  9. Lambda Calculus Computability, models of computation
  10. Miscellaneous other topics (depending on time and availability of sources).

Course Format

The course will be done primarily in lecture format -- questions and discussions are most welcome, however. Student participation is, in fact, strongly encouraged. Regular problem sets will be assigned and will often be discussed in class with students being requested to talk about their own work. Students will also be assigned to report on relevant papers from current periodicals/proceedings. Some programming may be required as well.

Course Grades

During the semester you will be assigned numeric grades on homework and tests. However, the final grade will be submitted as a letter grade and will be done according to the following procedure:   Homework will comprise 30%; tests make up the remaining 70%. The test component will be computed as follows: Two in-class tests and the final exam counted twice give four grades. The highest three will be used to compute the test component of your final grade. For instance if your in-class test grades are 70 and 80, and your final exam grade is 75, then the grades 80, 75, 75 (i.e., highest three of 70, 80, 75, 75) will be used.

Numerical grades translate to their letter grade counterparts using the following table: 

               90 - 100                A
               80 - 89                  B
               60 - 79                  C
               50 - 59                  D
               below 50              F

Tests and Exams

The exam schedule is tentative. We will have two tests plus the final exam. Tentative dates for the tests are Sept. 24th and Nov. 5th. The final exam is firmly scheduled as follows:  Wednesday, Dec. 10th, from 8:00 p.m. - 10:00 p.m.

Homework Assignment Policy

Homework assignments are a crucial part of the learning process in this course. It is by "getting one's hands dirty" that one absorbs the subtle points of theoretical issues. Only by being able to translate theory into practice can one truly say that the material has been learned. Policies that apply to homework are as follows:

  1. Homework will (typically) be assigned a week prior to its due date.
  2. "Late" work will be penalized. Every full day that an assignment is late doubles the penalty of the previous day, starting with one percentage point deducted on the first day. So in practice, an assignment that is turned in a week late automatically gets an F, having already incurred a penalty of -64! However, it is understood that during the course of the semester, life doesn't always follow a smooth path; therefore, everyone is entitled to a "free pass," that is, the lowest homework score will be dropped from the final computation of grades.
  3. Unintelligible=wrong=no credit. You are expected to communicate your thoughts clearly. Submitted homework is expected to be neat, solutions (if required) appearing in order, and, in general, clearly explained by accompanying explanations in English. One suggestion is to work out problems on scratch paper and to recopy them for the final submission.
  4. Assignments are expected to be your own personal effort. However, there is very little one can do to prevent you from "consulting" with each other on homework assignments. In a limited way, this can be beneficial to you. After all, teaching one another and working together are important skills. However, it is essential that your homework submissions reflect your own personal analysis and solution. It is suggested that you try to work on the problem on your own, and then only when you get stuck should you begin discussion with your colleagues. The interaction should be two-way -- you contributing to it as well as profiting from it. When writing the final submission. try to recreate the arguments on your own. Only when you can do this can you truly say that you have learned from the group effort. Needless to say, this joint work policy applies only to homework,, and not to examinations!

Office Hours

The instructor should normally be available for consultation at his office (MATH 308) during the following times: 

               Mon, Wed, Fri      TBA
               Tue, Thu               TBA
                                              other times by appointment only
                                              (phone 280-7370 or 280-6594)

Or send e-mail to ndepano@uno.edu or adlaidep@yahoo.com.  You are encouraged to make use of these periods for your personal profit and for me to get to know students better. Questions and suggestions are especially welcome at these times.

Attendance Policy

Attendance will be taken at each session. Although not specifically included as one of the criteria for the final grade, attendance can have an impact on borderline cases. Good attendance is an indication of the dedication of the student to the learning enterprise. This will be taken by the instructor into consideration in such cases.

Academic Dishonesty

Academic integrity is fundamental to the process of learning and evaluating academic performance. Academic dishonesty will not be tolerated. Academic dishonesty includes, but is not limited to, the following: cheating, plagiarism, tampering with academic records and examinations, falsifying identity, and being an accessory to acts of academic dishonesty. Refer to the Student Code of Conduct for further information. The Code is available online at http://www.studentaffairs.uno.edu.

Students With Special Needs

It is University policy to provide, on a flexible and individualized basis, reasonable accommodations to students who have disabilities that may affect their ability to participate in course activities or to meet course requirements. Students with disabilities should contact the Office of Disability Services as well as their instructors to discuss their individual needs for accommodations. For more information, please go to http://www.ods.uno.edu.

Again welcome to the course and I hope you will find it worth your time and effort.