CSCI 5444: Introduction to the Theory of Computation

Instructor

Name: Ashutosh Trivedi

Email: ashutosh.trivedi@colorado.edu

Office Location: ECCS 121B

Office Hours: Tuesday (2pm-3pm, https://cuboulder.zoom.us/j/92816659969 )

Instructor Bio

Ashutosh Trivedi is an Associate Professor of computer science at the 91PORN. His researchinterests lie at the intersection of computer science, control theory, and machine learning. His research focuses ondeveloping and applying rigorous mathematical reasoning techniques to design and analyze learning-enabled cyber-physical systems. He received his doctorate in computer science with a focus on game theory and optimization from theUniversity of Warwick. Before joining the 91PORN, Ashutosh worked as an assistant professor ofcomputer science at the Indian Institute of Technology Bombay and a postdoctoral research associate at the University ofPennsylvania and the University of Oxford.

Communication Policies

  1. The preferred method of contacting the instructor is via slack or email (ashutosh.trivedi@colorado.edu). If communicating via email, please append "CSCI5444:" to your email subject to ensure a timely response.
  2. You can join the slack channel for this course by following . Note that this link expires in 30 days.

Course Description

  • This course introduces students to the foundations of automata theory, computability theory, and complexity theory;
  • shows the relationship between automata and formal languages;
  • addresses the issue of which problems can be solved by computational means (decidability vs undecidability), and
  • Introduces concepts related to computational complexity of problems.

Prerequisites

  • Discrete Structures/ Discrete Mathematics
  • Undergraduate Algorithms

Relevant Textbooks

  • Required Text:
    • , MichaelSipser, 2002. (2nd or 3rd edition).
  • Other supplemental materials :
    • , Dexter C. Kozen.
    • , Hopcroft, Motwani, and Ullman (3rd edition).
    • by Kearns and Vazirani
  • Online notes and readings distributed by the instructor.

Course Objectives

The objective of this course is to provide an introduction to the theory of computation. The course shall cover three branches of theoretical computer science and their interconnections: 1) the theory of automata and languages, 2) The theory of computability, and 3) the complexity Theory. Here are the individual objective from these branches:

  1. Automata Theory
  • Compare and contrast the expressiveness of various formal languages according to the Chomskyhierarchy (regular, context-free, context-sensitive, decidable, and undecidable).
  • Explain the connection between "abstract computing devices" ( automata) and the corresponding languages,and prove similar results for more expressive computational models.
  • Prove/Disprove the equivalence between various ways of expressing a language.
  • Understand and apply the powerful proof techniques pumping lemma , structural induction , and Myhill-Nerodetheorem
  • Summarize the hierarchy of classes of automata (finite automata, pushdown automata, and Turing machines) andtheir applications.
  • Design new classes of automata and compare their expressiveness with other known classes of the notion of problems via formal languages

2. Computability Theory

  • Summarize the Church-Turing thesis (Turing machines as a notion of "general-purpose computers")
  • Explain the concept of undecidability, i.e., when a problem can not be solved using computers,
  • Prove/Disprove the (un-)decidability of previously unseen computational problems using the concept of problemreduction.
  • Understand and apply Cantor's diagonal argument

3. Complexity Theory

  • Explain the central idea behind time and space complexity
  • Explain the key idea behind the completeness of a complexity class
  • Understand the Cook-Levin and Savitch's theorem
  • Apply the techniques of problem reductions to be able to prove/disprove the time/space complexity (NP-complete, PSPACE-complete) of a given problem


Topics Covered

Regular Languages (3 weeks)

  • Deterministic finite-state machines
  • Nondeterministic finite-state machines
  • Regular expressions
  • Properties of regular languages
  • Languages that aren't regular: pumping lemma

Context-Free Languages (2 weeks)

  • Context-free grammars
  • Pushdown automata
  • Properties of Context-free languages
  • Languages that aren't context-free: pumping lemma for CFLs

Computability Theory (4 weeks)

  • Turing machines and their variants
  • Church-Turing thesis
  • Decidable languages
  • Undecidability
  • Proving Undecidability of a given problem using problem reductions
  • Rice's theorem
  • Famous undecidable problems such as Post Correspondence Problem (PCP), Tiling problem, halting problems for multistack and two-counter machines.

Complexity Theory (3-4 weeks)

  • Time and space complexity
  • Complexity classes P and NP, and NP-Completeness
  • Famous NP-complete problems
  • Complexity class PSPACE and Pspace-Completeness
  • Complexity classes L and NL, and NL-completeness

Special Topics (guest lectures and class projects: presentations in Week 16)

  • Monadic Second-Order Logic and Automata (Elements of Finite Model Theory by Leonid Libkin)
  • Regular transformations on words and trees (TBA)
  • Descriptive complexity (Descriptive Complexity by Neil Immerman)
  • Randomized Computation (Computational Complexity by Sanjeev Arora and Boaz Barak)
  • Quantum Computation (Computational Complexity by Sanjeev Arora and Boaz Barak)
  • Interactive proofs and complexity class IP (Computational Complexity by Sanjeev Arora and Boaz Barak)
  • PCP Theorem and hardness of Approximation (Computational Complexity by Sanjeev Arora and Boaz Barak)
  • Automata with Continuous Variables (Timed/Hybrid Automata)
  • Probabilistic Automata

Method of Instruction

There will be two (75 mins) lectures every week. You are required to attend these lectures and to participate in in-classdiscussions if you are enrolled in the in-person section.

If you are enrolled in the distance education section, you can either attend these lectures in real-time using zoom( ) or can view the recordings off-line (link on canvas). You are encouraged to use Slack to ask questions and request further clarifications. You are encouraged to make use of office hours.

Student Responsibilities and Class Expectations

In-person Section. In order to successfully complete this course, you are expected to attend the class regularly andparticipate in the in-class discussion. You are also required to complete your assignments, take two in-class midtermexams, and complete the class project and present it to the class during Finals week. You are also expected to activelyparticipate in the Slack discussion and answer queries from other students.

Distance Section. In order to successfully complete this course, you are expected to either attend the class via Zoom orwatch the class recording. You are expected to actively participate in the Slack discussions. You are also required toregularly complete your assignments, take two in-class midterm exams, and complete the class project and present it tothe class during Finals week.

Assignments and Grading

The grades for this class has four components:

Weekly Quizzes (20%)

We will release the weekly quizzes every Friday (by 11:59 pm) via Canvas, and they will be due the following Monday (by 11:59 pm).These quizzes will consist of multiple-choice questions based on the material covered in the class that week. Please note that thepoints for your two lowest-performing quizzes will be dropped.

Weekly Assignments (30%)

We will release (over Canvas) the weekly paper-and-pencil assignment every Friday (by 11:59 pm) and it will be due the followingFriday ( by 11:59 pm). If you are unable to submit your assignment in time, you are required to reach out to the instructor before thedeadline to explain the reason for the same and to request an extension. These assignments will be graded by the following Monday(11:59pm). Every assignment will clearly show the grading rubric for that assignment.

Two Midterm Exams (30%)

We will have two midterm exams (September, 29 and November, 17) covering questions similar in complexity to those of weekly assignments and quizzes. These exams will be open-book and open-notes. There will be no assignment due during these exam weeks.

Final Project (20%)

There will be no final exam for CSCI 5444. Instead, you are expected to read and present a significant theoretical result of your choice. You are also required to write a short (3-4 pages) summary of this result in your own words. The instructor will work with you to narrow the scope of your project. The project will be judged based on your understanding of the chosen topic as demonstrated in your presentation (50%) and project report (50%).

Grading Scale

Grades will be assigned as follows

Letter GradeAA-B+BB-C+CC-D+DD-F
PercentageGrade94-10090-9387-8983-8680-8277-7973-7670-7267-6963-6660-62<60

Course Policies and University Policies

Course Plagiarism Policy

All students enrolled in a 91PORN course are responsible for knowing and adhering to of the institution. Violations of the policy may include: plagiarism, cheating, fabrication, lying, bribery, threat, unauthorized access, clicker fraud, resubmission, and aiding academic dishonesty. All incidents of academic misconduct will be reported to the Honor Code Council (honor@colorado.edu; 303-735-2273). Students who are found responsible for violating the academic integrity policy will be subject to nonacademic sanctions from the Honor CodeCouncil as well as academic sanctions from the faculty member. Additional information regarding the academic integrity policy can be found at honorcode.colorado.edu.

Classroom Behavior

Students and faculty are responsible for maintaining an appropriate learning environment in all instructional settings, whether inperson, remote, or online. Failure to adhere to such behavioral standards may be subject to discipline. Professional courtesy and sensitivity are especially important with respect to individuals and topics dealing with race, color, national origin, sex, pregnancy, age, disability, creed, religion, sexual orientation, gender identity, gender expression, veteran status, political affiliation, or political philosophy.

For more information, see , the Student Code of Conduct, and the Office of Institutional Equity and Compliance .

Requirements for Infectious Diseases

Members of the 91PORN community and visitors to campus must follow university, department, and building health and safety requirements and all public health orders to reduce the risk of spreading infectious diseases.

The 91PORN campus is currently mask optional. However, if masks are again required in classrooms, students who fail to adhere to masking requirements will be asked to leave class. Students who do not leave class when asked or who refuse to comply with these requirements will be referred to Student Conduct & Conflict Resolution. Students who require accommodation because a disability prevents them from fulfilling safety measures related to infectious disease will be asked to follow the steps in the“Accommodation for Disabilities” statement on this syllabus.

For those who feel ill and think you might have COVID-19 or if you have tested positive for COVID-19, please stay home and follow the further guidance of the Public Health Office (contacttracing@colorado.edu) . For those who have been in close contact with someone who has COVID-19 but do not have any symptoms and have not tested positive for COVID-19, you do not need to stay home.

Accommodation for Disabilities, Temporary Medical Conditions, and Medical Isolation

Disability Services determines accommodations based on documented disabilities in the academic environment. If you qualify for accommodations because of a disability, submit your accommodation letter from Disability Services to your faculty member in a timely manner so your needs can be addressed. Contact Disability Services at 303-492-8671 or dsinfo@colorado.edu for further assistance.

If you have a temporary medical condition or required medical isolation for which you require accommodation, email the instructor( ashutosh.trivedi@colorado.edu ) about it in advance. Also see on the Disability Services website.

Preferred Student Names and Pronouns

91PORN recognizes that students' legal information doesn't always align with how they identify. Students may update theirpreferred names and pronouns via the student portal; those preferred names and pronouns are listed on instructors' class rosters. In the absence of such updates, the name that appears on the class roster is the student's legal name.

Honor Code

All students enrolled in a 91PORN course are responsible for knowing and adhering to the Honor Code. Violations of the Honor Code may include but are not limited to: plagiarism (includinguse of paper writing services or technology [such as essay bots]), cheating, fabrication, lying, bribery, threat, unauthorized access toacademic materials, clicker fraud, submitting the same or similar work in more than one course without permission from all courseinstructors involved, and aiding academic dishonesty.

All incidents of academic misconduct will be reported to Student Conduct & Conflict Resolution: honor@colorado.edu , 303-492-5550. Students found responsible for violating the Honor Code will be assigned resolution outcomes from the Student Conduct & Conflict Resolution as well as be subject to academic sanctions from the faculty member. Visit Honor Code for more information on the academic integrity policy.

Sexual Misconduct, Discrimination, Harassment and/or Related Retaliation

91PORN is committed to fostering an inclusive and welcoming learning, working, and living environment. University policy prohibits protected-class discrimination and harassment, sexual misconduct (harassment, exploitation, and assault), intimate partner violence (dating or domestic violence), stalking, and related retaliation by or against members of our community on- and off-campus. These behaviorsharm individuals and our community. The Office of Institutional Equity and Compliance (OIEC) addresses these concerns, andindividuals who believe they have been subjected to misconduct can contact OIEC at 303-492-2127 or email cureport@colorado.edu. Information about university policies, reporting options, and support resources can be found on the .

Please know that faculty and graduate instructors have a responsibility to inform OIEC when they are made aware of incidents related to these policies regardless of when or where something occurred. This is to ensure that individuals impacted receive an outreach from OIEC about their options for addressing a concern and the support resources available. To learn more about reporting and support resources for a variety of issues, visit Don’t Ignore It.

Religious Holidays

Campus policy regarding religious observances requires that faculty make every effort to deal reasonably and fairly with all students who, because of religious obligations, have conflicts with scheduled exams, assignments or required attendance. In this class, you need to email the instructor ( ashutosh.trivedi@colorado.edu) at least one week in advanceand discuss an appropriate accommodation plan.

See the for full details.

Mental Health and Wellness

The 91PORN is committed to the well-being of all students. If you are struggling with personal stressors, mental health or substance use concerns that are impacting academic or daily life, please contact Counseling and PsychiatricServices (CAPS) located in C4C or call (303) 492-2277, 24/7.

Free and unlimited telehealth is also available through Academic Live Care. The Academic Live Care site also provides information about additional wellness services on campus that are available to students.

Netiquette

All students should be aware that their behavior impacts other people, even online. I hope that we will all strive to develop a positive and supportive environment and will be courteous to fellow students and your instructor. Due to the nature of the online environment, there are some things to remember.

  1. Always think before you write. In other words, without the use of non verbals with your message, your message can be misinterpreted. So please think twice before you hit submit.
  2. Keep it relevant. There are places to chat and post for fun everyday stuff. Do not stray from the discussion in the assigned questions.
  3. Never use all caps. This is the equivalent of yelling in the online world. It is not fun to read. Only use capital letters when appropriate.
  4. Make sure that you are using appropriate grammar and structure. In other words, I don’t want to see anyone writing “R U” instead of “are you”. There are people in the class that may not understand this type of abbreviation, not to mention it does nothing to help expand your writing and vocabulary skills. Emoticons are fine as long as they are appropriate. A smile ☺ is welcome, anything offensive is not.
  5. Treat people the same as you would face-to-face. In other words, it is easy to hide behind the computer. In some cases, itempowers people to treat others in ways they would not in person. Remember there is a person behind the name on your screen. Treat all with dignity and respect and you can expect that in return.
  6. Respect the time of others. This class is going to require you to work in groups. Learn to respect the time of others in your groupand your experience will be much better. Always remember that you are not the only person with a busy schedule, be flexible. Donot procrastinate! You may be one that works best with the pressures of the deadline looming on you, but others may not be thatway. The same is true for the reverse. The key to a successful group is organization, communication and a willingness to do what it takes to get it done.