Syllabus Collection >
Please use this identifier to cite or link to this item:
|Authors: ||UMass Lowell Department of Computer Science|
|Issue Date: |
|Publisher: ||UMass Lowell Department of Computer Science|
|Abstract: ||University of Massachusetts Lowell
Department of Computer Science
91.502 Theoretical Foundations of Computer Science --- Spring 2005
SYLLABUS AND COURSE POLICY
Prerequisites: 1) 91.500 or 92.322, 2) 91.404 or 91.583, and 3) at least one computer programming course or significant programming experience. This course is highly mathematical. This course is not for you if you miss any one of these three prerequisites.
Math prerequisites - details:
1. Set theoryâ€”notations, operations, DeMorgan laws, infinity, countable sets, uncountable sets, one-to-one correspondence
2. Algebraâ€”symbol manipulations, linear equations, substitutions, number systems (binary, decimal, etc)
3. Mathematical inductionâ€”normal version and stronger version; induction on integers, on string length, on set sizes, etc
4. Number theoryâ€”congruence relations, prime numbers, Fundamental Theorem of Arithmetic, etc
5. Combinatoricsâ€”basic concepts and counting techniques
6. Recursionâ€”recursive definition of mathematical concepts, solving simple recursive relations
7. Integer functionsâ€”function limits, asymptotic comparisons, logarithmic functions, polynomials, exponential functions
8. Seriesâ€”summation of common series, approximations to n!
9. Graph theoryâ€”basic terminology and properties, trees, traverse algorithms
TEXTBOOK: Du and Ko, Problem Solving in Automata, Languages, and Complexity, Wiley, 2001. ISBN 0-471-43960-6 Errata
Rice Theorem handout
Quantum computing handout (tentative topic)
Worked Homework Assignments
Instructor: G. Pecelli
Office: Olsen 217.
Office Hours: M 2:00-5:15; Th 1:30-4:00.
Other times, by appointments.
web site for course: http://www.cs.uml.edu/~giam/91.502/
Math. Preliminaries; Strings and Languages; Regular Languages and Regular Expressions. Note: If you find Sections 1.1 and 6.1 difficult, then this course is not for you.
Due: Feb. 7: p. 7: 2,3,5,6; p. 15-16: 3, 5,7,8; p. 21-22: 1, 3, 4.
Deterministic Finite Automata (DFA), Checker method of constructing DFA, Product automata method and complement automata method of constructing DFA, NFA, Equivalence of NFA and DFA Due: Feb. 14. #2.1.1, 2.1.2; 2.2.1, 2.2.2, 2.2.3; 2.3.1, 2.3.3. 2.3.4; 2.4.1, 2.4.2.
DFA and Regular Expressions, Closure Properties of Regular Languages, Myhill-Nerode Theorem, Minimum DFA, Pumping Lemma Due: Feb. 22. #2.5.3, 2.5.4; 2.6.3, 2.6.6, 2.6.8; 2.7.2, 2.7.3, 2.7.5.
Hour+ Exam 1. Pumping Lemmas
Due: Feb. 28. # 2.8.2, 2.8.5, 2.8.7 a, b, c.
Feb. 28 Ch 3 Context-Free Grammas, Parsing and Ambiguity, Pushdown Automata and Context-Free Grammars. Due: March 7. #3.1.2, 3.1.5, 3.1.8; 3.2.1a, 3.2.2a, 3.2.3a, 3.2.4; 3.3.3, 3.3.6; 3.4.1adf.
March 7 Ch 3, Ch 4 Pumping Lemmas for CFL, One-Tape Turing Machines Due: March 21. #3.4.3, 3.4.4; 3.5.1a, 3.5.3ab, 3.5.6; 3.6.1, 3.6.2ag, 3.6.5ab, 3.6.9ab.
Ch 4 Multi-tape Turing Machines, Church-Turing Thesis, Unrestricted Grammars Due: March 28. 4.1.2, 4.1.5; 4.2.1, 4.2.3a,c, 4.2.4a,c; 4.3.3, 4.3.4a,c, 4.3.5a,c, 4.3.6.
March 28 Ch 5
Primitive and Partial Recursive Functions (brief introduction), Universal Turing Machines, R.E. Sets and Recursive Sets Due: April 4. 4.5.1, 4.5.3a; 4.6.1a,b, 4.6.3; 4.7.1; 4.8.1.
Apr. 4 Ch 5
Diagonalization, Reducibility, Rice Theorem, Due: April 11. 5.1.1; 5.2.1, 5.2.3a, 5.2.4, 5.2.5, 5.2.7abc.
Recursion Theorem, Undecidable Problems Due: April 20. 5.3.1, 5.3.2, 5.3.4; 5.4.1, 5.4.2, 5.4.7.
Hour+ Exam 2. Time & Space Complexity
Due: April 25. 5.5.2, 5.5.6; 5.6.1a, 5.6.2a.
Apr. 25 Ch 6
Hierarchy Theorems, NTMâ€™s Due: May 2. 6.1.1, 6.1.2; 6.2.1, 6.2.3, 6.2.7.
May 2 Ch 6, Ch 7
Context-Sensitive Languages, NP, Polynomial-Time Reducibility Due: May 9. 6.3.3a, 6.3.4a; 6.4.1a, 6.4.4; 6.5.3, 6.5.4.
May 9 Ch 7
Bounded halting, Bounded tiling, and Cookâ€™s Theorem Due: May 16
Comprehensive from day one.
Hour+ Exam 1 : Tuesday, Feb. 22
Hour+ Exam 2 : Wednesday, April 20
Hour+ Exams will be held during class time.
3 Hour Final Exam (Comprehensive): as scheduled during Final Exam period.
For sample exams, see: http://www.cs.uml.edu/~wang/cs502/
Course Grading Policy
HOMEWORK 20% or less
2 HOUR+ EXAMS 40%
FINAL EXAM 40% or more
Homework is due when stated Late homework will be accepted, with a penalty of 2^n (n=number of calendar days past due date). It will not be graded at all if received beyond 6 days after the due date.
Exam Make-Up Policy .
Students who are unable to attend on the day of an exam must notify the instructor as soon as possible, must have a documented legitimate reason, and must take the make-up within one week of the original date of the exam . Exceptional circumstances will receive due consideration, provided appropriate and timely notification is given, accompanied by appropriate documentation. Any attempt at notifying the instructor after one week has elapsed requires proof that no earlier notification was physically possible. Having two or more exams during the same week is not a legitimate reason for special consideration.
Incompletes will be considered only if the student has had a major and unavoidable catastrophe during the semester. Ex.: extensive, employer-mandated travel that was not forseeable at the time of enrollment in the course.
Plagiarism and "collaboration".
Homework is supposed to be your own. Discussion with other students is encouraged, but sharing of finished copy will be considered cheating. There are solutions for most problems from the textbooks "out in cyberspace". Please work out your own. If you have used help from "cybersources" you must so state - problem by problem. The first failure to do so will result in a grade of 0 on the whole assignment; the second failure will result in an F in the course. Evidence of cheating on an exam will result in an F in the course.|
|Appears in Collections:||Syllabus|
Files in This Item:
All items in DSpace are protected by copyright, with all rights reserved.