Welcome to CSE 105! This course will help you answer fundamental questions about computing:
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 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.
See also: Course Catalog description of CSE 105.
Name | Role | |
Prof. Mia Minnes | Instructor ( minnes@eng.ucsd.edu ) | |
Benjamin Cosman | Teaching Assistant | |
Aditya Suresh Kumar | Teaching Assistant | |
Justin Lazarow | Teaching Assistant | |
David Qiu | Teaching Assistant | |
Kevin Yin | Teaching Assistant | |
Alec Brickner | Tutor | |
Timothy Deng | Tutor | |
Abhishek Goyal | Tutor | |
Rachel Keirouz | Tutor | |
Julia Len | Tutor | |
David Luu | Tutor | |
Ladislav Steffko | Tutor | |
Stephanie Wagner | Tutor |
Announcements and Q&A are through Piazza (sign up link: piazza.com/ucsd/spring2017/cse105): use public posts to ask questions that might interest other students in the class and private posts (visible to the instructional team) for questions specific to you. Our office hours and locations can be found in the calendar above.
The lectures for this course meet twice a week 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. There are two in-class exams during the quarter and a final exam on the Saturday before exam week. We will use Piazza for Q&A, announcements, and to distribute HW solutions, practice exams, and seat assignments.
Course grades will be computed using the following weights.
Grading | |
Exams MAX ( (Final 41%, Exam 1 15%, Exam 2 15%), (Final 56%, Best Exam 15%)) | 71% |
Homework 4% for each of top six homework assignments aka "drop the lowest HW score" | 24% |
Class Participation and Preparation Average weekly participation score, after dropping lowest week. | 5% |
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):
A | B | C | D | F |
90 - 100 | 80 - 89.999 | 70 - 79.999 | 60 - 69.999 | < 60 |
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 weekly review quizzes, we know your class preparation time is limited. Each weekly review quiz will be worth 5 points and will be counted for credit if it is submitted before 11pm on Friday night. Any points that you miss on the weekly review quiz can be made up through lecture attendance (each lecture = 2 points) and discussion attendance (1 point).
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 is an issue that is important to all students on campus. When students act unethicially by copying someone's work, taking an exam for someone else, plagiarizing, etc., these students are misrepresenting their academic abilities. This makes it impossible for instructors to give grades and for the University to give degrees that reflect student knowledge. This devalues the worth of a UCSD degree for all students, making it important for the entire campus to band together and enforce that all members of this community are honest and ethical. We want your degree to be meaningful and we want you to be proud to call yourself a graduate of UCSD!
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.
The Office for the Prevention of Harassment & Discrimination (OPHD) provides assistance to students, faculty, and staff regarding reports of bias, harassment, and discrimination. OPHD is the UC San Diego Title IX office. Title IX of the Education Amendments of 1972 is the federal law that prohibits sex discrimination in educational institutions that are recipients of federal funds. UCSD students have the right to an educational environment that is free from harassment and discrimination.
Students have options for reporting incidents of sexual violence and sexual harassment. Sexual violence includes sexual assault, dating violence, domestic violence, and stalking. Information about reporting options may be obtained at OPHD at (858) 534-8298, ophd@ucsd.edu or http://ophd.ucsd.edu. Students may receive confidential assistance at CARE at the Sexual Assault Resource Center at (858) 534-5793, sarc@ucsd.edu or http://care.ucsd.edu or Counseling and Psychological Services (CAPS) at (858) 534-3755 or http://caps.ucsd.edu.
You may feel more comfortable discussing your particular concern with a trusted UCSD employee. This may be a CSE student affairs staff member, a department Chair, a faculty member or other University official. These individuals have an obligation to report incidents of sexual violence and sexual harassment to OPHD. This does not necessarily mean that a formal complaint will be filed.
If you find yourself in an uncomfortable situation, ask for help. The CSE department is committed to upholding University policies regarding nondiscrimination, sexual violence and sexual harassment.
The required textbook is Sipser, Michael Introduction to the Theory of Computation, Third Edition
The international edition is available at the bookstore and is under $20. Page references and section numbers will be to this edition. However, most editions of the book include the content we will cover and you can consult any of them you like. We will be closely following some sections of the book and highly recommend making sure you have access to the required reading, as well as the additional opportunities for worked examples and exercises found in the book.
For more background on writing proofs, the following textbook is recommended: Richard Hammack, Book of Proof, 2nd ed. (available for download here , as well as print version through Amazon)
An iClicker is also required, and is available for purchase at the bookstore. You should register your iclicker, if you have not done so already, and make sure you bring it to every class.
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):
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:
Some assignments will include exercises in the haskell programming language. These exercises will let you work with different representations of the objects we're discussing, and will help you check your work. 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 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.
You will submit homework assignments and receive 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 (A01, A02, A03, A04, B01, B02, B03, B04). We will not be able to add you to the class without *all* of this data.
This course is designed to be challenging and rewarding. It's expected that you'll need help with some of the material and techniques. We have many opportunities for you to get this help:
NOTE: Subject to change throughout the quarter.
Date | Day | Subject | Reference | Notes |
Week 1 | Sipser Chapter 0, Sec 1.1 | |||
4/4/17 | Tu | Introduction, Deterministic Finite Automata | Slides Lecture A (annotated) Lecture B (annotated) |
|
4/6/17 | Th | Designing DFA | Slides Lecture A (annotated) Lecture B (annotated) |
|
4/7/17 | F | Discussion Section | Discussion 1 worksheet Review Quiz 1 due by 11pm |
|
4/10/17 | Mon | HW 1 due PDF; Source; Style file DFA image; haskell file; haskell tester |
||
Week 2 | Sipser Sec 1.1, 1.2 | |||
4/11/17 | Tu | Closure of the class of regular languages | Slides Lecture A (annotated) Lecture B (annotated) |
|
4/13/17 | Th | Nondeterministic Finite Automata, NFA-DFA equivalence | Slides Lecture A (annotated) Lecture B (annotated) |
|
4/14/17 | F | Discussion Section | Discussion 2 worksheet Additional worksheet on constructions with DFAs and NFAs Review Quiz 2 due by 11pm |
|
4/17/17 | Mon | HW 2 due PDF; Source; Style file DFA M1 image, DFA M2 image DFA M1 JFLAP, DFA M2 JFLAP HW2.hs DFA.hs |
||
Week 3 | Sipser Sec 1.3, 1.4 | |||
4/18/17 | Tu | NFAs + Regular expressions | Slides Lecture A (annotated) Lecture B (annotated) |
|
4/20/17 | Th | Regular sets + Review | Slides Lecture A (annotated) Lecture B (annotated) |
|
4/21/17 | F | Discussion Section | Discussion 3 worksheet Review Quiz 3 due by 11pm |
|
4/23/17 | Sun | HW 3 due PDF; Source; Style file |
||
Week 4 | Sipser Sec 1.4 | |||
4/25/17 | Tu | Exam 1 | Study guide | |
4/27/17 | Th | Pumping Lemma | Slides Lecture A (annotated) Lecture B (annotated) |
|
4/28/17 | F | Discussion Section | Discussion 4 worksheet Review Quiz 4 due by 11pm |
|
Week 5 | Sipser Sec 2.1, 2.2 | |||
5/2/17 | Tu | Nonregular sets and Context-free grammars | Slides Lecture A (annotated) Lecture B (annotated) |
|
5/4/17 | Th | Context-free languages and ambiguity | Slides Lecture A (annotated) Lecture B (annotated) |
|
5/5/17 | F | Discussion Section | Discussion 5 worksheet Review Quiz 5 due by 11pm |
|
5/8/17 | Mon | HW 4 due PDF; Source; Style file |
||
Week 6 | Sipser Sec 2.2, some of 2.3, 3.1, 3.2, 3.3 | |||
5/9/17 | Tu | Push-down automata | Slides Lecture A (annotated) Lecture B (annotated) |
|
5/11/17 | Th | Non-context-free languages and Turing machines | Slides Lecture A (annotated) Lecture B (annotated) |
|
5/12/17 | F | Discussion Section | Discussion 6 worksheet Review Quiz 6 due by 11pm |
|
5/15/17 | Mon | HW 5 due PDF; Source; Style file CFG.hs; HW5TM.jff; HW5TM.png |
||
Week 7 | Sipser Sec 3.3, Chapter 4 | |||
5/16/17 | Tu | Decidability, Recognizability, and Variants of TMs | Slides Lecture A (annotated) Lecture B (annotated) |
|
5/18/17 | Th | Church-Turing thesis | Slides Lecture A (annotated) Lecture B (annotated) |
|
5/19/17 | F | Discussion Section | Discussion 7 worksheet Review Quiz 7 due by 11pm |
|
5/21/17 | Sun | HW 6 due -- Files updated 5/18 PDF; Source; Style file |
||
Week 8 | Sipser Chapter 4 | |||
5/23/17 | Tu | Exam 2 | ||
5/25/17 | Th | Decidable problems | Slides Lecture A (annotated) Lecture B (annotated) |
|
5/26/17 | F | Discussion Section | Discussion 8 worksheet Review Quiz 8 due by 11pm |
|
Week 9 | Sipser Sec 5.1 | |||
5/30/17 | Tu | Undecidability and diagonalization | Slides Lecture A (annotated) Lecture B (annotated) |
|
6/1/17 | Th | Reductions | Slides Lecture A (annotated) Lecture B (annotated) |
|
6/2/17 | F | Discussion Section | Discussion 9 worksheet Review Quiz 9 due by 11pm |
|
6/4/17 noon | Sun | HW 7 due (extended) PDF; Source; Style file End of course survey |
||
Week 10 | Sipser Chapter 7 | |||
6/6/17 | Tu | Time complexity, P vs. NP | Slides Lecture A (annotated) Lecture B (annotated) |
|
6/8/17 | Th | Review | Slides Lecture A (annotated) Lecture B (annotated) |
|
6/9/17 | F | Discussion Section | Discussion 10 worksheet - Study guide for final exam Review Quiz 10 due by 11pm |
|
Exam week | ||||
6/10/17 | Sat | Lec A final exam and Lec B final exam | 11:30am - 2:29pm Lec A: PCYNH 109 Lec B: PCYNH 106 |