Instructor: Daniele Micciancio
TAs: Justin Lazarow, Shreya Saha, Mark Schultz, Nirmal Thomas, (Rishabh Ranjan)
Tutor: Dennis Luc
Syllabus and Policies: Read the course Syllabus for course description, textbook, prerequisites and objectives, detailed information about assignments, exams, grading, and other course policies. Pay special attention to academic honesty and collaboration policies.
Canvas: https://canvas.ucsd.edu/courses/29516. If you are enrolled in this class, you should have access to it through Canvas. We will use Canvas to distribute homework assignments, solutions, lecture notes (slides), and any additional course material. Enrollment in Piazza and Gradescope is automatically handled by Canvas.
Discussion board: Piazza. This will be the main platform to answer student questions and post course announcements. Enrollment/access to piazza is handled automatically by Canvas. Please check that you can access the discussion board, and enable email notifications.
Homework submission and Grades: We will use Gradescope for homework submission and grading. Each homework should be done in groups of one to three people, see syllabus for details. Enrollment/access to gradescope is handled automatically by Canvas.
Other tools: See below for active learning/attendance (iClickers) machine visualization (JFLAP/flap.js) and homework typesetting (LaTeX/Overleaf)
Contact Information: For general/technical questions that may be of interest to other students, please use the Piazza discussion board. If you are not sure if your question should be publicly posted, or want only the instructors/TAs to read it, you can still use piazza and mark it as private. For in-person questions/help about homework assignments, you should attend discussion and office hours of any of the course staff. Office hours and other events are posted on the canvas calendar.
Lectures: Tu,Th 9:30p-10:50p (GA AUD)
Podcast recordings of the lectures will be available (shortly after class, typically within a day) at https://podcast.ucsd.edu/watch/fa21/cse105_a00 for review, or for making up for occasionally missing a lecture.
Discussions: Th 7:00p-7:50p (GH 242)
An alternative (online, via zoom) discussion session has been scheduled Th 6:00p-6:50p, and posted on the canvas calendar. (See canvas calendar for the zoom link.) The two discussions cover the same material, and you should attend only one. Only the online discussion is recorded.
Important dates:
Here is a weekly schedule of topics covered in class, exams and homework due dates. Reading assignments are tentative, and they are provided in case you want to read ahead. Chapter pointers refer to the course textbook, M. Sipser, Introduction to the Theory of Computation. (slides)
| Date | Topic | Reading | Notes |
|---|---|---|---|
| Week 0 | Intro + DFA | Ch. 0 + 1.1 | Th Sep 23 |
| Week 1 | DFA + closure | Ch. 1.1 | HW1 due (Wed Sep 29) + clicker registration deadline |
| Week 2 | NFAs, RegEx | Ch. 1.2 + 1.3 | HW2 due (Wed Oct 6) |
| Week 3 | Pumping Lemma | Ch. 1.4 | HW3 due (Wed Oct 13) |
| Week 4 | CFGs | Ch. 2.1 | Midterm 1 (Tue Oct 19) |
| Week 5 | PDAs, TM | Ch. 2 + 3.1 | HW4 due (Wed Oct 27) |
| Week 6 | TM variants | Ch. 3 + 4 | HW5 due (Wed Nov 3) |
| Week 7 | Midterm 2 (Tue Nov 9), Veterans’ day holiday (Thu Nov 11) | ||
| Week 8 | Undecidabiltiy and Reductions | Ch 5 | HW6 due (Wed Nov 17) |
| Week 9 | More Reductions | Ch 5 | Thanksgiving holiday (Thu Nov 25) |
| Week 10 | Time complexity | Ch 7 | HW7 due (Wed Dec 1) |
| Final week | Final exam (Thu Dec 9) |
You should have your clicker registered with Canvas by Wed September 29. (See course syllabus for clicker and attendance policy.) How to register your clicker in Canvas:
There are multiple tools to help you visualize and test finite state machines, the foundational computer models we are studying in this class. We will support two of these tools in CSE 105 this quarter: JFLAP and flap.js. JFLAP was developed starting in the 1990 by a team led by Susan Rodger (RPI, then Duke). It is now a mature tool with a lot of functionality. Some of the conventions and notation it uses differ from the course textbook for CSE 105. The second tool, flap.js, is a webapp under development by a group of UCSD students that is being piloted in CSE 105. It is being customized for use in this class. Let me know if you are interested in joining the development team for flap.js to help future CSE 105 students.
The homepage for the tool is at https://flapjs.github.io/FLAPJS-WebApp/; a detailed tutorial is available here. It currently has many features for designing and working with DFA and NFA. The module on PDA allows you to draw state diagrams.
The homepage for the tool is at https://www.jflap.org; the current stable version is version 7.1.
Basic installation and configuration
For those who already have Java Virtual Machine installed. NOTE: you should be able to install JFLAP on systems with JVM even if you don’t have install/Administrator rights.
If you don’t already have JVM (Java Virtual Machine) installed on your computer
You’ll need to get the JVM in order to run JFLAP. You will need install/Administrator rights to do this. To install:
Frequently asked questions about JFLAP
Regular Expressions Do not use whitespace in your regular expressions unless a space is a valid symbol in the alphabet. JFLAP uses a + symbol instead of the U used in the textbook to indicate union.
Start and Accept States Don’t forget to specify these when drawing your automata!
Multiple Transitions If you need multiple possible inputs for the same arrow in your diagram (e.g. if you can move between states on either a 0 or a 1), this is done by creating separate edges in JFLAP for each input symbol. JFLAP will combine these into one arrow on your diagram. Automata with transitions labeled with a comma (e.g. “0,1”) are not equivalent, because those transitions will not be followed unless “0,1” actually appears in your input string.
Empty String In class and in the text, we use ε (epsilon) to denote the empty string. The instructions above help you change the JFLAP default λ (lambda) to match our conventions. If you need a state transition (or a stack symbol for PDA’s) for ε, do not enter any characters into the text box for that transition and ε will appear. Entering a space does not work; that transition will be followed only if the input string has a space on it. Similarly, entering E or “epsilon” will not work because JFLAP will try to match those exact symbols in your input string for the transition.
Push Down Automata Each transition has three labels: an input symbol, a stack symbol to pop, and a stack symbol to push. JFLAP uses the semicolon (;) instead of a right arrow to separate the stack symbols. Any of the three labels can be the empty string. Settings: Your PDAs should be “Single Character Input” (this option appears when you first create an automaton), and they should accept by final state, not by empty stack.
Context Free Grammars If you have a production rule of the form “S -> A | B”, enter it as two rules “S -> A” and “S -> B”. Typesetting (LaTeX) Resources
All submitted homework for this class must be typed. Diagrams may be hand-drawn and scanned and included in the typed document. You can use a word processing editor if you like (Microsoft Word, Open Office, Notepad, Vim, Google Docs, etc.) but you might find it useful to take this opportunity to learn the LaTex document preparation system. LaTeX is a markup language used widely in computer science and mathematics. The homework assignments are typed using LaTeX and you can use the source files as templates for typesetting your solutions.
If you have never used LaTeX, we recommend cloud resources (e.g. Overleaf) that don’t require you to download and install LaTeX on your local machine. In particular, Overleaf has great collaboration functionality if you choose to work with a group.
An open source LaTeX reference is here, and you can Google for many templates and examples to get you started.