Welcome to the home page for a Fall 2016 offering of Theory of Computation CS 3800

Piazza page: https://piazza.com/northeastern/fall2016/cs3800/home

FAQ: http://www.ccs.neu.edu/home/viola/classes/faq.txt

-----------------------------------------------------

This class is recorded. You can watch the videos using Tegrity or Blackboard.


-----------------------------------------------------

Class: 11:45 am - 1:25 pm 	MR 	Cargill Hall 097 	Sep 07, 2016 - Dec 07, 2016 	 

Instructor: Emanuele Viola. Office: #338 West Village H (WVH). Office hours: Monday 2:30 - 3:30, and by appointment. See schedule for changes to office hours. Email: viola@our college

Teaching assistant: Chin Ho Lee. Office hours 10:30am - 11:30am on Wednesday. See Piazza announcement for location. Email: chlee@our college

Teaching assistant: Chinmayee Nitin Vaidya <vaidya.c@husky.neu.edu> Office hours 4pm-5pm Friday. See Piazza announcement for location.

-----------------------------------------------------
Readings:

We will be following closely the slides available on the instructor's web page http://www.ccs.neu.edu/home/viola/#Slides
Note: Slides may be updated throughout the course. Make sure you have the last version.

You do not need to buy any book for this class. However, we list next a few books that cover overlapping material:

¦ Introduction to Automata Theory, Languages, and Computation, Hopcroft, Motwani, Ullman.

¦ Introduction to the Theory of Computation, Sipser.


Syllabus:

+ Introduction

+ Mathematical background

+ Regular languages and finite automata
--- DFAs
--- regular operations
--- closure properties
--- non-determinism
--- equivalence of NFAs and DFAs
--- regular expressions
--- equivalence of RE and FA
--- the pumping lemma

+ Context-free languages and pushdown automata
--- context-free grammars
--- ambiguity
--- pushdown automata
--- equivalence of CFLs and PDAs
--- pumping lemma for CFLs
--- closure properties

+ Turing Machines and Computability
--- Turing Machine variants
--- Church-Turing thesis
--- cardinality of infinite sets
--- diagonalization
--- undecidability
--- Halting Problem
--- reducibility
--- Rice's theorem

+ Complexity
--- P and NP
--- NP-Completeness
--- the Cook-Levin Theorem
--- EXP, PH, BPP
-----------------------------------------------------

Tentative schedule

2016-09-08 Thu
2016-09-12 Mon
2016-09-15 Thu PS OUT
2016-09-19 Mon
2016-09-22 Thu PS DUE
2016-09-26 Mon
2016-09-29 Thu PS OUT
2016-10-03 Mon
2016-10-06 Thu PS DUE
2016-10-10 Mon Columbus Day--no classes, no office hours
2016-10-13 Thu Extra office hours: 2:30 - 3:30
2016-10-17 Mon QUIZ 1
2016-10-20 Thu
2016-10-24 Mon
2016-10-27 Thu PS3OUT
2016-10-31 Mon
2016-11-03 Thu PS3DUE
2016-11-07 Mon
2016-11-10 Thu Quiz 2
2016-11-14 Mon
2016-11-17 Thu
2016-11-21 Mon PS 4 out
2016-11-24 Thu Thanksgiving -- no classes
2016-11-28 Mon
2016-12-01 Thu PS 4 due
2016-12-05 Mon

12/9 Fri First day of final exams
12/16 Fri Last day of final exams
12/17 Sat Makeup day for exams if needed
12/18 Sun Winter vacation begins
12/19 Mon Final grades due by 2:00 PM

---

Grading:
Your final grade is calculated as follows:

: Quizzes: 84%
: Problem Sets: 16%

There will be about 3 quizzes. The last quiz will be held during exam week. The other quizzes will be held during regular class times. Quizzes are "closed-book." You cannot bring any book, notes, or electronic device. Each quiz is worth the same fraction of your grade.

Your least-scoring problem-set will be "dropped." That is, it will not count toward your final problem-set grade.