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.

Announcements

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

Course Schedule

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

Textbook

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

See book website for Errata.

Staff

	Name	Office Hours	Room	Email
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

Homeworks

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)

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:

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.