This course provides an introduction to models of computation and computability. In particular, we will ask the question,

• Determinstic finite automata (DFA), Non-deterministic finite automata (NFA), and their equivalence.
• Regular expressions, equivalence between regular expressions and finite automata, properties of regular languages, and the pumping lemma.
• Context-free grammars (CFG), properties of context-free languages, and pushdown automata.
• Turing machines (TM), variants of TMs, and Church-Turing Thesis.
• Undecidable problems, diagonalization, and Rice's Theorem.
• Unrecognizable problems.

Instructor
Seung Geol Choi (Office hours: Stop in anytime, or email for an appointment. Research day is Thursday)

Links

• Course homepage: http://www.usna.edu/Users/cs/choi/courses/si340/f13/index.html
• Calendar: http://www.usna.edu/Users/cs/choi/courses/si340/f13/si340.html

Learning Objectives

• Understand the various models of computation, from both the formal language and the corresponding machine model perspective;
• Apply the mathematical methods that let us describe computation and language in order to understand formal algorithms.

Program Outcomes - Goals for the whole major to which this course contributes

• (PO a) An ability to apply knowledge of computing and mathematics appropriate to the discipline
• (CS-j) An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices

Textbook
We will use Introduction to the Theory of Computation, Third Edition by Michael Sipser, Course Technology.

Extra Instruction
You are strongly encouraged to come in for extra instruction (EI) when you are having trouble. You may just stop by your instructor's office, or make an appointment in advance to ensure availability. If you miss class, get the notes from the section leader or other classmate.

Grading
The break-down on your final grades will be:

• 20%: Homeworks
• 6%: Quizzes
• 34%: Exams 1 and 2
• 40%: Final Exam

Honor
You are required to abide by the USNA and department honor policies at all times , including, but not limited to: The Honor Concept of the Brigade of Midshipmen, and the Policies Concerning Graded Academic Work.

You may discuss homework problems with your classmates freely, but must write your own solution, and list the names of all people that you collaborated with. If you use a source other than the textbook in doing your homework, explain the material from the source in your own words and acknowledge the source. Collaboration without acknowledgment is considered cheating. In any case, you are not allowed to look at written solutions of any other student (even if you worked on solving the homework together) or of any other external sources.

Section Leader
The duties of the section leader include:

• calling the section to attention at the beginning and end of class reporting absences to the instructor
• contacting the department office (3-6800, Room 346) if the instructor is more than 10 minutes late for class
• directing the class in productive work if the instructor is absent

Abscences
You are responsible for obtaining any material missed due to an absence. You must ensure your work is submitted on time regardless of other commitments, i.e. duty, sick call, MO, etc. Should emergencies arise, it is your responsibility to coordinate in advance with the instructor (emergency leave, hospitalization, SIR, etc.).

There will be no make-up for missed quizzes. You can miss at most two quizzes with little harm, but you must accept the consequence missing more than two.

Classroom Decorum
Beverages are permitted in classrooms and labs provided they are in closed containers. No food is permitted in classrooms or labs. You are not allowed to use a laptop or a smartphone during the lecture.