COT 6410: Computational Complexity (Spring 2017)

Computer Science Department

College of Engineering and Computer Sciences, University of Central Florida

Instructor: Dr. Sharma Thankachan

Office: HEC-207

Phone: (407) 823-5316

E-Mail: sharma(dot)thankachan(at)ucf(dot)edu

Course website: http://www.cs.ucf.edu/~sharma/COT6410

Class Meeting Days: Tuesday,  Thursday 

Class Meeting Hours: 1:30 pm - 2:45 pm

Class Location: HEC 0117

Office Hours: Tu, Th 3:00 pm – 4:30 pm
_________________________________________________________________________________________________________

University Course Catalog Description

Properties of algorithms, computational equivalence of machines, time-space complexity measures, examples of algorithms of different complexity, classification of algorithms, classes P and NP. Occasional.

Course Overview 

Review of mathematical background, DFA, NFA,  basic Turing machine models, languages, Gödel's incompleteness theorems, NP and NP completeness; the Cook-Levin Theorem; the classes of coNP, EXP, NEXP, Polynomial reduction and NP-complete (and NP-hard) problems, Time Hierarchy Theorems; oracle machines, Space complexity,The polynomial hierarchy. If time permits, we might touch upon  advanced topics like Approximation Algorithms and in-approximability, Probabilistic Algorithm Interactive Proof Systems etc. 

Course Objectives 

• Understanding of various types of computational models and their relation to each other
• Understanding of the limits that are imposed by the very nature of computation, and the ubiquity of unsolvable problems throughout CS
• Understanding of the notion of computational complexity and mainly of the classes of problems known as P, NP, co-NP, NP-complete, NP-Hard and beyond. 
• Gain stronger formal proof skills and a better appreciation of the importance of discrete mathematics to all aspects of CS

Course Credits 

3

Required Texts and Materials

• Arora & Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Draft (2007 publication) [link]
• Michael Sipser: Introduction to the Theory of Computation [link]
• More coming !!!

Grading Policy:

• Midterm – 25%; Final Exam – 25%; Assignments - 25%; Paper and Presentation - 15%; Class Participation - 10% and Challenge Problems (with extra credits). 
• Grading will be on the curve.However, scores equal to or above 85%, 70%, 60% are guaranteed to receive at least A, B, and C, respectively. 

Rules to Abide by

• Homework problems can be discussed, but you must write your own answer and the name of the person with whom you have collaborated. 
• Late Assignments: there will be 5-6 assignments, and 2 assignments with two lowest scores will not be considered towards the final grade. This means (i) you are free to miss 2 assignments (ii) late assignments will not be accepted. 
• Laptop/Cell Phone/Tablet/ Ebook Reader Usage: The use of electronic equipment in the class is forbidden, except by permission of the Student Disability Services.
• Both midterm and final are going to be open book. 

Course Policies: Student Expectations

Disability Access: The University of Central Florida and the instructor is committed to providing reasonable accommodations for all persons with disabilities. This syllabus is available in alternate formats upon request. Students who need accommodations must be registered with Student Disability Services, Ferrell Commons Room 185, phone (407) 823-2371, TTY/TDD only phone (407) 823-2116, before requesting accommodations from the professor.

Attendance Policy: Students are expected to make every effort to attend all classes. Please see the instructor if you plan to be absent for more than 4 consecutive classes.

Professionalism Policy: Per university policy and classroom etiquette; mobile phones, iPods, etc. must be silenced during all classroom and lab lectures. Those not heeding this rule will be asked to leave the classroom/lab immediately so as to not disrupt the learning environment. Please arrive on time for all class meetings. Students who habitually disturb the class by talking, arriving late, etc., and have been warned may suffer a reduction in their final class grade. 

Academic Conduct Policy: Academic dishonesty in any form will not be tolerated. If you are uncertain as to what constitutes academic dishonesty, please consult The Golden Rule, the University of Central Florida's Student Handbook (http://www.goldenrule.sdes.ucf.edu/) for further details.  As in all University courses, The Golden Rule Rules of Conduct will be applied.  Violations of these rules will result in a record of the infraction being placed in your file and receiving a zero on the work in question AT A MINIMUM.  At the instructor’s discretion, you may also receive a failing grade for the course.  Confirmation of such incidents can also result in expulsion from the University.

University Writing Center: The University Writing Center (UWC) is a free resource for UCF undergraduates and graduates. At the UWC, a trained writing consultant will work individually with you on anything you're writing (in or out of class), at any point in the writing process from brainstorming to editing. Appointments are recommended, but not required. For more information or to make an appointment, visit the UWC website at http://www.uwc.ucf.edu, stop by MOD 608, or call 407.823.2197.

Religious Observances: Students are expected to notify their instructor in advance if they intend to miss class to observe a holy day of their religious faith. The Office of Diversity Initiatives at 407-823-6479 may assist students in this process.