CSCI 550:  Theory of Computing
CSCI 659:  Topics in Computing Theory

Registration Information

This course is also being offered as a special session, self-paced, archived course. If you are interested in signing up for this course as a distance education student, please contact the Center for Regional and Continuing Education (RCE) by sending e-mail to rce@csuchico.edu, or call 530 898-6105 for detailed registration information. Additional information is also available at http://rce.csuchico.edu/cen/selfpaced.asp ...

Information for local students:

Term/Year	Class  Number	Section	Act	Days	Time	Room
Sp 2010	3271	CSCI 550-01	DIS	MW	400-515	OCNL 123
Sp 2009	3584	CSCI 550-01	DIS	TR	200-315	OCNL 123
Fa 2008	4363	CSCI 550-01	DIS	MWF	1200-1250	GLNN 210
Sp 2008	6455	CSCI 550-01	DIS	MWF	1200-1250	OCNL 123
Fa 2007	4816 7977	CSCI 550-01 CSCI 659-01	DIS LEC	TR	1230-0145	OCNL 121
Sp 2007	7078	CSCI 550-01	DIS	MW	0400-0515	LANG 104
Fa 2006	5003	CSCI 550-01	DIS	TR	0930-1045	LANG 104
Sp 2006	2244	CSCI 550-01	DIS	TR	0930-1045	MLIB 031
Fa 2005	2090	CSCI 550-01	DIS	TR	0930-1045	OCNL 254

 * Archived webcast available through HorizonLive! as part of the CHICO Computer Science Program.

Prerequisites

• MATH 317(120), Discrete Mathematical Structures
• Senior-level standing highly recommended
• Note:
• Local (on-campus) graduate students may sign up for this class as CSCI 659, Topics in Theory of Computing. Be sure to discuss this with Dr. J for clarification.
• Remote (off-campus) graduate students can contact Dr. J via e-mail at Juliano@csuChico.edu to verify eligibility for this course.

  (When in doubt, please see the Instructor to verify eligibility.)

Current Catalog Description

(3.0 credit units)  An introduction to formal languages, grammars, and automata theory, with unsolvable problems. Formerly CSCI 256.

Class/Laboratory Schedule

• One hundred fifty minutes a week lecture (DIS)

Textbook

Introduction to Automata Theory, Languages, and Computation, 3/e J.E. Hopcroft, R. Motwani, and J.D. Ullman, 2007. Addison Wesley, Boston, Massachussetts. ISBN 0-321-46225-4 (Also available: Companion website for the textbook.)

Additional Requirements

	Students officially registered for the course will have their own Chico State Connection (CSC Portal) account.  Students are responsible for regularly checking their BB Vista account (automatically generated through the CSC Portal) to access an up-to-date on-line calendar of events, current scores, and other course-related matters.
	For local students only: Clickers (Student Response Systems) are required in this class; students are required to have their own Clicker by the end of the second week of classes to guarantee enrollment in class. Details of Clicker use will be covered during the first two weeks of classes. For your reference, check out Dr. J’s Clicker Reference Page, and Dr. J’s Clicker Sessions Page ...
	Students will also be using JFLAP, the Java Formal Languages & Automata Package, developed by Dr. Rodger and her students at Duke University. Since Dr. J’s Coding Standards do not fit well with the JFLAP work in this class, the following standards are expected if students want earn credit from any JFLAP submission (details will be discussed when we cover JFLAP): All solutions must have “notes” that clearly have your name, the course name and number, and the due date of the submission. All solutions must be accompanied by screenshots of (multiple) test runs of your submission (showing both “accept” and “reject” cases, where applicable). Each solution must be named hh-pp-lastname.jff where hh is the homework number, pp is the problem number, and lastname is your last name. All solutions must be e-mailed to Dr. J at Juliano@csuChico.edu by the due date and time of the corresponding homework.

Course Objectives

The objectives of this course are to:

1. help students develop an awareness of the classical and contemporary theory of computation, and the fundamental paradigms of computer science.
2. familiarize students with algorithms, complexity analysis, and algorithmic ideas.
3. help students develop a fundamental understanding of automata in the context of their applications, complexity and combinatorial problems, approximation algorithms, etc.

Course Outcomes

Upon successful completion of this course, the student shall be able to:

1. exhibit an awareness of the classical and contemporary theory of computation, and the fundamental paradigms of computer science.
2. recognize the relationships between algorithms, complexity analysis, and algorithmic ideas.
3. understand the fundamentals of automata in the context of their applications, complexity and combinatorial problems, approximation algorithms, etc.

Relationship of Course to Program Objectives

This course supports the achievement of the following program objectives:

• Problem Analysis and Solution Design: Significant
• Oral and Written Communication: Some
• Social and Ethical Issues: Minimal
• Applicability to Future Endeavors: Significant

Relationship of Course to Program Objectives

This course supports the achievement of the following program outcomes:

• Outcome A: An ability to apply knowledge of math, science, and engineering.
• Outcome E: An ability to identify, formulate, and solve computing problems.
• Outcome F: An understanding of professional and ethical responsibilities.
• Outcome G: An ability to communicate effectively.
• Outcome H: The broad education necessary to understand the impact of computing solutions in a global and societal context.
• Outcome J: A knowledge of contemporary issues.
• Outcome K: An ability to use the techniques, skills, and modern computing tools necessary for computing practice.

Grade Evaluation

Theoretical Component  (50%)
	40%		Midterm Exam
	60%		Final Exam (as scheduled in the Class Schedule)
Practical Component  (50%)
	85%		Written Homework and JFLAP Assignments
	15%		(Mandatory) Class participation: presentation and discussion of homework solutions

Students are required to earn a C- or better in both the Theoretical and the Practical components; otherwise, the minimum of the scores of the two components will be used to calculate the student’s final grade.

Note: Homework is regularly assigned in class. Students are required to attempt to solve and to submit their own solutions to all assigned homework. All homework is collected, but only a subset of the collected homework may actually be graded. However, it is the student’s responsibility to prepare for and participate in class discussions regarding all homework-related material. Participation in class discussions is mandatory and is required to pass this course.

Final Grades

Final grades shall be expressed as a percentage of the maximum possible score of all evaluated materials. Letter grades will be given according to the following scheme:

Real Interval	Letter Grade	University Definition
[96.25,100.00]	A	Superior Work
[92.50, 96.25)	A-
[88.75, 92.50)	B+	Very Good Work
[85.00, 88.75)	B
[81.25, 85.00)	B-
[77.50, 81.25)	C+	Adequate Work
[73.75, 77.50)	C
[70.00, 73.75)	C-
[66, 70)	D+	Minimally Acceptable Work
[60, 66)	D
[ 0, 60)	F	Unacceptable Work

Note:  It is Dr. J’s policy not to assign a final grade of D or D+ to graduate students. Hence,
graduate students with a class standing less than C- (70%) earn a final grade of F.

General Policies

Dr. J has some general policies (see http://www.ecst.csuchico.edu/~juliano/Teaching/Policies.html) that apply to all courses that he teaches. Students are expected to read and understand these policies upon registration of the course.

Please note that these policies are designed specifically for all Dr. J’s on-site courses; not all policies may apply to this course, particularly if you are registered through the Center for Regional and Continuing Education (RCE) as a remote student. You must contact Dr. J if you have any questions or concerns regarding the applicability of a policy to this course.

Tentative Schedule

The following tentative schedule is subject to change without notice:

Week	Chapter	Coverage/Comments
1	1 2.1	Review of proof techniques     Introduction to automata
2	2.2-2.4	Deterministic and nondeterministic automata
3	2.5 3.1-3.3	Epsilon-NFAs     Regular expressions
4	3.4 4.1-4.2	Properties of regular languages
5	4.3-4.4	Algorithms for regular languages
6	5.1-5.3	Context-free grammars
7	5.4 6.1-6.2	Ambiguous grammars     Pushdown automata     Midterm Exam, class time
8	6.3-6.4	PDA/CFG equivalence     Deterministic PDAs
9	7.1-7.2	Chomsky-normal-form grammars     Pumping lemma
10	7.3-7.4	Closure properties and algorithms for CFLs
11	8.1-8.3	Introduction to Turing machines
12	8.4-8.5	Variations of Turing machines
13	9.1-9.3	Decidability; recursive and RE languages
14	9.4-9.5	Some “real” undecidable problems
15	10.1-10.2	P, NP, and an intractable problem
16		Final Exam (see Final Exam Schedule)