The course staff have to critically examine several thousand pages of homework submissions each 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.I apologize in advance for the length of this document. Most of this stuff is obvious to most students, but after teach this class for 12 years, I've seen a lot of strange things.
- Homework Logistics: How to submit
- Homework 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%.
- 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. We strongly encourage (but will not require) every student to work in a group with at least one other student.
- Homework is due every Tuesday at 1:00. You may submit homeworks either in class or in the homework drop boxes in the basement of Seibel. If you put your homework in the wrong drop box, we won't get it.
- 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 and a half assignments).
- 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). 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 lowest unforgiven homework grades are dropped. Please see Jeff for details.
- Graded homeworks and midterms will be returned in discussion section. Alternately, you can pick up your graded work during Jeff's or any of the TAs' 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 problem once 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: "Jeff Erickson (jeffe) HW0 #5". For group solutions, print the name and NetID of every group member on every page. We want to give you credit for your work even if papers get shuffled out of order 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 strongly recommend LaTeX, by far the best system for typesetting mathematics (and you will be 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 will 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 is especially important 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”, or “. . .” will get no credit. Those 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. 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 programmer who has not taken this course to easily implement your algorithm in their favorite 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” (and nothing else) to any homework or exam question is automatically worth 25% partial credit for that question. Synonyms like “No idea” or “WTF” or “知りません” or “أنا لاأعرف” are also acceptable, but you must write something; a blank page is worth zero points. Readable, correct, but suboptimal solutions are always worth 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. For example, if the complete and correct answer appears on page 6 of Jeff's lecture notes on recursion, the best solution 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 homeworks from this semester. Vomiting will cost you points. If your answer comes from any other 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
- Write everything in your own words, and properly cite every outside source you use. We strongly encourge you to use any outside 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 473, other students in 473, other students not in 473, whiteboards that someone forgot to erase, and your mom. The only sources that you do not need 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, 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'! (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 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.
- Give a concise pseudocode description of your algorithm. Don't regurgitate, and don't turn in code!
- Describe a correct algorithm.
- 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 to n, 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.