CSE105

Introduction to the Theory of Computation


Top



Course Description

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.

Top


Instructional team

NameRole
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.

Top



Logistics

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

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
  • Exams will include all material covered up to the day of the exam, unless otherwise noted.
  • No makeup tests will be given.
  • You must go to the examination room for your class section.
  • You must sit in your own assigned seat for exams, as specified in posted seat maps before each exam.
  • No electronic devices, books, or written notes are allowed for these examinations except for one (double-sided) handwritten standard sized (3 inch by 5 inch) index card.
  • Sharing of index cards during the exam is not allowed, and will be considered a violation of academic integrity.
  • You must have a score of at least 50% on the final exam to pass the course.
  • The final exam will cover all material from the whole quarter.
Homework policies
  • Homework is due roughly every week, the schedule and assignments will be posted below.
  • Homework is due at 11pm on the day it is due. No late submissions will be accepted for any reason.
  • You may solve and write up each of the seven homework assignments in groups of size one to three . Your homework partners can be enrolled in any of the two Spring 2017 sections of CSE 105, and you can change your homework group with each assignment.
  • Members of a group are responsible for all parts of any assignment with their names on it. Problems should be solved by the group, and not divided up between group members. It is highly recommended that each member of the group try solving the problems individually on their own, before meeting as a group. Each member of a group should participate in discussions about each problem. To encourage full homework participation by all members, each exam will include one problem similar to a homework problem from the two most recent assignments prior to the exam.
  • Homework must be typed and the names of all group members should appear at the top of every page of the homework submitted. The homework should be submitted via gradescope by a single representative of the group. For step-by-step instructions on scanning and uploading your homework, see this handout: make sure to select all group members' names when you "Add Group Members" to the submission; it's not enough to just list their names on the page. (Note: since your homework will be typed, you'll probably only need to follow the instructions for *uploading*.)
  • You may submit updated versions of your homework up until the deadline. Only your most recent Gradescope submission will be graded.
  • Depending on staff support, one or more of the homework problems on a graded assignment may be graded only for completeness and fair effort.
  • When computing the homework portion of the course grade, the lowest of your seven graded homework scores will be dropped and the average computed using the remaining six assignments.
  • Homework must be completed through the independent fair effort of the group members. You should not look for answers to homework problems in other references (i.e. anything other than the course textbook and class notes) or other sources (e.g. wikipedia, Internet, discussion groups). Discussion of the homework problems should be heard only by group members from a single group, unless it is in instructor or TA/tutor office hours. Not giving an acknowledgment of any other source you use is academic dishonesty, and will be treated as such. As well, students may not share answers to homework problems with others or on the internet.
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 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).

  • You must attend the lecture and discussion section in which you are enrolled to earn participation credit. If you need to attend an alternate lecture or discussion section, please post a private note on Piazza ahead of time and, space permitting, we'll accommodate.
  • The lowest weekly participation score will be dropped when calculating your participation average.
  • You must register your iClickers on iClicker by the end of the second week (Friday April 14). It is not enough to register your remote on TritonEd.
  • Clicker questions will be graded for participation only and not correctness of the response, unless otherwise noted.
  • 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!
  • Discussion sections (scheduled on Fridays) are designed to ease your start on the homework problems or to review material for an upcoming exam. Each will cover identical material, and you need only attend one session fully and submit your discussion worksheet to get credit for that week.
  • 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 latest submission before 11pm on Friday 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.
  • Participation credit from lecture and discussion section will be used to make up any lost points on that week's review quiz. For example, full credit for the week's participation score can be earned by any one of the following scenarios: (1) answering all questions on the review quiz correctly; or (2) attending both lectures and one discussion section; or (3) attending two lectures and getting one answer correct on the review quiz; etc.
Regrades
  • Regrade requests should be made through private Piazza post tagged "Regrades" and will be handled directly by Prof. Minnes.
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

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 only legitimate sources of help on submitted homework problems are:
    • Your designated homework partner or partners
    • the associated sections in the course textbook and/or provided course readings, and
    • class instructors, TAs, tutors and Piazza discussion.
  • Other websites, materials from previous classes, or assistance from other individuals listed above are not to be used in any way, not even for consultation prior to writing up your solution.
  • Do not share written solutions or partial solutions with others outside your group, or on the Internet.
  • Do not attempt to falsify iClicker or discussion participation or review quiz submissions. This is considered a violation of academic integrity.

Prevention of Harassment and Discrimination

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.


Top



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



Required materials

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

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.
haskell

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 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.

  • Overleaf This free version allows multiple user collaboration.
  • ShareLaTeX You can collaborate with a single partner for free using this resource.

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

Gradescope

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.


Getting help



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:

  • Effective group work We recommend working on the homework assignments with one or two partners. You can use the Piazza "Search for Teammates" tool to form a group. Try solving the problems individually on your own, before meeting as a group. Each member of a group should participate in discussions about each problem. You should not look for answers to homework problems in other references (i.e. anything other than the course textbook and class notes) or other sources (e.g. wikipedia, Internet, discussion groups). Discussion of the homework problems should be heard only by group members from a single group, unless it is in instructor or TA/tutor office hours.
  • Textbook reading and review quizzes Before coming to class, try to skim the posted textbook sections. After class, review your notes (and the annotated slides) from class, watching the podcast as necessary, and reviewing the definitions and worked examples in the textbook. Each week, the online review quiz will help you solidify the basic concepts, terms, and definitions covered.
  • Discussion sections During Friday discussion sections, your TA will facilitate active learning that will help you work on material similar to the homework problems or to review material for an upcoming exam.
  • Office hours Prof. Minnes, each TA, and each tutor will offer group office hours (times and location announced on the Google calendar above). In addition, you will have the opportunity to sign up for one-on-one tutoring with one of the tutors or TAs each week.
  • Piazza The Piazza discussion board will be the main platform to answer student questions and post announcements. You must self-enroll in this site at: piazza.com/ucsd/spring2017/cse105.

Schedule

NOTE: Subject to change throughout the quarter.

DateDaySubjectReferenceNotes
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

Top