|Title:||Introduction to the Theory of Computation|
|Institution:||Metropolitan State College of Denver|
|Semester:||Fall 2003 (August 18 - December 13)|
|ID, Section [CRN]:||CSI 3240, Section 1 |
Mondays and Wednesdays, 6:00 PM - 6:50 PM
|Instructor:||Dr. Jody Paul (schedule)|
Mondays/Wednesdays 6:50PM - 7:50PM
|Campus Mail:||Campus Box 38|
|This course explores language theory and computability. Language theory includes: regular expressions, regular languages, finite automata (deterministic and non-deterministic), context-free languages, pushdown automata, and language grammars. Computability includes: Turing machines and their computing power, unsolvable problems, and intractable problems (NP-Completeness).|
|Prerequisites: CSI 3050 and MTH 3100 with grades of C or better, or permission of instructor.|
|Upon completion of this course the you should be able to:
You must have World Wide Web access and an e-mail account. Note that you receive an e-mail account and Internet access by virtue of being a student at MSCD (see: http://www.mscd.edu).
Your final course grade is determined by combining your grades on assignments and exams. You are guaranteed a grade no lower than that computed by the following distribution of total points and weighted average conversion to letter grade:
Every assignment turned in must include a section labeled Reflection that includes your personal insights and observations. This section is expected and required, whether or not the assignment specification mentions it explicitly.
Formats of files turned in for assignments must not depend on specific operating systems or software that requires purchase or paid licensing. The following are examples of acceptable formats: ASCII text, UNICODE text, HTML, PDF, GIF, JPEG. The following are examples of unacceptable formats: Microsoft Word, AppleWorks. If the assignment consists of multiple files, you are encouraged to bundle them into an archive in tar, zip or sit format.
Late assignments will not earn course credit. You may submit an assignment after its due date for comments and advice, and you are encouraged to do so. However, the score for that assignment will be recorded officially as 0. Likewise, missing an exam will result in a score of 0 for that exam. Late homework and make-up exams will not be accommodated without prior arrangement and written agreement. Unforeseeable crises and emergency situations will be dealt with on a case-by-case basis in accordance with MSCD, College, and Departmental policies.
Note that significant information will be disseminated during class sessions or on the course website that you will be responsible for whether or not you attended the sessions or accessed the website. Not all information necessary to successfully complete the assignments or examinations is covered in the texts.
I encourage collaboration and regard it as essential aspect of Computer Science. Collaboration and discussion with fellow students concerning course information, materials, assignments, and studying for exams is encouraged. You are not expected to learn the course content or work on assignments in isolation on your own. However, you must write up your own solution, individually, to every problem you turn in even if the solution is the result of a collaborative effort. In your write-up, you must credit the people with whom you worked. If you consult any reference material other than the textbook, please note in your assignment which sources you used for each problem. Note that collaboration is not acceptable during any exam.
|Background, Review, Introduction||Chapter 0|
|Finite State Automata & Regular Languages||Chapter 1|
|Pushdown Automata & Context-Free Languages||Chapter 2|
|Turing Machines||Chapter 3|
|Complexity (P, NP, NP-completeness)||Chapter 7|
See MSCD Calendar
The college policy on Class Attendance on Religious Holidays is posted on the information board outside the Mathematical and Computer Sciences department office (SI141). In addition, copies of this policy are available from the department upon request. It is the students' responsibility to understand and abide by the policy.
Students desiring a reasonable accommodation under the ADA must contact the instructor immediately to discuss their needs. Failure to notify the instructor, in a timely manner, of the need for a reasonable accommodation may hinder the college's ability to assist students in successfully completing the course.
©2002,2003 Dr. Jody Paul