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, 2017. 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/27–1/31 | Mathematics Preliminaries, Basic Concepts | |
| 2 | 2/3–2/7 | Finite Automata, DFA, NFA, Regular Languages | 2/7: Add/Drop deadline |
| 3 | 2/10–2/14 | Equivalence of DFA and NFA | |
| 4 | 2/17–2/21 | Equivalence of DFA and NFA | |
| 5 | 2/24–2/28 | Pumping Lemma | |
| 6 | 3/3–3/7 | Context-Free Grammars | |
| 7 | 3/10–3/14 | Pushdown Automata | |
| 8 | 3/17–3/21 | Spring Break | |
| 9 | 3/24–3/28 | Properties and Pumping Lemma | 3/28: Mid-term grades due |
| 10 | 3/31–4/4 | Turing machines | |
| 11 | 4/7–4/11 | Decidability , countable sets | |
| 12 | 4/14–4/18 | Enumerability, decidable and enumerable languages | |
| 13 | 4/21–4/25 | Complexity classes | 4/21: Last day to withdraw |
| 14 | 4/28–5/2 | NP | |
| 15 | 5/5–5/9 | Reductions, completeness | 5/9: Last day of class |
Important Dates:
- Normal Add/Drop deadline: February 7
- Spring break: March 17-21
- Midterm grades due: March 28
- Last day to Withdraw (WD): April 21
- Classes end: May 9
- Reading Days: May 10-11
- Final Exams: May 12-19
Grading
Evaluation methods:
The course grade will be computed as a weighted average of different components listed below:
| Participation | Homework and Quizzes | Exams |
| 10% | 40% | 50% |
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. However, you must give credit to AI tools whenever used, even if only to generate ideas rather than usable text or illustrations. You MUST write up the solutions in your own words.
Any violation of these principles may result in a failing grade in this course.
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.
COVID-19 Health Concerns:
If you suspect you have COVID-19 and are seeking a Dean’s Excuse, please follow these steps:
- Students learning remotely/from home: Please obtain documentation from a medical provider at home regarding your diagnosis and submit to Bailey Health Center. After review, and if symptoms are significant enough to interfere with remote learning/engagement with classes, Bailey Health Center will submit a Dean’s Excuse confirmation to the Office of Advising, who will process the Dean’s Excuse.
- Students learning on campus: First contact Bailey Health Center for consultation and COVID-19 testing. If a positive test result is received, the student must follow the College’s protocols for clearance. If symptoms are significant enough to interfere with remote learning/engagement with classes, Bailey Health Center will submit a Dean’s Excuse confirmation to the Office of Advising, who will process the Dean’s Excuse.
If through Bailey Health Center’s protocols you are not cleared to attend in-person classes for a period of time, I will be informed of this status through the Office of Advising. You must not return to class until medically cleared to do so. I will also be notified when you are cleared to return to in-person classes. Please note that Bailey Health Center or the Dean’s Office will not disclose to me your specific medical information; they will not specify to me if you have to “isolate” due to a positive COVID-19 test, or “quarantine” due to possible exposure. They will only specify if you are “not cleared” or “cleared” to attend in-person classes. Additionally, please email me so that together we can make a plan to help you keep up with the course until you are cleared to return to in-person instruction.
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.