Theory of Computation
Is there a problem that NO computer can ever solve?
What resources are needed to solve a problem?
Are some problems harder than others?
In this course, we will explore what it means to be "computable". We begin with a very constrained model of computation, and work our way to the most powerful, the Turing machine. We'll see how remarkable this model is in terms of how much it captures about the capabilities of computation, even though it appears far removed from implementation. Alan Turing formalized the notion of "algorithm" using this model 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 reductions. Finally, you'll develop your technical communication skills in writing formal arguments and proofs.
- Pre-class survey
- Please fill out the pre-class survey that was sent to your @ucsd.edu email so that we can learn about your preferences and needs for this quarter; you can also find a link to this survey on our Canvas page as the #FinAid assignment for this quarter.
- Notes and resources
- Use our Calendar to get links to class times and notes. Lecture material is available in PDF, tex, and html formats so you can download and annotate or print it if you'd like. In class, we'll explore concepts and work through examples. There will often be some pre-class reading (listed on the notes PDF) to help you prepare for class. You may attend whichever lecture suits your schedule, so long as there is space in the room. Lecture recordings are available through the UCSD podcast system and linked from the Calendar page.
- Ask for help
- Reach out to the CSE 105 team if you have questions. This term we will be using Piazza for class discussion; sign up to our class discussion on Piazza. Drop-in (in person and Zoom) Q&A times are listed on the office hours page. You can also reach out to your instructor directly by email: email@example.com or firstname.lastname@example.org . To address us, please use Prof. Minnes, Dr. Minnes, and/or Mia (with pronouns she/her), or Prof. Grier, Dr. Grier, and/or Daniel (with pronouns he/him), as you feel comfortable. Please do not use the title Ms./ Mrs. or Mr. for either of us.
- Learn by doing
- Review quizzes based on class material are assigned each day. These quizzes will help you track and confirm your understanding of the concepts and examples we work in class. Quizzes can be submitted on Gradescope as many times (with no penalty) as you like until the quiz deadline: the three quizzes each week are all due on Friday (with no penalty late submission open until Sunday). Your primary out-of-class work for this class will be weekly homework assignments and a project. There will also be an in-class midterm and a final (at the scheduled time). In each of these assessments you will practice using precise tools to represent and solve technical problems and to communicate your solutions and get feedback on your work.
- The weekly 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 (and also an evidence-based practice for learning). To find group members: reach out to people sitting around you in class, in discussion section, or during office hours; you can also use the "find teammate" tool on Piazza. Students enrolled in different lecture sections may choose to work together in groups. The pre-survey also asks if you want help finding group members: the CSE 105 instructional team can help you connect with other students. We highly recommend meeting synchronously so that your group can work through the homework problems *together* ( in person or online). Note that the project assignment will be completed individually.
Textbook and lecture resources
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 your instructor know (email@example.com or firstname.lastname@example.org).
The required textbook for this course is Sipser, Michael Introduction to the Theory of Computation . We highly recommend this book for the class - it's very well-written and we'll be using it extensively. For a physical copy, the Third Edition (international) of this book is available through multiple vendors; we've seen it listed online for under 30 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 (email@example.com) 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).
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.). 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 assignment prompts are typed using LaTeX and you can use the source files as templates for typesetting your solutions (click the "LaTeX" button at the top of each assignment on the Assignments page to download the source files).
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. If your group has 3 people, you can 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.
We will support two tools in CSE 105 this quarter that help visualize some of the state machines we'll be studying: 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, install JFLAP by (1) Download the JFLAP.jar file from Duke University. (2) Double-click it to run JFLAP. If it doesn't launch, that probably means you don't have JVM installed. See instructions below. (3) Go to Preferences, then select "Set the Empty String Character" and change it from "Lambda" to "Epsilon." This will make JFLAP match the notation we use in the book and in class for the empty string character.
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: (1) Go here for the latest version of Java, (2) download JDK 8 for your personal machine and install it (you may need to reboot), (3) follow the "Basic Install and Configuration" instructions above to install and configure 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 textbook, 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"
Grading and academic integrity
Grades in this class are designed to reflect your work and to document evidence of your learning this core material. Please reach out to your instructor (firstname.lastname@example.org or email@example.com) if you face 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, Midterm, and Final exam. Your overall grade for CSE 105 will be computed using the weights
- Review quizzes:
8% of overall score. You will need to achieve a passing grade
(70%) with integrity on the
review quiz component of this class to pass this course.
Why? To help you track and confirm your understanding of the concepts and examples we work in class and give you immediate feedback.
How? Quizzes can be submitted as many times (with no penalty) as you like until the quiz deadline: the three quizzes each week are all due on Friday (with late submission open until Sunday; no penalty for late submission of quizzes). The lowest three quiz scores will not be included in your overall review quiz average. You can collaborate with other CSE 105 students on review quizzes and you can ask questions about them in public posts on Piazza and in drop-in help hours.
- Homework: 36% of overall score.
You will need to achieve a passing grade
(70%) with integrity on the homework
component of this class to pass this course.
Why? To give you practice with the main concepts and techniques of the course, while getting to know and learn from your classmates.
How? Weekly homework may be done individually or in groups of up to 3 students. You may switch HW partners for different HW assignments. Your HW partners may be from either lecture section for the class. The lowest HW score will not be included in your overall HW average. Please ensure your name(s) and PID(s) are clearly visible on the first page of your homework submission and then upload the PDF to Gradescope. If working in a group, submit only one submission per group: one partner uploads the submission through their Gradescope account and then adds the other group member(s) to the Gradescope submission by selecting their name(s) in the "Add Group Members" dialog box. You will need to re-add your group member(s) every time you resubmit a new version of your assignment. Each homework question will be graded either for correctness (including clear and precise explanations and justifications of all answers) or fair effort completeness. You may only collaborate on HW with CSE 105 students in your group; if your group has questions about a HW problem, you may ask in drop-in help hours or post a private post (visible only to the Instructors) on Piazza.
- Project: 12% of overall score.
Why? To go deeper and extend your work on assignments and to explore an application of your choosing.
How? During emergency remote instruction in the last few years, we discovered that video assessment and some open-ended personalized projects help ensure fairness and can be less stressful for students than in-person midterm exams. Projects give you another opportunity to work through class material and demonstrate your understanding.
- Midterm: 16% of overall score.
Why? To review the first half of the course and solidify your understanding of CSE 105's foundational material.
How? The midterm exam will be during scheduled lecture time (see date on class calendar). You will need to attend the class for which you are enrolled.
- Final: 28% of overall score.
You will need to achieve a passing grade with integrity on the final
component of this class to pass this course.
Why? To review the entire quarter and solidify your understanding of CSE 105's foundational material.
How? Cumulative test on class content at the scheduled final exam slot for this class during exam week. The exam must reflect your own independent effort. The exam may have a combination of True/False, multiple choice, select-all-that-apply, and free-response questions. The parts of the final exam corresponding to the content covered on the midterm may replace the midterm exam score.
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:
- Use only resources explicitly allowed for each assignment. Resources not affiliated with this quarter's version of the class may use inconsistent notation or definitions. If you need help, please reach out to the instructor, TAs, and tutors.
- Do not share written solutions or partial solutions for homework with other students in the class who are not in your group. Doing so would dilute their learning experience and detract from their success in the class.
- Before and during taking any individual assessment, do not attempt to obtain information about the contents of the exam from students who have already taken it or from any nonauthorized source.
- You may not ask for help from anyone while taking individual assessments since they are intended to reflect your own mastery of the material. In particular, you may not collaborate on exam questions with other students in the class and you may not post any portion of the exam on forums where others may assist you.
- After taking an exam or quiz, do not discuss its contents with anyone in the class who has not yet taken it. Do not post information about it or share information about it with others who haven't taken it.
UC San Diego 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, including learning strategies coaching.
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.
Accommodations for students with disabilities
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 and want 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.
Class material and intellectual property
Our lectures and course materials, including videos, assignments, and similar materials, are protected by U.S. copyright law and by University policy. We are the exclusive owner of the copyright in those materials we 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 our 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.