OLD - To be updated

Format: What to submit

• You are free to choose whatever way you find comfortable to generated a pdf with your solution. If you have a tablet, xournal seems like a decent application if you want to write in free form. Otherwise, google doc openoffice, and word (gag) all have limited (but probably sufficient) support for mathetmatics.

  Namely, 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. Remember that you should be able to produce pdf files using your software and your pdf files should not be too large (at most 2 MB).

• 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

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

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