Jody Paul (Logo) Dr. Jody Paul – EducationMSCD Courses
Theory of Computation
jody@acm.org    
     
Link to Home Page for Jody Paul Link to the Education section main page Link to Software Engineering section Link to Music section Link to Recommendations section
    Link to MSCD Courses page        

Course Information

Title: Introduction to the Theory of Computation
Institution: Metropolitan State College of Denver
Semester: Spring 2010 (January 19 - March 13)
ID [CRN]: CS 3240 [34775]
Meeting Times:

Tuesdays & Thursdays, 3:00 PM - 4:50 PM

Location:

Science 1097

Prerequisites: CS 3050 and MTH 3100
Course Website: http://www.jodypaul.com/cs/theory
Course Support: http://www.jodypaul.com/moodle/
Instructor: Dr. Jody Paul (schedule & office hours)
E-mail: jody@cse.mscd.edu
Office: Administration 420
Campus Mail: Campus Box 38

Course Description:

This course is concerned with the following:
     What are the fundamental capabilities and limitations of computers?
     What makes some problems computationally hard and others easy?

The 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, complexity, unsolvable problems, and intractable problems (NP-Completeness).

Prerequisites: CSI 3050 and MTH 3100 with grades of C or better, or permission of instructor.

Course Objectives:

Upon completion of this course you should be able to:
  • Determine the language represented by a regular expression
  • Create a regular expression from a language description
  • Construct a deterministic finite automaton accepting a given language
  • For a given finite automaton (deterministic or nondeterministic) determine if a string is accepted
  • Draw a state diagram for a finite automaton (deterministic or nondeterministic) that accepts a given language
  • For a given finite automaton (deterministic or nondeterministic) find a minimum-state equivalent deterministic finite automaton
  • Use a grammar to generate or accept a string
  • For a given grammar give the derivation(s) of a specified string and draw the corresponding parse tree(s)
  • Construct a context-free grammar for a language
  • Construct a pushdown automaton that accepts a given language
  • Show that a specific language is context-free
  • Trace the computation for a specified Turing machine
  • Create a Turing machine to solve a specified problem
  • Determine whether a problem about Turing machines is solvable or undecidable
  • Arrange classes of languages in order of increasing generality
  • Discuss relative computational power of language recognizers

Resources:

Textbooks (Available at Auraria Campus Bookstore)
Image of Book Cover - Introduction to the Theory of Computation / Link to Amazon.com

Introducing the Theory of Computation
by Wayne Goddard
Jones and Bartlett (2008)
ISBN 0763741256  [Amazon]

jflap text / link to Amazon.com

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

Application
 

JFLAP
A package of graphical tools that aid in learning the basic concepts of Formal Languages and Automata Theory

JFLAP Website


Computation & Connectivity:
Participants need to use JFLAP and to access the World Wide Web and MSCD e-mail accounts. Note that all participants receive access to necessary technology resources by virtue of being students at MSCD (see: http://www.mscd.edu).

Policies:

N.B. Significant information will be disseminated during class sessions or on the course support website for which you are responsible whether or not you attended the sessions or accessed the website.

Learning — Practice & Collaboration

Extensive hands-on practice is necessary to achieve the required understanding of and ability to utilize the concepts in computer science theory. Experience confirms that such practice is also necessary for successful performance on exams.

The assigned exercises specifically 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. You are expected to use JFLAP to verify your solutions. JFLAP is also a valuable tool to support your experimentation with and exploration of the course material.

Since exercises represent your initial opportunity to work with and learn the material, your facility with the materialwill not be assessed until the midterm and final examinations, thereby affording additional time and opportunity for practice. Thus the correctness of exercise solutions will not be graded.

Rather, an individual write-up is required for each exercise set, in which you are to reflect on the experience of working on the assignment and report personal insights and observations about learning that took place. The write-up must also demonstrate your attempts at working through the exercises and resulting familiarity with the concepts expressed in the exercises and the exercises themselves.

The correctness of exercise solutions is also not graded so as to foster an environment that emphasizes learning and collaborative study versus grades and isolation.

I strongly encourage collaboration and regard it as essential aspect of Computer Science and its study. Collaboration and discussion with fellow students concerning course information, materials, assignments, and studying for exams is very much advised. You are not expected to learn the course content or work on assignments in isolation on your own. Note that collaboration is not acceptable during any exam.

Grading

Your final course grade is determined by combining your scores on exercise write-ups and exams.

Here is the rubric used for the assessment of individual write-ups.

5/5: Relevant, reflective and insightful; focuses on learning aspects of the experience (such as identification of unexpected and interesting occurrences); demonstrates concerted effort and resulting familiarity with all exercises; goes beyond the obvious; correct spelling and grammar.

3/5: Limited demonstration of effort or resulting learning; descriptive rather than reflective (such as describing the steps rather than insights); minor spelling or grammar errors that do not interfere with the content.

1/5: Content trivial or unclear; major spelling or grammar errors; turned in late.

0/5: Missing or off-task.

You are guaranteed a grade no lower than that computed by the following distribution of total points and weighted conversion to letter grade:

Distribution:
Exercise write-ups = 35%
Midterm = 25%
Final Exam = 40%

Weighted conversion to letter grade
100-90%: A;  89-80%: B;  79-70%: C;  69-60%: D;  59-0%: F

 

Official Announcements:

Official policies applicable to all courses: http://cs.mscd.edu/metadot/index.pl?iid=2249

Also see the MSCD College Catalog at http://www.mscd.edu/academic/catalog/ for official announcements, including Academic Policies and Procedures and Student Rights and Responsibilities, and the Academic Calendar at http://www.mscd.edu/academic/acal.htm for additional official dates and deadlines, including the last dates to withdraw and receive NC (with and without faculty signatures).

Valid HTML 4.01 Transitional©2002,2003,2006,2008,2009,2010 Dr. Jody Paul – All Rights Reserved