Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
~35% Automata and Language Theory
Deterministic and nondeterministic nite automata, regular expressions, context-free grammars, push-down automata, pumping lemma.
~35% Computability Theory
Turing machines, the Church-Turing thesis, decidability, the halting problem, reducibility. ~30% Complexity Theory
Time complexity, complexity classes P, NP, NP-completeness, P versus NP, space complexity, PSPACE.
Modifications might happen
Canvas:
Homeworks and recitation problems will be posted on Canvas. As will any relevant
announcements. If you don't regularly check email on Canvas, you should forward it to your usual email account.
Required Textbook:
Michael Sipser, Introduction to the Theory of Computation, 3rd Edition.
Cengage Learning. ISBN-13: 978-1-133-18779-0, ISBN-10: 1-133-18779-X, 2013. On reserve in the Engineering Library and the Physical and Mathematical Sciences Library.
A note on course difficulty over the semester:
We will intentionally follow the textbook relatively closely. The most important homework is to
read in the book after each lecture until you understand everything (relevant portions will be
posted on canvas). An even better strategy is to read before the lecture too. This requires
several hours a week. The time might double, when we reach Computability Theory (the second part). As a tradeoff , homeworks will be much easier after studying. You will probably find the first tier of the course much easier as it is concrete but the latter tier is more abstract and will be significantly more challenging . So please keep this in mind.
Homeworks:
The homework assignments have to be written up individually. Cheating will
be handled according to Penn State policy (see below):
You are allowed to discuss the problems and their solutions with one or two other
students, but you have to write up your solution by yourself while not seeing any
solutions from anyone or anywhere else. If two or three students work together, then all of you have to write with whom you worked together at the top of the rst page.
Write, "I worked with . . . ."
It is strictly forbidden to use ChatGPT in any way to create your solution. You are
welcome to use the internet in any honest way, say to find definitions or theorems.
However, you are not allowed to search for the solution for the problem you are asked to solve.
If you cannot solve a problem, instead of writing something random hoping for partial credit, you just write, "I go for 30%," and you get 30% of the points for that problem. You will get much fewer points, if any, for a really bad solution. The 30% option is not available on exams.
Exams and Grading:
First Midterm 20 %
Second Midterm 20 % Final Exam 25 %
Homeworks 25 %
Project 10%
Time and date: 14th Feb 8pm-10pm 108 Forum and 162 Willard.
Time and date : 3rd April 8pm-10pm 108 Forum and 162 Willard
Roughly weekly