CISC 301   -   Elements of Logic and Automata Theory   -  

Fall 2005
T/Th 11:00 - 12:15, GORE 204

 

 

Course Page: http://www.cis.udel.edu/~vijay/cisc301.html

Instructor: Vijay Shanker  TA: Michael Bloogdgood
Office: Room 202, The Green House (77-79 E. Delaware)  Office: Pearson 115B
Hours: Tuesdays and Wednesdays 1:30-2:30pm  Hours: Wednesdays 9:00am-11:00am
Phone: 831-1952  Phone:
Email: vijay@cis.udel.edu  Email: bloodgoo@cis.udel.edu

Textbook

Logic For Computer Scientists by Uwe Schoening
Automata and Computability by Dexter Kozen

Course Description

In the first half of the course, we will study propositional and first-order predicate logic. An understanding of logic and automated reasoning methods is useful for advanced computer science subjects such as artificial intelligence (knowledge representation and reasoning), databases (especially for database query systems), logic programming languages, programming language semantics, and formal verification techniques. In the second half of the course, we will study automata theory and formal languages which has many applications in compilers, networks, operating systems and natural language processing.

Topics

Homeworks:

There will be a number of written homeworks, perhaps 8-10. They will have to be turned in at the beginning of the class on the due date. Without prior permission, late submissions will not be accepted.

All homework assignments have to be completed individually. While students are encouraged to discuss the course material with each other, students should not collaborate among themselves in answering the homework assignment questions.

Mid-term and Final Exams:

There will be a final exam and one mid-term exam. In addition, there will be 4-5 quizzes (10 minutes long). The mid-term exams and quizzes will be announced at least a week in advance.

Overall Course Grade:

    30% Final
    30% Mid-term + Quiz
    40% Homework

Policies

Homeworks

Homework 1 Due date September 15, 2005. No late submissions

Homework 2 Due date September 22, 2005. No late submissions

Homework 3 Due date September 29, 2005. No late submissions

Homework 4 Due date October 13, 2005. No late submissions

Homework 5 Due date Tuesday October 18, 2005. No late submissions

Homework 6 Due date Tuesday November 8, 2005. No late submissions Please note that the due date is on a Tuesday.

Homework 7 Due date Tuesday November 15, 2005. No late submissions Please note that the due date is on a Tuesday.

Homework 8 Due date Tuesday November 22, 2005. No late submissions Please note that the due date is on a Tuesday.

Homework 9 Due date Thursday December 1, 2005. No late submissions

Extra example questions and other handouts

You can find some example problems on propositional logic here.

Solutions to some of the example questions on propositional logic can be found here.

An algorithm to convert a formula into a set of clauses can be found here.

You can find some example problems on Resolution here.

Translating English Sentences -- Sample Questions

Full proofs of some exercises involving pumping lemma that I covered in class.

Homework Solution Sketches

A solution set for Homework 1 can be found here.

A solution set for Homework 2 can be found here.

A solution set for Homework 3 can be found here.

A solution set for Homework 4 can be found here.