CSE105 Spring 2016

Introduction to the Theory of Computation

This page is an archive of an older offering of the class.


Top



Instructor

Professor Jeanne Ferrante
Office Hours
When: See Google calendar above
Where: EBU3b (CSE) 3102
Professor Mia Minnes
Office Hours
When: See Google calendar above.
Where: EBU3b (CSE) 4206

Contact
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


TAs
Dhivya Anandakrishnan
Karthikeyan Balasubramaniam
Juliana Curtis
Olivia Simpson
Nathan Speidel


Tutors
Alec Brickner
Asha Camper Singh
John Clara
Jesse Gallaway
Rachel Keirouz
Madhu Krishnan
David Luu
Purag Moumdjian
Maya Nyayapati
Timothy Nguyen


Contact
To contact the CSE 105 instructional team, please post any non-confidential question 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.

Top



Welcome Message

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

It's a lot of fun to look at these basic questions, and you will be picking up some of the essential skills of a computer scientist, such as writing mathematically sound and clear arguments, from formal proofs to more informal explanations.

This website provides basic course information, the class calendar, and the class schedule. Homework assignments and class notes will be posted on the class schedule. This and three other important web sites, gradescope (for homework submission and exam grades), Piazza (our discussion and announcements board), and TritonEd (formerly Ted, for reading quizzes, posted homework solutions, and iclicker registration), will provide you with the information you need to thrive in the class. Podcasts for each section can be found at podcast.ucsd.edu. Please check the class schedule and Piazza often for important information, announcements, and course materials.

Course Description:

In this course, we will undertake an exploration of 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.



Please click here for a course description as given in the undergraduate course listing.



Grading:

Course grades will be computed using the following weights.

Grading
Midterm Exams and Final Exam70%
Homework20%
Class Participation5%
Class Preparation = MAX (Reading quiz grade, Discussion Participation)5%

Midterm and Final Exams are the most important indicator of how well you have mastered the content of this course.

There will be two specially scheduled midterm exams outside of the usual lecture time and the usual lecture room; the times and locations of these exams are posted in the schedule of classes and in the calendar above. No makeup tests will be given. You should go to the examination room for your class section. 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. These exams will include all material covered up to the day of the exam, unless otherwise noted.

The final exam will cover all material from the whole quarter, though more emphasis will be given to material covered after the second exam.

It is highly recommended that you start preparing for an exam at least a week beforehand by reviewing class notes, the relevant textbook chapters, and most importantly, doing homework and similar problems. Each exam will include one problem similar to one of the homework problems from the two most recent assignments before the exam.

There will be no make-up exams. The weighting of the exam scores will be

MAX ( (Final 35%, Best Exam 20%, Other Exam 15%), (Final 45%, Best Exam 25%)).

You must have a score of at least 50% on the final exam to pass the course.


Homework is the second most important component in learning this material, and it is essential that you do the homework to gain the skills we will study. Proof writing and clear technical arguments are skills that need practice, practice, practice. Proofs need to be logically sound, make precise use of mathematical language and terminology from the course, be clearly stated, and be concise but not lacking critical details.

There will be seven graded homework assignments. Homework assignments will be posted on the class schedule, and grades will be available on gradescope. Solutions will be posted on TritonEd (formerly Ted). 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.

Many students find it challenging to discern what the proper level of detail to be included is (i.e., how to be "concise but not lacking critical details"). The best way to acquire this skill is through repeated iterations of practice and feedback on your work, as well as being exposed to others' proofs to sharpen your proof reading skills.

Group Collaboration

In order to get peer feedback, students are allowed to solve and write up all homework assignments in groups of size one to three . Your homework partners can be in either class section, and you can change your homework group with each assignment. All names of the group should appear on the submitted assignment, and all will get the same score on the 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. Even proof-reading a solution of another student in your group counts as participation.

To succeed in this class, it is important that each student in a group be able to write and not just understand the solutions. Understanding a proof is very different from being able to write a proof yourself. 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.

Logistics All names of the group should appear at the top of the homework submitted. Homework must be typed and submitted as a single PDF by a single representative of the group. Homework submission is via gradescope and is due by the time specified on the due date on the class schedule. 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. You may submit updated versions of your homework up until the deadline. Late homework is not accepted for any reason.

Integrity Guidelines

Homework must be completed through the independent fair effort of the group members. Students 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 should not share answers to homework problems with others or on the internet.


Class Participation

There will be frequent opportunities for structured active participation during lecture, discussion, and online (solving problems, responding with clickers, critiquing proofs, Piazza participation, surveys, and group discussion), in which everyone is expected to participate. Additionally, alerting the instructor, TAs, and tutors when you are confused, lost, didn't hear something, or otherwise in need of additional explanation is strongly encouraged. For this reason, you will be required to have an iClicker for this course, and to bring it to each lecture and discussion section you attend. For the same reason, do not use electronic media in class without explicit permission.

Clicker discussion questions in lecture will be the major (but not only) part of your class participation grade. 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. Your two lowest lecture participation days will be automatically dropped. Forgetting your clicker counts as missing a class, so please remember to bring it!


Class Preparation: Reading Quizzes and Discussion

Reading the textbook selectively in advance of class to get an overview of the definitions and theorems before they are discussed is an important tool for learning. To encourage you to do this, there will be 9 short online reading quizzes on TritonEd that will be graded on the correctness of your answers. If you do the suggested preparation, the reading quiz will be easy, and you will get an excellent grade nearly every time.

To receive credit for each quiz, you should read the relevant sections of the textbook and then complete and submit the quiz by the due time on the due date. Reading quizzes are open book, and you have as much time as you want, as long as you submit by the due date and time. You can only submit once; there are no retakes. Reading quizzes should be completed individually . We will drop your lowest score and take the average score for the remaining reading quizzes. Please note that reading quizzes are not scheduled before every class; you are responsible for checking the schedule for reading quiz due dates. There will be no makeups for missed reading quizzes.

Discussion sections (scheduled on Mondays) are designed to ease your start on the homework problems, generally due on Fridays, or to review material for an upcoming exam. We highly recommend that you attend one of the four discussion sections each week. Each of the four scheduled discussion sections each week will cover identical material, and you need only attend one session fully and submit your discussion worksheet to get credit for that week. One discussion section grade will be dropped from your overall discussion participation grade.

While we highly recommend BOTH taking all the reading quizzes by the due date and attending one discussion session per week, we know your class preparation time is limited. Therefore, doing EITHER will satisfy your class preparation requirement. Note that your class preparation grade component is the MAX of your reading quiz grade and your discussion attendance grade, not their SUM, so doing half of each only earns 2.5% out of a total of 5%.

iClicker Participation

You are required to have an iClicker for this course, and to bring it to each lecture and discussion section you attend. You must register your iClickers on TritonEd by the end of the second week (April 8, 2016).

Clicker questions in lecture will be graded for participation only and not correctness of the response, unless otherwise noted. Full credit for clicker points for a given class will be awarded for clicking in at least 80% of the time that day. Your two lowest lecture participation days will be automatically dropped. Forgetting your clicker counts as missing a class, so please remember to bring it! Discussion participation is recorded via attendance sheets.

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 grade (50%) on the final exam in order to pass the course (regardless of total percentage):

A B C D F
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. We emphasize that you must receive at least 50 % on the final exam in order to pass the course.

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.


Regrades:

All grades are fixed 3 days after being reported in gradescope. Please be prompt (< 3 days) in reporting to the TAs any errors in the grading of your work, or in the recording of the grade. Regrade requests should be made by gradescope and should only be used if you believe there was an error in the grading. Requests for clarification of the rubric or how it was applied should be made in person in office hours or by private post to the instructors using our Piazza site, with subject "HW Grade Inquiry".


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



CSE 105 Academic Integrity policy:

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.

Top


Textbook

The textbook for this course is

Sipser, Michael   Introduction to the Theory of Computation, Second Edition

There is a later third edition of Sipser's book, but we are using the second edition because it has everything we need, and is less expensive. A "second international edition" is available at the bookstore, and is fine for our use as well.



An iClicker is also required, and is available at the bookstore. You should register your iclicker on TritonEd, if you have not done so already, and make sure you bring it to every class.



If you want 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)


Homework Assignments and Lecture Notes



Homework Assignments will be posted on the Class Schedule above and are due by the date and time indicated in the schedule above. The PDF of your group's homework solutions should be submitted via gradescope . Homework solutions will be posted on TritonEd.

Lecture Notes for each section will be posted on the Class Schedule after each class. Lecture podcasts for each section will be available at podcast.ucsd.edu

Top


LaTeX, JFLAP, and Other 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.



LaTeX Cloud Resources:



The easiest way to get started with LaTeX is one of the following free resources:

Both are reasonably easy to use and require registration.



Other LaTeX Resources:



JFLAP:



General J-FLAP Info

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.


Class Meetings

DateTimeLocation
Lecture A00 TuTh9:30am - 10:50amCENTR 101
Midterm Exam 1(section A) Wed April 20, 20168:00pm - 9:50pmWLH 2001
Midterm Exam 2(section A) Wed May 11, 20168:00pm - 9:50pmWLH 2001
Final Exam (section A) Sat Jun 4, 2016 11:30am - 2:29pmWLH 2001
Lecture B00 TuTh11:00am - 12:20pmCENTR 101
Midterm Exam 1(section B) Wed April 20, 20168:00pm - 9:50pmSOLIS 107
Midterm Exam 2(section B) Wed May 11, 20168:00pm - 9:50pmSOLIS 107
Final Exam (section B) Sat Jun 4, 2016 11:30am - 2:29pmPeterson 108
Discussion 1 (open to all) Mon11:00am - 11:50amSOLIS 104
Discussion 2 (open to all) Mon1:00pm - 1:50pmCENTR 105
Discussion 3 (open to all) Mon3:00pm - 3:50pmSOLIS 104
Discussion 4 (open to all) Mon4:00pm - 4:50pmSOLIS 104

There are 2 sections of the class, with joint homework, discussion sections, and examinations. 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).

Top


Schedule

Homework is due via gradescope by 11:59 pm on the due date (usually Fridays, but some on Wednesdays). The weekly reading quizzes are due by 11:59 pm on the due date (usually Wednesday or Monday). You are responsible for keeping track of due dates.


NOTE: Subject to change throughout the quarter.

>
DateDaySubjectReferenceNotes
3/28/16 Mon Discussion section Sipser 0
Strings, closure
Review class web site info
3/29/16 Tues Introduction, Deterministic Finite Automata (DFA) Sipser 0, 1.1 Section A Lecture Notes Section B Lecture Notes
3/30/16 Wed 11:59 pm Sipser 1.1 Reading Quiz 1
3/31/16 Thu Designing DFA, Regular Languages, Closure of Regular Languages Section A POST Lecture Notes Section B PRE Lecture Notes
4/1/16 Fri 11:59 pm HW 1 Due
TeX source and class file
4/4/16 Mon Discussion section
4/5/16 Tues More on Closure of Regular Languages, Introduction to Nondeterministic FA (NFA) Sipser 1.2 Section A POST Lecture Notes
Section B POST Lecture Notes
4/6/16 Wed 11:59 pm Sipser 1.2 Reading Quiz 2
4/7/16 Thurs Designing NFA, NFA-DFA Equivalence, Another Closure Proof Sipser 1.2 Section A POST Lecture Notes
Section B POST Lecture Notes
4/8/16 Fri 11:59 pm HW 2 Due
TeX source and class file
4/11/16 Mon Discussion section
4/12/16 Tues Regular Expressions; An Introduction to Non-Regular Languages Sipser 1.3 Section A POST Lecture Notes
Section B POST Lecture Notes
4/13/16 Wed 11:59 pm Sipser 1.3, 1.4, pp. 176-179 Reading Quiz 3
4/14/16 Thurs Non-Regular Languages Sipser 1.4, pp. 176-179 Section A POST Lecture Notes
Section B POST Lecture Notes
4/15/16 Fri 11:59 pm HW 3 Due
TeX source and class file
4/18/16 Mon Discussion section
4/19/16 Tues Using the Pumping Lemma Sipser 1.4 Section A POST Lecture Notes
Section B POST Lecture Notes
4/20/16 Wed 8:00 - 9:50 pm Exam 1
4/21/16 Thurs Context-Free Grammars, Ambiguity Sipser 2.1 Section A POST Lecture Notes
Section B PRE Lecture Notes
4/25/16 Mon Discussion section
4/25/16 Mon 11:59 pm Sipser 2.1, 2.2 Reading Quiz 4
4/26/16 Tues Push-Down Automata (PDA's) Sipser 2.2 Section A POST Lecture Notes
Section B POST Lecture Notes
4/27/16 Wed 11:59 pm HW 4 Due *REVISED 4/21*
TeX source *REVISED 4/21* and class file
4/28/16 Thurs Review of CFG and PDA's; Introduction to Turing Machines Section A POST Lecture Notes
Section B POST Lecture Notes
4/30/16 Sat 11:59 pm Sipser 2.1 - 2.2 OPTIONAL Reading Quiz 4B
5/2/16 Mon Discussion section
5/2/16 Mon 11:59 pm Sipser 3.1 - 3.3 Reading Quiz 5
5/3/16 Tues Turing Machines (TM's) Sipser 3.1 Section A POST Lecture Notes
Section B POST Lecture Notes
5/5/16 Thurs More TM's (Variants, Algorithms, Church-Turing Thesis) Sipser 3.2, 3.3 Section A POST Lecture Notes
Section B POST Lecture Notes
5/6/16 Fri 11:59 pm HW 5 Due
TeX source and class file
5/8/16 Mon Discussion section
5/9/16 Mon 11:59 pm Sipser 3.3, 4.1 Reading Quiz 6
5/10/16 Tues Decidability Sipser 4.1 Section A POST Lecture Notes
Section B POST Lecture Notes
5/11/16 Wed 8:00 - 9:50 pm Exam 2
5/12/16 Thurs Counting Infinite Sets, Paradoxes and Diagonalization; Undecidability: The Acceptance Problem for TM's Sipser 4.2 Section A POST Lecture Notes
Section B POST Lecture Notes
5/16/16 Mon Discussion section
5/16/16 Mon 11:59 pm Sipser 4.2 Reading Quiz 7
5/17/16 Tues The Halting Problem for TM's and Other Undecidable Problems Sipser 4.2 Section A POST Lecture Notes
Section B POST Lecture Notes
Scooping the Loop Snooper: A Proof that the Halting Problem is Undecidable
5/18/16 Wed 11:59 pm HW 6 Due (updated with correct due day)
TeX source and class file
5/19/16 Thurs More Undecidable Problems Sipser 5.1 Section A POST Lecture Notes
Section B POST Lecture Notes
5/23/16 Mon Discussion section
5/23/16 Mon 11:59 pm Sipser 5.1 (no computation histories) Reading Quiz 8
5/24/16 Tues Undecidability and Unrecognizability Sipser 5.1 Section A POST Lecture Notes
Section B POST Lecture Notes
5/26/16 Thurs Time Complexity and the class P Sipser 7.1 Section A POST Lecture Notes
Section B POST Lecture Notes
5/27/16 Fri 11:59 pm HW 7 Due
TeX source and class file
5/30/16 Mon No Discussion section (holiday)
5/30/16 Mon 11:59 pm Sipser 7.1 - 7.3, p. 271 in 7.4 Reading Quiz 9
5/31/16 Tues P, NP, and NP Completeness Sipser 7.2, 7.3, p. 271 in 7.4 Section A POST Lecture Notes
Section B POST Lecture Notes
6/2/16 Thurs Final Exam Review Section A POST Lecture Notes
Section B POST Lecture Notes
6/4/16 Saturday Final Exam 11:30 am - 2:29 pm, Location:Check Class Meetings

Top