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:


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 

Course Credits 


Required Texts and Materials

Grading Policy:

Rules to Abide by

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, etcmust 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 ( 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, 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.