The course staff have to critically examineseveral thousandpages of homework submissions each semester! We desperately need your help to make sure your work is graded fairly 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.

- Homework Logistics: How to submit
- Homework Format: What to submit
- Form: How to write — Be clear, be concise, and be honest.
- Content: What to write

- "Repeat this for all
n" is an automatic zero.- "I don't know" is worth 20%.
- Don't plagiarize!

## Homework 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 with at least one other person.

You should submit homeworks in class.

We will not accept late homeworks for any reason.To offset this rather draconian policy, we will drop your five lowest problem scores (roughly one full assignment).

In extreme circumstances, we mayExtreme circumstances include serious illness, injury, and research-related travel (for example, you are presenting a paper at a conference). We will compute your grade as if the forgiven homework or exam did not exist; your other homeworks or exams will have more weight in your final course grade. In particular, the five lowestforgivehomeworks or even exams.unforgivenhomework grades will be dropped. Please see Chandra for details.

Graded homeworks and midterms can be retrieved during office hours.Under normal circumstances, your graded work will be ready to pick up at most two weeks after you submit it. Please see the grading policies for more information about grading and regrade requests.

## Homework Format: What to submit

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, each numbered homework problem will be graded by a single person, and grades for each problem will be recorded separately. We need your help to make distribution of problems to graders possible.

Start each numbered homework problem on a new sheet of paper.We will grade only the first problem on every sheet.

If necessary, staple your solution for each numbered problemonce in the upper left corner. Please 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 solutions, print the name and NetID ofeverygroup member oneverypage. We want to give you credit for your work even if papers get shuffled or staples fall out.

Nicely typeset homework will be given a small amount of extra credit.The graders get to decide what "nicely" means.If you want to typeset your homework, I

stronglyrecommend LaTeX, by far the best system for typesetting mathematics (and youwillbe typsetting mathematics). Nothing else even comes close, especially the crappy equation editor that comes with Microsoft Word. I recommend TeXShop for Mac OS X, TeX Live for Linux (already included in many distributions), and MiKTeX for victims of the Redmond Virus.Some LaTeX distributions are configured to use A4 paper by default. Please make sure your solutions will print correctly on US Letter paper. To make absolutely sure, start your solutions with

`\documentclass[letterpaper]{article}`

.

## 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.## Be Clear

Write carefully.We can only grade what you actually write, not what you mean. We will not attempt to read your mind.Write legibly and sensibly.You will lose points for bad handwriting, spelling, grammar, punctuation, arithmetic, algebra, logic, pseudo-code, and so forth. If we can't decipher your solution, we 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.

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 phrases like “and so on”, “etc.”, “do this for all X”, “repeat this process for all X”, or “. . .” will get no credit.Yes, I am completely serious. Those phrases are clear signals that your algorithm should have used a loop or recursion, or that your proof should have used induction, but didn't.

Write top-down, breadth-first solutions.Describe the key ideas behind your solution before going into details. The reader should understand your approach almost immediately. 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.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.Simliarly, even the most complicated exam problem can be answered completely in less than a single hand-written page.

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.

Don't submit code.This is not a programming class; your grader is not a compiler. Describe your algorithms using well-structured, human-readable pseudocode. See the lecture notes and recommended textbook for examples of the type of presentation we want. Your description should allow a competent programmerwho has not taken this courseto easily implement your algorithm intheirfavorite programming language.## Be Concise

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 homework solution is longer than two typeset pages, you've included too many details.

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 “知りません” or “أنا لاأعرف” are also acceptable, but you must writenothingelse) to any homework or exam question is automatically worth 20% partial credit for that question.something; a blank page is worth zero points. Readable, correct, but suboptimal solutions arealwaysworth more than 20%. 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. For example, if the complete and correct answer appears on page 6 of Jeff's lecture notes on recursion, thebestsolution you can submit is "See page 6 of Jeff's lecture notes on recursion." The same goes for any material presented in the actual lectures, the recommended textbook (Dasgupta, Papadimitriou, and Vazirani), or previous exams and homeworksfrom this semester. Vomiting will cost you points. If your answer comes fromanyother source, you must write the solution in your own words and cite your source; see below.

Don't submit code.We want to see your ideas, not syntactic sugar.## Be Honest

WriteWeeverythingin your own words, and properly citeeveryoutside source you use.stronglyencourge you to useanyoutside source at your disposal, provided you use your sources properly and give them proper credit. 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.Sources that you may use but must cite include textbooks, journal papers, conference papers, newspaper and magazine articles, web pages, blog postings, tweets, Wikipedia, newsgroup postings, lecture notes from other algorithms classes, official homework solutions from previous offerings of 573, other students in 573, other students not in 573, whiteboards that someone forgot to erase, and your mom.

The only sources that you donotneed to explicitly cite are official course materials (lectures, lecture notes, previous homework and exam solutions from this semester) and sources for prerequisite material (which we assume you already know).

List everyone you worked with on each homework problem.Again, we strongly encourage you to work together, but you must give everyone proper credit. If you work in a group of 20 students, then all 20 names should appear on your homework solution. If someone was particularly helpful, describe their contribution. Be generous; if you're not sure whether someone should be included in your list of collaborators, include them. For discussions in class, in section, or in office hours, where collecting names is impractical, it's okay to write something like "discussions in class".

In particular, if you find a complete solution on the web, do not just submit a printout.The homework is supposed to demonstrate your mastery of the material, not your ability to use Google and a stapler.

- 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'! (Proofs are only required on exams if we specifically ask for them.)

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

Give a concise pseudocode description of your algorithm.Don't regurgitate, and don't turn in code!

Describe acorrectalgorithm.

Justify the correctness of your algorithm.You usually won't have to do this on exams.

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²)." Or 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.

Describe the fastest correct algorithm you can, even if the problem does not include the words "fast" or "efficient". Faster algorithms are worth more points; 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.However, if your algorithm is incorrect, you won't get any points, no matter how fast it is!Some problems may deviate from these default requirements. For example, we may ask you 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. Exam problems will rarely ask for proofs of correctness.