Professor Fran Berman
AP&M 4202
Office Hours: TBA
This course will cover topics from automata and formal language theory including finite state automata (FSAs, PDAs, Turing Machines), formal languages (regular, context-free and unrestricted grammars), and undecidability (the halting problem, reductions from unsolvable problems, etc.). Prerequisites for the course are CSE 9B or CSE 10 or CSE 11 and CSE 20 or consent of the instructor.
The concepts in this course are mathematical in nature and reasonably sophisticated. You will be in the best shape if you have some degree of familiarity with proofs and manipulating mathematical symbols. You should expect the course to be challenging but stick with it. The best way to learn the material in this course is to spend time on it, i.e. read the book and do the problems. The TAs, reader, and Professor will be available if you have trouble.
Homework will be given and collected roughly every week and a half. There will be one midterm and one final exam. Your course grade will be determined from the two exams and the homework (normalized to 100) all weighted equally.
The TAs for this course are Skip Garibaldi (skip@math.ucsd.edu) and Giovanni di Crescenzo (giovanni@cs.ucsd.edu). The reader for this course is Adam Heine (aheine@ucsd.edu). The required text is Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman. You may find it helpful to look at other texts on the same material. There are a number of other automata theory books in the Science and Engineering Library including a very good one by Lewis and Papadimitriou (Elements of the Theory of Computation, on class reserve). There will be a discussion section every Monday with the TA which will focus on problem-solving.
Homework is due at the beginning of class on the day given on the assignment. Late homework will only be accepted at the beginning of the next (regular) class period and will be marked off 10%. After that, late homework will not be accepted.
We recognize that it is unrealistic to assume that you will not talk to other students in the course about homework problems, but it is considered plagarism to turn in uncredited work that is not your own. If you talk to other students about the problems, make sure that your write-up is your own. If you find the solution to a homework problem in a book or in the solutions to another problem set, the reference should be credited. Duplicate homework papers or problems will get a grade of 0. Since the tests will be based on the problem-solving skills learned doing the homework, the more time and effort you are able to put into the homework, the better shape you will be in for the exams.