CS 473: Homework Policies

The course staff will have to critically examine several thousand pages of homework submissions before the end of semester! We desperately need your help to make sure homeworks are graded and returned quickly. If you have any questions or concerns, please don't hesitate to ask in lecture, during office hours, on the course newsgroup, or by email.

Logistics: How to submit
Format: What to submit
Form: How to write
Content: What to write
"Repeat this for all n" is an automatic zero.
"I don't know" is worth 25%.
Work together, use the web, but cite your sources.
Don't plagiarize!

Logistics: How to submit

Each student must submit their own individual Homework 0 solution. Starting with Homework 1, groups of up to three students may submit a common solution for each written homework. Students are are responsible for forming their own homework groups. We strongly encourage (but will not require) every student to work in a group with at least one other student.
~~We will not accept late homeworks for any reason.~~ To offset this rather draconian policy, we will drop your lowest homework score.

In extreme circumstances, we may forgive homeworks or even exams. Extreme circumstances include serious illness, injury, and research-related travel (for example, if you are presenting a paper at a conference). Please see professor for details.

Submit a paper copy of your homework in the homework boxes in the basement of Siebel Center. They are in the lower-level next to the snack machines. You should submit each question separately; one stapled copy per problem per homework in the appropriate box. So, for example if HW0 has 5 problems, then you should make 5 different submissions, one per problem. We highly recommend you typeset your homework, but alternatively you can use a tablet and write in free form, or write a solution on paper. If you are to typeset your homework, we strongly recommend you use latex.

For a single problem, a single submission per group suffices. It is not necessary that everybody in the group submits his/her own file separately.

It is not necessary to submit all the problems at once, you can do this gradually but of course before the deadline.

It is not necessary for all the problems of a homework to be submitted by the same member of the group. Different problems of a homework can be submitted by different members of the group.

It is OK that a group submits a single problem many times. While we collect all the submission, just state clearly which one is the final one.

You are not allowed to submit different problems of a single homework within different groups. Although we are not monitoring this constraint while you submit the problems, before we start to grade a homework we will carefully check for violations.

Scores and solutions will be made available on Moodle. Graded homeworks will be available during office hours and in discussion sections.

Format: What to submit

You can use any typesetting software that you are comfortable with as long as it is mature enough to let you typeset a reasonable detail of mathematical formulas (like exponents, indices, greek letters, a solution for including figures when needed,...) so the grader can understand your mathematical symbols without any need for guessing.
LaTeX is by far the best system for typesetting mathematics (and you will be typsetting mathematics). TeXShop for Mac OS X, TeX Live for Linux (already included in many distributions), and MiKTeX for Windows are good options. We encourage you to use latex. We will provide you with a very simple latex template that you can use to typeset your solutions, as well as a very basic latex tutorial. You can read the tutorial here.
Clearly print/type your name(s), your NetID(s), the homework number, and the problem number at the top of every page. For example: "Chandra Chekuri (chekuri) HW0 #5". For group homework solutions, print the name and NetID of every group member on.

Form: How to write

In short, make it easy for the graders to figure out what you mean. If your solutions are difficult to read or understand, the graders will be less sympathetic to your mistakes. All this goes for exam problems, too.

Write concise, legible, and sensible solutions. You will lose points for bad handwriting, spelling, grammar, punctuation, arithmetic, algebra, logic, and so forth. If the graders can't decipher your solution, they can't give you credit. If you have sloppy handwriting, it's time to learn LaTeX. This is especially important for students whose first language is not English.

Write carefully and precisely. We can only grade what you actually write, not what you mean. We will not attempt to read your mind.

State your assumptions. If a problem statement is ambiguous, explicitly state any additional assumptions that your solution requires. (Of course, you should also ask for clarification in class, in office hours, or on the course newsgroup.) For example, if the performance of your algorithm depends on how the input is represented, tell us exactly what representation you require. If your solution to a recurrence assumes a particular base case, tell us what base case you require.

Give a top-down, breadth-first description. Describe the key ideas behind your solution before going into details. The reader should understand your approach almost immediately. Even the most complex homework problem in this class can be answered completely in at most two typeset pages (or about five handwritten pages); most problems will require considerably less. An incomplete solution that includes all the main ideas but omits some details is worth far more than a complete, correct, detailed, but opaque solution.

Omit irrelevant details. Don't turn in the piece of paper you used to figure out your answer; copy the relevant information onto a new empty page. If the same algorithm works equally fast whether the input is an array, a singly linked list, a doubly linked list, or a binary tree, try to describe it so that a competent programmer can easily use any of these data structures. If your solution is longer than two typeset pages, you've included too many details.

Use pseudocode to describe your algorithms. Do not turn in source code! Your description should be human-readable. See the lecture notes and recommended textbook for examples of the type of presentation we want. Ideally, your description should allow a competent programmer who has not taken this course to easily implement your algorithm—in their favorite programming language, not yours. Your favorite programming language sucks, even if it's python or ruby.

Give generic solutions, not just examples. In particular, don't describe the first two or three iterations of your algorithm and then write "and so on". Solutions that include "and so on", "etc.", "do this for all X", "...", or similar phrases will get no credit. Those are automatic indications that your algorithm should have used a loop or recursion, or that your proof should have used induction, but didn't.
Don't babble! A crucial part of mastering any new material is learning to recognize when you don't know something. Don't try to bluff your way through; if you don't know the answer, just say so. Answering "I don't know" (and nothing else) to any homework or exam question is automatically worth 25% partial credit for that question. Synonyms like "No idea" or "WTF" are also acceptable, but you must write something; a blank page is worth nothing. Readable, correct, but suboptimal solutions are always worth more than 25% (but remember a totally incorrect solution - one with no idea that can somehow be used to build a correct solution - will get a zero). This rule does not apply to extra credit problems.
IDK points will not be given for programming exercises.
Don't regurgitate! If your answer is a simple modification of something we've seen in class, just say so and (carefully!) describe the changes. This applies to the actual lectures, the recommended textbook (Kleinberg and Tardos), or previous exams or homeworks from this semester. Vomiting will cost you points.
If you find a solution from any other source, you must rewrite it entirely in your own words, and you must properly cite your sources. We strongly encourge you to use any outside source at your disposal, but please remember that the homework is supposed to demonstrate your mastery of the material, not your ability to use Google.
Don't plagiarize! Write everything in your own words, and properly cite every source you use, whether paper, electronic, or human. Again, we strongly encourge you to use any outside source at your disposal, but we expect you to be ethical scholars. If you get an idea from an outside source, citing that source will not lower your grade. Failing to properly cite an outside source—thereby taking credit for ideas that are not your own—may result in a zero on the homework, or worse. Please see the academic integrity policy for more details.

Content: What to write

Answer the right question. No matter how clear and polished your solution is, it's worthless 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 clarification! This is especially important on exams.
Justify your answers. Unless the problem specifically says otherwise, every homework problem requires a proof. Without a proof, even a perfectly correct solution is worth nothing. In particular, the sentence "It's obvious!" is not a proof—'obvious' is often a synonym for 'false'! (In exams we will indicate clearly whether we need a proof or not.)
By default, if a homework or exam problem asks you to describe an algorithm, you need to do several things to get full credit:
- If necessary, formally restate the problem in terms of combinatorial objects such as sets, sequences, lists, graphs, or trees. 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 you can. The more efficient your algorithm, the more points you get. Brute force is usually not worth very much. We will not always tell you what time bound to shoot for; that's part of what you're trying to learn!
- Give a concise pseudocode description of your algorithm. But don't regurgitate! And don't turn in source code!
- Justify the correctness of your algorithm. You may not have to do this on exams unless asked for.
- Analyze your algorithm's running time. This may be as simple as saying "There are two nested loops from 1 to n, so the running time is O(n²)." On the other hand, it may require setting up and solving a summation and/or a recurrence, in which case you'll also have to prove your answer is correct.
Some problems may deviate from these default requirements. For example, you may be asked for an algorithm that uses a particular approach, even though another approach may be more efficient. (Answer the right question!) Some problems may ask you to analyze the space used by your algorithm in addition to the running time.