Computing and Information Technology Interactive Digital Educational Library


Syllabus Collection >
Syllabus >

Please use this identifier to cite or link to this item:

Title: 91.502
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 Other Materials: Rice Theorem handout NP-Completeness 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. e-mail: web site for course: 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. 15-16: 3, 5,7,8; p. 21-22: 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, 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. 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 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. March 21 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. 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 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 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: 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 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. Incomplete Policy. 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:

File SizeFormat

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


Valid XHTML 1.0! DSpace Software Copyright © 2002-2006 MIT and Hewlett-Packard - Feedback