{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\f1\fswiss\fcharset0\fprq2{\*\panose 020b0604020202020204}Arial;}
{\f2\fmodern\fcharset0\fprq1{\*\panose 02070309020205020404}Courier New;}{\f3\froman\fcharset2\fprq2{\*\panose 05050102010706020507}Symbol;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;
\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;
\red192\green192\blue192;}{\stylesheet{\widctlpar\adjustright \fs20\cgrid \snext0 Normal;}{\s1\sb240\sa60\keepn\widctlpar\adjustright \b\f1\fs28\kerning28\cgrid \sbasedon0 \snext0 heading 1;}{\s2\sb240\sa60\keepn\widctlpar\adjustright \b\i\f1\cgrid 
\sbasedon0 \snext0 heading 2;}{\s3\sb240\sa60\keepn\widctlpar\adjustright \f1\cgrid \sbasedon0 \snext0 heading 3;}{\s4\sb240\sa60\keepn\widctlpar\adjustright \b\f1\cgrid \sbasedon0 \snext0 heading 4;}{\s5\qc\keepn\widctlpar\adjustright \b\fs20\cgrid 
\sbasedon0 \snext0 heading 5;}{\*\cs10 \additive Default Paragraph Font;}{\s15\widctlpar\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid \sbasedon0 \snext15 header;}{\s16\widctlpar\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid \sbasedon0 \snext16 footer;}
{\*\cs17 \additive \sbasedon10 page number;}{\s18\fi-360\li720\widctlpar{\*\pn \pnlvlblt\ilvl10\ls2047\pnrnot0\pnf2\pnstart1\pnindent360\pnhang{\pntxtb ?}}\ls2047\ilvl10\adjustright \fs20\cgrid \sbasedon0 \snext18 \sautoupd List Bullet 2;}{
\s19\li720\sa120\widctlpar\adjustright \fs20\cgrid \sbasedon0 \snext19 List Continue 2;}{\s20\qc\sb240\sa60\widctlpar\adjustright \b\f1\fs32\kerning28\cgrid \sbasedon0 \snext20 Title;}{\s21\sa120\widctlpar\adjustright \fs20\cgrid \sbasedon0 \snext21 
Body Text;}{\s22\li360\sa120\widctlpar\adjustright \fs20\cgrid \sbasedon0 \snext22 Body Text 2;}{\s23\li360\sa120\widctlpar\adjustright \fs20\cgrid \sbasedon22 \snext23 Body Text 3;}{\s24\li360\sa120\widctlpar\adjustright \fs20\cgrid \sbasedon22 \snext24 
Body Text 4;}{\s25\li360\sa120\widctlpar\adjustright \fs20\cgrid \sbasedon22 \snext25 Body Text 5;}{\s26\qc\sa60\widctlpar\adjustright \f1\cgrid \sbasedon0 \snext26 Subtitle;}}{\*\listtable{\list\listtemplateid-224892096\listsimple{\listlevel\levelnfc23
\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \s18\fi-360\li720\jclisttab\tx720 }{\listname ;}\listid-125}}{\*\listoverridetable{\listoverride\listid-125\listoverridecount0\ls1}}{\info
{\title HUMBOLDT STATE UNIVERSITY}{\author Sharon M. Tuttle}{\operator Tuttle}{\creatim\yr2000\mo4\dy6\hr16\min13}{\revtim\yr2000\mo4\dy6\hr16\min13}{\printim\yr1998\mo8\dy21\hr15\min3}{\version2}{\edmins0}{\nofpages4}{\nofwords1317}{\nofchars7507}
{\*\company CNRS - HSU}{\nofcharsws9219}{\vern113}}\widowctrl\ftnbj\aenddoc\lytprtmet\hyphcaps0\formshade\viewkind1\viewscale90\pgbrdrhead\pgbrdrfoot \fet0\sectd \linex0\endnhere\sectdefaultcl {\header \pard\plain \s15\widctlpar
\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid {\fs18 CIS 480 - Course Syllabus\tab \tab p. }{\field{\*\fldinst {\cs17  PAGE }}{\fldrslt {\cs17\lang1024 2}}}{\cs17 
\par }{\cs17\fs18 Spring 2000}{
\par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}
{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \s5\qc\keepn\widctlpar\outlinelevel4\adjustright \b\fs20\cgrid {HUMBOLDT STATE UNIVERSITY
\par }\pard\plain \qc\widctlpar\adjustright \fs20\cgrid {\b CIS 480 - Computer Theory
\par Spring Semester - 2000
\par }\pard \widctlpar\adjustright {
\par }{\b Lecture:}{        \tab MWF           \tab 12:00 - 12:50               SH 120
\par }{\b Instructor:}{\tab Sharon Tuttle, Ph.D.\tab \tab \tab \tab }{\b Office: \tab }{237E NHW
\par }{\b Phone:}{\tab         \tab 826-3381 (Office/Message)\tab \tab \tab }{\b E-Mail:}{\tab st10@axe.humboldt.edu
\par }{\b Web Page:}{\tab follow link from http://www.humboldt.edu/~st10
\par }{\b Office Hours:}{   \tab 
\par }\pard\plain \s15\widctlpar\adjustright \fs20\cgrid {\f2\fs18            \tab Monday        2:00 p.m. -   4:00 p.m.,
\par }\pard\plain \widctlpar\adjustright \fs20\cgrid {\f2\fs18 \tab \tab Wednesday     2:00 p.m. -   4:00 p.m.,
\par }\pard \widctlpar\tx1260\adjustright {\f2\fs18 \tab \tab or by appointment.}{\b\f2\fs18 
\par }\pard \widctlpar\adjustright {
\par }{\b Required text:}{ \tab Sipser, "Introduction to the Theory of Computation", PWS Publishing Company, 1997.
\par 
\par }{\b Course description:}{ The purpose of this course is to give an
 introduction to the area of computing theory (or, theoretical computer science). Topics to be covered include automata, formal languages, Turing machines, uncomputability, and computational complexity. These help provide insight into the capabilities and
 limitations of computers.
\par 
\par }{\b Prerequisite:}{ (recommended) }{\b MATH 253}{ (discrete math).
\par 
\par }{\b Grading breakdown:}{
\par \tab Homeworks (6-8)\tab \tab 30%
\par \tab Midterm #1\tab \tab 20%
\par }\pard \ri180\widctlpar\adjustright {\tab Midterm #2\tab \tab 20%\tab 
\par }\pard \widctlpar\adjustright {\tab Final\tab \tab \tab 30%
\par }\pard\plain \s15\widctlpar\adjustright \fs20\cgrid {
\par }\pard\plain \widctlpar\adjustright \fs20\cgrid {\b APPROXIMATE Course Schedule:  (subject to change!)
\par }{
\par }{\b BRIEF version:
\par }{
\par }\pard \li720\widctlpar\adjustright {\fs18 Ch. 0: Preliminaries                            \tab \tab (4 lectures) 
\par Ch. 1: Regular Languages  \tab \tab \tab (9 lectures) 
\par Ch. 2: Context-Free Languages                    \tab (4 lectures) 
\par }{\b\fs18 
\par MIDTERM #1 
\par }{\fs18 
\par Ch. 3: the Church-Turing Thesis                          \tab (4 lectures) 
\par Ch. 4: Decidability                           \tab \tab (3 lectures)
\par Ch. 5: Reducibility\tab \tab \tab \tab (3 lectures)
\par }{\b\fs18 
\par MIDTERM #2}{\fs18 
\par 
\par Ch. 7: Time Complexity         \tab \tab (7 lectures) 
\par }\pard \widctlpar\adjustright {
\par }{\b MORE DETAILED version:
\par }{\f2\fs18 
\par Week  1:      Jan. 19:    Reading: (none)
\par               Jan. 21:    Reading: Ch. 0: Introduction
\par 
\par Week  2:      Jan. 24:    (Ch. 0 continued)
\par               Jan. 26:    (Ch. 0 continued)
\par               Jan. 28:    Reading: Ch. 1: Regular Languages
\par 
\par Week  3:      Jan. 31:    (Ch. 1 continued)
\par               Feb.  2:    }{\b\f2\fs18 HW #1 available on course web page}{\f2\fs18 ; (Ch. 1 continued)
\par               Feb.  4:    (Ch. 1 continued)
\par Week  4:      Feb.  7:    (Ch. 1 continued)
\par               Feb.  9:    }{\b\f2\fs18 HW #1 due, beginning of class; 
\par                           HW #2 available on course web page
\par                           }{\f2\fs18 (Ch. 1 continued)
\par               Feb. 11:    (Ch. 1 continued)
\par 
\par Week  5:      Feb. 14:    (Ch. 1 continued)
\par               Feb. 16:    }{\b\f2\fs18 HW #2 due, beginning of class; 
\par                           HW #3 available on course web page; 
\par                           }{\f2\fs18 (Ch. 1 continued)
\par               Feb. 18:    NO LECTURE - instructor out of town
\par 
\par Week  6:      Feb. 21:    Reading: Ch. 2: Context-Free Languages
\par               Feb. 23:    }{\b\f2\fs18 HW #3 due, beginning of class; 
\par                           HW #4 available on course web page;
\par                           }{\f2\fs18 (Ch. 2 continued)
\par               Feb. 25:    (Ch. 2 continued)
\par 
\par Week  7:      Feb. 28:    (Ch. 2 continued)
\par               Mar.  1:    }{\b\f2\fs18 HW #4 due, beginning of class}{\f2\fs18 ; 
\par                           review for Midterm #1, to be held 3-6
\par               Mar.  3:    NO LECTURE - instructor unavailable
\par 
\par Week  8:      Mar.  6:    }{\b\f2\fs18 Midterm #1
\par               }{\f2\fs18 Mar.  8:    NO LECTURE - instructor out of town
\par               Mar. 10:    NO LECTURE - instructor out of town
\par 
\par (Spring Break:
\par               Mar. 13, Mar. 15, Mar. 17)
\par 
\par Week  9:      Mar. 20:    }{\b\f2\fs18 HW #5 available on course web page}{\f2\fs18 ; 
\par                           Reading: Ch. 3: The Church-Turing Thesis
\par               Mar. 22:    (Ch. 3 continued)
\par               Mar. 24:    (Ch. 3 continued)
\par 
\par Week 10:      Mar. 27:    (Ch. 3 continued)
\par               Mar. 29:    }{\b\f2\fs18 HW #5 due, beginning of class; 
\par                           HW #6 available on course web page;
\par                           }{\f2\fs18 Reading: Ch. 4: Decidability
\par               Mar. 31:    (Ch. 4 continued)
\par 
\par Week 11:      Apr.  3:    (Ch. 4 continued)
\par               Apr.  5:    }{\b\f2\fs18 HW #6 due, beginning of class; 
\par                           HW #7 available on course web page;
\par                           }{\f2\fs18 Reading: Ch. 5: Reducibility
\par               Apr.  7:    (Ch. 5 continued)
\par 
\par Week 12:      Apr. 10:    (Ch. 5 continued)
\par               Apr. 12:    }{\b\f2\fs18 HW #7 due, beginning of class; 
\par                           }{\f2\fs18 review for Midterm #2, to be held 4-14
\par               Apr. 14:    }{\b\strike\f2\fs18 Midterm #2 }{\b\f2\fs18 RESCHEDULED!!! Now WEDNESDAY, APRIL 19th
\par 
\par }{\f2\fs18 Week 13:      Apr. 17:    Reading: Ch. 7: Time Complexity
\par               Apr. 19:    }{\b\f2\fs18 HW #8 available on course web page; }{\f2\fs18 (Ch. 7 continued)
\par                           }{\b\f2\fs18 RESCHEDULED MIDTERM #2
\par }{\f2\fs18               Apr. 21:    (Ch. 7 continued)
\par 
\par Week 14:      Apr. 24:    (Ch. 7 continued)
\par               Apr. 26:    (Ch. 7 continued)
\par               Apr. 28:    NO LECTURE - instructor out of town
\par 
\par Week 15:      May   1:    (Ch. 7 continued)
\par               May   3:    }{\b\f2\fs18 HW #8 due, beginning of class}{\f2\fs18 ; (Ch. 7 continued)
\par               May   5:    review for Final Exam, to be held }{\b\f2\fs18 5-12
\par 
\par Final Exam: Friday, May 12, 10:20 a.m. - 12:10 p.m.
\par             LOCATION TO BE ANNOUNCED.
\par }{\b\fs18 Additional Course Miscellany:
\par }{You are expected to prepare (read and study) the assigned
 chapter readings before class and to participate in class discussions. You are required to have a working on-campus e-mail account that you check regularly. Course-related announcements will be sent during the semester via the course mailing list linked 
t
o the class roll on Banner. You are also expected to check the course web page from time to time --- course handouts, course-related announcements as needed, grades, and possibly more will be posted there. The grades will be identified by the last 5 digit
s of your student ID, in Excel spreadsheet format --- you are expected to monitor these, as well, and let me know of any discrepancies.
\par 
\par For some homeworks, electronic grade sheets may be created; if you would like these to be e-mailed to you, rather than printed, you need to give me permission to do so on the information slip that will be handed out during the first class session. 
\par 
\par }\pard \widctlpar\tx1260\adjustright {Each homework handout will state clearly when it is due. Some homework assignments will be turned in via e-mail --- each assig
nment will clearly state how it is to be turned in. SOMETIMES homeworks may be accepted late --- WHEN they are accepted late, a penalty of 20% will be deducted. Unless otherwise indicated, late homeworks will be accepted up to one week after the due date 
(but see additional comments on this below). Please note that each is due at the }{\b beginning}{ of the specified class session, and items turned in later }{\b during}{ the class session }{\b will}{ }{\b be}{ }{\b considered}{ }{\b to}{ }{\b be}{ }{\b 
late}{. This is to discourage you from missing a class session just to try to finish an assignment --- you might as well come to the class session, and finish the assignment within the week, if you cannot finish in time. 
\par \tab Please note that you can turn in both an on-time version and a late version of a homework, if
 desired --- I will record the grade of the version that gives you the higher grade. If part of a homework is on-time, and part is late, note that the late penalty will be computed only on the late portion --- 20% of the portion that is late, not the enti
re homework.}{\b  
\par \tab Except }{for homeworks turned in right before the midterms, assignments will be accepted up to one week after the due date. Except for very unusual circumstances, homeworks will }{\b not}{
 be accepted for a grade after this time. For some homeworks, s
olutions will be posted on the course web page --- no such homework will be accepted for a grade after its solution has been posted. No make-up tests will be given, except by special prior arrangement.
\par 
\par }\pard \widctlpar\adjustright {Discussing concepts with one another is encouraged. H
owever, all homework assignments are to be the work of a single individual student --- these are not group assignments! You may discuss homework assignments with each other, but when writing up anything to be handed in, you are to work alone, without note
s or private material that has been discussed or seen by others. In short, it is to be your own work. The following guidelines will apply, }{\b for}{ }{\b this}{ }{\b course}{: 
\par 
\par (adapted from L. Ruzzo, University of Washington)
\par }\pard \li720\widctlpar\adjustright {*   you may discuss the problems with your classmates, BUT without writing down or retaining any notes, computer files, materials, etc.
\par *   go watch TV for an hour. Dr. Ruzzo recommends "Gilligan's Island", but I'm not sure such torture, in particular, is necessary. "Emeril Live" will do just as well, and be much more pleasant.
\par *   then, write your solution.
\par *   The same basic guidelines apply to published solutions in other books, files of old homework solutions, etc. If you cannot write your solution unaided an hour after last reading or discussing it, then you did not really understand it. 
\par *   (also, note that if you do obtain a solution with some help as described above, particularly if it is from a book, you should acknowledge the source in your homework, even though you are still writing up the solution on your own.)
\par }\pard \widctlpar\adjustright {
\par I will not tolerate cheating, on homework assignments or exams; work showing significant duplication will receive no credit for anyone involved, and neither will any work done by anyone other than the person
\par handing it in. The University's policies on academic integrity will be enforced. 
\par 
\par }}