CSE 105 Course Description

This course introduces the basic, formal ideas underlying the notion of computation:

• regular expressions and finite automata (Chapter 1)
• context-free grammars and pushdown automata (Chapter 2)
• computability (Section 31, 3.3)
• decidability, reducibility, and the halting problem (Chapter 4, Section 5.1, 5.3)
• complexity of problems and NP-completeness (Chapter 7)

• Lectures given by the instructor
• Discussion sections and office hours given by the TA's to answer questions about the lecture, readings, and homeworks
• Readings from the textbook and the web
• Homeworks (ungraded) based on the lectures and readings; solutions will be provided.
• Exams: 3 scheduled in class, closed book quizzes, and a final exam during finals week. Exams cover the material in lectures, readings and homeworks