Introduction to the Theory of Computation



Professor Daniele Micciancio
Office Hours
When: Usually Mondays 10-12; see Google calendar above.
Where: EBU3b (CSE) 4214
Professor Mia Minnes
Office Hours
When: Usually Mondays 12-2; see Google calendar above.
Where: EBU3b (CSE) 4206

To contact the CSE 105 instructional team, please post on Piazza. Confidential questions to the instructional team can be made as "private posts".
Office hours and any changes in schedule will be posted on Google calendar above.

Teaching Assistants and Tutors

Marco Carmosino
Benjamin Cosman
Elaine Hwang
Aditya Suresh Kumar
Justin Lazarow
Edward Wong
Kevin Yin

Alec Brickner
Abhishek Goyal
Madhu Krishnan
Lucy Li
Grant Lin
David Luu
Purag Moumdjian
Becky Zhou

TAs and tutors will be available for group office hours as posted on the Google calendar above. There will also be some 1-1 tutoring slots available for sign-up (first come first serve) TBA.
The instructional team is regularly available on Piazza. Confidential questions to the instructional team can be made as "private posts".


Course Description

Welcome to CSE 105! This course addresses fundamental questions about computing:

You'll see how the answers to these questions shape many aspects of computer science. You'll also be developing and practicing essential skills of computer scientists, including writing mathematically sound and clear arguments (from formal proofs to more informal explanations), using visualization and testing tools, and dabbling in a new programming language.

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" in this last model. 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.

See also: Course Catalog description of CSE 105.

The lectures for this course meet three times a week (for Sections A and C) or twice a week (for Section B) and will include many opportunities for active learning using clickers, peer instruction, and opportunities to ask questions to the instructor, TAs, and tutors. Podcasts for each lecture section can be found at podcast.ucsd.edu. There will also be weekly discussion sections which will review the week's concepts and help you get started on homework (see schedule). Seven homework assignments will stretch and deepen your understanding of the concepts: you will submit these assignments and receive feedback on them via gradescope. Additional (optional) programming assignments will give you the opportunity to implement the theory with Haskell. These assignments will be submitted through scripts on ieng6. There are three 50-minute exams during the quarter and a final exam during exam week. Gradescope will also be used to distribute exam grades and feedback. Piazza, our discussion and announcements board, will also be used for announcements and distributing some files.

Course grades will be computed using the following weights.


    MAX ( (Final 26%, Exam 1 13%, Exam 2 13%, Exam 3 13%), (Final 39%, Best Exam 13%, Second Best Exam 13%))

    5% for each of top six homework assignments aka "drop the lowest HW score"
Class Participation and Preparation

    MAX ( Clicker score, Discussion Attendance, Haskell projects )
(or more)

After your weighted average is calculated, final letter grades will be assigned no stricter than the following grading scale, except that you must get a passing grade on the final exam in order to pass the course (regardless of total percentage):

90 - 100 80 - 89.9 70 - 79.9 60 - 69.9 < 60

Plus and minus to a letter grade will be assigned at the instructor's discretion. This includes but is not limited to: consideration of improvement over the course of the quarter, active class participation, and natural "breaks" in the distribution of scores. 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.

Standards for evaluation Your homework and exams in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.

Exam policies Homework policies Class Participation and Preparation

Solving new and challenging problems and regularly working with the concepts in this course is the best way to learn the material. There will be ample opportunity to do this throughout the quarter, and the Class Participation and Preparation component of your grade gives credit for the work you do in this regard. While we highly recommend actively participating in class, attending discussion, and completing the Haskell projects, we know your class preparation time is limited. Therefore, completing the work in ANY ONE of these categories will satisfy your class preparation requirement. Note that your class preparation grade component is the MAX of your clicker participation score, your discussion attendance score, and your Haskell project score; it is not their SUM. Moreover, your three highest-scoring Haskell projects will each be weighted 2% towards your final score: three perfect scores will earn you 6% (a 1% bonus in addition to the participation score).

Regrades Accommodations

The Office for Students with Disabilities (OSD), an Academic Affairs department, is responsible for the review of medical documentation and the determination of reasonable accommodations based on a disability. Authorization for Accommodation (AFA) letters are issued by the OSD and given to undergraduate, graduate, and Professional School students directly. If you have an AFA letter, meet with the CSE Student Affairs representative, and schedule an appointment with your instructor by Monday of Week 3 to ensure that reasonable accommodations can be arranged.

Academic Integrity

The guidelines for this class may be different from other courses and professors, and may prohibit things that you personally don't think of as "cheating." If you have any questions about what is acceptable or not under this class' guidelines, please ask before it is too late. UCSD's policy is that "I didn't know" is not an excuse.

The Jacobs School of Engineering code of Academic Integrity, the UCSD Policy on Integrity of Scholarship and this syllabus list some of the standards by which you are expected to complete your academic work, but your good ethical judgment (or asking us for advice) is also expected as we cannot list every behavior that is unethical or not in the spirit of academic integrity. You should make yourself aware of what is and is not acceptable by reading these documents. Ignorance of the rules will not excuse you from any violations. If you have any doubt as to whether a conversation you wish to have with someone or other activity might cross the line, please stop and go to the discussion forum on Piazza, where we will be happy to help you, and where the integrity of the discussion can be monitored for everyone's protection.

Academic integrity violations will be taken seriously and reported immediately. If you are suspected of not following the guidelines, your case will be referred to the Dean of your college. Consequences may include an F in the course, no matter how small the affected assignment or exam question. Be aware that TritonLink will block you from dropping the course if your case is in process with the Dean, so you will not be able to avoid consequences by dropping.


Tools: Textbook, LaTeX, JFLAP, Haskell, and Other Resources

Required materials JFLAP

JFLAP is a visualization tool for many of the models of computation we'll study in this class. The homepage is at J-FLAP. 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, than 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 it 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.
Programming tools

Your student computer account on ieng6.ucsd.edu will be used to collect the Haskell programming projects, as well as to provide access to various software and support files. You will submit your projects using Bundle on ieng6. Specific submission instructions will be distributed with each project instructions.

Some assignments will include simple programming exercises in the haskell programming language, and the haskell projects will go deeper. The ghc haskell compiler is available on ieng6 just by typing ‘ghc’ or ‘ghci’ on the command line. If you want to run haskell on your own computer, the recommended method is to install the Haskell Platform. See the CSE105 Haskell Page for more detailed instructions, help getting started, and other useful resources.

LaTeX Resources

LaTeX is a very commonly used typesetting language for computer science and mathematics. We use it to typeset the homework assignments, and we encourage you to use it for typing your solutions. We will provide the .tex source files of homework assignments, and a class file to use to get you started. If you have never used LaTeX, we recommend the Cloud resources below; the easiest way to get started with LaTeX is one of the following free resources.

Both are reasonably easy to use and require registration. Alternatively, you can install a version of LaTeX on your computer.


The Piazza discussion board will be the main platform to answer student questions and post announcements. There is a single Piazza site for all three sections of CSE 105 this quarter. You must self-enroll in this site at: piazza.com/ucsd/fall2016/cse105.


You will submit homework assignments and received feedback on homework and exams via Gradescope. If you were enrolled in the class on the first day, you should automatically have access to our Gradescope class. You will not be able to self-enroll for this class (we will not be handing out the access code for the class). Instead, if you need to be added, post a private note to Piazza with your Last Name, First Name (as recorded by the Registrar), UCSD Email address, PID, and Section (A, B, or C). We will not be able to add you to the class without *all* of this data.

Course Description

There are three sections of the class, with joint homework, discussion sections, and instructional team. You should go to the classroom and exam room for your section. You may go to any discussion section(s), as long as we do not exceed room capacity (first come, first served).

Lecture A
MWF 8:00am-8:50am CENTER 109
Exam 1 F Oct 14 in class
Exam 2 W Nov 2 in class
Exam 3 F Nov 18 in class
Final Exam M Dec 5
Lecture B
TuTh 9:30am-10:50am LEDDN AUD
Exam 1 Th Oct 13 in class
Exam 2 Th Nov 3 in class
Exam 3 Th Nov 17 in class
Final Exam Th Dec 8
Lecture C
MWF 9:00am-9:50am CENTER 109
Exam 1 F Oct 14 in class
Exam 2 W Nov 2 in class
Exam 3 F Nov 18 in class
Final Exam W Dec 7

Discussion Sections
Day Time Room Topic
Friday 11:00a-11:50a PCYNH 121 main
Friday 1:00p-1:50p CENTR 105 main
Friday 2:00p-2:50p CSB 005 main
Friday 3:00p-3:50p CSB 005 main
Friday 5:00p-5:50p WLH 2115 main
Tuesday 6:00p-6:50p PCYNH 106 haskell



NOTE: Subject to change throughout the quarter.

Week 0 Sipser Ch 0, Sec 1.1
9/22/16 Th Introduction, Deterministic Finite Automata (DFA) (Lec B) Review class web site info
Lecture B notes (annotated)
9/23/16 F Introduction, Deterministic Finite Automata (DFA) (Lec A,C)
Discussion Sections
Review class web site info
Lecture A,C notes
Week 1 Sipser Sec 1.1
9/26/16 M DFA and designing DFA (Lec A,C) Lecture A,C notes
9/27/16 Tu Designing DFA, Regular languages (Lec B) Lecture B notes (annotated)
9/28/16 W Regular Languages, Closure (Lec A,C) Lecture A,C notes
HW1 due (all sections)
.tex file, .cls file, Haskell files, png
9/29/16 Th Closure (Lec B) Lecture B notes (annotated)
9/30/16 F Closure (Lec A,C)
Discussion Sections
Lecture A,C notes
Week 2 Sipser Sec 1.2, 1.3
10/3/16 M NFA (Lec A,C) Lecture A,C notes
10/4/16 Tu NFA, NFA-DFA Equivalence (Lec B) Lecture B notes (annotated)
HW2 due (all sections)
.tex file, .cls file, Haskell files
10/5/16 W NFA-DFA Equivalence (Lec A,C) Lecture A,C notes
10/6/16 Th Regular Expressions (Lec B) Lecture B notes (annotated)
10/7/16 F Regular Expressions (Lec A,C)
Discussion Sections
Lecture A,C notes
Haskell Project 1 due (all sections)
.tex file, .cls file, Haskell files
Week 3 Sipser Sec 1.4
10/10/16 M Nonregular languages (Lec A,C) Lecture A,C notes
10/11/16 Tu Nonregular languages (Lec B) Lecture B notes (annotated)
HW3 due (all sections)
.tex file, .cls file, Haskell files, New!data.txt
10/12/16 W Nonregular languages (Lec A,C) Lecture A,C notes
10/13/16 Th Exam 1 and Pumping Lemma (Lec B) Exam 1
Lecture B notes
10/14/16 F Exam 1 (Lec A,C)
Discussion Sections
Exam 1
Week 4 Sipser Sec 1.4, 2.1, 2.2
10/17/16 M Using Pumping Lemma (Lec A,C) Lecture A,C notes
10/18/16 Tu Context-free grammars (Lec B) Lecture B notes (annotated)
10/19/16 W Context-free grammars (Lec A,C) Lecture A,C notes
10/20/16 Th CFG, ambiguity, and Pushdown automata (Lec B) Lecture B notes (annotated)
10/21/16 F Ambiguous grammars and Pushdown automata (Lec A,C)
Discussion Sections
Lecture A,C notes
Haskell Project 2 due (all sections)
.tex file, .cls file, Haskell files
Week 5 Sipser Sec 2.1, 2.2, 3.1
10/24/16 M PDA + CFG (Lec A,C) Lecture A,C notes
10/25/16 Tu Context-free languages (Lec B) Lecture B notes (annotated)
HW4 due (all sections)
.tex file, .cls file
TYPO: Q2a should read 0 , not {0}.
10/26/16 W Context-free languages (Lec A,C) Lecture A,C notes
10/27/16 Th Turing machines (Lec B) Lecture B notes (annotated)
10/28/16 F Turing machines (Lec A,C)
Discussion Sections
Lecture A,C notes
Week 6 Sipser Chapter 3
10/31/16 M Variants of TMs (Lec A,C) Lecture A,C notes
HW5 due (all sections)
.tex file, .cls file, Haskell3 files
11/1/16 Tu Variants of TMs, Church-Turing thesis (Lec B) Lecture B notes (annotated)
11/2/16 W Exam 2 (Lec A,C) Exam 2
11/3/16 Th Exam 2 and Chuch-Turing thesis (Lec B) Exam 2
Lecture B notes (annotated)
11/4/16 F Church-Turing thesis (Lec A,C)
Discussion Sections
Lecture A,C notes
Week 7 Sipser Chapter 4
11/7/16 M Decidability (Lec A,C) Lecture A,C notes
Haskell Project 3 due
.tex file, .cls file, Haskell files
11/8/16 Tu Decidability (Lec B) Lecture B notes (annotated)
11/9/16 W Cardinality arguments (Lec A,C) Lecture A,C notes
11/10/16 Th Cardinality and diagonlization (Lec B)
Lecture B notes (annotated)
11/11/16 F Veterans' Day - No class
Week 8 Sipser Chapter 4, Sec 5.1
11/14/16 M Undecidability (Lec A,C)
Lecture A,C notes
11/15/16 Tu Undecidability (Lec B) Lecture B notes (annotated)
HW6 due (all sections)
.tex file, .cls file, Haskell4 files
11/16/16 W Undecidability (Lec A,C) Lecture A,C notes
11/17/16 Th Exam 3 and Reduction (Lec B) Exam 3
Lecture B notes (annotated)
11/18/16 F Exam 3 (Lec A,C)
Discussion Sections
Exam 3
Week 9 Sipser Sec 5.1
11/21/16 M Reduction (Lec A,C) Lecture A,C notes
Haskell Project 4 due
.tex file, .cls file, Haskell files
11/22/16 Tu Reduction (Lec B) Lecture B notes (annotated)
11/23/16 W Reduction (Lec A,C) Lecture A,C notes
11/24/16 Th Thanksgiving holiday - no class
11/25/16 F Thanksgiving holiday - no class
Week 10 Sipser Chapter 7
11/28/16 M Time complexity (Lec A,C) Lecture A,C notes
11/29/16 Tu Time complexity and P vs. NP (Lec B) Lecture B notes (annotated)
HW7 due (all sections)
.tex file, .cls file
11/30/16 W P vs. NP (Lec A,C) Lecture A,C notes
12/1/16 Th Review Lecture B notes
12/2/16 F Review (Lec A,C)
Discussion Sections
Lecture A,C notes
Exam week
12/5/16 M Lec A final exam 8am - 11am
Location CENTER 109
12/6/16 Tu
12/7/16 W Lec C final exam 8am - 11am
Location CENTER 109
12/8/16 Th Lec B final exam 8am - 11am
Location LEDDN AUD
12/2/16 F