COSC5315: Foundation of Computations: Course syllabus Fall 2012.
Instructor: Dr. Hikyoo Koh, Professor of CS
Office: MA68
Phone: 880-8779 (My Cell: 808-2554901, you can call me any time, day and night)
E-Mail: hkoh@lamar.edu(or HKPK32@YAHOO.COM)
HTTP: galaxy.cs.lamar.edu/~hkoh
Office hours (Summer):
MW: 14:50 --- 15:40
TTH: 11:00 --- 12:00
Sat: 11:00 --- 14:00 (About every other Saturday, with appointments preferred)
Others by appointments.
Required textbook:
Automata, Computability, and Complexity: THEORY AND APPLICATIONS,
by Elaine Rich, Prentice Hall, 2008
Other References:
1. Computability, Complexity, and Languages, Second Edition,
by Martin D. Davis, et al, Academic Press, 1994.
2. Introduction to Languages and The Theory of Computation, Third Edition, by
John Martin, McGraw-Hill, 2003
3. Elements of the Theory of Computation, Second Edition, by Harry Lewis and
Christos Papadimitriou, Prentice Hall, 1998.
4. Automata Theory, Languages, and Computation, 3rd Edition, by John E. Hopcroft
and Jeffrey D. Ullman, Addison Wesley, 2007.
Learning Objectives:
By completing this course, students will
1. deepen their understanding of measures for separating what computers can do
from what they cannot do,
2. deepen their understanding of hierarchical classifications and closure properties
of various grammars, languages, and accepting machines,
3. deepen their understanding of equivalences among grammars, languages and
accepting machines,
4. deepen their understanding of differences and equivalences between determinism
and non-determinism of various computing models, and
5. grasp thorough understanding of predicate logic and computational complexity
Topics to cover:
1. Review:
Computable functions:
Simple Programming Language
Partially computable functions, Total functions and Computable functions.
Macros.
Primitive recursion:
Composition, Recursion.
Initial functions.
Iterated Operations and Bounded Quantifiers and Bounded Minimalization.
Encoding schemes
Universal Programs:
Program Coding and Halting Problem (An Unsolvable Problem)
Recursively enumerable sets
Reducing the number of function arguments and Practical implication.
2. Turing Machines
Two Roles: Function computers and Language acceptors
Quadruples vs. Quintuples
Determinism vs. Non-determinism
Universal TM
TEST-1
3. Processes and grammars
Simulation of NTM's by Semi-Thue Processes
Post's Correspondence Problem.
Unsolvable problems on Grammars.
4. Regular Languages and Finite-State Automata
Equivalence of DSFA and NDSFA
Pumping Lemma and Closure Properties
Myhill-Nerode Theorem
5. Context-Free Languages
Normal Forms
Closure properties and Pumping Lemma
Push-down Automata
Deterministic CF Languages and their Closure Properties
Compiler applications
TEST-2
6. Context-Sensitive languages
Linear bounded automata
Closure properties
7. Quantification
Predicate logic and Semantics
Herbrand's Theorem
Unification
Satisfiability Problem and Unsolvability
8. Polynomial-Time Computability
Rates of Growth
P-Class Versus NP-Class
Cook's Theorem
Final Exam.
Grading methods:
2 tests: 200 points
Final Exam: 200 points
4 or more programs: 80 points
Occasional Pop Quizzes: 40 points
-----------------------------------------------------
TOTAL MAX: 520 points
If your class average is
85% or higher: A
Else 75% or higher: B
Else 65% or higher: C
Else: D
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:
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)
NOTE:
1. Everything you turn in to the instructor to be graded is expected to be your
own work at least for the most part.
In an unpleasant event of the instructor identifying two or more students having
submitted an identical or a very similar program, all students involved will get ZERO credit.
When above happens twice to a student, he/she will be dropped from the course and
further will be reported to the Department for additional punitive sanctions.
In particular, NO solution programs available on a computer locally or through
the INTERNET should be copied without the instructor's prior approval.
2. All programs will be accepted only in class and only when they are due.
No sooner or no later.
3. It is to your advantage if you highlight output statements such as Java print or println or
C++ cout statements of your programs to clearly indicate where in your program
outputs are being actually done.
4. A program is normally due in a week after it is assigned.
5. Each program must have a comment at the VERY beginning.
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.
6. If the language allows, the main program/function/method must appear at the very end of the program.
7. If you have five or more unexcused absences, your final grade will be lowered by one letter grade.