Overview:

This course will help you get a perspective about the difficulties of computing tasks. Therefore, before you get into the details of solving a new practical problem you should be able to categorize it in order to guide you to the kind of solution you expect to find. It will introduce you to the theoretical aspects of this process.

Time and Location:

Tuesday, Thursdays 4:35 -5:50 Sparks Building 010

Instructor:

Ishan Behoora, [email protected]

Office hours: (Tentative) Fridays 3pm-4pm via zoom (link: https://psu.zoom.us/j/96225019830 ) or in person if preferred by appointment. Alternate meeting times may also be available

depending on the week and can be requested via email.The best way to contact me is directly via email instead of through canvas

Teaching Assistants:

Omer Faruk Ozdemic, [email protected]

Office hours: Tuesdays 3:00pm-4:15pm Zoom link: https://psu.zoom.us/j/4177385250

Akash Kumar, ajk6173@psu.edu

Office hours: Thursday 3:00pm-4:15pm 300 building on burrows TA room

Najrin Sultana [email protected]

Office hours: Wednesday 9:30am-10:45am Zoom link: https://psu.zoom.us/j/76851851977

Abhiram Vasudeva Sharma abv5402@psu.edu Office hours::

Office hours: Monday 2:30pm - 3:45pm Zoom link: https://psu.zoom.us/j/3308536930

Prerequisite:

CMPSC 465

Recitations:

Start from 2nd week of classes (week of Jan 15th)

Section 1: Wednesday 10:10 - 11:00 Walker Building 109 by Akash Kumar

Section 2: Wednesday 11:15 - 12:05 Walker Building 109 by Abhiram Vasudeva Sharma Section 3: Wednesday 01:25 - 02:15 Walker Building 012 by Omer Faruk Ozdemic

Section 4: Wednesday 03:35 - 04:25 Walker Building 012 by Najrin Sultana

Topics to be covered:

~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.

https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X

Textbook homepage (including errata): https://math.mit.edu/sipser/book.html.

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

Academic Integrity Statement:

Academic integrity is the pursuit of scholarly activity in an open, honest and responsible manner.

Academic integrity is a basic guiding principle for all academic activity at The Pennsylvania State University, and all members of the University community are expected to act in accordance with this principle. Consistent with this expectation, the University's Code of Conduct states that all students should act with personal integrity, respect other students' dignity, rights and property, and help create and maintain an environment in which all can succeed through the fruits of their efforts

.

Academic integrity includes a commitment by all members of the University community not to engage in or tolerate acts of falsification, misrepresentation or deception. Such acts of dishonesty violate the fundamental ethical principles of the University community and compromise the worth of work completed by others.

The CSE Department is quite specific on Academic Integrity.

(http://www.eecs.psu.edu/students/resources/EECS-CSE-Academic-Integrity.aspx).

Department policy for academic sanctions of academic integrity violations specifies a reduction of score on the submission (typically reduced to a 0 except for minor infractions) and a reduction of up to 1 letter grade for the final course grade. For students with previous academic integrity violations (occurring in any course), the department will recommend to the College of

Engineering Academic Integrity Committee that the student receive an F in the course.