
CITIDEL >
Syllabus Collection >
Syllabus >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10117/6352

Title:  91.502 
Authors:  UMass Lowell Department of Computer Science 
Issue Date:  
Publisher:  UMass Lowell Department of Computer Science 
Citation:  http://www.cs.uml.edu/~giam/91.502/Syllabus_Spring_2005.html 
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, onetoone 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 0471439606 Errata
Other Materials:
Rice Theorem handout
NPCompleteness handout
Quantum computing handout (tentative topic)
Worked Homework Assignments
Instructor: G. Pecelli
Office: Olsen 217.
Office Hours: M 2:005:15; Th 1:304:00.
Other times, by appointments.
email: giam@cs.uml.edu
web site for course: http://www.cs.uml.edu/~giam/91.502/
IkonBoard:
Week Of
Readings
Topics
Problem Sets
Jan. 31
Ch. 1
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. 1516: 3, 5,7,8; p. 2122: 1, 3, 4.
Feb. 7
Ch 2
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.
Feb. 14
Ch 2
DFA and Regular Expressions, Closure Properties of Regular Languages, MyhillNerode 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.
Feb. 22
Ch 2
Hour+ Exam 1. Pumping Lemmas
Due: Feb. 28. # 2.8.2, 2.8.5, 2.8.7 a, b, c.
Feb. 28 Ch 3 ContextFree Grammas, Parsing and Ambiguity, Pushdown Automata and ContextFree 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, OneTape 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.
March 21
Ch 4 Multitape Turing Machines, ChurchTuring 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.
Apr. 11
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.
Apr. 20
Ch 6
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
ContextSensitive Languages, NP, PolynomialTime 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
May 16
Final Exam.
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
Total 100%
Homework Policy
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 MakeUp 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 makeup 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.
Incomplete Policy.
Incompletes will be considered only if the student has had a major and unavoidable catastrophe during the semester. Ex.: extensive, employermandated 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. 
URI:  http://www.citidel.org/handle/10117/6352 
Appears in Collections:  Syllabus

Files in This Item:
File 
Size  Format 
53Syllabus_Spring_2005.html  11Kb  HTML  View/Open 

All items in DSpace are protected by copyright, with all rights reserved.
