This web page (http://www-cse.ucsd.edu/classes/wi00/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, fornal 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, NP-completeness.
| Day | Time | Room | |
| Lectures | Mon, Wed, Fri | 11:15-12:05 | Center 214 |
| Discussions | Monday | 12:20-1:10 | Peter 104 |
| 1:25-2:15 | WLH 2208 |
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 | Wed. 2-4pm | AP&M 5230 | dmiccian@ucsd.edu |
| TAs | Jee Hea An | Thu. 2-3:30pm | AP&M 3337D | jeehea@cs.ucsd.edu |
| Qiao Xin(Joy) | Tue. 12:45-2:15pm | AP&M 3349D | qxin@cs.ucsd.edu |
TAs can be reached using email address cse105ta@cs.ucsd.edu.
Prerequisite for the class are CSE 10 or 11 (Intro to Computer Science) and CSE 20 (Discrete Math).
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), Midterms (30%, 15% each), Final (40%).
Homeworks will be due at the beginning of class, generally on Friday. Late problem sets will NOT be accepted, no exceptions. If you conldn'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 paper 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).
Midterms will take place in class during regular lecture hours. Midterms are tentatively scheduled at the beginning of February and March. Exact dates will be announced at least one week in advance. There will be no makeup midterms, and missing a midterm exam will count as 0.
You will be allowed to use the textbook and course notes during the exam, but they must be your own. No other references allowed.
No form of collaboration with other students allowed during midterms and final, of course! (This includes passing around books and course notes. If you want to use the textbook or some notes you must bring your own.)