CIS 262: Automata, Computability, and Complexity

Spring 2018

Course Overview:

This is an introductory course on theory of computation. We would like to understand what can be computed and what cannot, even if unbounded amount of resources like memory and CPU are available. Also, in case an answer can be computed, aka. a problem can be solved, we would like to know how efficient an algorithm can be. Treatment will be mathematical and proofs of correctness will be emphasized. The course is divided into three areas. In Part A, we will learn about models of computation that use finite amount of memory. These will be very simple models yet powerful enough to capture what is called Regular Languages. Every time you compile your program in your favorite language, regular languages are most likely used to tokenize your input, i.e. find what/where the identifiers, numbers, strings, whitespace, etc. are in your source code. Not every problem can be solved by Regular Languages though and we will learn about this limitation and how to formally prove a language is not regular. In Part B, will learn about Turing machines, a computation model far more powerful than regular languages. As far as we know, everything that can be possibly computed by a physical machine, even if we have not discovered such a machine yet, can also be computed by a Turing machine. We will learn about decidable and undecidable problems and learn that that even Turing machines are fundamentally limited and number of problems that can be solved by them are much lower than those that cannot be solved. In Part C, we focus on Computational Complexity of decidable problems. We would like to know how efficiently a problem can be solved. For example, is it enough to use polynomially many steps, with respect to the size of input, to solve a problem (class P)? What about polynomially many memory cells (class PSPACE)? What is the relation between problems in class P with those in PSPACE? We will also learn about the class of non-deterministic polynomial time (NP), polynomial time reduction, and completeness of a class.

Staff:

Instructor:

TA/Graders: Solomon Maina, Rohith Venkataraman, Xuan Ru Ng, Andrej Ilić, Romit Nagda, Artemis Panagopoulou, Waley Zhang

Office Hours:

 Nima Roohi Mondays 3:00pm to 4:00pm 506 Levine Hall Solomon Maina Thursdays 3:00pm to 5:00pm 4:00pm to 6:00pm the Graduate Student Lounge in the basement of Levine Levine 057 Rohith Venkataraman Mondays 12:00pm to 1:00pm 4th Floor Bump Space Xuan Ru Ng Thursdays 3:30pm to 4:30pm Harnwell Mezzanine Romit Nagda Wednesdays 5:00pm to 6:00pm Roding Mezzanine Artemis Panagopoulou Thursdays Sundays 5:00pm to 6:00pm 11:00am to 12:00pm Active Learning (Towne 2nd floor) Moore 100C Wei (Waley) Zhang Mondays 6:00pm to 8:00pm 4th Floor Bump Space Andrej Ilić Fridays Saturdays 2:00pm to 3:00pm 11:00am to 12:00pm Active Learning (Towne 2nd floor) Rodin Mezzanine

Logistics:

 Time and Location Monday, Wednesday, Friday 1:00pm to 2:00pm, Town 100 Recitation Monday 4:30pm to 5:30pm Levine Hall 101 Prerequisite CIS 160 - Mathematical Foundations of Computer Science Textbook Introduction to the Theory of Computation (3rd Edition), by Michael Sipser Piazza This term we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. Automata Tutor To help students learn the basic model of finite automata, we use an interactive tool AutomataTutor with novel features for automatically generated feedback and automatic grading. Grades Will be posted on Gradescope: Final Grade Final Exam 30%, Midterms 45%=3x15%, Homework 25%

Exams:

 Midterm 1 Monday February 12 1:00pm to 2:00pm Town 100 Midterm 2 Monday March 19 1:00pm to 2:00pm Town 100 Midterm 3 Monday April 23 1:00pm to 2:00pm Town 100 Final Exam Wednesday May 2 12:00pm to 2:00pm Town 100

Students should familiarize themselves with the rules governing final examinations (http://www.upenn.edu/registrar/pdf_main/Provost-Rules-Governing-Final-Examinations.pdf). If you have a conflict for your exam, please talk to the instructor as soon as possible. Exams are open book. You are only allowed to consult the text book for this course and your lecture notes. Since a lot of you might use electronic version of the textbook, it is possible to use laptop or tablet in exams (no phone). However, you are not allowed to share any electronic device under any circumstances. You are not allowed to share any non-electronic material either. Furthermore, all electronic devices must be unable to make any communication with other devices (turn off wireless network, cellular data, and put your device on Airplane mode). Your phones should make absolutely no sound.

Policies:

Homework:

Homework will be posted on Gradescope every week on Wednesday and are due the following Wednesday 12:30pm. There will be no homework before exams. Two of your least scores will be dropped from your homework. You should use this policy to cover all your problems (illness, interview, personal matter, collision with other work, etc.). Late homework submissions are not allowed. If you have a special circumstance like a disability that requires special accommodations, please talk to the instructor.

Your first name, last name, and PennKey must at the top of every page of your homework. If there are more than one problem in your homework, each problem should be written on a separate page, and properly assigned/selected for each question on Gradescope. If there are more than one problem in your homework, each problem should be written on a separate page, so we can distribute them for grading. You must typeset your homework. Handwritten solutions to homework are not accepted or will receive grade 0. You must explain your answers precisely in homework. Most likely you will lose points if your answer is too short, skips steps, or is vague. Homework are designed for you to find your weaknesses and solidify your understanding of materials. It is very likely that you will be able to find solutions on the Internet or by looking at those from the previous semesters. Please refrain from doing so, as it is a dishonest activity. Refer to Academic Integrity at University of Pennsylvania (http://www.upenn.edu/academicintegrity) for further information.

Regrades:

While the teaching staff will make every effort to grade fairly and properly to evaluate students' understanding of the materials, there are bound to be grading irregularities. To this end, students have a 1 week window to ask for regrades on assignments through Gradescope. Regrades must be endorsed by a TA before submission and students must indicate so on the request. Submissions without explicit endorsements will not be considered. In addition, please be aware that submission of a regrade opens the full assignment up for reevaluation and your final score may go down.

Plagiarism and Cheating:

You should make yourself familiar with Academic Integrity at the University of Pennsylvania (http://www.upenn.edu/academicintegrity). If you find it helpful to collaborate on homework, I encourage you to do so. However, you should write up and submit your answers individually. For every problem that you worked with others, please indicate at the beginning of your solution who you worked with (full name plus PennKey). First offense results in a zero for the homework. In addition to receiving another zero, second offense will be reported to the Office of Student Conduct (OSC) for appropriate disciplinary actions. Homework that are graded zero because of cheating/plagiarism will not be dropped when we compute your final grade. Cheating in exams (mid-terms and final) will not be tolerated and suspicious activities are reported to the Office of Student Conduct (OSC).