Syllabus

General Info

Course

CS335 Theory of Computation

Instructors

Charilaos Skiadas

Term

Fall 2019-2020

Office

SCH 111 / LYN 108

Office Hours

MWF 10:30am-11:30am in SCH 111 and by appointment

Book

What can be computed, 1st ed, by John MacCormick, ISBN 978-0-691-17066-4

Websites

for notes.

Class times

TR 10:00am-11:45am in LYN120A.

Course Description

Theory of Computation concerns itself with an examination of the capabilities and limitations of computers. In essence the fundamental questions are:

• What do we mean by computing something?
• What are the limits to what is computable?
• Are there things that we can prove are not computable?
• How does our choice of computation engine determine what can and cannot be computed?
• Can we identify problems that are computable but not in a reasonable amount of time? How would we define that to begin with?

This course is much more rigorous than most Computer Science courses. A certain level of familiarity with logic and proofs is expected. Even though we will often use Python programs as a vehicle to explore the topics of computation, a lot of the discussion and statements will appear to be quite theoretical in nature. For instance we will explore the fact that there are certain problems that we can prove are unsolvable.

At the end of this course you:

• will have become familiar with various descriptions of what it means to compute something.
• will have developed a solid foundation on various kinds of computation engines and their abilities and limitations.
• will be able to articulate the fundamental issues regarding computability and its limits.
• will be able to distinguish problems based on their computational difficulty.

Course Components

Reading Notes and Practice Problems

On the website you will find a schedule with information on each class day’s lesson plan. In those documents you will find notes for the day’s lesson, a reading assignment, and a list of practice problems. You should work on those practice problems, and ask any questions you have about them. You do not have to turn the problems in.

Class Participation

You are expected to attend every class meeting, including labs. You are only allowed to miss 2 classes without excuse. From that point on, every unexcused absence will result in a reduction of your final score by two percentage points, up to a total of 10 points. Excused absences should be arranged in advance, and backed by appropriate documentation. Emergencies will be dealt with on an individual basis. There are very few reasons that would qualify as an excuse for an absence.

There will also be numerous in-class group activities that you will be asked to participate in, that contribute towards your class participation grade.

Homework Assignments

There will be regular homework assignments about once per week. Questions on the exams tend to be similar to the homework problems, so it is to your advantage to really understand the homework, and not merely “do it” or copy it just to get it turned in. Homework assignments are 25% of your final grade.

Exams

There will be two midterms, on Tuesday, October 1st and Thursday, November 7th, and a final/3rd midterm during finals week (as scheduled by the registrar). You have to be here for the exams. If you have conflicts with these days, let me know as soon as possible. Do not plan your vacation before you are aware of the finals schedule. In terms of your final grade, the exams you did better on will weigh more.

Getting Help

• You should never hesitate to ask me questions. I will never think any less of anyone for asking a question. Stop by my office hours or just email me your question, which has the great benefit of forcing you to write it down in clear terms, which often helps you understand it better.
• You are allowed, and in fact encouraged, to work together and help each other regarding the class material. However, I strongly encourage you to try things out on your own first before talking to someone about them.
• You may discuss homework problems with others, but only after you have spent some time trying them on your own. And in any event the submitted work must be your own! So even though you may talk to others about the problem, when you sit down to write the answers you should be on your own.

Classroom policies

Cell phones may not be used in class at any time. If you must use your phone during class time (for an emergency), please step out into the hall or outside the building so you do not disturb others.

Grading

Your final grade depends on class participation, homework, and three exams, as follows:

This gives a number up to 100, which is then converted to a letter grade based roughly on the following correspondence: