Intro:

Course Overview:

This course introduces students to an essential part of theoretical computer science where you will learn about the following.

1. Formal models of computation:

• Finite Automata and Turing Machines,

• Universality Theorem and the Church-Turning Thesis.

2. Computability Theory (“What can or cannot be computed?”)

3. Complexity Theory (“How e cient can a certain computation be?”)

• NP-completeness,

• PSPACE-completeness.

Recitation Sessions:

• 001R : We 10:10AM - 11:00AM @ Leonhard Bldg 103
• 002R : We 11:15AM - 12:05AM @ Sackett Bldg 108
• 003R : We 1:25PM - 2:15PM @ Leonhard Bldg 103
• 004R : We 3:35PM - 4:25PM @ Leonhard Bldg 103

Important Links:

• Canvas: You should be automatically signed up. We use Canvas as the main course platform. Everything will be uploaded here.
• Gradescope: You should be automatically signed up. We use this site for homework submissions. You should submit you answers here.
• Piazza: You should be automatically signed up. We use this platform to ask and answer questions.
• Public page of the course: You are already here.

Tentative Schedule:

Textbooks and References:

Here is the main textbook of the course:

• Michael Sipser, Introduction to the Theory of Computation, 3rd Edition. ISBN-13: 978-1133187790.

I do recommend reading the textbook before and after each lecture. However, I do not want the extremely high price of the book to pose a barrier to the learning process. If you were not able to get this book, an older version -which will be much cheaper- seems fine. But in that case, remember to double check the assignments that are given. Sometimes we assign problems from the textbook and it might be different in the previous editions. So make sure to double check if you are using an older edition.

Here are the other textbooks that you can use:

• John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006.
• Dexter C. Kozen. Automata and Computability. Springer-Verlag, Berlin, Heidelberg, 1st edition, 1997.
• Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2009.

I also recommend reading the following free e-book which is an introduction to the standard methods of proving mathematical theorems. It is a good read for sure.

• R.H. Hammack. Book of Proof. Open Textbook Library. Richard Hammack, 2013.

Grading Criteria:

• Homeworks: 40% (should be submitted on Gradescope [two HW low scores will be dropped])
• Midterm 1: 15% (scheduled on 02/18/2020, 8pm -- 10 pm @ 105 Forum Building)
• Midterm 2: 20% (scheduled on 04/01/2020, 8pm -- 10 pm @ 108 Forum Building)
• Final exam: 25% (check Lionpath)

The following letter grades are guaranteed if you earn the corresponding percentages:

A = 93% - 100%, ;A- = 90% - 93%; B+ = 87% - 90%; B = 87% - 83%; B- = 83% - 80%; C+ = 80% - 77%; C = 77% - 70%; D = 70% - 60%; F = 0% - 60%.

• Curving is at the discretion of the instructor.

Homeworks:

You will have weekly homework through out the semester. The problem sets will be uploaded on Canvas and you have to upload your submissions on Gradescope. Note that:

• NO late homework is accepted even if the latency is few seconds. The system gets closed immediately after the deadline.
• Two of your lowest homework grades will be dropped (to compensate no-late-homework policy)
• Either type your answers or make sure to write in a neat way and then either scan it or use proper apps and cameras to make sure that the graders can read your submission. It is your responsibility to make sure that others can read your answers. Write clean and clear.
• All objections to the grades should be submitted through Gradescope. You should submit a regrade request in order to make sure that we will consider it.
• You have one week to complete each homework (except HW # 0 and HW # 13).
• Homework problems are mostly comprehensive. That being said, you need time to be able to answer them. Start early to make sure that you can meet the deadline.
• Attend office hours if you want to discuss about the problems. Office hours are one of the best resources. You can also use Piazza if you think your question is general and others might have that question as well.
• If you do not know the answer to a question, do not write irrelevant stuff. You can simply just write that “I go for 25%”. Knowing that your answer is wrong deserves 25% of the grade. This sentence should be written specifically. If you leave blank, we will not give you 25%. There is no limit in using this feature. Going for 25% is NOT available in exams and applies only to homeworks. If a
• problem has more than one part, you should write this sentence for each part, otherwise it will be applied for only the first part. If you write both an answer and “I go for 25%” sentence, we will only consider whichever comes first.