Instructor: Daniele Micciancio
Contact information: Course Staff and Office Hours.
Syllabus and Policies: Read it! Pay special attention to academic honesty and collaboration policies.
Textbook: M. Sipser, Introduction to the Theory of Computation (any edition)
Discussion board: Piazza. This will also be used to distribute additional course material and make course announcements.
Other Tools: links to other resources we will use in this course.
There are two sections of CSE105 offered this quarter (CSE105-a and CSE105-b). The two sections are equivalent, and share the same webpage and other course resources.
Course Calendar: Reading assignments will be posted on the calendar page. You are responsible for all the reading material posted up to the current lecture, as well as the lecture notes posted below on this page.
Lectures: Monday, Wednesday, Friday
Discussions: (You are only required to attend one.)
Exams:
These are supplementary lecture notes, to be read in addition to the reading assignments posted on the course calendar. You are responsible for everything above the line. Notes and pointers below the line are posted in case you want to read ahead.
Lecture Notes 1: Notes on using the haskell programming language. For a good tutorial introduction to haskell, see “Learn you a Haskell for Great Good!”.
Lecture Notes 2: Mathematical definition of Deterministic Finite Automata, evaluation function, configurations, etc.
Lecture Notes 3: Defining DFAs and the functions they compute in haskell.
Lecture Notes 4: DFAs with parametric state type, closure properties of Regular languages, and reading/writing JFLAP files in haskell.
Lecture Notes 5: Mathematical definition of Non-deterministic Finite Automata (NFA), configurations, etc.
Lecture Notes 6: Implementing Nondeterministic Finite Automata (NFA) and equivalence with DFAs.
Lecture Notes 7: Regular expressions, and conversion to finite automata.
Lecture Notes 8 Building a nonregular language by diagolanization.
Lecture Notes 9 Finite State Transducers: mathematical definition of FST and NFST.
Lecture Notes 10: FST in haskell.
Lecture Notes 11: Configurations and Computations in haskell.
Lecture Notes 12: FST-reductions and map-reductions
homework 1 is out. Due on Thursday October 8, 10pm. Starter files can be found here
homework 2 is out. Due on Monday October 19, 10am. Starter files can be found here
homework 3 is out. Due on Friday October 30, 10pm. Starter files can be found here. As usual you will also need all the files from the automata library
homework 4 is out. Due on Wednesday November 11, 11:59pm. Starter files can be found here. Remember to download the latest copy of the automata library files.
homework 5 is out. Due Saturday November 21, 11:59pm. Starter files can be found here. Make sure you get new CTS.hs file from automata library.
homework 6 is out. Due Thursday December 3, 11:59pm. Submit on gradescope following the instructions on the assignment.