3306 Introduction to Theory of Computation (3-3-0)

CS3306 Introduction to Theory of Computation (3-3-0)

Spring 2023 (CRN: 21657, 3 credit hours, Teaching mode: Face-to-Face, Class time: Monday & Wednesday 10:00am-11:15am)

Prerequisites: Grade of C or better in CS 2410, MATH 2305 and MATH 2307.

Catalog Description: An introduction to the modern theory of computing. Topics selected from the abstract algebra, finite automata, regular expressions, regular languages, pushdown automata, context-free languages, and Turing machines. The capabilities and limitations of abstract computing devices are investigated from a theoretical perspective.

Textbook: Hein, J. L., Discrete Structures, Logic, and Computability, Fourth Edition. Jones and Bartlett, 2017. ISBN-13: 9781284070408.

Instructor: Dr. Hong Lin Office: S-717

Office Hours: Monday&Wednesday 11:30am-12:30pm

Campus Phone: (713) 221 2781 E-mail: linh@uhd.edu

Course Web Site: http://cms.uhd.edu/faculty/linh/courses/CS3306

Course Objectives

Upon the successful completion of this course students will be able to:

1.	Describe basic properties of sets, bags, tuples, relations, graphs, trees, and functions. Perform traversals of graphs and trees. Construct inductive definitions for sets.
2.	Write grammars for simple languages, to determine whether a given string is acceptable by the grammar by derivation; Be able to determine whether a grammar is ambiguous and give proofs. Understand the classification of languages and their relations. Particularly, students should know regular languages and context-free languages including LL(k) languages.
3.	Write regular expression and regular grammar for a given language. Design finite automata (DFA and NFA) for a given language. Transform between regular expressions and NFAs. Transform between NFAs and regular languages. Transform an NFA to a DFA and transform a DFA to a minimum state DFA.
4.	Write context-free grammar for a given language. Design a pushdown automaton for a given language. Transform between a context-free grammar and pushdown automaton. Remove left recursion of a context-free grammar. Determine whether a context-free grammar is an LL(k) grammar and transform an LL(k) grammar to LL(1) grammar. Write recursive-descent parser for LL(1) grammar; Construct LL(1) parse table.
5.	Design Turing machine to solve simple problems. Understand Church-Turing Thesis and other computational models.

Grading and Evaluation Criteria

Course grades will be determined as follows:

2 Midterm Exams, 20% each
Final Exam (Comprehensive), 30%
Exercises, Labs, and Homework, 30%
Exam dates will be posted at course schedule (at the bottom of this page).
Your final course grade will be determined by the standard college formula based on your course average: 90-100à "A", 80-89à "B", 70-79à "C", 60-69à "D", 0-59à "F".
You must have a passing average (60+) on both the major tests and the labs/exercises to pass this course.

Make-up exam late assignments: Homework/programming assignments are to be completed and turned in by the due date at the beginning of class. Late assignment will not be accepted. There are no makeup exams. If the final exam grade is higher than that of the midterm exam, it replaces the grade of the midterm exam. If you miss the midterm exam, your grade of the final exam will be counted twice. All missed grades will be recorded as zeros.

Course Content

	Topic
1.	Elementary Notions and Notations: Sets, Ordered Structures, Graphs and Trees
2.	Facts about Functions: Constructing Functions
3.	Grammars
4.	Regular Languages and Finite Automata: Regular Languages, Finite Automata, Constructing Efficient Finite Automata, Regular Grammars
5.	Context-free Languages and Pushdown Automata: Context-free Languages, Pushdown Automata, Parsing Techniques, Transforming Grammars
6.	Turing Machines and Church-Turing Thesis

Academic Dishonesty: For this class, all work must be done individually -- no group work is allowed. You are encouraged to generally discuss assignments with fellow students, but may not copy their solution or code. Doing so constitutes academic dishonesty which will be sanctioned with a grade of F, and possibly further disciplinary actions by the University.

Attendance Policy: Your failure to attend class (face to face or hybrid), engage course material (Online only); or make contact with faculty to adequately explain your absence by the 10^th class calendar day of the semester will result in your being administratively dropped from this course. Being dropped from this course may affect your enrollment status and/or your financial aid eligibility.

Statement on reasonable accommodations: The University of Houston-Downtown complies with Section 504 of the Rehabilitation Act of 1973 and the Americans with Disabilities Act of 1990, pertaining to the provision of reasonable academic adjustments/auxiliary aids for students with a disability. In accordance with Section 504 and ADA guidelines, UHD strives to provide reasonable academic adjustments/auxiliary aids to students who request and require them. If you believe that you have a disability requiring an academic adjustments/auxiliary aids, please contact the Office of Disability Services, One Main St. Suite 409-South Houston, TX 77002. (Office) 713-226-5227; (Website) www.uhd.edu/disability/; (Email) disabilityservices@uhd.edu.

Course Schedule

This is the tentative course schedule. It will be updated during the progress of the course. You should check it regularly for the assignment due dates and exam dates. Although it will be updated in the best effort, any conflicts should be resolved according to the announcements made in the class.

Week

Monday

Wednesday

1/16
Martin Luther King Jr Holiday

1/18
Chapter 1 Part 1

1/23

Chapter 1 Part 2

1/25
Chapter 1 Part 2

1/30

Chapter 3 Section 1

2/1

Chapter 3 Section 3