CSCI 572 - 01  Computability and Complexity (Spring)

Time: Thursday 2:10pm - 4:30PM
Class Room: TBA
Instructor: Dr. Chunmei Liu
Office: Levis K. Downing 2038A
Email: chunmei AT
Office Hour: 2:00pm - 4:00pm T, 1:00pm - 2:00pm R
Textbook: Introduction to the Theory of Computation, by Michael Sipser, Thomson Course Technology, third edition.

Course Description:

This course will introduce fundamental ideas in the theory of computation including computability and complexity. Topics will include Turing machines; decidable and undecidable problems, reducibility, recursive function theory, and time and space measures on computation.


There is no prerequisite for this course, although taking CSCI 570 "Advanced Algorithms" is preferred.

Course Objectives:

This course aims to provide computer science students with a broad understanding of various models of computation, the relative power of the models, and the characterizations of the power of each model. They will be exposed to essential computational paradigms in a rigorous way.


There will be about six written assignments.


There will be a midterm exam which will cover all material up to and including the previous lecture. The final exam will cover all materials taught in the course.

Grading Policy:

The assignments and exams all contribute significantly to your grade. Specifically, your final course grade will be calculated as follows:

A: 90-100, B: 80-89, C: 70-79, D: 60-69, F: 0-59

Estimate CSAB Category Content:




Data Structures






Software Design



Computer Organization and Architecture



Concepts of Programming Languages



Oral and Written Communications:

Every student may be required to submit written reports (not including exams, tests, quizzes, or commented programs) of typically 2-3 pages and to make an oral presentation accordingly of typically 5 minutes.

Social and Ethical Issues:

Policy on submission, late assignments, projects, and make-up exams:

        a. No late submissions are accepted (even if the submission was wrong).

        b. Students may submit assignments late if an emergency occurs. The instructor must be notified of the emergency at least 12 hours before the deadline if possible. An approval from the instructor before the late submission must be obtained, and the submission must be done within a week from the deadline. In addition, a proof of the emergency must be provided.
Academic Integrity:
Although discussions are encouraged, all homework and programming projects must be completed independently. Suspected plagiarism will incur interviews. The first verified plagiarism will result in zero point of the involved submission and cancel all extra credits. The second will result in a failure in the course.

Attendance policy:

You are expected to and should attend classes regularly and complete all assignments on time. Class attendance may be a factor in determining the course grade. If you must miss a class, it's a good idea to let your instructor know in advance or as soon thereafter as possible. If you don't explain your absence, your instructor may assume you don't care about the class or your grade. Coming to class late three times will be counted as one class absence. And later than 10 minutes will also be counted as one class absence. Students are required to attend class during the regularly scheduled tests and the final exam unless prior arrangements have been made.

Tentative Schedule:      

Date Content Homework Assignment Homework Due Date
J11,J18,J25 Ch. 3

The Church-Turing Thesis: Turing machines, variants of Turing machines, the definition of algorithm

J25    Homework 1  2/2
F1, F8, F15 Ch. 4

Decidability: decidable languages, the halting problem

F22 Midterm Review    
M1 Midterm Examination    
M8, M22 Ch. 5


M29, A5 Ch. 7

Time complexity

A12 Ch. 8

Space complexity: Savitch's theorem, the class PSPACE, PSPACE-completeness

A19 Final Review    
A26 Final Examination    

NOTE: The instructor reserves the right to change the course content, omit parts of the topics listed above or introduce new material midstream to supplement the  course text.

University ADA Policy:

Howard University is committed to providing an educational environment that is accessible to all students. In accordance with this commitment, students in need of accommodations due to a disability should contact the Office of the Dean for Special Student Services for verification and determination of reasonable accommodations as soon as possible after admission to the University, or at the beginning of each academic semester. The Dean of the Office for Special Student Services, Dr. Barbara Williams, may be reached at 202.238.2420.

Syllabus Addendum for all CEA Courses

The following understandings, expectations, and requirements shall apply to all classes that are offered by the College of Engineering and Architecture, effective fall 2016. These are the expectations that the students can have from their professors, and the expectations that the professors will have from each student taking her/his class. These are intended promote the success of our students here at Howard, and after graduation.

Students expect that their professors will:

1.      Care about the success of each student, and promote mutual respect.

2.      Come to every class, and on time.

3.      Keep abreast of the technical field she/he is teaching.

4.      Explain how the subject being taught is broadly connected to the field and possibly to other courses.

5.      Keep abreast of, and adapt to, evolving teaching approaches.

6.      Have office hours for each class, and be present at these times.

7.      Coordinate any travel with his/her Department Chairs.

Students who feel that a professor fails in the above expectations may confidentially express his concerns in the Comments box in the Office of Student Services in the L. K. Downing Building, Room 1114, or email Dr. Rhoulac Smith, Director of Student Services, at Your communication must be respectful, professional, and truthful.


Professors expect that their Students will:

(Failing to comply will result in appropriate penalties. In certain cases these penalties are expressly defined below.)


1.      Take a professional approach to all class activities and interactions. Show that your take the class seriously and come to class prepared.

2.      Absenteeism: Come to every class.

         2% penalty from total class grade for every unexcused absence

3.      Lateness: Not come to class after it begins.

         1% penalty from total class grade for every instance of infraction

4.      Leaving Early: Not leave class before it ends.

         1% penalty from total class grade for every instance of infraction

5.      Disruption: Avoid entering and leaving the classroom during instruction.

6.      Eating: No eating in class.

         1% penalty from total class grade for every instance of infraction.

7.      Electronics: No use of laptop, cell phone, iPad, headphones or other electronic equipment that are not explicitly requested to be used by the Professor.

         1% penalty from total class grade for every unexcused absence

8.      Cheating: Any form of cheating, including plagiarism, in an exam or assignment shall automatically result in a zero-grade for all involved, for that exam or assignment.

9.      Communication: Communication, oral or written, with the Professor, including email, in all matters concerning the course, shall be done professionally; that is, as it would be done with a potential employer. (e.g., respectful, include your full name, clearly articulate the objective of the communication concisely)