Welcome to CS 311: Theory of Computation.

Updates [2014-10-28 Tue]:

• Moved up HW 2 due date to 11/6

Updates [2014-10-20 Mon]:

• Assignment 5 has been dropped
• Syllabus has been adjusted to slow pace of course slightly
• Assignments will now each be 17.5 % of grade, putting slightly more emphasis on final but not really changing overall course dynamic
• Assignment due dates have been redistributed

Updates [2014-10-07 Tue]:

• The first homework has been pushed back to 10/21 from 10/16
• Future homeworks are pushed back accordingly
• Any adjustments to overall syllabus will be reflected in the syllabus document

Most of the materials for this course will be found in this repository: lecture notes, assignments, and material for studying for the final.

Let's talk about the goals of this course. By the end of this class I want everyone to

• Be able to construct basic finite automata (DFAs, NFAs, PDAs) and context-free grammars (CFGs)
• Understand the relationship between regular expressions and DFAs
• Understand the relationship between PDFs and CFGs
• Be able to prove that a language isn't regular using the regular language pumping lemma
• Be able to prove that a language isn't context-free using the context-free pumping lemma
• Define Turing machines to solve simple algorithmic problems
• Understand the distinction between decidable and recognizable languages
• Understand how to prove, using computational reductions, whether or not a language is decidable or recognizable
• Know the definitions of the language classes P and NP and what it means to be NP-complete and NP-hard

We'll also explore a bit on lambda calculi and, time permitting, a bit on constructive logic and maybe even spend a little time on theorem provers.

There will be a total of five assignments in this course and a final. Each assignment will be 15% of your final grade and the final will be 25% of your grade. Assignments can be done as part of a group, but you must include the names of all members of the group on the assignment. There will roughly be an assignment due every two weeks. There will also be in-class worksheets for practice every lecture, to help break up the monotony of hearing me talk for two hours straight. These will be ungraded, but are intended for you to get immediate feedback on whether you understand the material and to ask me questions while I'm right in front of you. I also highly encourage everyone to work in small groups of 2-3 on the in-class exercises.

I will not be grading on attendance, but if you skim the lecture notes and worksheets and aren't immediately comfortable with all the material therein I'd still recommend attending lecture so you can ask questions and practice with your fellow students.

There is a google group for the course found here: https://groups.google.com/forum/#!forum/cs-311