Computability and Complexity

CSCI 572 - 01 Computability and Complexity (Spring)

Name:	Computability and Complexity
Course Code	CSCI 572, CRN 14251
Credit Hours:	3
Meeting Time:	Thursday 11:10am - 1:30pm
Class Room:	TBD
Instructor:	Dr. Chunmei Liu
Office:	Levis K. Downing 2038A
Email:	chuliu AT howard.edu
Office Hours:	12:00pm - 2pm T, 1:30pm - 2:30pm Th
Textbook:	Introduction to the Theory of Computation, by Michael Sipser, Thomson Course Technology, third edition.

Course Content:

This course provides a challenging introduction to the theory of computation. Beginning with the mathematical foundations for the subsequent topics, this course briefly reviews different computational models, then progresses to explore Turing machines, decidability, reducibility, time and space measures on computation, NP-completeness, and the P versus NP problem.

Course Objectives:

This course aims to offer computer science graduate students a comprehensive understanding of theoretical computer science. Students will be exposed to essential computational paradigms in a rigorous manner. Through the course, students will gain a thorough and in-depth understanding of theoretical computer science.

Prerequisites:

There is no prerequisite for this course.

Required Course Materials:

Textbook: Introduction to the Theory of Computation, by Michael Sipser, Thomson Course Technology, 3rd edition. ISBN: 113318779X

Grading Policy:

Your grade in this course will be determined as follows:

Assignments: 20%

Project: 20%

Midterm exam: 30%

Final Exam: 30%

All activities will receive a numerical grade of 0-100. You will receive a score of 0 for any work not submitted. Your final grade will be a letter grade. Letter grade equivalents for numerical grades are as follows:

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

Note: No scale-up adjustment will be made if the grade is out of the range.

Assignments, exams, and policy on grading, late submissions and make-up exams:

Generally, homework assignments will be assigned in class. They are usually due in a week unless specified.
Your written assignments must be TYPED.
There will be a midterm exam and a final exam. The midterm exam will cover all the materials up to the midterm. The final exam will cover all materials taught in the course.
No late submissions are allowed unless there is a validated excuse such as sickness. The instructor must be notified of the excuse at least 12 hours before the submission 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 excuse must be provided.
No make-up exams will be given unless there is a written doctor's excuse or other emergencies. A proof of the excuse must be provided. In the case that such an excuse is accepted, the deadline will be extended the number of days specified in the excuse.
Regrading request must be sent within a week of the date the graded material was returned to the class. Requests for regrading or any questions regarding graded material will not be accepted after that time. Any graded material that is not picked up within two weeks after distribution may be discarded.
No extra work requests will be accepted. Grades will only be calculated based on the marking scheme.

Attendance policy:

All students are expected to attend classes regularly and promptly. Students are expected to participate in class discussions and group projects if any. Students should not leave the class while it is in progress unless it is extremely urgent or an emergency. Students that are absent for health reasons are expected to present documentation as soon as possible. If you are absent from classes or laboratory periods, you are still responsible for the work missed. If you miss a scheduled midterm or final exam, you must obtain your instructor's approval to take a substitute exam or you will receive a grade of zero for the exam.

Plagiarism Policy

Howard University has adopted a new policy on plagiarism and cheating. In short, all instances of plagiarism will be resolved by an office of the administration, which will conduct the appropriate hearings. See the section entitled "ACADEMIC CODE OF STUDENT CONDUCT" on pages 26-27
of the "Student Reference Manual and Directory of Classes." ALL INSTANCES OF PLAGIARISM WILL RESULT IN ASSIGNMENT FAILURE AND REPORTING TO THE HOWARD UNIVERSITY Computer Science ADMINISTRATION.

Resources:

Canvas: canvas.howard.edu

Tentative Schedule (please note the schedule and the course content may be a little different from the actual ones):

Date Content Assignment Due Date

1/16, 1/23, 1/30 Ch.0, Ch.1, Ch2 　　

2/6, 2/13, 2/20 Ch. 3
The Church-Turing Thesis: Turing machines, variants of Turing machines, the definition of algorithm
　　

2/20 　 Homework 1: 3.1c, 3.2c, 3.7, 3.8b 2/27

2/27, 3/6 Ch. 4
Decidability: decidable languages, the halting problem
　　

3/6 　 Homework 2: 4.13, 4.16 3/20

　　 Project: write a short paper of 6 pages in IEEE two column format. 4/17

3/20 Midterm Exam 　　

3/27, 4/3 Ch. 5
Reducibility
　　

4/3 　 Homework 3: 5-10, 5-11, 5-12, 5-13 4/10

4/10 Ch. 7
Time complexity
　　

4/17 Ch. 8
Space complexity: Savitch's theorem, the class PSPACE, PSPACE-completeness
　　

4/17 　 Homework 4:
7.1(a,b), 7.2 (a,b), 7.10, 8.4
4/24

4/17 Project Presentation 　　

4/24 Final Exam 　　

Class Attendance Restricted to Registered Students

Only students whose names appear on the official course roster are permitted to attend class meetings. Students who are not registered are not permitted to attend or participate in course activities, do not have access to Blackboard, cannot submit course assignments, and will not receive a grade for this course. It is the students’ responsibility to ensure that they are properly registered by the published registration deadline. Requests to add courses after the deadline will not be considered.

University ADA Policy:

The Americans with Disabilities Act requires institutions to accommodate the needs of persons with disabilities. If you need special arrangements such as sign language interpreters or audiotapes of lectures, etc. ALL DOCUMENTATION IS REQUIRED NO LATER THAN THE FIRST WEEK OF CLASS.

Statement of Interpersonal Violence:

Howard University’s Policy Prohibiting Sex and Gender-Based Discrimination, Sexual Misconduct and Retaliation (aka, the Title IX Policy) prohibits discrimination, harassment, and violence based on sex, gender, gender expression, gender identity, sexual orientation, pregnancy, or marital status.
With the exception of certain employees designated as confidential, note that all Howard University employees – including all faculty members – are required to report any information they receive regarding known or suspected prohibited conduct under the Title IX Policy to the Title IX Office
(TitleIX@howard.edu or 202-806-2550), regardless of how they learn of it. For confidential support and assistance, you may contact the Interpersonal Violence Prevention Program (202-836-1401) or the University Counseling Service (202-806-7540). To learn more about your rights, resources, and
options for reporting and/or seeking confidential support services (including additional confidential resources, both on and off campus), visit titleix.howard.edu.

Date	Content	Assignment	Due Date
1/16, 1/23, 1/30	Ch.0, Ch.1, Ch2
2/6, 2/13, 2/20	Ch. 3 The Church-Turing Thesis: Turing machines, variants of Turing machines, the definition of algorithm
2/20		Homework 1: 3.1c, 3.2c, 3.7, 3.8b	2/27
2/27, 3/6	Ch. 4 Decidability: decidable languages, the halting problem
3/6		Homework 2: 4.13, 4.16	3/20
		Project: write a short paper of 6 pages in IEEE two column format.	4/17
3/20	Midterm Exam
3/27, 4/3	Ch. 5 Reducibility
4/3		Homework 3: 5-10, 5-11, 5-12, 5-13	4/10
4/10	Ch. 7 Time complexity
4/17	Ch. 8 Space complexity: Savitch's theorem, the class PSPACE, PSPACE-completeness
4/17		Homework 4: 7.1(a,b), 7.2 (a,b), 7.10, 8.4	4/24
4/17	Project Presentation
4/24	Final Exam