CSE105W24 ×  Calendar Assignments Glossary Supplemental Videos Office Hours Week 1Week 2Week 3Week 4Week 5Week 6Week 7Week 8Week 9Week 10Finals week

Theory of Computation

CSE105W24

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. Remarkably, it is still relevant today and is equivalent to super computers and quantum computers!

We'll also explore the relationship of these models to some essential tools in a computer scientist's toolkit, such as regular expressions and reductions. Throughout the course, you'll develop your technical communication skills in writing formal arguments and proofs.

Syllabus

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. The reading is often just a few lines of text or an example in the book and will be very helpful so we can jump into problem solving in class. You can also watch the posted supplementary videos listed with each week.
Learn by doing
After each class, you'll work on review quizzes to track and confirm your understanding of the concepts and examples we covered 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). Open-ended (group-optional) homework assignments will stretch your understanding and will ask you to put together complete, coherent, convincing explanations. There will also be a project and two (in person, synchronous) tests. In each of these assessments you will practice using precise tools to represent and solve technical problems and to communicate your solutions, and you will get feedback on your work.
Collaborate
In-class, in office hours, and on the online discussion board, we encourage you to discuss the course concepts and examples. Review quiz questions are open to collaboration with everyone in CSE 105. To get the maximum benefit from working on homework assignments, we encourage you to find a group to work with. 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. The pre-survey 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). Questions in homework assignments that are labelled "graded for correctness" (rather than for "fair effort completeness") should only be discussed with your group members and the CSE 105 instructional team. The project assignment will be completed individually.
Ask for help
Reach out to the CSE 105 team if you have questions. The CSE 105 instructional team this quarter is one instructor (Mia Minnes), two TAs (Rachel Lim and Xinsong Lin), and eleven tutors. On our Canvas page, select "People" and filter by "Roles" to see our names, contact information, and brief profiles. This term we will be using Piazza for class discussion; you can access Piazza through our Canvas site or directly (the Piazza roster is synced to the Registrar class list and waitlist). 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: minnes@ucsd.edu . To address me, please use Prof. Minnes, Dr. Minnes, and/or Mia (with pronouns she/her), as you feel comfortable. Please do not use the title Ms./ Mrs. for me.

Resources

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 (minnes@ucsd.edu).

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 of this book is available through multiple vendors; we've seen it listed online for approximately 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 (minnes@ucsd.edu) to arrange a time to pick up a copy.

To brush up on proofs, you can refer to: 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.

Software tools for state diagrams and formal models

flap.js is a webapp under development by a group of UCSD students that is being piloted in CSE 105. Click the "Help" icon for a tutorial for using the app, and hit "Save" to download an image of the diagram you create or to get a permalink for your machine. flap.js is being customized for use in this class; the github repo is https://github.com/flapjs . You can find older versions of the app there, e.g https://flapjs.github.io/FLAPJS-WebApp/ , if you're curious in its development. At the end of the quarter, you can also let me know if you're interested in joining the development team for flap.js to help future CSE 105 students.

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, but some of the conventions and notation it uses are different from the course textbook for CSE 105. You can follow the instructions on the JFLAP website to download and install the current stable version (you may need to install the Java Virtual Machine as well). If you use JFLAP, here are some things to keep in mind:

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 (minnes@ucsd.edu) 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 engagement, assignments, tests.

Engagement
Engagement in class is reflected in review quizzes available on Gradescope. These quizzes help you track and confirm your understanding of the concepts and examples we work in class and give you immediate feedback. They will also sometimes preview upcoming class topics based on the assigned textbook reading. 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). 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. You get credit for a quiz by getting most of the questions right.
Assignments
Assignments are biweekly homeworks plus one project, all listed on the assignments page. Homework assignments give you practice with the main concepts and techniques of the course, while getting to know and learn from your classmates. These homework assignments may be done individually or in groups of up to 3 students. You may switch HW partners for different HW assignments. 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 you're 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 "graded for correctness" questions with CSE 105 students in your group; if your group has questions about a problem, you may ask in drop-in help hours or post a private post (visible only to the Instructors) on Piazza. In the project you'll go deeper and extend your work to explore an application of your choosing. The project is an individual assignment.
Tests
There are two tests in the course, one in week 5 and one in week 9, scheduled (in person and synchronous) during the Friday afternoon discussion section. The scheduled final exam time during finals week will give you an opportunity to retake an equivalent version to one or both of these tests if you miss them or get low scores. There are no make-up tests for the tests during the quarter. If you miss an in-class test, you can regain credit for it from that part of the final exam. This policy is designed to encourage you to treat the in-class tests as learning opportunities so that you can study any mistakes you make and re-apply that knowledge on the final. In addition, if you score high enough on the tests during the quarter, you can skip the final exam with no penalty and just have the test grades applied to your grade.

At the end of the quarter, grades will be assigned according to the following standards:

A
A on both tests or A on one of the tests and B on the other
And one of:
A on at least 4 homeworks, B or above on project, any grade on rest of assignments.
or
B or above on at least 4 homeworks, A on project, any grade on rest of assignments.
B
B or higher on both tests or A on one of the tests and C on the other
And one of:
B or above on at least 4 homeworks, C or above on project, any grade on rest of assignments.
or
C or above on at least 4 homeworks, B on project, any grade on rest of assignments.
C
C or higher on both tests
And:
C or above on at least 3 homeworks and the project, any grade on rest of assignments.

The assigned letter grade will be the highest grade for which the standards are met. Engagement is used to add +/- modifiers at the end of the quarter, and won't make the difference between A/B/C etc. We may adjust the above scale to be more lenient, but we guarantee that we will not adjust the scale to make it harder to get a better grade.

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:

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.

Policies

Regrades

The window for requesting regrades once assignment feedback has been published will be set in Gradescope and will typically be 2-3 days. If you submit a regrade request, please 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. We acknowledge the cumulative contributions to this course material of previous CSE 105 instructors, TAs, and tutors, as well as contributions to the class structure from colleagues in CSE and at UCSD.

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.

Solicitation

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.

Learning goals

You can find the learning outcomes for CSE 105 in this overview page. The Theory-CS homepage also links to archived course sites.