CSIT 443 Theory of Computation Spring 2007
Tentative Syllabus and Course Policies
_____________________________________________________________________________________________
Instructor: Dr. Iyad Abu-Jeib
Office: 109 Fenton Hall
Office Phone: 673-4757
Office Hours: MWF 4:00-5:00 PM, R 12:00-1:00 pm, F 5:00-6:00 PM or by appointment.
E-mail: abu-jeib@cs.fredonia.edu
Website: http://www.cs.fredonia.edu/abu-jeib
Meeting Times:
MWF 3:00 - 3:50 Fenton 175.
Textbook:
Introduction to the Theory of Computation, 2nd Edition, by Michael Sipser. Thomson Course Technology, 2006. ISBN-10: 0-534-95097-3.
In addition to the material in the textbook, there will be material covered from other sources. References: May be available later in the library (on reserve).
Prerequisites:
CSIT 242 and CSIT 341.
Grading:
1. Two hour exams and a comprehensive final. Each hour exam will consist 15% of your course grade. The final will consist 25% of the course grade.
2. Assignments. The assignments will consist 10% of your course grade.
3. Project: The project will consist 10% of the course grade.
4. Quizzes. The quizzes will consist 15% of the course grade.
5. Attendance and participation. Attendance and participation will consist 10% of the course grade. Here is the attendance policy:
a) You'll be allowed to miss at most 3 classes with no documented acceptable excuse (email is not considered as such).
b) Any class you miss after the first 3 classes described above will result in deducting 2% of your course grade. This applies until the 10% portion of the course grade assigned for attendance is consumed. Attendance may be taken randomly (may be 8 random classes).
c) If the student does not have satisfactory attendance, the student may not be notified, but I'll take a note of that and keep it in my records until I assign the course grades at the end of the semester.
d) You must be on time. You must not leave before the class ends. Repeated late arrival or early departure may be considered as absence.
e) Excusable absence must be documented and must be inline with the college's policy about that. You must inform me in advance if you intend to miss class for a legitimate reason. Legitimate reasons are reasons such as death in the family (with a proof) and illness (with a doctor's report). Absences for family gatherings or family problems or to catch a flight or because of another course, etc, are not considered excusable absences.
Remark: There is a possibility that I may not include attendance in the course grade for those who don’t want to count attendance. If that is the case, the 10% portion of the course grade that is assigned for attendance and participation will go for the final exam.
Attendance: Attendance is required (see above). You are responsible for material presented in class and for announcements announced in class. If you miss a class, it’s your responsibility to ask about the material covered in the class you missed and about the announcements announced that day. Make ups of exams/quizzes/worksheets are allowed only if you have a documented hardship. Late assignments won’t be accepted. Any measure to improve your grades (like extra-credit, extra points, and dropping a quiz/assignment (if happened)) may apply only to students who have satisfactory attendance.
Note: What’s stated above does not mean that I’ll give you extra-credit work or extra points or drop a quiz/assignment. I may do one of them or more of them or none.
Incomplete: Incomplete grade will be given only if you meet the university guidelines for incomplete.
Grading Scale: 92-100: A, 90-91: A-, 88-89: B+, 82-87: B, 80-81: B-, 78-79: C+, 72-77: C, 70-71: C-, 68-69: D+, 62-67: D, 60-61: D-, < 60: F.
Behavior: Inappropriate behavior will not be tolerated and severe consequences may follow. Any behavior that may result in disturbing the class, students, or the professor, is considered inappropriate behavior.
Academic Integrity (Fraud, Plagiarism, Cheating, Collusion): The consequences of any violation of academic integrity may include (but not limited to): a formal warning, a grade of zero assigned to that particular work (quiz, assignment, exam, project, etc), a failing grade in the course.
Final Exam: The final exam is accumulative. It will be Thursday, May 10, 6:30 PM – 8:30 PM.
Remarks:
1) This course is not CCC.
2) I may assign extra work to do for bonus points or do something else to improve your grades. Such work (if assigned) will be optional.
3) If you need help, please do not hesitate to ask for it. My job is to help you understand the material and succeed. I’ll be extremely happy to answer your questions and to assist you.
4) If you have a hardship, please let me know in advance.
5) I’ll be extremely happy to get a feedback from you about my teaching style and the level of difficulty of the exams and the assignments. We have to work together to make improvements if such improvements are needed. You can provide me with feedback directly or indirectly (by leaving a note underneath my office door or using the teaching feedback form on my website).
6) You must do your assignments by yourself. Do NOT work in pairs or in groups unless I ask you to.
7) I may cover material not available in the textbook. You are responsible for such material and for everything I mention in class.
8) I may not grade all the assignments and I may not grade all the questions/parts in the assignment I decide to grade.
9) Check your Fredonia email daily. I may contact you any day by email.
10) The syllabus is subject to change.
11) Bring your Fredonia ID to the exams and the quizzes.
12) The grading scale is subject to be made more flexible if that’s needed to improve the grades.
13) Keep all of your graded assignments, quizzes, exams, and all other graded stuff.
14) At some point of time, I’ll give you usernames and passwords to access your grades and other stuff. You’ll be able to change the password, but if you're taking two classes with me, make sure that each class has a different password.
15) Sometimes I repeat questions. Repeated mistakes result in harsher grading.
16) Here's how (unless I tell you something else) my makeup work is done (of course provided there is an acceptable documented excuse): If a student misses a quiz, the next quiz will be doubled (counted twice) and if a student misses a test, the next one will be doubled (i.e. counted twice). That does not apply, of course, to the final.
17) Always use only the notation used in class. Using a different notation may result in no credit or partial credit.
18) Always spread out when a quiz/test is given.
19) Never give two answers for the same question. If you do that, you'll get no credit.
20) On tests, quizzes, homework, always cross out unwanted writing.
21) An extra credit quiz may be given (may be without advanced notice) within a week of a quiz/test/homework. There will be no make up for such a quiz. Such quizzes will be given only when necessary.
22) I may make random photocopies of some random graded quizzes/homework/exams.
23) For “identify the error” questions, identifying non-errors as errors would result in deduction of points.
24) Suppose that I asked you to find all solutions of an equation and suppose the equation has two solutions. If you write down three solutions and two of them are the correct ones, you will not get a full credit and if you write down more than 3 solutions and two of them are the correct ones, you may get no points at all. A similar thing can be said about "find the error" questions.
25) One of the goals of discrete math (this is in addition to the fact that it's needed for other courses) is to offer students experience in mathematical thinking, problem solving, logic and reasoning.
26) If you make a mistake in "determine whether the following is true or false" in the truth value of one of the statements but that has no effect on the truth value of the whole compound statement, I may not deduct points. But, if you make a mistake in the truth value of a statement that changes the truth value of the whole compound statement, I may give you no points at all even if your answer is correct. For example, suppose the compound statement is true and it's of the form (F -> F) but someone ended up having (T -> F) and said the compound statement is true, then I give no points, because (T -> F) is a false statement.
27) I may ask each student to answer a question or more every class.
28) If a class was cancelled for an unexpected reason and a test/quiz/assignment/homework was scheduled or due that day, it will be held/due next meeting time.
Objectives:
This course provides students with the fundamentals in the theory of finite automata and formal languages, the theory of computability, and the theory of complexity.
Topics:
Regular languages and expressions; finite automata; contest-free languages and grammars; pushdown automata; Turing machines; decidable and undecidable problems; reducibility; computability; complexity theory. The topics in detail are:
1) Review of sequences, sets, multisets, graphs, prime numbers, Boolean logic, proof techniques, functions, relations, big O and small o notation, analyzing algorithms.
2) Strings and languages.
3) Historical overview.
4) Finite automata.
5) Regular expressions and languages..
6) Deterministic finite automata (DFA).
7) Minimizing DFA.
8) Nondeterministic finite automata (NFA).
9) Nonregular languages.
10) Equivalence of NFA and DFA: converting NFA to DFA.
11) Contest-free grammar/languages.
12) Pushdown automata.
13) Turning machines (TM).
14) Multitape TM.
15) Nondeterministic TM.
16) Enumerators.
17) Algorithms.
18) Hilbert’s problems.
19) Decidable languages (concerning regular languages and contest-free languages).
20) The Halting Problem.
21) Undecidable languages.
22) Turing-unrecognizable languages.
23) Reducibility; computable functions.
24) Class P, class NP, class NPC, class L, class NL, class PSPACE, class L, class NL, class coNL, class NLC.
25) Many other topics from time and space complexity and many examples from the classes mentioned above.
26) Other topics.
Remark: In addition to almost all of the first 8 chapters of the textbook, I may cover a lot of material from other books. The examples (as it’s the case in my other classes) are usually not from the book in order for students to have more examples to look at.