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

Science 1097

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).

• 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

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