CSCI 341  Theory of Computation

Time: Tuesday & Thursday 4:10PM - 5:30PM
Credit Hours: 3
Room: L.K. Downing Hall 2113
Instructor: Dr. Chunmei Liu
Office: Levis K. Downing Hall 2038
Email: chuliu AT
Office Hour: 2pm - 3:30pm Tuesday and Thursday
URL: or
Textbook: Introduction to the Theory of Computation, by Michael Sipser, Thomson Course Technology, third edition. ISBN: 113318779X.

1.   General Course Information

1.1  Current Catalog Description:

Introduction to the classical theory of computer science. A study of the formal relationships between machines, languages and grammars; we will cover regular, context free, recursive and recursive enumerable languages. Sequential machines and their applications to devices, processes, and programming. Models of computation: finite state automata, push down automata, and Turing machines. This course will also introduce undecidability and time complexity theory.

1.2  Prerequisites by Topic:

There is no prerequisite for this course, although taking "Fundamentals of Algorithms" is preferred.

2  Learning Resources

2.1  Required Textbooks

2.2  Department Resources

3  Aims, Objectives, & Program Outcomes

3.1  Course Aims

This course aims to teach students to 

3.2  Learning Objectives:

  1. Critical, logical-mathematical reasoning

  2. Ability to transform informal problems into formal ones and vice versa

  3. Ability to apply mathematical knowledge and logic in solving problems

  4. Ability to analyze and summarize problems

  5. Understanding of formal grammars, analysis and compilation

  6. Understanding of the relationship between generative processes and recognition processes

  7. Understanding of hierarchical organization of problems depending on their complexity

  8. Understanding of the logical limits to computational capacity

  9. Understanding of undecidable problems

3.3 Relationship between Learning Objectives and Program Outcomes

Program Outcomes

 Learning Objectives

A. An ability to apply knowledge of computing and mathematics   appropriate to the discipline


J. An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices


4  Teaching and Learning Activities

4.1 Learning Activities



Learning Objectives

Tuesday and Thursday Lectures (Lecture Series): A detailed teaching plan can be found in section 4.2

1, 2, 3, 4, 5, 6, 7, 8, 9

4.2 Major Topics Covered in the Course (tentative schedule)

Part 0: Introduction Ch. 0 Introduction: Sets, strings and languages, theorems and proofs 1 week: 8/20
Part 1: Automata and Languages (Ch.1-Ch.2) Ch. 1 Regular Languages: finite automata, nondeterminism, regular expressions, nonregular languages, the pumping lemma 4 weeks: 8/27, 9/3, 9/10, 9/17
Ch. 2 Context-free Grammars: context-free grammars, pushdown automata, non-context-free languages, the pumping lemma 3 weeks: 9/24, 10/1, 10/8
Part 2: Computability Theory Ch. 3 The Church-Turing Thesis: Turing machines, variants of Turing machines, the definition of algorithm 3 weeks: 10/8, 10/15, 10/22
Part 3: Undecidability Ch. 4.2 Undecidability 1 week: 10/29
Part 4: Time Complexity Ch. 7.1 Time Complexity Theory (P and NP) 1 week: 11/5

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.

5  Assessment

5.1  Assessment Summary (tentative schedule)

Assessment Task Assignment Date Due Date Weighting
Homework #1

1.1, 1.2, 1.3, 1.4 (a, c, e, f, g), 1.6(a, c, e, f, g)

9/6 9/13 6%
Homework #2

1.5 (c, d), 1.7 (b, c), 1.8a, 1.9a, 1.10 a

9/13 9/20 6%
Homework #3

1.16 b, 1.17 a, 1.21 a, 1.29b

9/13 9/27 6%
Project 9/20 10/2, 10/12, 11/2, 11/27 20%
Midterm Exam   10/04 20%
Homework #4

2.1 (b, d),  2.4 (b, c, e, f),  2.16, 2.30 a

10/16 10/23 6%
Homework #5 11/6 11/22 6%
Final Exam   11/29 25%

5.2  Course Grading (actual grading percentage may change during the term)

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

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

        a. No late submissions are accepted.

        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.

5.4  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.

5.5  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."

6.  Notices

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, please make an appointment to see me.

7. Howard University Statement on ADA Policies and Procedures

Howard University is committed to providing an educational environment that is accessible to all students. In accordance with this policy, students in need of accommodations due to a disability should contact the Dean of Student Services for verification and determination of reasonable accommodations as soon as possible. Note: Accommodations are not retroactive. The Office of Student Services is located in Suite 725 of the Howard Center and may be reached at (202) 238-2420.

8. Howard University Statement on Interpersonal Violence

Howard University takes sexual assault, dating violence, domestic violence, stalking and sexual harassment seriously. If a student reveals that he or she needs assistance with any of these issues, all Responsible Employees, which includes faculty, are required to share this information with the University Title IX Office (806-2550) or a student can be referred for confidential services to the Interpersonal Violence Prevention Program (IVPP) (238-2382) or University Counseling Services (806-6870). For more information about these services, please go to

9. Syllabus Addendum

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.)

   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)