Please send questions to
st10@axe.humboldt.edu .
HUMBOLDT STATE UNIVERSITY
CIS 480 - Computer Theory
Spring Semester - 2000
Lecture: MWF 12:00 - 12:50 SH 120
Instructor: Sharon Tuttle, Ph.D. Office: 237E NHW
Phone: 826-3381 (Office/Message) E-Mail: st10@axe.humboldt.edu
Web Page: follow link from http://www.humboldt.edu/~st10
Office Hours:
Monday 2:00 p.m. - 4:00 p.m.,
Wednesday 2:00 p.m. - 4:00 p.m.,
or by appointment.
Required text: Sipser, "Introduction to the Theory of Computation", PWS
Publishing Company, 1997.
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.
Prerequisite: (recommended) MATH 253 (discrete math).
Grading breakdown:
Homeworks (6-8) 30%
Midterm #1 20%
Midterm #2 20%
Final 30%
APPROXIMATE Course Schedule: (subject to change!)
BRIEF version:
Ch. 0: Preliminaries (4 lectures)
Ch. 1: Regular Languages (9 lectures)
Ch. 2: Context-Free Languages (4 lectures)
MIDTERM #1
Ch. 3: the Church-Turing Thesis (4 lectures)
Ch. 4: Decidability (3 lectures)
Ch. 5: Reducibility (3 lectures)
MIDTERM #2
Ch. 7: Time Complexity (7 lectures)
MORE DETAILED version:
Week 1: Jan. 19: Reading: (none)
Jan. 21: Reading: Ch. 0: Introduction
Week 2: Jan. 24: (Ch. 0 continued)
Jan. 26: (Ch. 0 continued)
Jan. 28: Reading: Ch. 1: Regular Languages
Week 3: Jan. 31: (Ch. 1 continued)
Feb. 2: HW #1 available on course web page; (Ch. 1 continued)
Feb. 4: (Ch. 1 continued)
Week 4: Feb. 7: (Ch. 1 continued)
Feb. 9: HW #1 due, beginning of class;
HW #2 available on course web page
(Ch. 1 continued)
Feb. 11: (Ch. 1 continued)
Week 5: Feb. 14: (Ch. 1 continued)
Feb. 16: HW #2 due, beginning of class;
HW #3 available on course web page;
(Ch. 1 continued)
Feb. 18: NO LECTURE - instructor out of town
Week 6: Feb. 21: Reading: Ch. 2: Context-Free Languages
Feb. 23: HW #3 due, beginning of class;
HW #4 available on course web page;
(Ch. 2 continued)
Feb. 25: (Ch. 2 continued)
Week 7: Feb. 28: (Ch. 2 continued)
Mar. 1: HW #4 due, beginning of class;
review for Midterm #1, to be held 3-6
Mar. 3: NO LECTURE - instructor unavailable
Week 8: Mar. 6: Midterm #1
Mar. 8: NO LECTURE - instructor out of town
Mar. 10: NO LECTURE - instructor out of town
(Spring Break:
Mar. 13, Mar. 15, Mar. 17)
Week 9: Mar. 20: HW #5 available on course web page;
Reading: Ch. 3: The Church-Turing Thesis
Mar. 22: (Ch. 3 continued)
Mar. 24: (Ch. 3 continued)
Week 10: Mar. 27: (Ch. 3 continued)
Mar. 29: HW #5 due, beginning of class;
HW #6 available on course web page;
Reading: Ch. 4: Decidability
Mar. 31: (Ch. 4 continued)
Week 11: Apr. 3: (Ch. 4 continued)
Apr. 5: HW #6 due, beginning of class;
HW #7 available on course web page;
Reading: Ch. 5: Reducibility
Apr. 7: (Ch. 5 continued)
Week 12: Apr. 10: (Ch. 5 continued)
Apr. 12: HW #7 due, beginning of class;
review for Midterm #2, to be held 4-14
Apr. 14: (Midterm #2 RESCHEDULED for WED. APRIL 19th)
Week 13: Apr. 17: Reading: Ch. 7: Time Complexity
Apr. 19: HW #8 available on course web page; (Ch. 7 continued)
RESCHEDULED MIDTERM #2
Apr. 21: (Ch. 7 continued)
Week 14: Apr. 24: (Ch. 7 continued)
Apr. 26: (Ch. 7 continued)
Apr. 28: NO LECTURE - instructor out of town
Week 15: May 1: (Ch. 7 continued)
May 3: HW #8 due, beginning of class; (Ch. 7 continued)
May 5: review for Final Exam, to be held 5-12
Final Exam: Friday, May 12, 10:20 a.m. - 12:10 p.m.
LOCATION TO BE ANNOUNCED.
Additional Course Miscellany:
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 to 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
digits of your student ID, in Excel spreadsheet format --- you are
expected to monitor these, as well, and let me know of any discrepancies.
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.
Each homework handout will state clearly when it is due. Some homework
assignments will be turned in via e-mail --- each assignment 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 beginning of the specified class
session, and items turned in later during the class session will be
considered to be 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.
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
entire homework.
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 not be accepted for a
grade after this time. For some homeworks, solutions 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.
Discussing concepts with one another is encouraged. However, 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 notes 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, for this course:
(adapted from L. Ruzzo, University of Washington)
* you may discuss the problems with your classmates, BUT without
writing down or retaining any notes, computer files, materials, etc.
* 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.
* then, write your solution.
* 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.
* (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.)
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
handing it in. The University's policies on academic integrity will be
enforced.