Section ID: 465818
This web page (http://www-cse.ucsd.edu/classes/sp03/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,Syllabus: finite automata, regular expressions, context-free grammars, pushdown automata, turing machines, decidability, undecidability, the halting problem, introduction to complexity theory.
| Day | Time | Room | |
| Lectures | Tuesday, Thursday | 6:30p-7:50p | York 2722 |
| Discussions | Wednesday | 1:00-1:50 | Center 212 |
| Quiz 1 | Thursday April 17 | 6:30p-7:50p | York 2722 |
| Quiz 2 | Thursday May 8 | 6:30p-7:50p | York 2722 |
| Quiz 3 | Tuesday June 3 | 6:30p-7:50p | York 2722 |
| Final Exam | TBA | TBA | TBA |
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 | TBA | AP&M 4202 | dmiccian@ucsd.edu (*) |
TAs |
Jacob Sorensen | Tue & Thu. 1:00-2:30am | AP&M 3337D | jcsorens@cs.ucsd.edu |
| Min Qian | TBA | TBA | mqian@cs.ucsd.edu |
(*) If you want your messages to be read, you should send them from your ucsd email account in plain text format. Emails sent from external accounts (e.g., hotmail), with no return address, blank body and the message text included as an html attachment, may be automatically deteled by my email spam filter programs and are likely to never reach my email inbox..
You can access your grades and course statistics through WebCT.
Chapter 0: The material covered in this chapter is prerequisite to this course. This material will not be explicitly covered in class, but you are supposed to read the chapter to make sure you have the necessary background.
Below are some pointers to where in the textbook you can find the material covered in each lecture. The list is tentative, and will be updated lecture by lecture as the course goes on. The book also contains many excercises and problems at the end of each chapter. You are encouraged to try solve them (in addition to the regularly assigned homeworks of course). That's the best way to test your understanding and problem solving abilities.
The final exam will cover all of Chapters 1,2,3,4,5.
Class members are expected to do all of the following in order to satisfactorily pass this class:
Quizzes are scheduled during regular lecture hours, and everybody is expected to attend. There will be no make up quizzes. Not showing up to a quiz will count as 0 grade. Each quiz will account for 20% of the final grade, the final exam gives the remaining 40%. Both the quizes and the final exam will be closed books, closed notes. You can take 1 double sided sheet of notes to the exam, but the notes must be your own.
Grades will NOT be assigned on a curve. You will receive a grade based on your own performance. If everybody does well, everybody will get an A. Final grades will be based roughly on the following scale: 50-54 (D), 54-58 (C-), 58-62 (C), 62-66 (C+), 66-70 (B-), 70-75 (B), 75-80 (B+), 80-85 (A-), 85-90 (A), 90-100 (A+)
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.