The course staff will have to critically examineseveral thousandpages 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. Westronglyencourage (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 mayExtreme circumstances include serious illness, injury, and research-related travel (for example, if you are presenting a paper at a conference). Please see Chandra for details.forgivehomeworks or even exams.

Submit Homework 0 in class. Submit all other homeworks to Elaine Wilson in 3229 Siebel Center.Do not submit homeworks to the instructor.

- You can pick up your graded homeworks and midterms during Chandra's or any of the TAs' office hours. Under normal circumstances, your graded work will be ready to pick up no more than 15 working days after you submit it. Please see the grading policies for more information about grading and regrade requests.

## Format: What to submit

Nicely typeset homework will be given a small amount of extra credit.Thegradersget to decide what "nicely" means and the credit is included in the score they give. LaTeX is by far the best system for typesetting mathematics (and youwillbe typsetting mathematics). TeXShop for Mac OS X, TeX Live for Linux (already included in many distributions), and MiKTeX for Windows are good options.

Use standard US Letter paper (8.5" × 11")or a close approximation. Most US notebook paper is close enough. Spiral notebook paper with the frilly bits still attached will be discarded, unread. Use both sides of the page whenever possible.

- To keep grading fast and consistent, all solutions for each numbered homework problem will be graded by a single person. We need your help to make distribution of problems to graders possible.

Start each numbered homework problem on a new sheet of paper.

If necessary, staple your solution for each numbered problemonce in the upper left corner. Do not use paper clips, tape, glue, spit, or rubber bands. Do not try to keep pages together by folding or tearing.

Do not staple your entire homework together.Keep your solutions to individual problems separate.

Clearly print 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 ofeverygroup member oneverypage. We want to give you credit for your work even if papers get shuffled out of order or staples fall out.

## 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 symapathetic 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 isespeciallyimportant 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.Donotturn 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 programmerwho has not taken this courseto easily implement your algorithm—intheirfavorite 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" (andSynonyms like "No idea" or "WTF" are also acceptable, but you must write something; a blank page is worth nothing. Readable, correct, but suboptimal solutions arenothingelse) to any homework or exam question is automatically worth 25% partial credit for that question.alwaysworth more than 25%. This rule does not apply to extra credit problems.

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 homeworksfrom this semester. Vomiting will cost you points.

If you find a solution fromWeanyother source, you must rewrite it entirely in your own words, and you must properly cite your sources.stronglyencourge 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 and a stapler.

Don't plagiarize!Writeeverythingin your own words, and properly citeeverysource you use, whether paper, electronic, or human. Again, westronglyencourge 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,everyhomework 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 problemin terms of combinatorial objects such as sets, sequences, lists, graphs, or trees. In other words, tell us what the problem isreallyasking 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 ton, so the running time is O(n^{2})." 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.

Webpage contents generously borrowed/copied from those of Jeff Erickson.