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.

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.

- Final is scheduled on Monday March 19, 7:00pm - 9:59pm in
**Center 212** - Monday March 19 office hours will be held in Room
**AP&M 5218**, instead of 3337D. Time is 12:00-1:30 as usual. - Here is a list of practice problems for the final
- Homework 5 solutions are ready
- Homework 4 solutions are available
- Notes (ps,pdf) on Alejandro's discussion of Feb 16.
- Notes (ps,pdf) on Alejandro's discussion of Jan 26 and solutions (ps,pdf) to the suggested problems

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 | ||

Instructor | Daniele Micciancio | Wed 2:30p-3:50p | AP&M 5230 | dmiccian@ucsd.edu |

TAs |
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 |

- Problem Set 1 (ps, pdf). Solutions (ps,pdf)
- Problem Set 2 (ps, pdf). Solutions (ps,pdf)
- Problem Set 3 (ps, pdf). Solutions (ps,pdf)
- Problem Set 4 (ps, pdf). Solutions (ps,pdf)
- Problem Set 5 (ps,pdf). Solutions (ps,pdf)

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:

- Attending lectures
- Reading from the textbook
- 5 Homework assignments
- 1 Midterm exam
- 1 Final exam

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.