CSE 105: Theory of Computation (Spring, 2006)

Discussion Section: The discussions sections will cover material (for which you'll be responsible) that augments that of the lectures. You'll be assigned to one of the following mandatory discussion sections.

Friday 8-8:50 WLH 2110 (Lucas)
Friday 1-1:50 WLH 2204 (Lucas)
Friday 2-2:50 Peterson 104 (Lawrence)
Friday 3-3:50 WLH 2110 (Lawrence)

Course Objectives: This course gives a precise definition of the notion of an algorithm as well as developing a theory of automata and formal languages. The course stresses the understanding of the basic concepts and constructions.

An introduction to the mathematical theory of computability. Formal languages. Finite automata and regular expression. Push-down automata and context-free languages. Computable or recursive functions: Turing machines, the halting problem. Undecidability.

Discussion Board: his class has a discussion board available. It's monitored by TAs and the instructor. You'll find it a good place to go for help (although office hours are good, too!).

Textbooks:

Introduction to the Theory of Computation, 2nd edition by M. Sipser (available from the bookstore)

Academic honesty

All students are expected to be familiar with and abide by the rules of UCSD Policy on Integrity of Scholarship as described in the UCSD General Catalog. In case of cheating, such policy will be enforced. This means an F grade in the course, and action by the Dean of your college (probation or suspension from UCSD). You are allowed (and encouraged) to collaborate with other students in doing the homeworks. No form of collaboration is allowed during the quizzes and final exam.

Grades

A final overall percentage score will be calculated based on the weighted average of the scores earned on exams and quizzes. This percentage score will be used to determine a final letter grade as follows:

90%-100%	A
80%-90%	B
65%-80%	C
50%-65%	D
<50%	F

Pluses and minuses will be attached to the letter grades as the instructor deems appropriate.