COSI 30: "Theory Of Computation" - Spring 2012

CONTENTS

Lectures will cover an general introduction to the theory of computation, including regular sets and finite automata, context-free languages, Turing machines and undecidability, and computation complexity (NP-complete problems, etc.). The course centers on the basic theory and philosophy about the nature of computation, what is possible, and what resources are required. Students should have already taken a course in discrete mathematics. Assignments with have problems sets requiring reasoning about the concepts presented in class (little or no programming is required).

Learning Objectives:

To gain a fundamental understanding of the power and limits of basic models of computation, and to gain comfort with associated proof techniques.

Expected Learning Outcomes:

• The notion of a regular set and its representation by DFA's, NFA's, and regular expressions.
• The notion of a context-free language and its representation by context-free grammars and push-down automata.
• The notion of a universal model of computation and its representation by a Turing machine.
• The notion of an undecidable problem.
• Basic understanding of computational complexity and the P=NP problem.

Expected Skill Development:

• Basic proof techniques, such as proof by induction and diagonalization.
• Practical applications of regular expressions and context-free grammars.
• Basic approaches for accessing the complexity of computational tasks, and comfort with the basic notion of reducing one computational problem to another.
• Experience with giving a presentation of technical material.

The course will follow selected sections of:

Introduction to Automata Theory, Languages, and Computation
Hopcroft, Motwani, and Ullman
Addison Wesley, third Edition, hardcover, 535 pages.
ISBN-10: 0321462254
ISBN-13: 978-0321462251

Note: Earlier editions of this book are also ok, it will be straightforward to identify the equivalent sections for suggested reading.

Alternate book: This is also a great book; although reading will be assigned based on sections in the book above, it is easy to find the same sections in this book.

Introduction to The Theory Of Computation
Sipser
Course Technology, 2nd Edition, hardcover, 456 pages.
ISBN-10: 0534950973
ISBN-13: 978-0534950972

Monday, Wednesday
2:00pm - 3:20pm
Volen 106

Jim Storer
office: Volen 254
email: storer@cs.brandeis.edu
phone: 781-736-2714
web page: www.cs.brandeis.edu/~storer
Hours: Monday and Wednesday 1pm - 2pm, or by appointment

Kevin Thomas
Office: Volen 255
Phone: 781-736-2718
Email: ktho@cs.brandeis.edu
Hours: by appointment

Nine assignments and three quizzes all count equally. The lowest assignment score and the lowest score of Quiz 1 and Quiz 2 will be dropped, and the 10 remaining scores will each count 10% of the final grade. The final grade may then be adjusted by as much as 1/2 a grade based on class participation, class homework presentations, and exgtra credit work.

The schedule for when assignments are given and due is shown on the course calendar.

*** Solutions to assignments will be presented the day assignments are due; there is no credit for assignments passed in late or quizzes missed (except in cases of doctors note, etc.).

A significant portion of class time will be discussions and working out examples at the blackboard. Class attendance is strongly encouraged, and class attendance is required for the last two weeks of classes. Significant class participation may also serve to add an upward bias to the computation of the final grade.

This reading is not like a novel; you may have to read parts of it several times (and come back to specific sections when working on the homework).
Additional reading will be posted here each week:

Finite Automata and Regular Sets:

Chapter 2 (DFA's and NFA's)
Section 3.1 (regular expressions)
Section 3.2.3 (converting a regular expression to a NFA with epsilon moves)
Section 3.3 (application - the UNIX grep command)
Section 4.1 (the pumping lemma)
Section 4.2.1 (closure of regular sets under boolean operations)
Section 4.4 (DFA minimization)

Handouts cover material presented in class that is not in the book or is presented differently than in the book.
Additional handouts will be posted here each week:

Finite Automata and Regular Sets:

DFA Introduction
Regular Expressions And Pattern Matching
DFA = O(1) Memory
Example: First Halves Of Regular Sets Are Regular
Pumping Lemma For DFA's
DFA Minimization

The day of the class that an assignment is due, solutions to three of the assigned problems will be presented at the blackboard by students, according to a schedule maintained by the TA:

Assignment Solutions Presentation Schedule

Here are some guidelines for preparing assignments:

Assignment Guidelines

Assignments will be posted here a per the course calendar:

Assignment 1
Assignment 1 Solution Hints

Assignment 2

Academic honesty is essential for all coursework at Brandeis. The following handout is excerpted from a presentation made by Prof. Cherniack to new students (copyright by and courtesy of M. Cherniack, Brandeis Computer Science Department, 2011):

Academic Honesty Handout

Class meets Monday and Wednesday, 2:10 - 3:30pm.

Week 1: Introduction
    Wed, Jan 18

Week 2: Regular Sets and Finite Automata
    Mon, Jan 23 - HW1 assigned
    Wed, Jan 25

Week 3: Regular Sets and Finite Automata, continued
    Mon, Jan 30
    Wed, Feb 1 - Hw1 Due, HW2 assigned

Week 4: Regular Sets and Finite Automata, continued
    Mon, Feb 6
    Wed, Feb 8

Week 5: Regular Sets and Finite Automata, continued
    Mon, Feb 13 - Hw2 due / review
    Wed, Feb 15 - QUIZ 1

Week 6: NO CLASS (Midterm Recess)

Week 7: Context-Free Languages
    Mon, Feb 27 - HW3 assigned
    Wed, Feb 29

Week 8: Context-Free Languages, continued
    Mon, Mar 5 - Hw3 due, HW4 assigned
    Wed, Mar 7

Week 9: Context-Free Languages, continued
    Mon, Mar 12 - HW4 due, HW5 assigned
    Wed, Mar 14

Week 10: Context-Free Languages - Additional Topics and Review
    Mon, Mar 19 - Hw5 due / review
    Wed, Mar 21 - QUIZ 2

Week 11: Turing Machines
    Mon, Mar 26  - Hw6 assigned 
    Wed, Mar 28

Week 12: Turing Machines and Undecidability
    Mon, Apr 2 - Hw6 due, HW7 assigned
    Wed, Apr 4

Week 13: NO CLASS (Passover and spring recess)

Week 14: Undecidability continued
    Mon, Apr 16 - Hw7 due, Hw8 assigned, review
    Wed, Apr 18 - QUIZ 3

Week 15: NP and PSPACE Complete Problems
    Mon, Apr 23 - Hw9 assigned 
    Wed, Apr 25

Week 16: NP and PSPACE Complete Problems
    Mon, Apr 30 - Hw8, Hw9 due