Course Information

Title:	Introduction to the Theory of Computation
Institution:	Metropolitan State University of Denver
Course ID:	CS 3240, §1 & §2     (HON 3240)
Semester:	Spring 2015
Meetings:	Tuesdays & Thursdays 2:00PM - 3:50PM §1 Jan 20, 2015 - Mar 14, 2015 §2 Mar 16, 2015 - May 16, 2015
Location:	Central 101
Credit Hours:	2
Prerequisites:	CS 2050 and MTH 3170 with grades of "C" or better
Policies:	http://www.jodypaul.com/cs/theory
Moodle Site:	http://http://gouda.msudenver.edu/moodle
Instructor:	Dr. Jody Paul (schedule & office hours)
E-mail:	jody @ computer.org
Office:	Science 1038 (x68435)
Campus Mail:	Campus Box 38

Course Description

---

Participants are expected to have good working facility with the mathematical concepts and tools addressed in the prerequisite course MTH 3170 and its cascaded prerequisites. This course makes heavy use of formal logic, set theory, and formal proofs in working with functions, relations, graphs, induction, and recursion. Knowledge and skill in computer programming are likewise presumed, commensurate with the application of concepts from the prerequisite course CS 2050 and its cascaded prerequisites.

Note that this 2 credit-hour course is taught as a 4-hour course over half of a semester. The demands are thus equivalent to a 4 credit-hour course for the duration of that half-semester. A nominal expectation for students with strong prerequisite knowledge is a minimum of 8 hours per week outside of class (approximately 64 hours) in addition to the scheduled class time. Students with weaker prerequisite knowledge may find they need to invest substantially more time. N.B. Attendance during the first week of class is required (as specified in the MSU Denver Student Handbook Academic Policies for Students.

Distribution (weights):
30% = Assignments
26% = Midterm
44% = Final Exam

The lowest assignment score will be dropped in computing the total for the Assignments category.

Conversion:

          A  : 93% ≤ score
          A- : 90% ≤ score < 93%
          B+ : 87% ≤ score < 90%
          B  : 83% ≤ score < 87%
          B- : 80% ≤ score < 83%
          C+ : 77% ≤ score < 80%
          C  : 73% ≤ score < 77%
          C- : 70% ≤ score < 73%
          D+ : 67% ≤ score < 70%
          D  : 63% ≤ score < 67%
          D- : 60% ≤ score < 63%
          F  : score < 60%

Introduction to the Theory of Computation (Third Edition)
by Michael Sipser
Cengage Learning (2012); ISBN 113318779X
REQUIRED

 

JFLAP: An Interactive Formal Languages and Automata Package
by Susan H. Rodger and Thomas W. Finley
Jones & Bartlett Learning (2006); ISBN 0763738344
REQUIRED

JFLAP
A package of interactive graphical tools that aid in learning the basic concepts of formal languages and automata theory
http://www.jflap.org
REQUIRED

Assignments

Extensive hands-on practice is necessary to achieve the required understanding of and ability to utilize the concepts in computer science theory. Such practice is correlated with successful performance on exams.

Assignments represent your opportunity to practice applying the concepts, thereby enhancing your understanding and helping you to identify questions regarding the concepts and their application.

The assigned exercises target these objectives. You are expected to work through all assigned exercises and are strongly advised to attempt as many additional exercises as you need to develop facility with the concepts and techniques.

JFLAP provides you with the direct means to objectively determine the correctenss of your work. Even where JFLAP files are not required to be submitted, you are expected to use JFLAP to verify your solutions. JFLAP is a valuable tool that supports your experimentation with and exploration of the course material.

Details regarding assignments and projects will be provided in class and on the course websites.

Online Submission

Assignments must be turned in using the course "moodle" website unless explicitly specified otherwise. In particular, e-mail and hard-copy will not be accepted in lieu of online submission. The Moodle assignment activity allows you to enter and upload working-drafts (such as work in progress that you do not intend to be assessed as the assignment submission). Therefore, to indicate that you wish your assignment entry to be accepted for assessment, you must click the Submit button for that assignment. Note that failure to click the Submit button will result in no earned score for the assignment. Note further that use of the Submit button indicates that the assignment is ready to be scored.

Due Dates/Times

Deliverables associated with assignments may be aubmitted for scoring at any time prior to the published due date/time.

No assignment deliverables will be accepted more than 24 hours after the published due date/time.

N.B. All risks associated with late submissions are assumed by the student. Note in particular that system and network failures occuring after the published due date/time will not result in an extension of the late submission acceptance period.

Illness, crises, and emergency situations will be dealt with on a case-by-case basis in accordance with University, School, and Departmental policies.

Deliverable Formats

Text-only documentation should be plain (unformatted) text in ASCII or UTF-8. If a diagram is part of the documentation then the file must be one of PDF, GIF, JPEG, PNG or ASCII text using fixed-width style character diagramming. (Specifically unacceptable formats include: Microsoft Word, Apple Pages, Microsoft Powerpoint) If an archive of multiple files is required, the format will be specified. JFLAP files must use the associated extension .jff

Note that a deliverable submitted in an unacceptable format is equivalent to no submission at all. Similarly, a submission with an incorrect name is likewise equivalent to no submission. If you are unsure about the acceptability of a file format or the specification of file name, please check with your instructor well before submission.

Class Sessions & Websites

You are expected to prepare in advance for class sessions (reading, exercises, etc.).

Substantial information is disseminated during class sessions and via the course websites. You are responsible for knowing this information whether or not you attended the sessions or accessed the websites.

In addition to important course and domain information, the course support website also provides the vehicle for managing assignments and assessment.

Collaboration & Citation of Sources

Collaboration is encouraged and regarded as an essential aspect of learning Computer Science and programming. Collaboration and discussion with fellow students and instructors concerning course information, materials, assignments, projects, proofreading, and concept exploration is strongly encouraged. You are not expected to learn the course content or work on assignments and projects in isolation on your own.

That said, you must generate your own submissions, reflecting your individual effort, for every assignment you turn in to be assessed, even if the outcome results from collaborative effort. You must also credit the people with whom you worked.

If you consult any sources, you must explicitly reference the sources and indicate where and how they apply.

Turning in work that does not credit collaborators, includes quotations without corresponding citations, or does not properly cite sources, must be treated as academic dishonesty and an attempt at fraud. All incidents of suspected dishonesty will be reported to the department and the Dean of the college. Consequences may include a score of 0 on the assignment, a grade of "F" for the course, academic probation, or dismissal from the institution. This is a very serious matter and should not be taken lightly. If you have any uncertainty or concerns, please discuss them with me or your advisor.

Note that collaboration is not acceptable during any exam.

Official Information

Official policies applicable to all courses: http://cs.msudenver.edu/degrees/courses/policies

MSU Denver College Catalog: http://catalog.msudenver.edu
Official announcements, including Academic Policies and Procedures and Student Rights and Responsibilities

MSU Denver Academic Calendar: http://www.msudenver.edu/events/academic/
Additional official dates and deadlines, including the last dates to withdraw and receive NC and holidays

MSU Denver Student Handbook: http://www.msudenver.edu/handbook/
Important Metro State and Auraria campus policies and procedures for students