========================================================================= CSI5311 A -- Computational Complexity -- Fall 2014 General Information Professor: Iluju Kiringa (kiringa@site.uottawa.ca) Office Hours: Tuesday 13:00-14:00PM, in my office (SITE 5072) Lectures: Tuesday and Thursday. See calendar. Objectives The goal of the course is to provide students with an introductory graduate level knowledge of Computational Complexity. With the knowledge from this course, students should be able to characterize and prove many basic complexity tasks they face in their own area of research. Computational Complexity is so basic to graduate studies that any serious student of Computer Science must display solid knowledge in that area. Classical topics covered include, but are not necessarily limited to: Basic computation models. Undecidability and related proof techniques. Basic computational resources and their associated complexity classes (P, NP, Co-NP, PSPACE, ...). Relationships among resources and complexity classes. Theory of class completeness (NP completeness, PSPACE completeness, ...) and related proof techniques. Inside P and Beyond NP. Randomized computation. Prerequisites Required is a solid knowledge of design and analysis of algorithms as well as undergraduate notions of computability. Text book M.J. Sipser, Introduction to the Theory of Computation, 2nd Edition, Thompson, 2006. Supplemental reading C. Papadimitriou, Computational Complexity, Addison Wesley, 1994 (This is a more advanced book than Sipser's book; it covers much of the material needed for the course and has been for a long time the classic textbook in the area) M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979 (This is the classic book on NP-completeness) D. Z. Du and K. Ko, Theory of Computational Complexity, Wiley, 2000 (A very advanced book, very useful reference for experts in the area) J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd Edition, Addison Wesley, 2001 (The last 3 chapters are another source on NP completeness material) Workload - Three assignments worth 10% each - Midterm worth 20% (This will be a take home midterm to be done within 3 days) - Presentation worth 10% - Term project worth 40%