CS 2250 / Computability and Complexity / 2024 Spring

Compiled: 2024-02-07 09:51

Instructor: Clayton Cafiero

Email: [email protected]

Office: Innovation E309

Office hours: M 2:10–3:00 PM, W 8:30–10:00 AM, F 9:00–11:00 AM, or by appointment

Website: https://www.uvm.edu/~cbcafier

GTA: Yeonhee Yeh

Email: [email protected]

Section A: T/Th 8:30–9:45 AM, Perkins 107

Section C: T/Th 02:50–04:05 PM, Perkins 107

Overview: This course is a study in automata, automata as models of computation, the fundamental

limits of computing, and complexity theory. Topics include: formal languages, regular expressions,

deterministic and non-deterministic finite automata, context-free grammars and pushdown automata,

Turing machines, decidability, computable functions, reducibility, and time complexity classes (P, NP, NP-

complete, NP-hard). This course fulfills the Qualitative Reasoning (QR) requirement of the Fall 2020

revision of the Catamount Core curriculum. See: https://go.uvm.edu/qr.

Important dates:

• First exam: 2024-02-22, in class (tentative)

Unlimited. Other materials supplied Brightspace.

1

Software: We may do a little programming (just a little), so please be prepared with a reasonably

current version of Python (>= 3.9) and a working installation of Jupyter (this is pip installable; see:

https://jupyter.org/install).

Learning objectives:

• Prove properties of languages and automata using formal mathematical methods.

• Collaborate with peers to solve problems and present results.

• Recognize flaws in invalid proofs.

• Understand decidability and undecidability.

• Understand how reduction techniques are used to prove decidability or undecidability.

• Understand relationships between languages in the context of the Chomsky hierarchy.

• Explain the relationship between time complexity classes P, NP, NP-hard, and NP-complete.

Important websites:

• Brightspace, for course materials, announcements, and submitting certain assignments.

• Gradescope, for submitting certain assignments.

Correspondence: Please use email for electronic correspondence (and not MS Teams). As I teach

multiple courses please indicate the course in which you are enrolled in the subject line. Please use

your UVM email for all correspondence.

in class exams you will be allowed two 8.5" × 11" pages of handwritten notes (both sides OK).

Active learning exercises: Throughout the semester, we’ll have active learning exercises in class.

These will be conducted in small groups (i.e., three to five students per group). Active learning exercises

will be graded on a simple check / check plus kind of scale. Weights of individual exercises TBD.

should be submitted via Gradescope (links on Brightspace).

2

Final exam: The final exam, which counts for 20% of your overall grade, will be administered at times

scheduled by the Office of the Registrar. Exams will be administered using pencil and paper. You will be

allowed two 8.5" × 11" pages of handwritten notes (both sides OK). The final exam will be cumulative,

but primary emphasis will be on Turing machines, decidability, reducibility, and time complexity classes.

Weekly schedule of topics (tentative and subject to change):

Week Topics covered Assessment

01 Math foundations; introduction to computability; Chomsky hierarchy quiz

02 Deterministic finite automata (DFAs) quiz

09 Review: regular and context-free languages exam

10 Turing machines; Church-Turing thesis quiz

11 Decidability and the Entscheidungsproblem quiz

12 Reducibility; mapping reducibility and computable functions quiz

13 Computational complexity; the classes P and NP quiz

14 NP-Completeness and Cook-Levin quiz

15 Topics TBD

Grading:

Assignment of letter grades will be on a conventional scale. Any grade appeal (assignment, quiz, lab,

exam, etc.) must be directed to your grader within one week of the grade being posted. If grading is

done on Gradescope (e.g., for homework), there’s a regrade request feature which should be used for

grade appeals.

Academic integrity: The Department of Computer Science enforces UVM’s Code of Academic Integrity.

Any suspected violation of this policy will be referred immediately to UVM’s Center for Student Conduct

(https://www.uvm.edu/sconduct). Sanctions for a violation may include a grade of XF in the course.

Additional violations can result in dismissal from the university. In a word: Don’t. All students should

be read and understand this policy. See: https://go.uvm.edu/cai.

3

Collaboration on quizzes and exams is strictly prohibited. Use of online services as a source of solutions

is strictly prohibited. Using AI-content generators such as ChatGPT or websites such as Chegg or Course

Hero to complete coursework is a form of academic dishonesty. Work you submit for an individual grade

must be your own. Any work not produced by you (or teammates in the case of active learning exercises

or labs, where applicable) must be cited. If you have any questions ask!

Sharing of course materials without the specific, express approval of the instructor may be a violation

of the University’s Code of Academic Integrity and an act of academic dishonesty, which could result

in disciplinary action. Violations will be handled under UVM’s Intellectual Property Policy and Code of

Academic Integrity, as appropriate. See: https://go.uvm.edu/ipp and https://go.uvm.edu/cai.

Attendance: The UVM attendance policy is available at https://go.uvm.edu/srr. There will be no

make-ups for in class active learning exercises if you did not attend class without prior notification and

approval. While there is no explicit weight for your attendance, a good attendance record will be taken

into consideration when assigning letter grades in the course (e.g., whether a close score is rounded up

for final grade).

If you are not able to attend in-person classes please notify the instructor via email as soon as possible.

Class participation: You are expected to be an active participant in class. The more engaged you are,

the more you will learn—and the more fun you’ll have. This includes being prepared and attentive,

responding when called on, participating in group discussion, and asking questions as appropriate.

When it comes to asking questions, please don’t be shy! There’s no such thing as a “dumb” or “silly”

question. If there’s something you don’t understand—ask! Asking questions helps you understand the

material presented in the course. Asking questions is good for your classmates. It’s almost certain that

if you need clarification on some point, that there’s at least one other student in the class with the same

question. So help each other out—ask! Finally, when you ask a question you help the instructor to do

a better job of explaining. If someone explains something, and you still don’t quite grasp it, it’s not

unlikely that the explanation could be improved or clarified.

4

Late policy / extensions: Each homework assignment has a specific due date / time. You may submit

work up to 24 hours after the due date / time, however, late submissions will be penalized 20%. Sub-

missions that are more than 24 hours late will not be accepted unless an extension has been granted. We

will consider reasonable requests for extensions when extenuating circumstances arise. (It can’t hurt to

ask.) However, extensions will not be granted if the request for extension is made within 24 hours of the

Diversity, equity, and inclusion: UVM is a place where you should be treated with respect and kind-

ness. We welcome individuals of all ages, backgrounds, beliefs, interests, ethnicities, genders, gender

identities, gender expressions, national origins, religious affiliations, sexual orientations, ability, and

other visible and non-visible differences. All students are expected to contribute to a respectful, wel-

coming and inclusive environment for every other member of the community. If you ever feel that you

have been unfairly treated or judged by an instructor, a mentor, another student, or another member of

the community, please let someone know. Your instructors and advisors in the CEMS Office of Student

Services are available to discuss any concerns, or you can report an incident of bias through the bias

report program (https://www.uvm.edu/deanofstudents/bias_response_program).

Conduct: Be kind to one another and to yourself. Be respectful of yourself, others, and the institution.

Please arrive on time. Please, no food in class. Please, no cell phones in class (except for using the

iClicker app when requested). You may use a laptop or tablet, but only for active learning sessions, pair

programming, taking notes, or assistive technologies.

in utilizing ADA accommodations, you should contact Student Accessibility Services (SAS), the office

Contact SAS: A170 Living/Learning Center; +1 802 656 7753; [email protected]; or visit https://www.

uvm.edu/access.

5

Promoting health and safety: If you are concerned about a UVM community member or are concerned

about a specific event, we encourage you to contact the Dean of Students Office (+1 802 656 3380).

If you would like to remain anonymous, you can report your concerns online by visiting the Dean of

Students website at https://www.uvm.edu/deanofstudents.

6