The course staff must critically examine somewhere between ten and twenty thousand pages of homework submissions this semester! We desperately need your help to make sure homeworks are graded and returned quickly. If you have any questions or concerns about these policies, please don't hesitate to ask in lecture, during office hours, or on Piazza (publicly, or in private post to the course staff).
Starting with Homework 1, homework solutions may be submitted by groups of up to three students. We strongly encourage (but will not require) every student to work in a group with at least one other student. Students are responsible for forming their own homework groups. Groups may be different for each numbered homework problem.
Upload your solution in pdf format to Moodle via the problem submission pages.
For group solutions, only one member of the group should submit the solution to a given problem.
It is okay if the same group member submits all problems for a homework set, or if each person in the group submits a different problem. But, each problem solution should be uploaded by one and only one group member.
Additionally, you must type in all group members' NetIDs in the Online Text box on each problem submission page separated by single spaces (the order of NetIDs doesn't matter):
If Alex is working alone, he still enters "ajsteig2".
If Alex and Mark are submitting as a group, whoever is submitting enters "ajsteig2 midlema2".
If Alex, Spencer, and Mark are submitting as a group, whoever is submitting enters "ajsteig2 slgordo2 midlema2".
After we grade the submissions for each problem, we use this information to automatically copy each submitter's grade to the other members of their group. If this information is not entered correctly, the other groups members' grades will be delayed or possibly lost entirely.
In extreme circumstances, we may forgive quizzes, homeworks, or even exams. Extreme circumstances include documented illness or injury, but do not include registering late, travel for job interviews or conferences, forgetting the homework deadline, or just not finishing on time. We will compute your final course grade as if your forgiven homeworks and exams simply do not exist; your other work will have more weight. Please ask the instructors for details.
Yeah, if you could just go ahead and make sure
you do that from now on, that would be great.
To keep grading fast and consistent, each numbered problem on each homework will appear in Moodle as a separate assignment.
Each homework problem solution must be uploaded as a separate pdf file. We strongly recommend using
but any typesetting means that enable you to save as a pdf should be fine. If you insist on hand-writing your homework and scanning, then make sure that you write very neatly, and that you scan using a high-quality scanner. This means you should not take pictures of your hand-scribbled homework with your phone. If we cannot read what you have written, you will not get any credit.
If you plan on using LaTeX, we recommend TeXShop for Mac OS X, TeX Live for Linux (already included in most distributions), and MiKTeX for Windows. We will provide a LaTeX template for homework solutions.
Each homework problem submission should have the following information on the first page, in large friendly letters:
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".
If we can't decipher your solution, we can't give you credit. If you have sloppy handwriting, use LaTeX. Please don't submit your first draft. Writing legibly also helps you think more clearly.
You will lose points for poor spelling, grammar, punctuation, arithmetic, algebra, logic, and so on. This rule is especially important for students whose first language is not English. Writing sensibly also helps you think sensibly.
We can only grade what you actually write, not what you mean. We will not attempt to read your mind. If your answer is ambiguous, we will deliberately choose the interpretation that makes it wrong. Writing carefully also helps you think carefully.
Write solutions, not examples.
Don't describe algorithms by showing the first two or three iterations and then writing "and so on". Similarly, don't try to prove something by demonstrating it for a few small examples and then writing "do the same thing for all $n$". Any solution that includes phrases like "and so on", "etc.", "do this for all $n$", or "repeat this process"automatically gets a score of zero. Those phrases indicate precisely where you should have used iteration, recursion, or induction but didn’t.
Declare all your variables.
Whenever you use a new variable or non-standard symbol for the first time, you must specify both its type and its meaning, in English. Similarly, when you describe any algorithm, you must first describe in English precisely what the algorithm is supposed to do. Any solution that contains undeclared variables automatically gets a score of zero, unless it is otherwise perfect.
Never use weak induction! Always, always, always use a strong induction hypothesis, even in proofs that only apply the induction hypothesis at $n-1$. Why would you even want to tie $n-2$ hands behind your back?
State your assumptions.
If a problem statement is ambiguous, explicitly state any additional assumptions that your solution requires. (Please also ask for clarification in class, in office hours, or on Piazza!) For example, if the performance of your algorithm depends on how the input is represented, tell us exactly what representation you require.
Don't submit code.
Describe your algorithms using clean, human-readable pseudocode. Your description should allow a bright student in CS 225 to easily implement your algorithm in their favorite language.
Don't submit your first draft.
Revise, revise, revise. After you figure out the solution, then think about the right way to present it, and only then start writing what you plan to submit.
Keep it short. Every homework problem can be answered completely in at most two typeset pages or five handwritten pages; most problems require considerably less. Yes, I am aware of the crushing irony.
Omit irrelevant details. Don't write "red-black tree" when you mean "balanced binary tree" or "dictionary". Don't submit code; We want to see your ideas, not syntactic sugar.
Don't regurgitate. Don't explain binary search; just write "binary search". Don't write the pseudocode for Dijkstra's algorithm; just write "Dijkstra's algorithm". If the solution appears on page 6 of Jeff's notes, just write "See page 6 of Jeff's notes." If your answer is similar to something we've seen in class, just say so and (carefully!) describe your changes. You will lose points for vomiting.
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'! However, 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 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!)