- Course URL: http://prof.msoltys.com/?page_id=6906
- Canvas Page: https://cilearn.csuci.edu/courses/27302
- Course Material
- CI Catalogue URL
- Instructor: Michael Soltys <michael.soltys@csuci.edu>
- Course Outline: This course is an introduction to the theory of computation, from the point of view of languages over finite alphabets. We are going to start with Regular Languages, and the equivalence of several definitions: Finite Automata (deterministic and non-deterministic) and Regular Expressions (and applications to text search). The Pumping Lemma, and other approaches to showing that languages are not regular. We will continue with Context-free languages, and again the equivalence of several definitions: Context-free grammars and Push-Down Automata. We will finish with a version of the Pumping Lemma for Context-free languages. The final topic will be the Church-Turing thesis, and decidability.
- Lectures: W 7:00-8:00 online
- Textbook: Introduction to the Analysis of Algorithms (Chapter 8), by Michael Soltys
- Grading: 10 quizzes (best 8 selected), worth 5% each, and 4 assignments, worth 5% each, and two midterms, worth 10% each and a final exam worth 20%.
- Missing or late work policy: Assignments are worth 5 points, and late assignments will have one (1) point deducted for each day they are late (up to five points). Regarding missing quizzes: since best 8 out of 10 quizzes are used for final grade, up to two quizzes can be missed. If more quizzes are missed, or a midterm or final exam is missed, this will be dealt with on a case by case basis, requiring a letter from the students explaining the situation. Please note that in the industry, work has to both meet requirements and be delivered on time.
- How to avoid plagiarism: Verbal discussions of problems among students are allowed, but you should not show written notes, and you should not leave such discussions with written notes.
- Attendance: Students are encouraged but not required to attend the lectures. All quizzes, midterms and the final will be written online.
- Some useful links:
- DFA designer: https://www.madebyevan.com/fsm/
Course outline
| Jan 24 | Course Introduction | 8.1 8.2 | |
| Jan 31 | DFA | 8.3.1 | |
| Feb 7 | NFA | 8.3.2 | Quiz 1 |
| Feb 14 | Regular Expressions | 8.3.3 | Quiz 2 |
| Feb 21 | Properties of Regular Languages | 8.3.4-5 | Quiz 3 Assignment 1 |
| Feb 28 | CFG | 8.4.1 | Quiz 4 |
| Mar 6 | PDA | 8.4.2 | Quiz 5 |
| Mar 13 | Midterm 1 Assignment 2 | ||
| March Break | |||
| Mar 27 | CFG and PDA | 8.4.2 | Quiz 6 |
| Apr 3 | Turing Machines | 8.5.1 | Quiz 7 Assignment 3 |
| Apr 10 | Midterm 2 | ||
| Apr 17 | Encodings and Decidable Languages | 8.5.2 8.5.3 | Quiz 8 |
| Apr 24 | Church-Turing Thesis | 8.5.4 | Quiz 9 |
| May 1 | Undecidable Languages | 8.5.5 | Quiz 10 |
| May 8 | Final Exam | ||
Students with disabilities: Cal State Channel Islands is committed to equal educational opportunities for qualified students with disabilities in compliance with Section 504 of the Federal Rehabilitation Act of 1973 and the Americans with Disabilities Act (ADA) of 1990. The mission of Disability Accommodation Services is to assist students with disabilities to realize their academic and personal potential. Students with physical, learning, or other disabilities are encouraged to contact the Disability Accommodation Services office at (805) 437-8510 for personal assistance and accommodations. Please discuss your arrangements with the instructor as soon as possible.