Theoretical Foundations of Computing

Kno.e.sis Center, Wright State University, Dayton, Ohio

Fall Quarter 2010

Meeting Times

Tuesdays and Thursdays, 4:10pm to 5:50pm, Rike Hall 161
Office Hours: Thursdays 2pm to 3pm. Email contact is preferred.

Course Materials

Required: Thomas S. Sudkamp, Languages and Machines, Addison Wesley, 3rd Edition, 2006.
We will cover most of Part III, excluding Chapter 10.

Slides and my personal manuscript will be posted here as they become available. However, relevant for the exams is the material presented in class. If you miss a class, it's your responsibility to get all missing information.

Downloads
Slides 2010-09-07 - Introduction (final)
Slides 2010-09-09 - Infinities, Languages, Automata (final)
Slides 2010-09-09 - 2010-09-28 - Chapter 8 (Turing Machines) (final)
Slides 2010-09-30 - 2010-10-01 - Chapter 9 (Turing Computable Functions) (final)
Slides 2010-10-05 - Chapter 11 (Decidability) (final)
Slides 2010-10-07 - 2010-10-28 - Chapter 12 (Undecidability) (final)
Slides 2010-11-02 - 2010-11-04 - Chapter 13 (Mu-recursive functions) (final)

Evaluation
Homework (20%), mid-term exam (30%), final exam (50%)
Grading will follow a standard scale (A: 100-90, B: 89-80, C: 79-70, D: 69-60, F: 59-0)

Homework: hand-in exercises are graded, and up to 5 points per exercise is awarded. An average of 4 points counts as 100% for the exercise part of the grade.

Course Outline (tentative)
Note the cancelled classes below. Replacement sessions on Fridays will be in Russ 346.

Week 1 (9/6): (Tue) Intro, (Thur) Chap-8, no office hour
Week 2 (9/13): (Tue) Chap-8, (Thur) Chap-8, (Fri) exercise session.
Week 3 (9/20): no classes, no office hour
Week 4 (9/27): (Tue) Chap-8, (Thur) exercise session, (Fri) Chap-9,
Week 5 (10/4): (Tue) Chap-11, (Thur) exercise session, (Fri) mid-term exam
Week 6 (10/11): (Tue) Chap-12, no class on Thursday, no office hour
Week 7 (10/18): no classes, no office hour
Week 8 (10/25): no class on Tuesday, (Thur) Chap-12, (Fri) Chap-12
Week 9 (11/1): (Tue) exercises, Chap-13, (Thur) exercises, Chap-13, and questions
Week 10 (11/8): no classes, no office hour
Exam: Tuesday, Nov. 16, 2010 at 5:45pm in Rike Hall 161

Back to my home page.