Class meeting times
The class meets from 11:00 to 12:15,
Tuesdays and Thursdays, in 1320 DCL.
Staff
Professors:
Office Hours: Monday 5-6pm, Thursday 5-6pm
Office Hours: Monday 11-12, Friday 9-10:30
The prerequisites for this course are CS 125 (or ECE 190) and CS 173 (or MATH 213). We also recommend that you take CS 225 before this course. Other experience (e.g. advanced math courses) may be able to serve in lieu of these prerequisites: speak to the instructors.
Our office hours will be posted as our fall-term schedules firm up. Please come to office hours if you are having trouble, have an issue with the course, or just need a hint. If you can't make any of the scheduled office hours (or if you need help before we post regular hours), contact us to set up a time to meet.
Help is also available via email, the course newsgroup, and head-banging sessions.
If you think a homework problem is buggy or unclear, post a query to
the newsgroup. If you think an exam problem is buggy or unclear,
ask one of the proctors. Sometimes there really are bugs and you
will be helping everyone by bringing them to our attention.
Course Topics
This course will focus on fundamental mathematical models of computation.
We will be interested in both the inherent capabilities and limitations
of these computational models as well as their relationships with formal
languages. Rigorous arguments and proofs of correctness will be emphasized.
Particular topics to be covered include:
Textbook
The official course text is
Introduction to the Theory of Computation
Michel Sipser
2nd Ed., PWS Publishing Company, 2005.
Check out its
errata page, which contains a few substantive (as opposed to
stylistic) errors.
Other books you may find useful are:
These texts are on reserve in Grainger Library.
You are expected to attend lectures. If you cannot be at lecture, you
must arrange to pick up any handouts or returned homeworks you may
have missed, e.g. by coming to office hours.
Some handouts may be hardcopy and some virtual. Virtual handouts
will available on the main lectures web page. Spare copies of
hardcopy handouts will be put on the wall outside Fleck's office.
Announcements, homework hints, etc will be posted on the
class newsgroup
class.cs273 .
Here are instructions for accessing it
You must read the
newsgroup regularly (at least once a day).
Particularly important announcements will be duplicated on the
course home page.
You are encouraged to use the newsgroup to initiate
and participate in discussion related to the class. However, students
should not post solutions or hints to homework problems.
We will use Illinois Compass
for online grade posting. It may take a week or more before
our course site becomes active.
There will be problem sets roughly every week, typically due a week
from the release date. There may also be some on-line web quizzes,
which will be treated as part of the homework.
Your homework must follow the
homework guidelines.
Some homework problems may be marked "bonus." Scores from these
problems will be added to your homework average just like other
problems. However, we anticipate that they are appropriate for
only some of you (e.g. very difficult) and the rest of you should
not feel bad if you don't do them.
Do not wait until the last minute to print or download a copy of the
homework. Many of the problems will require significant thought.
Even if you tend to work right up to the deadline,
skimming the problem set early will give you a chance to start
thinking about it and to seeking out help if you need it.
While you will get the most out of the homeworks if you solve
them yourself,
in this course you are allowed to discuss the problems with your classmates,
and to work together in groups of size at most three.
If you choose to do so, you must indicate the name(s)
of the people with whom you have worked.
Moreover, each person in the group must write up and turn in
their own solutions, in their own words.
Consulting with other students is expressly forbidden.
When trying to solve a homework problem, it is often helpful to study
solutions to other problems on the same topic, e.g. examples in the course
textbook or the other texts on reserve in the library, problems used
in head-banging sessions, worked solutions posted on line. However,
it is cheating to consult solutions to the same , or almost
the same, problem. It is also dishonest to go searching (e.g. on the
internet) for solutions to the assigned problems. Refer to the Campus
Code regarding academic integrity.
We try to avoid assigning problems whose solutions are readily
available.
However, if you accidently happen upon a solution to an assigned problem,
we would appreciate being told where you found it.
A typical session will involve small
groups solving homework-style problems (some hard with hints, some
easier without) under the helpful supervision of TAs and other course
helpers to be named later. The theory is that a massive group
head-banging in a friendly atmosphere will prevent (or at least
minimize) prolonged individual head-banging and consequent
implosion/explosion during the regular written homework
assignments. Participating in HBS will contribute a small amount to
your grade, see the section. More importantly,
it will help you do well on the homeworks and exams.
Times and places for headbanging sessions will be announced soon.
If your schedule prevents you from attending any of the head-banging
sessions, you may make individual arrangements with the TAs to work
on the HBS problems and receive bonus credits similar to those for
attending HBS sessions.
The basic policy is that late homeworks will not be accepted.
Your lowest homework score will be dropped when computing final
grades. This is intended to cover all manner of minor reasons why you
might have trouble turning in a homework on time or completing it
well. These include minor illnesses, car trouble, collisions with work due for
other courses, and the like. See below for our policies on excuses
for major problems.
Our policy of dropping one homework is designed to cover the usual,
common range of minor problems (e.g. minor illness). In the rare
cases where you have some problem that is out of the ordinary, please
come speak to us about appropriate arrangements. This would include,
for example, serious illness or injury, family emergencies, major
snowfall blocking roads between your home and campus, major computer
systems outages in the Siebel center, and the like.
We expect to hear about such issues promptly and to receive delayed
work as soon as reasonably possible. Depending on the circumstances,
we may ask you to provide documentation (e.g. a doctor's note).
If you notice major problems (e.g. our exam conflicts with an exam in
another course that many of you are taking), please tell us promptly
so that we have the best chance to fix it.
If you have a disability or other special circumstance which may
require special accomodations, please speak to us.
If you have a question or complaint about the way a
homework or exam problem was graded, contact any one of the course
staff to get it straightened out. Normally, it's easiest if you find
out who actually graded that problem and speak to them in person at
their office hours.
When this isn't possible, explain the problem on a separate piece of paper, attach it to the assignment, and give it to
one of us. We want everyone happy and satisfied, but we can't do much
in the couple of minutes before and after class.
We hope that you are all honest and have no intentions of cheating.
Cheating ruins the experience for everyone and we will pursue
appropriate penalties if we catch someone cheating.
You can find a general discussion of cheating, plagiarism, and the
like on the
university's web page and on the
CS department's page.
In this class, you are explicitly allowed to work on homework problems
in small groups (2-3 people). Therefore, it's likely that everyone in
the group will submit solutions that use a similar approach and share
key technical details. However, you must write up your final solution
yourself, in your own words. Among other things, this helps
you ensure that you do understand all the details and it gives you
practice composing mathematical English. If you don't understand your
group's solution well enough to write it out by yourself, you will do
badly on the exams.
To keep everyone honest, you must
note the names of the other group members on your homework (under
your own name).
If you don't understand these guidelines, please talk to us. If
something unusual happens (e.g. a roommate blurts out advice that you
didn't ask for), consult with us and also write an explanation on your
homework. If you clearly acknowledge all help you received, you might
lose points but it won't be considered cheating.
If we do catch someone cheating, we will apply
the following penalties for a first offense:
For a second cheating offense of any kind, you will fail this course.
Lectures, Handouts, Announcements
Examinations
There will be two midterm exams and one final exam.
The midterms will probably be held in the evenings, roughly
1/3 and 2/3 of the way through the term.
There will be an optional review session conducted before each midterm
and final exam.
Details will be posted on the
Exams web page.
Homework
Head Banging Sessions
Head banging sessions are optional,
but strongly encouraged, especially if you are finding the material
challenging.
Excuses, Extensions, Regrades
Cheating