Welcome to CS321, where we learn about:
- the limits of computation: what computers can and cannot do
- what makes certain problems impossible for computers to solve
- how to communicate formally and precisely about abstract computation and algorithmic processes
- Meeting: Mon/Wed/Fri 9:00-9:50am, FURM (Furman Hall) 102
- Instructor: Jiayu Xu, xujiay@oregonstate.edu, KEC (Kelley Engineering Center) 3049
- office hours: Wed 1:00-2:00pm
- TA: David Richardson, richdavi@oregonstate.edu, KEC main lobby
- office hours: Tue 1:00-2:00pm
- TA: William Solow, soloww@oregonstate.edu, KEC main lobby
- office hours: Thu 1:00-2:00pm
None, reference book: https://sarielhp.org/teach/notes/373/book.pdf Links to an external site. (contains much more materials than what we will cover)
60% (there will be 5 of them, and lowest score will be dropped, so each homework assignment is 15%)
40% (no mid-term exam)
Final exam will be on 12/12 at 6:00pm; see https://registrar.oregonstate.edu/final-examination-schedule
Everything you write for this course must reflect your personal understanding of the material. Submissions from different students should never look similar. Use of generative AI tools such as ChatGPT is allowed, provided that you understand everything in your homework submission.
Accommodations for students with disabilities are determined and approved by Disability Access Services (DAS). If you, as a student, believe you are eligible for accommodations but have not obtained approval please contact DAS immediately at 541-737-4098 or at http://ds.oregonstate.edu. DAS notifies students and faculty members of approved academic accommodations and coordinates implementation of those accommodations. While not required, students and faculty members are encouraged to discuss details of the implementation of individual accommodations.
Classes begin on 09/27 and ends on 12/08 (see https://registrar.oregonstate.edu/osu-academic-calendar); no class on 11/10 and 11/24 (see https://registrar.oregonstate.edu/simple-tab/holidays-closures-0). As such, there will be 30 lectures in total. I only listed the schedule for 29 lectures below (starting from 0th); this will allow us to go slower than expected, or cancel a class, or cover some more advanced materials.
Lecture slides will be posted (in .pptx form) on "Files" page before or shortly after corresponding lectures.
- 0th lecture (Wed 09/27): course introduction
- 1st lecture (Fri 09/29): strings & deterministic finite automata
- 2nd lecture (Mon 10/02): how to construct DFAs
- 3rd lecture (Wed 10/04): extended transition functions
- 4th lecture (Fri 10/06): DFA closure properties
- 5th lecture (Mon 10/09): nondeterministic finite automata
- 6th lecture (Wed 10/11): NFA-DFA equivalence
- 7th lecture (Fri 10/13): epsilon transitions, more NFA closure properties
- 8th lecture (Mon 10/16): regular expressions
- 9th lecture (Wed 10/18): more regex practice
- 10th lecture (Fri 10/20): NFA-regex equivalence
- 11th lecture (Mon 10/23): non-regular languages
- 12th lecture (Wed 10/25): pumping lemma
- 13th lecture (Fri 10/27): more pumping lemma examples
- 14th lecture (Mon 10/30): minimizing DFAs
- 15th lecture (Wed 11/01): review (of materials covered so far)
- 16th lecture (Fri 11/03): context-free grammars
- 17th lecture (Mon 11/06): more CFG practice
- 18th lecture (Wed 11/08): pushdown automata
- No class on Fri 11/10
- 19th lecture (Mon 11/13): converting CFG to PDA
- 20th lecture (Wed 11/15): converting PDA to CFG
- 21st lecture (Fri 11/17): pumping lemma for CFLs
- 22nd lecture (Mon 11/20): more pumping lemma examples
- 23rd lecture (Wed 11/22): Turing machines
- No class on Fri 11/24
- 24th lecture (Mon 11/27): more Turing machine examples
- 25th lecture (Wed 11/29): universality & Turing machine variants
- 26th lecture (Fri 12/01): undecidability, Berry paradox, Kolmogorov complexity
- 27th lecture (Mon 12/04): review
- 28th lecture (Wed 12/06): practice problems for final exam
