This web page (http://www-cse.ucsd.edu/classes/wi02/cse105/) will be used to make important announcements related to the course. All class members are responsible for reading information on the web page, and checking it frequently for updates.
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, introduction to complexity theory.
| Day | Time | Room | |
| Lectures | Tuesday, Thursday | 8:00p-9:20p | Center 113 |
| Discussions | Friday | 3:35 & 4:40 | Center 113 |
Introduction to the Theory of Computation by Mike Sipser, PWS Publishing Co., 1997.
See book website for Errata.
| Name | Office Hours | Room | ||
| Instructor | Daniele Micciancio | Tue 2:00p-3:00p | AP&M 5230 | dmiccian@ucsd.edu |
TAs |
Sashka Davis | Mon. 1:30p-2:30p | AP&M 3337-A | sdavis@cs.ucsd.edu |
| Dan Liu | Wed 12:00p-1:00p | AP&M 2331 | d3liu@cs.ucsd.edu |
| Total | Average | Std. Dev. | |
| HW1 | 40 | 35.95 | 4.40 |
| HW2 | 40 | 33.45 | 4.30 |
| HW3 | 40 | 15.86 | 7.15 |
| MT | 30 | 22.27 | 5.12 |
| HW4 | 40 | 26.05 | 7.25 |
| HW5 | 30 | 20.78 | 4.31 |
Chapter 0: The material covered in this chapter is prerequisite to this course. This material will not be explicitly covered in class, but you are supposed to read the chapter to make sure you have the necessary background.
Below are some pointers to where in the textbook you can find the material covered in each lecture. The book also contains many excercises and problems at the end of each chapter. You are encouraged to try solve them (in addition to the regularly assigned homeworks of course). That's the best way to test your understanding and problem solving abilities.
Class members are expected to do all of the following in order to satisfactorily pass this class:
Homeworks, midterms and the final exam will contribute to the final grade according to the following percentages: Homeworks (30%, 5% each), Midterm (30%), Final (40%).
Homeworks will be due at the beginning of class, on Tuesday or Thursday as specified on the problem set. Late homeworks will NOT be accepted, no exceptions. If you can't solve all the problems, just sumbit what you have for partial credit. If you do not submit your solutions by the due date, it will count as 0.
Collaboration policy: Talking with other students about assignments is acceptable, as long as you write up the work on your own and clearly acknowledge any collaboration. (I.e., if you talk to student X about problem Y, write at the beginning of your homework "I talked to X about problem Y"). Copying from another assignment, book or other resource is cheating and will be taken very seriously. In case of cheating we will enforce the UCSD Policy on Integrity of Scholarship. This means an F grade in the course, and action by the Dean of your college (probation or suspension from UCSD).
Midterm will take place in class during regular lecture hours on February 7. There will be no makeup midterms, and missing the midterm exam will count as 0. The exam will be closed book, closed notes. You can take one double sided sheet of notes to the exam.