CSE 105: Introduction to Theory of Computability


Course grades will be computed using the following weights.

65% of overall score
Computed by MAX (15% midterm 1 + 15% midterm 2 + 35% final, 15% best midterm + 50% final)
30% of overall score
Weekly HW has individual component (worth 10% overall) and group component (worth 20% overall), with separate due dates.
Drop lowest HW score of each type
5% of overall score
Earn weekly participation credit by attending class and discussion section; make up missed attendance with review quiz

Minimum letter grade cutoffs

After your weighted average is calculated, letter grades will be assigned based on the following grading scale:

A+ A A- B+ B B- C+ C C- D, F
  >97    93-96.99     90-92.99    87-89.99    83-86.99    80-82.99    77-79.99    73-76.99    65-72.99    Below 64.99 

We may adjust the above scale to be more lenient (depending on the overall class performance), but we guarantee that we will not adjust the scale to make it harder to get a better grade. In addition, you must pass the final exam in order to pass the course.

Regrade policy

Regrades need to be requested within three days of announcement of grades. To do so, fill out the form linked here. In the description of the regrade, clearly specify
  • The HW number in question and whether it is an individual HW or a group HW.
  • An itemized list of the questions you think were graded incorrectly, with a brief but detailed explanation of why you think there was an error in the grading.
You should submit the form only once for each assignment. If the regrade request is about a group HW, only one group member should submit the form.

Exam policy

There will be two midterm exams and one final exam. The midterms will be during the usual lecture time and place and you must attend the lecture for which you are registered. No makeup tests will be given.

The exams will test all material covered up to the day of the exam. In particular, the final exam will be cumulative and will cover all material from the whole term.

You may not use calculators on any exams but you may use handwritten notes, double-sided on a standard sized index card.

You must have a passing score on the final exam in order to pass the course.

Homework policy

Each week, homework assignments will help you work towards mastery of the course techniques.

  • Individual homework assignments will help guide your explorations of the content. They must be completed without any aids or collaboration. Most of the questions on these homework will be graded for fair effort completeness; one will be graded for correctness.
  • Group homework assignments may be done in groups of one to three CSE 105 students. Group members may be in any of the sections of CSE 105. You are encouraged to change groups between assignments. Problems should be solved together, not divided up between group members. Group homework will be graded for correctness, including clear and precise explanations and justifications of all answers.

Homework sumbissions must be typed and turned in through Gradescope by 11pm on the day they are due. Illegible assignments will not be graded. Submit only one submission per group. One representative group member can upload the submission through their Gradescope account and then add the other group member(s) to the Gradescope submission: make sure to select their names when you "Add Group Members" to the submission; it's not enough to just list their names on the page. For step-by-step instructions on scanning and uploading your homework, see this handout.

Late homeworks will not be accepted. Submit early drafts well before the deadline to make sure partial work is graded.

For homework help, consult your textbook, class notes and podcast, lecture slides, instructors, TAs, and tutors. It is considered a violation of the policy on academic integrity to:

  • look or ask for answers to homework problems in other texts or sources, including the internet, or to
  • discuss the homework problems with anyone outside your group (unless you are in office hours with someone from the instructional team).
Only post about graded homework questions on Piazza if you suspect a typo in the assignment, or if you don't understand what the question is asking you to do. Other questions are best addressed in office hours.

Homework solutions will be posted on Piazza after the submission deadline.

JFLAP Resources

JFLAP is a visualization tool that will help you check your work and explore the machines you build in class. The homepage for the tool is at www.jflap.org. We will be using the stable version (7.0) for this class.

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.

  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.
  3. After downloading, run the file (double-click) to install.
  4. After the install is finished, you may need to reboot.
  5. Now follow the "Basic Install and Configuration" instructions above to install and configure JFLAP.

Frequently asked questions

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. 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 (Overleaf, ShareLaTeX) that don't require you to download and install LaTeX on your local machine.

Alternatively, you can install a version of LaTeX on your computer e.g. TeXworks.

An open source LaTeX reference is here, and you can Google for many templates and examples to get you started.

Participation policy

We highly recommend actively engaging with the class material consistently throughout the quarter. To facilitate this, you will earn credit for participating in class, attending discussion, and completing weekly review quizzes. You can earn a maximum of 4 participation points each week. If you earn 30 participation points during the quarter, you will get all 5% participation credit available.

  >= 30 points    5% 
  29 points    4% 
  28 points    3% 
  27 points    2% 
  26 points    1% 
  <26 points    0% 

Each weekly review quiz will be worth at most 3 points and will be counted for credit if it is submitted before 11pm on Sunday night. You can submit the quiz as many times as you like before the deadline. The last score before the deadline will be counted for credit.

Lecture attendance (each lecture = 1 points) and discussion attendance (2 points) also earn credit. You can attend any lecture or discussion section for credit, but you will earn at most one credit for each day. In lectures, attendance will be recorded by Clicker participation. Clicker questions will be graded for participation only and not correctness of the response. Full credit for clicker points for a given day will be awarded for clicking in at least 80% of the time that day. Forgetting your clicker counts as missing a class, so please remember to bring it; register your clicker here. Sign in on the class roster when you enter the discussion section room to record your attendance.

Do not attempt to falsify iClicker or discussion participation or review quiz submissions. This is considered a violation of academic integrity.

You will complete and submit review quizzes online. You can submit as many times as you like. The last submission before 11pm on Sunday will count towards your participation score.The review quiz must be completed independently and individually. You may refer to your textbook and class notes and slides but not other references. You may not share information about the review quiz with others, take the review quiz in someone else's name, or ask anyone for prior knowledge about the review quiz.

Getting help

We want you to do well in the class and also to get excited about the material. Outside the class and discussion time, we encourage you to attend office hours to ask questions and talk about the class.

Drop-in group office hours: Each of the instructors, the TAs, and the tutors will hold office hours each week where you can drop by and ask questions about the homework, key concepts, or the class in general. See the Google calendar on the main page for times and locations of these office hours.

One-on-one tutoring sessions: TAs and tutors will be available for one-on-one sessions to catch up or dig deeper on tough concepts. These half-hour sessions must be booked in advice (booking procedure TBA on Piazza) and cannot focus on the current HW assignment.

Accommodations for students with disabilities

Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (OSD) which is located in University Center 202 behind Center Hall. Students are required to present their AFA letters to Faculty (please make arrangements to contact me privately) and to the OSD Liaison in the department in advance (by the end of week 2, if possible) so that accommodations may be arranged. For more information, see here.

Academic Integrity

The Jacobs School of Engineering code of Academic Integrity is here. Academic integrity violations will be taken seriously and reported to the campus-wide Academic Integrity Office. Ignorance of the rules will not excuse you from any violations. Key facts about academic integrity related to CSE 105:

  • Do not discuss homework problems with people besides your homework group members and the instructional staff.
  • Do not share written solutions or partial solutions with other groups.
  • Prepare your final written solution without consulting any written material except class notes and the class text.
  • Do not use any external resources (other than the allowed index card of notes) during the in-class exams.
  • Before taking an exam or quiz, do not attempt to obtain information about the contents of the exam from students who have already taken it.
  • After taking an exam or quiz, do not discuss its contents with anyone in the class who has not yet taken it.


The IDEA Engineering Student Center, located just off the lobby of Jacobs Hall, is a hub for student engagement, academic enrichment, personal/professional development, leadership, community involvement, and a respectful learning environment for all. The Center offers a variety of programs, listed in the IDEA Center Facebook page and the Center web site. The IDEA Center programs support both undergraduate students and graduate students.

Educational Research

This class is participating in research to understand an array of specific classroom and learning experience that students have in response to the pedagogical and curricular decisions instructors make and to address the following research questions:

  • What pedagogies lead to better learning outcomes, and for which students?
  • What educational practices increase the persistence and success of students, particularly those from underrepresented groups?
  • What student practices lead to increased learning and success in real-world settings?
Answers to these questions will inform teaching practice at UC San Diego, and also have the potential to contribute to the global knowledge base of how to improve student learning in a large university setting.

For details on this research and to understand the consent process, please see this document.