Topics covered: Formal languages; finite automata and regular expressions; properties of regular languages; pushdown automata and context-free grammars; properties of context-free languages; introduction to computability and unsolvability (Turing machines) and computational complexity. The course will be divided into three phases:
First phase (roughly 3 weeks): Formal languages; finite automata and regular expressions; properties of regular languages; pumping lemma for regular languages.
Second phase (roughly 2 weeks): Pushdown automata and context-free grammars; properties of context-free languages; pumping lemma for context-free languages.
Third phase (roughly 4 weeks): Introduction to computability (Turing machines); unsolvability; computational complexity.
Pre-requisites. CS 40 with a grade C or better.
Text Book. Introduction to the Theory of Computation by Michael Sipser. Second or third edition is fine. It's available on Amazon.
Lecture hours: MW 12:30pm to 1:45pm
Lecture hall: ILP 2101
Instructor: Prabhanjan Ananth
Instructor's office hours: MW 2pm to 2:30pm, HFH 1119
Digital communication with the instructor: via Slack only.
TA office hours:
Divyanshu Bharadwaj: Tuesdays, 1-2pm (TA trailer)
Zach Miller: Wednesdays, 11am-12pm (TA trailer)
Peter Boyland: Thursdays, 1pm-3pm (TA trailer)
Jinghan Zhang: Mondays, 3:45pm-4:45pm (TA trailer)
ULA office hours:
Rohil Shah: Fridays, 2-4pm (Virtual; link is here)
Michael Cheng: Mondays and Wednesdays, 5-6pm (Outside "The Arbor")
Discussion Sections: Fridays 9-9:50am, 10-10:50am, 11-11:50am, 12-12:50pm.
First day of discussion sections: October 4th
Sections from the Introduction to the Theory of Computation (third edition) are posted below.
September:
30th: Introduction to the course, administrivia, discrete math basics. (Section 0.2)
October:
2nd: Introduction to finite automata (Section 1.1)
7th: Non-deterministic finite automata (Sections 1.1, 1.2)
9th: Equivalence of NFAs and DFAs (Section 1.2)
14th: Closure Properties (Section 1.2)
16th: Regular Expressions (Section 1.3)
21st (guest lecture by Zach Miller): Pumping lemma for regular languages (Section 1.4)
23rd (guest lecture by Zach Miller): Context-free grammars (Section 2.1)
28th: Midterm: everything until 21st will be included.
30th: Pushdown automata (Section 2.2)
November:
4th: Equivalence of pushdown automata and context-free grammars (Section 2.2)
6th: Pumping lemma for context-free languages (Section 2.3)
11th: No lecture (Veterans day)
13th: Turing machines: formal definition (Section 3.1)
18th: Turing machines: examples (Section 3.1)
20th: More examples, Multi-tape Turing machines, Non-deterministic Turing machines, Enumerators (Section 3.2)
25th: Cantor's diagonalization method (Section 4.2)
27th: Unrecognizable and undecidable languages (Section 4.2)
December:
2nd (guest lecture by Peter Boyland): Unrecognizable and undecidable languages - cont'd, reductions (Section 5.1)
4th (guest lecture by Peter Boyland): Unrecognizable and undecidable languages - cont'd, reductions (Section 5.1)
1st Assignment:
Release date: 2nd October (1st week)
Due date: 9th October (2nd week)
Graded assignments released: end of 3rd week
2nd Assignment:
Release date: 16th October (3rd week)
Due date: 23rd October (4th week)
Graded assignments released: end of 5th week
3rd Assignment:
Release date: 30th October (5th week)
Due date: 6th November (6th week)
Graded assignments released: end of 7th week
4th Assignment:
Release date: 13th November (7th week)
Due date: 20th November (8th week)
Graded assignments released: end of 9th week
5th Assignment:
Release date: 27th November (9th week)
Due date: 4th December (10th week)
Graded assignments released: end of 10th week
Midterm: 28th October (Monday) during lecture hours.
Graded midterms released: end of 6th week
Finals: 10th December, 12pm to 3pm. It will be held in ILP 2101.
Grading instructions:
Assignments contribute towards 40% of the grade
Midterm contributes towards 30% of the grade
Finals contribute towards 30% of the grade
Grading will be curved.
Assignment instructions:
Assignment submissions need to be made on Gradescope. The gradescope code is: BK863D.
The assignment schedule has been announced well in advance. Please mark the schedule in your calendar accordingly. No assignment extensions will be allowed.
No collaboration allowed on assignments. Discussing the solutions of the assignment with your fellow classmates before the due date is strictly prohibited. Please read the UCSB policy here.
Consulting the internet for solutions (including posting questions on Chegg) is strictly prohibited. In particular, the use of Artificial Intelligence tools (including LLMs such as ChatGPT) is strictly prohibited.
Top 4 out of 5 assignments will be considered. If for any reason, you think you will not be able to do 2 or more assignments then I suggest you not take the course this time.
Any medical reason for not being able to complete the assignments should be accompanied by a doctor's note. Read more about absence and withdrawal from a course here.
Exam instructions:
Please bring pens, pencils to the exam. We will provide solution booklets for you.
Discussing with your classmates during the exam time is strictly prohibited.
Please be on time. Please read the UCSB policy here.
Other instrutctions:
All announcements will be made on Slack. If you have enrolled in the course, the Slack link to join the course workspace will be sent to you via email.
If your grades are poor in the assignments or the exames then I suggest you re-do the assignment and submit it to the TAs by the end of 10th week. This doesn't necessarily improve the grade but could ensure that you won't fail in the course.