Welcome to Theory of Computation!
All course materials will be distributed on Moodle.
Instructor Information
- Instructor: Dr. Jia Tao
- Email: taoj at lafayette dot edu
- Office: 563 RISC
- Office Phone: (610) 330-3336
- Office Hours: See Moodle
Course Information
This course is a rigorous introduction to the theoretical foundations of computer science and formal models of computation. Topics will include formal languages, finite automata, computability and undecidability.
Course Goals
After successfully completing this course, the student will be able to:
- Understand the basic abstract machine types and the basic types of formal languages; understand the correspondence between the machine types and the languages.
- Understand the difference between computable and incomputable problems and tractable and intractable problems.
Course Outcomes
- ABET/CAC Outcome 1: Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions; in particular,
- be able to recognize the basic types of formal languages and the corresponding abstract machine types
- be able to distinguish computable and incomputable problems and tractable and intractable problems
Textbook
- Introduction to Theory of Computation, by Anil Maheshwari and Michiel Smid, 2024. Available online here.
Course Schedule
Students are expected to read the assigned course materials before coming to class. This will enable students to participate fully in the class discussions and exercises, and gain the maximum benefit out of the class meetings.
The schedule of topics and assignments below is tentative and will be updated as needed.
| WEEK | DATE | TOPICS | COMMENTS |
|---|---|---|---|
| 1 | 1/26–1/30 | Mathematics Preliminaries, Basic Concepts | |
| 2 | 2/2–2/6 | Finite Automata, DFA, NFA, Regular Languages | 2/6: Add/Drop deadline |
| 3 | 2/9–2/13 | Equivalence of DFA and NFA | |
| 4 | 2/16–2/20 | Equivalence of DFA and NFA | |
| 5 | 2/23–2/27 | Pumping Lemma | |
| 6 | 3/2–3/6 | Context-Free Grammars | |
| 7 | 3/9–3/13 | Pushdown Automata | |
| 8 | 3/16–3/20 | Spring Break | |
| 9 | 3/23–3/27 | Review, Exam | 3/27: Mid-term grades due |
| 10 | 3/30–4/3 | Properties and Pumping Lemma | |
| 11 | 4/6–4/10 | Turing machines | |
| 12 | 4/13–4/17 | Decidability , countable sets | |
| 13 | 4/20–4/24 | Enumerability, decidable and enumerable languages | 4/20: Last day to withdraw |
| 14 | 4/27–5/1 | Complexity classes, NP | |
| 15 | 5/4–5/8 | Reductions, completeness | 5/8: Last day of class |
Important Dates:
- Normal Add/Drop deadline: February 6
- Spring break: March 16-20
- Midterm grades due: March 27
- Last day to Withdraw (WD): April 20
- Classes end: May 8
- Reading Days: May 9-10
- Final Exams: May 11-18
Grading
Evaluation methods
The course grade will be computed as a weighted average of different components listed below:
| Attendance | Homework | Exams |
| 10% | 30% | 60% |
The success of this course is highly dependent on your involvement with the class material and classmates. As such, if no advance notice is given (i.e., 24 hours), you will be considered absent if you arrive at a class session more than 10 minutes late or not at all, and your attendance grade will be reduced proportionally. If you have a valid excuse that prevented you from providing advance notice, I will consider it on a case-by-case basis (again, open and honest communication will take you a long way in this class).
Course Policies
Submission for assignments
- All submissions should be made on the Moodle Website.
- NO LATE SUBMISSION IS ACCEPTED. Moodle assignment submission link will be closed promptly at the deadline. Submissions made after the due time (for example, via email) will not receive credit, unless the student has an allowed excuse. An allowed excuse is an approved Dean’s excuse or the instructor’s permission obtained prior to the fact. If you cannot finish the project before the deadline, please make sure to submit what you have before the deadline.
Electronic Devices in the Classroom
You should use your computer for learning only. No other use of electronic devices is permitted during class time, including listening to music, watching a movie, emailing, surfing the Internet, texting, tweeting, Facebook surfing, etc. There will be grade or other penalties for violations of this policy.
Intellectual Honesty
The college has strict guidelines on intellectual honesty. Please read the policy here. All students are expected to adhere to the college policy on academic honesty as listed in the Student Handbook. Discussion of concepts with others is encouraged, but all assignments must be done by yourself or your own team as specified in each assignment requirements. For the homework assignments, you are allowed to use generative AI tools such as ChatGPT for learning purposes, provided that this use is fully and properly documented in the comments. Your documentation must include the prompt(s) you used and the significant parts of the AI response. However, you must give credit to AI tools whenever used, even if only to generate ideas rather than usable text or illustrations.
The use of AI resources can support your learning by helping you explore the field, understand the kinds of contributions AI can make, and experiment with ideas. However, the following principles[1] must always be respected:
(1) An AI cannot pass this course.
Assessment is based on your understanding, reasoning, and ability to explain your work.
(2) AI contributions must be attributed and truthful.
Any use of AI must be accurately disclosed. Misrepresentation violates academic integrity.
(3) AI use must be open and documented.
Undisclosed or opaque use of AI tools is not permitted.
You can use AI tools to support your studying. Openness is required. A portion of your grade will assess the quality and completeness of your documentation of AI use throughout the course. By keeping track of how AI tools are used and reflecting on their impact, we collectively gain insight into the limitations, risks, and effective uses of these rapidly evolving technologies.
All exams and quizzes are closed book.
The use of AI tools is not permitted during exams or quizzes.
Any violation of these principles may result in a failing grade in this course.
[1] Boris Steipe (2023) “Syllabus Resources”. The Sentient Syllabus Project http://sentientsyllabus.org .
Learning needs and accessibility
Lafayette is committed to providing support and reasonable accommodations for students with disabilities who self-identify with Accessibility Services. Students requesting accommodations to alleviate the impact of their disability should register their needs as soon as possible with the Accessibility Services Office, which is housed in the Academic Resource Hub (resourcehub@lafayette.edu). Once registered, students should request their accommodation letters to provide notification of their needs to their professors, on a semester by semester basis. If you have questions or concerns pertaining specifically to your accommodations within this course, please contact the instructor [me] to discuss them.
Special Statement regarding Accessibility and COVID 19
Eligibility for, and provision of accommodations may be influenced by the changes to the academic environment that are necessitated by the COVID-19 pandemic. If you are in need of accommodations, or adjustments to your accommodation plan, it is your responsibility to contact Accessibility Services immediately to discuss your needs.
Counseling Services
Faculty recognize the important role that health and well-being have in your academic success. While stress is a normal and expected part of the college experience, many students face personal and environmental challenges that may interfere with their academic progress and overall well-being. Please reach out to me, your academic advisor or class dean about any difficulty you may be having in this course or others as soon as it occurs. In addition, please know that there are many resources at Lafayette to provide assistance and support during difficult times.
Counseling Center: Free, confidential counseling services as well as after-hours and weekend crisis support | 2nd Floor, Bailey Health Center | 610-330-5005
Academic Resource Hub: Peer tutoring, supplemental instruction, study skills, academic counseling, and accessibility services | 3rd Floor, Scott Hall | 610-330-5098
Respect for classmates, colleagues and team members
All students are expected to show respect and courtesy to each other. Mutual respect is a high ideal in academic, business, and personal life. It is central to learning well together. Disagreements over ideas or constructive criticism of someone’s work is in keeping with this ideal. Attacking or disparaging someone is not, and will not be tolerated. In group projects, mutual respect also includes reliably contributing to the project and keeping your commitments to the group.
We follow the College Diversity Statement which says in part:
All members of the College community share a responsibility for creating, maintaining, and developing a learning environment in which difference is valued, equity is sought, and inclusiveness is practiced.
Privacy
Moodle contains student information that is protected by the Family Educational Right to Privacy Act (FERPA). Disclosure to unauthorized parties violates federal privacy laws. Courses using Moodle will make student information visible to other students in this class. Please remember that this information is protected by these federal privacy laws and must not be shared with anyone outside the class. Questions can be referred to the Registrar’s Office.
Equal Access
In compliance with Lafayette College policy and equal access laws, I am available to discuss appropriate academic accommodations that you may require as a student with a disability. Requests for academic accommodations need to be made during the first two weeks of the semester, except for unusual circumstances, so arrangements can be made. Students must register with the Office of the Dean of the College for disability verification and for determination of reasonable academic accommodations.
Federal credit hour statement
The student work in this course is in full compliance with the federal definition of a four [two or one as appropriate for half and quarter unit courses] credit hour course. Please see the Registrars Office Website (http://registrar.lafayette.edu/additional-resources/cep-course-proposal/) for the full policy and practice statement.