**Important Notice: **

- Watch this space for important announcements throughout the course. Recent announcements will be highlighted in red.
- The first half of the course will be taught by Prof. Ravi Sandhu and the second half by Prof. Duminda Wijesekera.
- Both halves of the course have equal weight for the overall grade.
- The first half is described on this page. For the second half consult Prof. Duminda Wijesekera's teaching web page.
- Please do not sign up for this course unless you have completed INFS 501 or equivalent.
- This is a fast-paced and mathematically sophisticated course with high expectations of the students.
- Do not expect much help or hand-holding outside the lectures.
- For each lecture review the solved exercises and problems in the book and try some of the others on your own.
- Look forward to an exciting course!

**Assignments: **

- Each lecture will include an assignment which is due in the following class.
- Late assignments will not be accepted.
- The assignment is to be solved without any assistance from anybody.
- Solutions should be neatly handwritten or typed. Points will be deducted for shabby submission.
- Each solution should be accompanied with the following signed statement: "I have neither received nor provided any help in this assignment and it is my personal effort."

**Schedule of Classes and Assignments:** Please read ahead and come prepared to get maximum benefit from lectures.

- 8/28/06: Regular Languages,
Sipser Chapter 1 (Read Chapter 0 of Sipser prior to first lecture)

Assignment 1 (due 9/11/06 in class): (1) Sipser p27 problem 0.11 (2) Sipser p88 problem 1.31 (3) Sipser p89 problem 1.36 - 9/4/06: Labor Day. No Lecture.
- 9/11/06: Regular Languages,
Sipser Chapter 1. Turing Machines,
Sipser Chapters 3

Assignment 2 (due 9/18/06 in class): (1) Sipser p86 exercise 1.16 (2) Sipser p86 exercise 1.21 (3) Sipser p88 exercise 1.30 (4) Sipser p160 exercise 3.7 - 9/18/06: Turing Machines,
Sipser Chapters 3, 4

Assignment 3 (due 9/25/06 in class): (1) Sipser p161 problem 3.11 (2) Sipser p183 exercise 4.2 (3) Sipser p183 exercise 4.3 - 9/25/06: Turing Machines,
Sipser Chapters 4, 5

No assignment this week. - 10/2/06: Time Complexity,
Sipser Chapter 7

Assignment 4 (due 10/9/06 in class): (1) Sipser p295 exercise 7.8 (2) Sipser p295 exercise 7.11 (3) Sipser p295 problem 7.17 - 10/10/06 (class meets Tuesday 10/10/06 NOT Monday 10/9/06): Time Complexity,
Sipser Chapter 7

No assignment this week. - 10/16/06:
**Examination on Part I: (i) Closed book component 4:30pm-5:15pm 40%, (ii) Open book component 5:20pm-7:10pm 60%.** - 10/23/06: Second half of the course on Logic. Consult Prof. Duminda Wijesekera's teaching web page.

**Part I:** Theory of Computation

**Part II:** Mathematical Logic

**Grading Policy:**

- Grades will be based on examinations (25%), assignments (20%) and class participation (5%) for 50% overall for this portion of the course. Final grades will be “curved” based on overall class performance.

**Course Structure and Textbooks: **

- The course covers material from 2 textbooks as follows.
- Lectures on the theory
of computation (first half taught by Prof. Ravi Sandhu)

Textbook: Introduction to the Theory of Computation, Michael Sipser, 2nd edition, 2005. - Lectures on logic (second half taught by Prof. Duminda Wijesekera)

Textbook: A Mathematical Introduction to Logic, Herbert Enderton, 2nd edition, 2001.