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

Fall 2009 (CRN: 11134, 3 credit hours, Class time: Tuesday-Thursday 5:30-6:45pm)

(Cross-listed as MATH 3316. Credit may not be earned for both.)

Prerequisites: Grade of C or better in CS 2310, 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 form a theoretical perspective.

Textbook: Hein, J. L., Discrete Structures, Logic, and Computability, Second Edition. Jones and Bartlett, 2002.

Instructor: Dr. Hong Lin Office: S-717

Office Hours: 2:00-4:30pm MTWR

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
• 3 Projects, 20% total
• Final Exam (Comprehensive), 30 %
• Quizzes, 10%
• 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 programming assignments to pass this course.
• The Last day to withdraw from a course with a grade of "W" is October 29, 2009 (6pm).

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.

Statement on reasonable accommodations: UHD adheres to all applicable federal, state, and local laws, regulations, and guidelines with respect to providing reasonable accommodations for students with disabilities. Students with disabilities should be notified to register with Disabled Student Services and contact the instructor in a timely manner to arrange for appropriate accommodations.

Course Schedule

This is the tentative course schedule. It will be updated during the proceeding 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	Tuesday	Thursday
1	8/25 Chapter 1 Part 1 HW: Sec 1.1 – 2(a, c, e), 5 Sec 1.2 – 1(b, d, f), 3(b, d, f, h), 9(b, d), 14(b), 18, 24(b, d, f)	8/27 Chapter 1 Part 2 HW: Sec 1.3 – 2(b, d, f), 4(b, d), 7, 12(b, d), 14(b, d)
2	9/1 Chapter 1 Part 2 HW: Sec 1.4 – 6, 10 Project 1 Handout	9/3 Chapter 3 Section 1 HW: Sec 3.1 – 2(b, d, f), 6(b, d, f), 10(b, d, f), 14, 17(b)
3	9/8 Chapter 3 Section 3 HW: Sec 3.3 – 2(b, d), 4(b, d), 6(b), 11(b, d, f)	9/10 Chapter 4 Section 1
4	9/15 Chapter 4 Section 1 HW: Sec 4.1 – 2(b, d), 4(b, d, f), 9(b, d), 12(b, d), 13(b, d), 18 Chapter 4 Section 2	9/17 Chapter 4 Section 2 HW: Sec 4.2 – 1(b, d), 3(b, d, f), 4(b), 7(b)
5	9/22 Review for 1st Test	9/24 1st Test
6	9/29 Chapter 4 Part 3	10/1 Chapter 4 Part 3 HW: Sec 4.3 – 2(b, d, f), 3(d), 7(b), 10 Project 1 Due Project 2 Handout
7	10/6 Chapter 4 Part 4 HW: Sec 4.4 – 2(b, d), 8, 11(b)	10/8 Chapter 11 Part 1 HW: Sec 11.1 – 1(b, d, f), 2(b, d), 5(b), 6(b) Project 3 Handout
8	10/13 Chapter 11 Part 2	10/15 Chapter 11 Part 2 HW: Sec 11.2 – 2(b, d, f), 4, 5(b), 6(b, d), 8(b) Solution to Project 3 – Activity 1 Due
9	10/20 Chapter 11 Part 3	10/22 Chapter 11 Part 3 HW: Sec 11.3 – 1(b), 4(b), 5 (b), 6, 9(b), 10(b, d) Solution to Project 3 – Activity 2 Due
10	10/27 Review for 2nd Test	10/29 2nd Test
11	11/3 Chapter 11 Part 4 HW: Sec 11.4 – 1(b, d, f, h), 2(b, d, f, h), 5, 6 Solution to Project 3 – Activity 3 Due Project 2 Due	11/5 Chapter 12 – Part 1 Solution to Project 3 – Activity 4 Due
12	11/10 Chapter 12 – Part 2	11/12 Chapter 12 – Part 2 HW: Sec 12.2 – 1(b, d), 7(b), 8 Solution to Project 3 – Activity 5 Due
13	11/17 No class	11/19 Chapter 12 – Part 3 HW: Sec 12.3 – 1(b, d), 3(b), 4(b), 5, 6(b) Solution to Project 3 – Activity 6 Due
14	11/24 Chapter 12 – Part 4 Solution to Project 3 – Activity 7 Due	11/26 Thanksgiving Holiday
15	12/1 Chapter 13 Part 1 Solution to Project 3 – Activity 8 Due	12/3 Review for Final Exam Project 3 Due
16	12/8 Reading Day	12/10 Final Exam 5:30pm – 8:00pm