Computational Complexity and Algorithm Analysis
Prof. Dr. Pascal Hitzler
Kno.e.sis Center, Wright State University, Dayton, Ohio
Spring Quarter 2010
Meeting Times
- Mondays and Wednesdays 6:05pm to 7:20pm, Russ 154
- Office Hours: Wednesdays 3:00pm to 4:00pm, Joshi 389. Email contact is preferred.
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
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/29/10 (pdf)
Slides 2, 05/12/10 (pdf)
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)
- Each homework exercise is worth 4 points. Exceptions will be marked.
- Solutions to homework exercises are due one week after they are posted (hand them in during class, alternatively, push them through under my office door)
Course Outline (tentative)
- Week 1 Introduction. Big-O notation.
- Week 2 Turing Machines and time complexity. [sessions 20 minutes longer]
- Week 3 Exercise session. Properties of complexity. [sessions 20 minutes longer]
- Week 4 Exercise session. Adequacy of the complexity notion. [sessions 20 minutes longer]
- Week 5 Monday, 26th of April: mid-term exam; 8:00-9:15. 28th of April: P and NP [session 20 minutes longer]
- Week 6 no classes
- Week 7 Cook's Theorem
- Week 8 Is P=NP? NPI. The polynomial hierarchy.
- Week 9 Beyond NP. Class presentations I
- Week 10 Class presentations II. Recap.
Back to my home page.