CSCI 341  Theory of Computation

Name: Theory of Computation
Course Code: CSCI 341, CRN 86785
Credit Hours: 3
Modality: In person
Schedule: Tuesday & Thursday 11:10am - 12:30pm
Location: LKD 1017
Office Hours: 10:30am - 11am, 12:40pm - 2:40pm on Tuesday and Thursday, or by appointment.
Course URL: www.cs-howard.net/liu
Textbook: Introduction to the Theory of Computation, by Michael Sipser, Thomson Course Technology, 3rd edition. ISBN: 113318779X.
Instructor: Dr. Chunmei Liu
Office: LKD. 2038A
Email: chuliu AT howard.edu

Course Content:

This course introduces the classical theory of computation. It examines the formal relationships among machines, languages, and grammars, including regular, context-free, recursive and recursively enumerable languages. Topics include sequential machines and their applications to devices, processes, and programming, as well as models of computation such as finite state automata, pushdown automata, and Turing machines. This course also covers undecidability and time complexity theory.

Course Objectives:

This course aims to teach students to

Prerequisites:

CSCI 136 and MATH 181.

Required Course Materials:

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

Student Learning Objectives:

Exams:

There is a midterm examn and a final exam. The midterm exam covers all the materials up to the midterm. The final exam covers all materials taught in the class.

Grading Policy:

Your grade in this course will be determined as follows:

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 in the course 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 range.

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

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

Tentative Schedule:  (actual schedule may be slightly different)

Date

Topic

Assignments

Due Date
8/18, 8/20 Ch. 0: Introduction: Sets, strings and languages, theorems and proofs      
8/25, 8/27; 9/1, 9/3;

9/8, 9/10; 9/15, 9/17

 Ch. 1: Regular Languages: finite automata, nondeterminism, regular expressions, nonregular languages, the pumping lemma      

9/3

    Homework #1:

1.4c, 1.5c, 1.6g, 1.16a

 9/10
9/15    Homework #2

1.17a, 1.21a, 1.29b

 9/22
9/22, 9/24; 9/29; 10/6, 10/8 Ch. 2: Context-free Grammars: context-free grammars, pushdown automata, non-context-free languages, the pumping lemma      
9/29    Homework #3

2.1 b,c; 2.2 a; 2.4 b, c

 10/6
10/1

Midterm exam

      
10/13, 10/15; 10/20, 10/22 Ch. 3: The Church-Turing Thesis: Turing machines, variants of Turing machines, the definition of algorithm      
10/20    Homework #4

3.1c, 3.2c, 3.7, 3.8b

 10/27
10/27, 10/29, 11/3, 11/5, 11/10, 11/12 Ch. 4: Decidability      
11/3    Homework #5

4.13, 4.16

 11/10
11/17 Ch. 7: Time Complexity      
11/19

Final review

      
11/24

Final exam

      

NOTE: The instructor reserves the right to change the course content.

HU Class attendance policy:

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.