Section ID: 797377
Course Description: This course introduces the basic, formal ideas underlying the notion of computation. Syllabus: finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, decidability, undecidability, the halting problem, Turing reductions, map reductions, introduction to computational complexity.
Textbook: Sipser, Introduction to the Theory of Computation. The UCSD bookstore sells a custom edition of the book, containing only the portion that will be covered in this course, corresponding to Chapters 0-5 (second edition). If you already have the full book, that's fine too, and you can keep reading after the course is over. (Any edition of the book is fine: we will not cover the additional material in Ch. 2 of the third edition.)
Discussion board: We will be using Piazza for class discussion, posting important announcements, distributing assignments, etc. Sign up for the class on piazza clicking here and following the instructions.
Tools: Homework assignments will use JFLAP, a java program for experimenting with automata and formal languages. Follow the link to download jflap.
| Schedule | Day | Time | Room |
| Lectures | Monday, Wednesday, Friday | 11:00am-11:50am | PCYNCH 106 |
| Discussion | Wednesday | 3:00pm-3:50pm | CENTR 216 |
| Discussion | Wednesday | 4:00pm-4:50pm | CENTR 216 |
| Midterm 1 | Fri Jan 24 | 11:00am-11:50:am | PCYNH 106 |
| Midterm 2 | Fri Feb 21 | 11:00am-11:50am | PCYNH 106 |
| Final | Monday March 17 | 11:30am-2:20pm | PCYNH 106 |
Use staff email only for questions that require individual attention. Otherwise, post your question on piazza. If unsure if you question can be publicly posted, you can post it on piazza and mark it as "private", so that they are initially visible only to the instructor.
| Name | Office Hours | Room | ||
| Instructor | Daniele Micciancio | Wednesday 1:00pm-3:00pm | EBU3b 4214 | daniele(at)eng.ucsd.edu |
| TA | Nathan Feldman | Thursday 3:00pm-5:00pm | EBU3b B240A | ngfeldma(at)eng.ucsd.edu |
| TA | Sandy Wiraatmadja | Monday 2:00pm-4:00pm | EBU3b B250A | swiraatm(at)ucsd.edu |
| TA | Mark Saroufim | Tuesday 4:00-6:00pm | EBU3b Basement | msaroufi(at)ucsd.edu |
| TA | Ashna Jain | Friday 4:00-5:00pm | EBU3b B275 | asj008(at)ucsd.edu |
| Homework | Reading | Notes | |
|---|---|---|---|
| Week 1 (1/6-1/10) | HW 1 | Ch. 0, Ch. 1.1 | Lecture Notes: DFA/NFA |
| Week 2 (1/13-1/17) | HW 2 | Ch. 1.2, Ch. 1.3 | Notes on haskell |
| Week 3 (1/21-1/24) | Review | Monday: MLK Day holiday. Friday: Midterm 1 | |
| Week 4 (1/27-1/31) | HW 3 sample email |
Ch. 1.4 + Notes | Lecture Notes: Transducers, FST in haskell |
| Week 5 (2/3-2/7) | HW 4 | Ch. 2.1, 2.2 | A nonregular language |
| Week 6 (2/10-2/14) | HW 5 | Ch. 2.3, 3.1 | |
| Week 7 (2/18-2/21) | Review | Monday: President's Day. Friday: Midterm 2 | |
| Week 8 (2/24-2/28) | HW 6 | Ch. 3.2, 3.3, 4 | |
| Week 9 (3/3-3/7) | HW 7 | Ch. 5 | |
| Week 10 (3/10-3/14) | Review |
Exams. There will be 7 homework assignments, 2 midterm exams, and a final. Midterm exams are scheduled during regular lecture hours and everybody is expected to attend. There will be no make up midterm or final. Not showing up to either exam will count as 0 grade, unless your absence is due to a demonstrated personal health problem at the time. You can take the textbook and 1 double sided sheet of notes to each midterm or final exam, but due to the limited amount of space in the classroom, you are not allowed to bring any other material for consultation. Also, the book and/or notes must be your own. You won't be allowed to share book/notes with other students.
Homework assignments will typically go out on Wednesday, and be due the following Wednesday. (No late submissions accepted.) Homework will not be formally graded. Unless specified otherwise on the assignment, you will receive 2 points for a complete submission that passes all checks, 1 point for an incomplete or partially correct submission, and 0 if you miss the submission deadline or submit a grossly incomplete/incorrect solution. Submission instructions may vary, and will be specified on every assignment. Your class grade will be based on your Homework submissions (10% total), the two Midterm exams (20% each), and the final (50%).
Grades will be available through GradeSource. If you are enrolled in the class you will receive an email from gradesource with instructions and a secret number to access your grades. Final grades will be based roughly on the following scale: 50-55% (D), 55-70% (C), 70-85% (B), 85-100% (A), with (+) and (-) assigned to the instructor discretion. This includes, but is not limited to improvement over the quarter, class participation, and natural "breaks" in the distribution of scores.
Regrade requests. Regrades on midterm exams are only accepted within a week after the graded object has been returned. Do not modify your solutions after they are returned to you. If you alter your solutions, you loose any right to request a regrade of that exam. Modifying the exam and then bringing it back to ask for a regrade will be treated as a violation of academic honesty rules, and so prosecuted.
Academic honesty: All students are expected to be familiar with and abide by the rules of UCSD Policy on Integrity of Scholarship as described in the UCSD General Catalog. In case of cheating, such policy will be enforced. This means an F grade in the course, and action by the Dean of your college (probation or suspension from UCSD). You are encouraged to form study groups to discuss the material presented in class and the homework assignments. However, you should write the solutions to the homework on your own. You can use Internet, additional textbooks, and any material you find useful as a study tool. However, the use of any such resource in the solution of homeworks assignments should be clearly aknowledged in your solutions. No form of collaboration is allowed during midterm and final exams.