Computational Complexity and Algorithm Analysis
Prof. Dr. Pascal Hitzler
Kno.e.sis Center, Wright State University, Dayton, Ohio
Spring Quarter 2012
This class has a distance learning option. Class sessions will be videotaped and made available online. If you enroll for the distance learning option, you are certainly also welcome to physically attend classes or a selection of them. In any case, you are expected to come in person for the exams.
Meeting Times
 Mondays and Wednesdays 6:05pm to 7:30pm, Joshi 193
 No class on Monday 28th of May and Wednesday 30th of May. We compensate for this by having all other meetings 10 minutes longer than originally scheduled, i.e. classes end at 7:30pm (instead of 7:20pm).
 extra midterm exam: Monday 23rd of April, 6:05pm to 7:20pm, Joshi 193
 final exam: Wednesday, 6th of June, 8:00pm to 9:15pm
 Office Hours: Wednesday 5:00pm to 6:00pm. Email contact is preferred. No office hour on 30th of May.
Course Materials

Required: Thomas S. Sudkamp, Languages and Machines, Addison Wesley, 3rd Edition, 2006.
We will mainly recap chapter 8, cover most of chapters 14 and 15, and cover parts of chapters 16 and 17, as time allows.

Supplementary: Michael R. Garey and David S. Johnson, Computers and Intractability, Freeman, 1979.
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
slideset 1 (pdf)
slideset 2 (pdf)
manuscript (pdf)
See also the Spring 2011 lecture for the old material. This class will be very similar.
Evaluation
Homework (20%), midterm exam (30%), final exam (50%)
Grading will follow a standard scale (A: 10090, B: 8980, C: 7970, D: 6960, F: 590)
 Each homework exercise is worth 5 points. An average of 4 points counts as 100% of the homework grade.
 Solutions to homework exercises are due one week after they are posted
Course Outline (tentative)
 Week 1 Introduction. BigO notation.
 Week 2 Turing Machines and time complexity.
 Week 3 Properties of complexity.
 Week 4 Adequacy of the complexity notion.
 Week 5 Midterm exam. P and NP
 Week 6 Cook's Theorem
 Week 7 Is P=NP?
 Week 8 NPI. The polynomial hierarchy.
 Week 9 Beyond NP.
 Week 10 NPcomplete Problems
Back to my home page.