C term 2017

Worcester Polytechnic Institute

This page is no longer being maintained, activity has been moved to the Canvas page for the course.

## What's New

## Course Information

### Instructor

- Dan Dougherty:
`dd at cs dot wpi dot edu`

- Office hours (Fuller Labs 231):
- Mondays and Thursdays 4–5 (i.e., after class)
- Tuesday and Fridays 2–3 (i.e., before class)

#### TA+SA office hours (in Fuller Labs A22)

**Please note the one-time-only change to TA hours on Wednesday Jan 19**

- John Lee
`jtlee at wpi dot edu`

- Thursdays 9 – 12 am

- Shijian Li
`sli8 at wpi dot edu`

- Wednesdays 6–9 pm

- Hang Cai
`hcai at wpi dot edu`

- Wednesdays 2–5 pm

#### Course mailing list: `cs3133-all at cs dot wpi dot edu`

Sending to this mailing list will reach all the registered students in the course, as well as the instructor.

### Textbook

There is no required textbook for the class. I will post notes online.

### Grading

Your course grade will be based on four exams, as described below.

### Exams

Exams will be given on the following evenings, in our classroom.

- Exam 1 (worth 10%) : Thu Jan 19, 7 – 9 pm
- Exam 2 (worth 30%) : Thu Feb 2, 7 – 9 pm
- Exam 3 (worth 30%) : Thu Feb 16, 7 – 9 pm
- Exam 4 (worth 30%) : Fri Mar 3, 4–6 pm
Note that Exam 4 is immediately after the last class period.

**This is important:** If there is any reason why taking an exam on any
of those evenings would create a difficulty for you, you must come
explain why by **Tuesday Jan 17.** If you don't talk me before
then, then I will consider that you have no prior commitment for those
dates.

### Homework

Your homework is precisely this: to do the exercises in the lecture
notes sections we are covering. This is the most important part of
the course: you can only **learn** stuff by **doing** stuff. The exams
will be based quite closely on these exercises.

Since the class is so large, I cannot grade your homework, so I will not collect it. Solutions to most of the exercises will be made available, but only the day before the exams. The idea is that you should grapple with the problems without the solutions available, that's the best way to learn. But I'll give solutions before the exam so you can check your work or see how to do problems that you got truly stuck on.

## Other Resources

The course content is well-established: the core topics comprise a set of techniques that everyone agrees should be mastered by every computer scientist. As a consequence, there are any number of good textbooks for this material. But the good texts are all way too expensive. That's a big reason why I am providing notes online. But here are some good texts that you might find useful as a supplement.

### Available via the library

The following text is a favorite of mine

- Automata and Computability

Dexter Kozen

Springer-Verlag

It is available as an electronic resource via the WPI library. I suggest that you bookmark it for yourself and use it as a resource to supplement the notes I provide.

### Other good resources

- Automata Theory, Languages, and Computation

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman

Addison-Wesley - Introduction to the Theory of Computation

Michael Sipser

PWS - Languages and Machines: An Introduction to the Theory of Computer
Science

Thomas Sudkamp

Pearson

## Schedule

class | date | topic | lecture notes reading |
---|---|---|---|

01 | R Jan 12 | functions | Ch 1 |

02 | F Jan 13 | cardinality | Ch 2 |

M Jan 16 | (MLK Day, no class) | ||

03 | T Jan 17 | strings and languages | Ch 3 |

04 | R Jan 19 | exam 1 review | |

EXAM 1 |
|||

05 | F Jan 20 | finite automata introduction | Ch 4 |

06 | M Jan 23 | more examples; product construction | Ch 4 |

07 | T Jan 24 | eliminating non-determinism | Ch 5 |

08 | R Jan 26 | nil-transitions; encoding | Ch 6,7 |

09 | F Jan 27 | the distinguishability relation | Ch 3 |

10 | M Jan 30 | regular expressions; from regular expressions to automata | Ch 9,10 |

11 | T Jan 31 | proving languages non-regular | Ch 8 |

12 | R Feb 2 | exam 2 review | |

EXAM 2 |
|||

13 | F Feb 3 | from NFA to regular expressions | |

14 | M Feb 6 | grammars | |

15 | T Feb 7 | context-free grammars introduction | |

16 | R Feb 9 | parse trees and ambiguity | |

17 | F Feb 10 | refactoring context-free grammars | |

18 | M Feb 13 | parsing 1 | |

19 | T Feb 14 | parsing 2 | |

R Feb 16 | (Advising Day, no class) | ||

EXAM 3 |
|||

20 | F Feb 17 | Turing machines | |

21 | M Feb 20 | (semi-)decision procedures | |

22 | T Feb 21 | decision problems for FAs and CFGs | |

23 | R Feb 23 | the halting problem | |

24 | F Feb 24 | reducibility | |

25 | M Feb 27 | more undecidable problems | |

26 | T Feb 28 | more undecidable problems | |

27 | R Mar 2 | Rice's theorem | |

28 | F Mar 3 | review | |

EXAM 4 |

## Academic Honesty.

The details of the university's policies and procedures can be found here.

My response to any sort of cheating on will be to pursue the strongest remedies available to me.