CS 373: Theory of Computation
Homework
BEFORE STARTING THE HOMEWORK, PLEASE READ THE INSTRUCTIONS BELOW!!!
Homework Instructions
Since CS 373 has many students, we desperately need your help to make
sure homeworks are graded and returned quickly. Any homework
that does not follow these (admittedly anal) instructions will
automatically receive a grade of zero. This is not a joke.
- Each homework is to be turned in by the start of class
on the day it is due.
-
Write your solutions on standard US Letter (8.5 by 11) paper.
- Start each problem on a new sheet of paper. This will make
it possible for us to separate your solutions and distribute them for grading. To make the grading as fair as possible, we intend for the same grader to grade the same problem for everyone.
-
DO NOT staple your homework together We intend to distribute the problems, so do not attach them all together.
-
Clearly print your name AND your group members' names at the top of EVERY sheet of
paper you turn in.. If you do not write the names, you will not get credit for your work.
-
Turn in your homework on time. Homework must be received by the
start of class on the due date. No late homeworks will be accepted,
except in unusual circumstances, in which case the instructor's
written permission must be obtained at least one full day before the
due date. To offset this somewhat draconian measure, we will drop the
lowest grade of all the homeworks; this should take care of any
unforeseen circumstances.
No matter what we state as course policies, students will often work
together on homeworks. We consider this practice to be perfectly
fine. In fact, exchanging ideas with your classmates is an excellent
way to learn, and maybe make some new friends. Remember, however,
that you still have to understand the solutions submitted to
all of the questions. Of course, there are always some
students who blindly copy most of their homeworks. This problem
usually works itself out on the midterms, especially in a class as
challenging as CS 373. Without a deep understanding of the homework
problems, it is practically hopeless to score well on exams.
We allow you to work in a group of up to three people, but you must
submit a copy of the solutions in your own words, with the names
of the others in your group listed at the top of the submission.
Form: How to write
Please be nice to the graders! Make it easy for them to see
that you've done everything right. The graders have to look at
thousands of pages of homework submissions during the
semester! If your answers are hard to read, the graders will be less
sympathetic to your mistakes.
-
Write concise, legible, and correct solutions. You
will lose points for bad handwriting, spelling, grammar,
arithmetic, algebra, logic, and so on. If we can't decipher what you
wrote, you will get no credit. This is especially important for
students whose first language is not English.
- One way to ensure legibility is to use LaTeX, which is far and away
the best system for typesetting mathematics. Nothing else even comes close, especially
the
crappy subpar equation editor that comes with Microsoft Word. The LaTeX
source file will be made available for each homework, for your
convenience. Here is a source for information on LaTeX.
-
Make the punch line obvious. Emphasize your final answers by
putting a box around them, or using a highlighter, or some similar
trick.
- Don't regurgitate! If the complete and correct answer is on
page 263 of the textbook, the best solution you can submit is
"See page 263 of the textbook." Period. Same with the lectures, the
lecture notes, and previous exams or homeworks from the current
semester. If your answer is a simple modification of something
we've seen in class, just say so and (carefully!) describe the
changes.
- Omit irrelevant details. Don't turn in the piece of paper
you used to figure out the answer; copy just the relevant bits onto a
new empty page. Don't include long rambling text in hopes of
accidentally hitting what we are looking for. This usually indicates
to a grader that you don't know what you are doing. Be clear and
concise.
- Include relevant details. If a problem statement is
ambiguous, tell us what additional assumptions you made in your
solution. If there are multiple ways to interpret the problem,
clearly state state assuptions you are making.
Content: What to write
Convince the grader that you understand exactly what you're doing.
- Answer the right question. Duh. No matter how clear and polished
your solution is, it's worth absolutely nothing if it doesn't answer
the question we asked. Make sure you understand the question before
you start thinking about how to answer it. If something is unclear,
ask for a clarification on the course newsgroup or during office hours!
- Justify all of your answers. Unless the problem
specifically says otherwise, every one of your homework and exam
answers requires a proof. Without a proof, the correct answer is
worth absolutely nothing.
-
If a homework or exam problem asks you to prove something, consider the
following guidelines:
- Proofs represent a well-established form of communication. In
addition to having the right technical insights required to solve a
problem, writing a good proof requires good proof-writing style, much
in the same way that good style is important for many forms of
writing. Never forget that you are trying to convince a skeptical,
mathematically-minded reader that something is true. Just like
many forms of writing, it takes practice to become great at writing
proofs.
- If the proof follows a standard proof technique at any point,
clearly state it (e.g., proof by contradiction, by induction, etc.).
It is generally a good idea to give the reader a brief overview of the
overall proof strategy, especially for longer proofs.
- Clearly and concisely define any notation or terms used in your proof.
- The sentence "It's obvious" is not a proof -- many obvious things
are actually false! Statements such as this will always appear
suspicious to the graders. If it is really that obvious, you should
be able to explain it, right?
- Be sure to explain any difficult steps made in your proof.
- If you are uncertain about the right level of detail to include
in a proof, ask the instructor or TAs, or follow the style used in
proofs that are given in the textbook. One way to get more comfortable
writing proofs is to spend substantial time reading many
proofs. You might even want to imagine that you are a grader!
- Remember that irrelevant rambling that appears in the proof often
indicates poor understanding of the problem and its solution. It will
be more difficult for the graders to understand what you are doing, and
the usual result will be little or no points.
-
If a homework or exam problem asks you to give/show/describe/develop
an algorithm/machine/model, you need to do several things to get full credit:
- If necessary, formally restate the problem in terms of
combinatorial objects such as sets, lists, graphs, trees, etc.
In other words, tell us what the problem is really
asking for. This is often the hardest part of designing an
algorithm!
- Describe the most efficient algorithm/model/machine possible. Needlessly complicated algorithms could lose points, especially for clarity.
- Give a concise description of your algorithm/machine/model. For algorithms, this is usually pseudocode. For machines, this is usually tied to the formal notation.
- Justify the correctness of your algorithm/model/machine. You usually
won't have to do this on exams.
Academic honesty
This final section is unfortunately necessary, thanks to the
actions of a very small minority of students.
Every student must write up his or her own homework solutions.
We strongly encourage students to work together on the
homeworks and to consult any outside resource at your disposal: other
students, TAs, professors, textbooks, journals, conference
proceedings, web pages, test files, etc. However, you must excerise
academic integrity. If you receive significant help from any
source, you must identify that source in your solution. This
will not lower your homework grade.
Directly copying someone else's work, or allowing others to
directly copy your work, is cheating.
We treat cheating cases very seriously. The penalty for a first
cheating offense is a grade of zero on the homework or exam. The
penalty for a second offense is an F in the course. All cheating
cases are reported to the department, and multiple offsenses can
result in suspension or dismissal from the university.
For further information, see this page on Academic
Integrity and Plagiarism and the university's Policies and
Procedures on Academic Integrity
Regardless of whether it constitutes cheating, or whether you get
caught, getting too much help on your homework will hurt your final
grade. If you don't learn how to solve problems on your own, you
will fail the (closed-book, closed-notes) exams, which make up
most of your final course average. Furthermore, you will have greater
troubles if you are continuing on to more advanced courses, such as CS
473, which is required for undergraduates in Computer Science.