CSE 105, Winter '01 - Introduction to the Theory of Computation

This web page (http://www-cse.ucsd.edu/classes/wi01/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.

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, introduction to complexity theory.


Course Schedule

Day Time Room
Lectures Tuesday, Thursday 6:00p-7:20p Center 212
Discussions Friday 12:20p-1:10p CSB 001


Introduction to the Theory of Computation by Mike Sipser, PWS Publishing Co., 1997.

See book website for Errata.


Name Office Hours Room Email
Instructor Daniele Micciancio Wed 2:30p-3:50p AP&M 5230 dmiccian@ucsd.edu


Jee Hea An Thu 11:00a-12:30p AP&M 3337A jeehea@cs.ucsd.edu
Alejandro Hevia Mon 12:00p-1:30p AP&M 3337D ahevia@cs.ucsd.edu


Course Requirements and Grading

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%, 6% 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 on Tuesday February 6 during regular lecture hours. There will be no makeup midterms, and missing the midterm exam will count as 0. The exam will be closed book.