Section ID: 781670
Course Webpage: http://www-cse.ucsd.edu/classes/sp13/cse105-b/
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, Turing reductions, map reductions, introduction to computational complexity.
Textbook: Sipser, Introduction to the Theory of Computation. The UCSD bookstore sells a custom edition of the book, containing only the portion that will be covered in this course, corresponding to Chapters 0-5. If you already have the full book (2nd edition), that's fine too, and you can keep reading after the course is over.
Discussion board: We will be using Piazza as a discussion board.
| Schedule | Day | Time | Room |
| Lectures | Monday, Wednesday, Friday | 10:00am-10:50am | CSB 001 |
| Discussion | TBA | ||
| Discussion | TBA | ||
| Midterm 1 | TBA | 10:00am-10:50:am | CSB 001 |
| Midterm 2 | TBA | 10:00am-10:50am | CSB 001 |
| Final | TBA |
| Name | Office Hours | Room | ||
| Instructor | Daniele Micciancio | Tuesday 1:30pm-3:00pm | EBU3b 4214 | daniele(at)eng.ucsd.edu |
| TA | Olivia Simpson | osimpson(at)cs.ucsd.edu | ||
| TA | Brendan Duncan | baduncan(at)cs.ucsd.edu |