CS 373: Theory of Computation

Homeworks

• Overview
• How to submit
• Late policy
• How to submit corrections
• Working in groups
• Form: How to write
• Content: What to write
• Academic honesty

Overview

Homeworks (excepting HW0) will be divided into three portions:

• In Class No-Submit
• In Class Submit
• Take Home

For the homework deadline, you will be required to submit solutions to the InClass Submit problems and the Take Home problems from that week's homework. We will record the grades for each of these separately, though they will be combined together to make your homework total at the end of the semester.

Homeworks will be posted directly on the lecture schedule.

How to Submit Homework

• 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.

• Your solutions must be typewritten in LaTeX or some other way. In particular, all mathematical notation should be properly formatted. It is OK to draw some diagrams by hand. For starting information on LaTeX, visit the course resources.

• 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.

Late policy

We can be slightly more lenient with the In Class Submit problems, but we still require you to receive instructor permission in advance of the deadline.

How to submit corrections

You may resubmit Take Home problems after the graded homework has been returned to you. If you do so, your second submission will be treated as your official solution. In particular, if you correct all of your mistakes, you can get full credit for those problems.

You may only submit corrections if you made a significant, 'good faith' effort to solve the problem the first time. The resubmit option is there to help you correct your style and address issues that you may not have noticed, not to give you an extra week to do the work. We will not let you resubmit a problem if you did not do substantial work on it originally. We understand that 'significant' and 'good faith' are subjective, but discretion is with the course staff.

If you want to submit corrections, you only need to submit the corrected problems (i.e. don't resubmit problems that you didn't change). At the correction deadline, submit both the original copy and the modified copy of the problem.

Working in groups

We allow you to submit homeworks in a group of up to two people. It is fine to submit one copy only for the two students. Even if you collaborate with others, you should acknowledge all help that you received in writing when solving a problem.

Form: How to write

• 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.

• Make the punch line obvious. Emphasize your final answers by putting a box around them, or highlighting them, or some similar trick.

• Don't regurgitate! If the complete and correct answer was covered during lecture 5, the best solution you can submit is "See lecture 5." Period. Same with any textbooks, lecture notes, and previous exams or homeworks that are required for 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

• 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 lecture or textbooks. 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 or diagram.
  • Justify the correctness of your algorithm/model/machine.

Academic honesty

This final section is unfortunately necessary, thanks to the actions of a very small minority of students.

Every student/group must write up his/her/their 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.