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: Nima Roohi

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

Office Hours:

Nima Roohi

roohi2@cis.upenn.edu

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

rohithv@wharton.upenn.edu

Mondays

12:00pm to 1:00pm

4th Floor Bump Space

Xuan Ru Ng

xng@seas.upenn.edu

Thursdays

3:30pm to 4:30pm

Harnwell Mezzanine

Romit Nagda

rnagda@seas.upenn.edu

Wednesdays

5:00pm to 6:00pm

Roding Mezzanine

Artemis Panagopoulou

artemisp@seas.upenn.edu

Thursdays

Sundays

5:00pm to 6:00pm

11:00am to 12:00pm

Active Learning (Towne 2nd floor)

Moore 100C

Wei (Waley) Zhang

wzha@seas.upenn.edu

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

https://piazza.com/upenn/spring2018/cis262/home

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

http://www.automatatutor.com

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:

https://gradescope.com/courses/14103

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