In this course, we will explore what it means to be "computable". We begin with a very simple model of computation, and work our way to the most powerful, the Turing machine, named after Alan Turing, who formalized the notion of "algorithm" even before there were any physical computers. You'll also learn about the relationship of these models to some essential tools in a computer scientist's toolkit, such as regular expressions and context-free grammars. Finally, you'll develop your technical communication skills in writing formal arguments and proofs.
Use our Calendar to get links to class times and notes. Submit your work for this class on Gradescope. Reach out to me (minnes@eng.ucsd.edu) or one of the other CSE 105 team members if you have questions. This term we will be using Piazza for class discussion; find our class page on Piazza; one thing Piazza is particularly good for is finding homework group mates. Some of the homework in this class will be group-work optional; students in previous versions of the class often found group conversations helped them learn the material more deeply, and were fun. Choosing to engage in groupwork is also supported by current work in CS Education Research: https://dl.acm.org/doi/10.1145/3478431.3499286.
Here are our plans for CSE 105 this quarter, keeping in mind we may need to be flexible in response to campus and public health guidance.
We encourage you to work on homework in groups of up to three CSE 105 classmates. To find group members: reach out to people sitting around you in class, in discussion section, or during office hours. The pre-survey also asks if you want help finding group members: the CSE 105 instructional team can help you connect with other students. Working within the campus safety guidelines, you may choose to meet with your group mates in person (find ideas for where to study on campus), or online. If you're working with one another remotely, we highly recommend meeting synchronously so that you can work through the homework problems *together*. Your @ucsd.edu account gives you access to Zoom, login at https://ucsd.zoom.us/ to schedule a meeting. Pro tip: if you change the meeting URL from https://ucsd.zoom.us/j/MEETING-ID to https://ucsd.zoom/us/wc/join/MEETING-ID, it will allow the user to join via the browser and not just through the app. The Zoom support page has details on hosting and joining meetings.
Lecture material is available in PDF and html formats so you can download and annotate or print it if you'd like. If you would like a hard copy of the notes and don't have access to a printer, please let me know (minnes@eng.ucsd.edu).
The required textbook for this course is Sipser, Michael Introduction to the Theory of Computation I highly recommend this book for the class - it's very well-written and we'll be using it extensively. A digital copy may be available through Cengage unlimited (linked from Canvas). For a physical copy, the Third Edition (international) of this book is available at the UCSD Bookstore for approximately 20 dollars. I also have a number of copies of the textbook available to borrow for the term if you have difficulty accessing the book. Please reach out (minnes@eng.ucsd.edu) to arrange a time to pick up a copy.
To brush up on proofs, use: Richard Hammack, Book of Proof, 2nd ed. (available for download here).
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 1990s 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're 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 www.jflap.org; the current stable version is version 7.1.
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.
You'll need to get the JVM in order to run JFLAP. You will need install/Administrator rights to do this. To install:
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".
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 LaTeX. 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 that don't require you to download and install LaTeX on your local machine. A good example is Overleaf, which has lots of documentation. Overleaf works similar to Google Docs in that all members can edit the file in parallel and changes are updated in real time. There is a way to directly invite group members to your document, but the free version of Overleaf only allows two people to work at the same time. To get around this, turn on link sharing: Click on “Share” in the top right, Click “Turn on link sharing”, Copy the displayed link and share it with your group members. To export your work, click on the “Download PDF” button on the right-hand side If you want to export the raw source files, click on the “Menu” button in the top-left, then click on “Source”
This open source LaTeX reference can be helpful when getting started, and you can use the .tex source of all the files we use in class as templates.
Alternatively, you can use Google Docs, which is available through your @ucsd.edu account. You can create documents and then share them with your group members with manual invites or a shareable link. Google Docs has a LaTex add-on that lets you type formulas in a math typesetting environment: search for "Auto-LaTeX Equations" if you want to try this option. You'll need to use the display environment (start and end with $) for all the portions you want rendered with LaTeX.
Grades in this class are designed to reflect your work and to document evidence of your learning this core material. quarter of building the foundations needed for your continued development in Computer Science. Please reach out to me (minnes@eng.ucsd.edu) if you have extenuating circumstances that you think will impede your ability to participate in the planned CSE 105 activities; I'd like to work out a solution together.
The graded components for CSE 105 will be Review quizzes, Homework, Project, and Final exam. Your overall grade for CSE 105 will be computed using the weights
The UC San Diego Academic Integrity pledge is here. Academic integrity violations will be taken seriously and reported to the campus-wide Academic Integrity Office. Key facts about academic integrity related to CSE 105:
UCSD has fantastic resources to support your learning, with integrity. Of course, the instructional team for CSE 105 is here to help you navigate the course content. The Jacobs School of Engineering IDEA Center organizes group study sessions and can connect you with student organizations. The Teaching and Learning Commons continues to offer their full suite of student success programs.
Regrades need to be requested within three days of announcement of grades. The regrade window will be set in Gradescope. In the regrade request, include a brief but detailed explanation of why you think there was an error in the grading. A regrade request may lead to us reviewing the entire assignment and may lead to the score being adjusted up or down depending on any errors found in the original grading. All regrades will be considered once the regrade window closes; thank you in advance for your patience while we carefully look through them.
We would like to work with each of you to make this course accessible and approachable. All course material is available in multiple formats to improve support for screen readers. Videos will also be captioned (to the best of our abilities). We need to hear from you if additional accommodations would improve your experience in the course. If you have documented need for accommodations because of a disability, please work with the Office for Students with Disabilities (OSD) to get a current Authorization for Accommodation (AFA) letter. The office is located in University Center 202 behind Center Hall and also provides the OSD Student Portal. We ask that you work to organize the AFA and to let us know about it as early in the quarter as possible so that we can best support your needs. For more information, see Disability Resources at UCSD.
My lectures and course materials, including videos, assignments, and similar materials, are protected by U.S. copyright law and by University policy. I am the exclusive owner of the copyright in those materials I create. You may take notes and make copies of course materials for your own use. You may also share those materials with another student who is enrolled in or auditing this course. You may not reproduce, distribute or display (post/upload) lecture notes or recordings or course materials in any other way — whether or not a fee is charged — without my express prior written consent. You also may not allow others to do so. If you do so, you may be subject to student conduct proceedings under the UC San Diego Student Code of Conduct.
Similarly, you own the copyright in your original work. If I am interested in posting your answers or papers on the course web site, I will ask for your written permission.
Individuals are not permitted to approach students to offer services of any kind in exchange for pay, including tutoring services. This is considered solicitation for business and is strictly prohibited by University policy.
You can find the learning outcomes for CSE 105 in this overview page.
