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: Mackey G-01
Office Hour: 10:10-11:00am 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: Levis K. Downing Hall 2038A / 1019
Email: chuliu AT howard.edu

Course Content:

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.

Course Objectives:

This course aims to teach students to 

Prerequisites:

CS136 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 are midterm exam and final exam. The midterm exam will cover all the materials up to the midterm. The final exam will cover 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 the 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."

Resources:

Tentative Schedule:  (actual schedule may be slightly different)

Date

Topic

Assignments

Due Date
8/20, 8/22 Ch. 0: Introduction: Sets, strings and languages, theorems and proofs      
8/27, 8/29; 9/3, 9/5;

9/10, 9/12; 9/17, 9/19

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

9/5

    Homework #1:

1.4c, 1.5c, 1.6g, 1.16a

 9/12
9/19    Homework #2

1.17a, 1.21a, 1.29b

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

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

 10/8
10/3

Midterm exam

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

3.1c, 3.2c, 3.7, 3.8b

 10/29
10/29, 10/31, 11/5, 11/7, 11/12, 11/14 Ch. 4: Decidability      
11/5    Homework #5

4.13, 4.16

 11/13
11/19, 11/21

Final review

      
11/26

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.