Computational Complexity and Algorithm Analysis
Prof. Dr. Pascal Hitzler
Kno.e.sis Center, Wright State University, Dayton, Ohio
Spring Quarter 2011
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.
- Mondays and Wednesdays 6:05pm to 7:20pm, Biological Sciences 105
- cancelled:04/13/11, 05/02/11, 05/04/11. replacements: 04/15/11, 05/06/11, both 6:05pm to 7:20pm (room Russ 346)
- extra mid-term exam, 04/26/11 at 8:30, Russ 153
- final exam: Wednesday, June 8th, 8pm, Biological Sciences 105
- Office Hours: Wednesdays 4:30pm to 5:30pm, Joshi 389. Email contact is preferred.
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.
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.
See also the Spring 2010 lecture for the old material. This class will be very similar.
Manuscript (pdf) - this will be updated constantly. Parts covered in past class sessions will always be stable [unless I inform you explicitly]. Date of the manuscript version is on the first page.
Slides 1, 03/28/11 (pdf)
Slides 2, 05/23/11 (pdf)
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)
- 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. Big-O notation.
- Week 2 Turing Machines and time complexity.
- Week 3 Properties of complexity.
- Week 4 Adequacy of the complexity notion.
- Week 5 Mid-term 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 NP-complete Problems
Back to my home page.