Course Syllabus
COSC3302 (Theory of Computation) Spring 2013.
Instructor: Dr. Hikyoo Koh, Professor of CS
Office: MA68
Phone: 880-8779 (Cell: 808-2554901, you can call this number any time, day and night)
URL: galaxy.cs.lamar.edu/~hkoh
E-Mail: hkoh@lamar.edu (or HKPK32@Yahoo.Com)
Office hours:
MW: 14:00 --- 15:30
TTh: 15:45 --- 16:45
Sat: 11:00 --- 14:00 (On the average, every other Saturdays, with appointments
Preferred in advance)
Others: By appointments
Required textbook:
Introduction to Languages and the Theory of Computation, 4th Edition, John C. Martin, McGraw Hill, 2011
Other References:
1. Theory of Computation: An Introduction by James L. Hein, Jones and Bartlett Publishers, 1996.
2. Computability, Complexity, and Languages, by Martin D. Davis and others, 2nd edition,
Academic Press, 1994.
Catalog Description:
Preliminary review/introduction of the mathematics and logic for the course. Programs and computable
functions, primitive recursive functions, the universal programs, Turing machines and regular languages.
Learning Outcomes:
By completing this course, students are expected to:
1. acquire clear understanding of foundation and principles of computer science
such as (a) what computers can do, (b) what computers cannot do, (c) relationships
and equivalences among different types of grammars, languages and accepting
machines, (d) limits of algorithmic computation, and (e) differences and
equivalences between determinisms and non-determinisms in various computing models..
2. acquire clear understanding of regular grammars, regular languages and finite-state acceptors,
3. acquire clear understanding of context-free grammars, context-free languages, and
non-deterministic push-down acceptors,
4. acquire clear understanding of phrase-structured grammars, recursively enumerable
languages and Turing machines, and
5. acquire basic understanding of computational complexity pertinent to different levels of difficulties
in solving computer-related problems.
Topics to cover:
A. Unit-1: Logic and Finite Automata and
Regular Expressions.
1. Binary Relations:
Properties of Binary Relations: Reflexive, Symmetric, Transitive.
Equivalence Relations: Equivalence Classes, Partitions.
2. Formal Logic.
Propositional Logic and Normal Forms.
Predicate Calculus.
3. Regular Languages and Finite State Automata Equivalence:
Regular Languages, Regular Expressions, Deterministic FA, Nondeterministic FA
Closure Properties
Pumping Lemma.
Exam-1
B. Unit-2: Context-Free
Languages and Pushdown Automata.
4. Context-free languages
Derivation Trees and Ambiguity
Normal forms
5. Non-deterministic Pushdown Automata
Deterministic Pushdown Automata (Special cases)
Equivalence between CFG and NDPD Automata
Pumping lemma
Closure properties and Decision Problems
Parsing Techniques.
Exam-2
C. Unit-3: Non-Context-Free Languages and
Undecidable Problems
6. Programs and Computable Functions
Simple Programming Language
Partially computable functions.
Total functions.
Computable functions and Primitive Recursive functions.
Universal Functions
Macros.
7. Turing Machines
Quadruples and Quintuples.
Universal Turing Programs
TM Halting Problems and Problem Reduction
Undecidable Problems, Limits of Computing.
Nondeterministic TM.
Exam-3
Grading method:
3 Exams 300 points
Final Exam: 200 points
5 programs: 100 points
(Programming assignments will include
Smallest Equivalence Relation Computation
Elimination of Empty-Transitions from NFA Automata
Parser Construction for simple Numeric Expressions
Reduction of Context-Free Grammars and
A Simple Interpreter construction for a Simple Language)
1 Research paper (On Applications): 20 points
3 Homework problem sets. 60 points
4 or so Pop Quizzes: 40 points
----------------------------------------------------------------------
TOTAL MAX: 720 points
Your final grade will be determined by your class average as follows:
1. If it is 88% or higher: A
2. Else if it is 78% or higher: B
3. Else if it is 68% or higher: C
4. Else if it is 58% or higher: D
5. Else: F
Online Course Evaluations.
Lamar University encourages students to evaluate online the courses they take
and the instruction they receive via a contract with a national company,
OnlineCourseEvaluations.com.
The evaluation instruments themselves were developed by LU faculty and administrators.
Evaluation windows for fall and spring courses open two weeks before the final
examination period and close at the end of the last class day.
The student is notified of the specific dates at his/her myLAMAR e-mail address.
If course evaluations are given during summers, mini semesters, and other
compressed terms, evaluation windows are extended past the last class meeting.
Evaluations are completely anonymous, and neither LU faculty nor LU administrators
have the ability to determine the name of the student who completed a specific
evaluation form.
The primary purpose of course evaluation is the improvement of instruction.
That is, after the semester has ended and grades have been awarded, I am able to access
the results of my course evaluations, to include all student comments.
I analyze the data and read the comments, and often use student observations and
suggestions to make changes in course content and delivery.
The results of course evaluations are also used by chairs and deans as one factor
in decisions involving merit pay, tenure, and promotion.
Both the administration and I take your input via course evaluations very seriously,
and I encourage you to participate in this process.
Any questions or comments you have about the process should be addressed to
Dr. Tom Matthews, University Assessment Coordinator, at 409-880-2385 or
tom.matthews@lamar.edu. Thank you.
Students with Disabilities:
It is the policy of Lamar University to accommodate students with disabilities pursuant to federal and state laws and the University’s commitment to equal educational opportunities.
This course complies with the University Policies on Disability, Accommodations and Academic
Honesty as published in the Student Handbook and also in the Computer Science Department
Policy (on Academic Honesty). Student needing accommodations must first have them approved
through the Office of Services for Students with Disabilities, Communication Building Room 105, phone number 409-8808347.
Please notify the instructor during the first week of class regarding accommodations needed
for the class.
University Policy on Academic Honesty:
The University expects all students to engage in all academic pursuits in a manner that is above reproach.
“Cheating” include:
· Copying from another student’s paper, report, computer files, data listings, and/or programs.
· Using (during an exam) materials not authorized by the instructor giving the exam.
· Collaboration, without authorizations, with another person during an examination or in preparing academic work.
· Knowingly, and without authorization, using, buying, selling, stealing, transporting, soliciting, copying, or possessing in whole part, the contents of an unadministered test.
· In the taking of an examination or in the preparation of academic work to be submitted for academic credit, (1) Substituting for another student, (2) permitting any other person, (3) or otherwise assisting any other person to substitute for oneself or another student.
· Bribing another person to obtain an unadministered exam or information about an unadministered exam.
· Purchasing (or acquiring) and submitting as one’s own work any research paper or other writing assignment prepared by an individual or firm. This does not apply to the typing of the rough and/or final versions fo an assignment by a professional typist.
“Plagiarism”: The appropriation of another’s work or idea and the unacknowledged incorporation of that work or idea into one’s own work offered for credit.
“Collusion”: The unauthorized collaboration with another person in preparing work offered for credit.
Course Attendance Policy:
It is the student’s responsibility to make sure that you are officially enrolled in this course. If at any point in time, you decide to drop the class, it is your responsibility to officially drop. The instructor will do everything possible to help you. Any student who stops attending the class and does not officially drop the course will be given an “F” as the final grade.
Regular class attendance is critical to your effective learning. Hence each time you miss the class without the instructor’s authorization, your final grade will be lowered by one letter grade.
Please view the Lamar University web page for dates for drops and withdrawals.
Student Services:
Student services information can be found at: students.lamar.edu.
NOTE:
1. The first violation of the above specified University Policy on Academic Honesty will get a grade of 0 and the second violation will get a final grade of F.
2. Furthermore, everything you turn in to the instructor to be graded is expected to be your own work at least for the most part.
In particular, NO solution programs available on a computer locally or through the INTERNET should be copied without the instructor's prior approval.
3. All programs will be accepted only in class and only when they are due. No sooner or no later.
4. It is to your advantage if you highlight output statements such as Java’s System.out.print() or System.out.println() or C++ cout statements of your programs to clearly indicate where in your program outputs are being actually done.
5. A program is normally due in two weeks after it is assigned and discussed.
6. Every four unexcused absences from class will lower your final grade by one letter grade.
7. Each program must have a comment at the VERY beginning of the program.
Without this comment, a program will not be graded at all.
This comment must include:
a. Your full name
b. Course Number and program number
c. Program title
d. Your own assessment of the program that includes, among others:
i. whether or not the program produces expected correct outputs.
ii. if not, why you think the program is not producing the expected
correct outputs.
iii. if not, whether or not the program was compiled at all.
8. If the language allows, the main program/function/method must appear at the very end of the program.