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 Policies
The graders will have to critically examine several thousand pages of homework submissions before the end of semester! We desperately need your help to make sure homeworks are graded and returned quickly.Logistics
- 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 homework. Students are responsible for forming their own homework groups, and students may change their homework groups as often as they like.
- Absolutely no late homeworks will be accepted for any reason. To offset this rather draconian policy, each student's lowest homework score will be dropped. In cases of extreme illness or other emergencies, we may forgive homeworks or even exams. This means that your grade will be computed 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 lowest unforgiven homework grade is dropped. Please see Jeff for details.
- Submit your homework to Elaine Wilson in 3229 Siebel Center. There are separate folders for each problem in Elaine's office; please put your solution to each problem in the appropriate folder. Do not submit homeworks to the instructor, for he is fond of losing important pieces of paper.
- Graded homeworks and midterms can be picked up from the TA office during office hours. Under normal circumstances, your graded work should be ready to pick up no more than 10 working days after you submit it.
Format
- 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.
- Start each numbered homework problem on a new sheet of paper. In order to make the grading faster and more consistent, each homework problem is graded by one person and returned as soon as it is graded. Only the first problem on any given page will be graded.
- Separately staple your solution to each problem once 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.
- 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 homework solutions, print the name and NetID of every group member on every page. Without this information, the graders will have no idea who you are or what problem you're supposedly solving, so you'll get no credit for your work.
- Never write your Social Security Number on anything! Social Security Numbers are extremely valuable personal information. Anyone who knows your SSN can steal your identity with very little effort. Social Security numbers should only be used for financial transactions that are reported to the IRS.
- Nicely typeset homework will be given a modicum of extra credit. The graders get to decide what "nicely" means. I strongly recommend LaTeX , far and away 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. If you're a PhD student, you'll have to learn to use LaTeX eventually; might as well start now. I recommend TeXShop for Mac OS X, teTeX for UNIX/Linux (already included in many distributions), and MiKTeX for all you poor victims of the Gates Virus.
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, arithmetic, algebra, logic, and so forth. If the graders can't decipher your solution, you will get no credit. If your handwriting is bad, it's time to learn LaTeX. This is especially important for students whose first language is not English.
- 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. Carefully describe the high-level 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.
- Omit all 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.
- Use pseudocode or outline format to describe your algorithms. Do not turn in source code! Your description should be human-readable. See the lecture notes and recommended textbook(s) 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 is python.
- 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". Algorithms or proofs that use phrases like "and so on", "etc.", "repeat this for all X", and "..." will get no credit. Those are perfect 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! If you don't know the answer, don't do a brain dump, hoping to get partial credit for incuding a few key words. That won't work in this class. A crucial part of mastering any new material is learning to recognize when you don't know something. 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. Readable, correct, but suboptimal solutions are always worth more than 25%.
- 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 63 of Jeff's lecture notes, the best solution you can submit is "See page 63 of Jeff's lecture notes." 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.
- However, if you find a solution from any other source, you must rewrite the solution in your own words, and you must properly cite your sources. This policy applies to all outside sources, including web pages, journal papers, different algorithms textbooks, other students (whether they're taking the class this semester or not), official homework solutions from previous semesters, and your mom. Assume the graders have access to all the official course material, but nothing else. 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 and a stapler.
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!
- 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—many 'obvious' things are actually 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.
- Describe the most efficient algorithm possible. 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 need 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 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(n2)." 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. Exam problems will rarely ask for proofs of correctness.
Grading Policies
Graded homeworks and exams
- Homework and exam grades will be posted on the course web page, using the alias you provide on Homework 0. For privacy reasons, your alias should not resemble your name or NetID. By providing an alias, you formally agree to let us list your grades. To comply with both fedaral law and university regulations, we cannot list your grades unless you provide us with an alias on Homework 0. We may also use Compass Gradebook, which will let you see your own grades, but not your relative standing in the class.
- Homework solutions will be posted a few days after the submission deadline; exam solutions will be posted immediately after the exam ends. Posted solutions will include suggested rubrics for grading each problem; if the graders need to amend or otherwise modify these suggested rubrics, final rubrics will be posted when grading is complete.
Regrade requests
- Please check that your grades are tabulated and recorded correctly. If you notice a mistake, please bring your graded work to the TA or the instructor, and we will correct it immediately.
- If you believe that your homework or exam has been graded unfairly, you may request a regrade. Homework will be regraded by the TA; exams will be regraded by the instructor. To request a regrade, resubmit the work in question along with a brief written explanation why you think you were graded unfairly. (For example, "My answer to problem 2 is correct; see the posted solutions." or "My grade does not match the posted rubric.") Don't revise or explain your answer; we can only grade what you submitted the first time.
- Regrade requests must be submitted at most two weeks after the homework or exam is returned. Except for arithmetic mistakes, late regrade requests will be ignored.
- If you submit a regrade request, your entire homework or exam will be regraded from scratch. Your grade may go down.
- We will readily admit, apologize for, and correct our mistake if you have been graded unfairly. However, please remember that "unfairly" means your grade is blatantly incorrect, or that you were graded more harshly than other people in the class, not just that you think the grading standard is too harsh. Please also keep in mind that each homework point is worth less than 0.1% of your grade. Frivolous regrade requests will be met with the scorn they deserve.
Final course grades
- Final course grades will be assigned using the following algorithm. (What do you expect from an algorithms course?)
- Drop each student's lowest homework grade. (If some homeworks have more weight than others, we will drop the homework that leaves the highest weighted homework average.)
- Compute everyone's raw average, which excludes all extra credit points. Course work is weighted as follows: homework is 30%, each midterm is 20%, and the final is 30%.
- Compute everyone's adjusted average, which includes extra credit points, even from the dropped homework. Extra credit points are not necessarily worth the same as regular points.
- Anyone with an adjusted course average over 95% gets an A+.
- Anyone with an adjusted course average below 50% automatically gets an F. (This is not the only way to fail!)
- Determine letter grade cutoffs, excluding outliers from steps 4 and 5. The mean is a borderline A-/B+, and each standard deviation is worth half a letter grade. (Thus, the B+/B cutoff is 2/3 standard deviations below the mean.)
- Compute final letter grades from adjusted averages, except for the outliers from steps 4 and 5.
- Adjust grades (only upwards!) at the instructor's whim.
This algorithm ensures that extra credit can only increase your grade, that other people's extra credit does not affect your grade, and that the curve isn't skewed by the handful of geniuses and doofuses in every class. We expect slightly more than half of the students to get an A- or better.
- In Spring 2005, the last time Jeff taught 473G, the mean was about 70% and the standard deviation was about 8%. Thus, an average of 64% or better was required for a B+ (to satisfy the CS PhD core requirement), and an average of 54% or better was required for a B- (to receive graduate credit and satisfy the CS master's core requirement).
Academic integrity
This last section is unfortunately necessary, thanks to the actions of a tiny minority of students.
Each student (or homework group) must write their own homework solutions, in their own words, and must properly credit all sources. We strongly encourage students to use any printed, online, or living resource at their disposal to help solve the homework problems, but you must cite your soruces. If you use something you found in a book, cite the book. If you use something you found on the web, cite the web page. If you get an idea from someone else, give them credit. This is the same standard of conduct that researchers are expected to follow in their formal publications; start following it now. Citing your sources will not lower your homework grade.
Avoiding plagiarism is really very simple: Never present someone else's words or ideas as your own. Repeating ideas from other people, papers, or web pages without giving proper credit is plagiarism. Verbatim duplication of any source is plagiarism, including official homework solutions from previous semesters of 373/473, even if you properly cite your sources. Turning in a copy of someone else's work as your own, even with their permission, is plagiarism. Allowing someone else to copy your work verbatim, or without giving you credit, is also a violation of academic integrity. See Article 1, Part 4 of the UIUC student code (http://www.admin.uiuc.edu/
policy/ for more information. If you have any doubt about whether something contitutes plagiarism, talk to the instructor or TA, and err on the side of caution.code/ article_1/ a1_1-402.html) Violations of academic integrity will not be tolerated. The default penalty for a first offense is a grade of zero on the entire homework or exam. (A zero homework grade that results from a cheating offense will not be dropped.) The penalty for a second offense, or a particularly egregious first offense, is an F in the course. (These are the department's recomended penalties for cheating offenses.) All cheating cases are reported to the department. Multiple offenses can result in suspension or dismissal from the computer science program or from the university. More than one student has been expelled from the university (in part) because of cheating offenses in CS 473.
Our high expectations for graduate students extend to issues of academic integrity. A notice of any cheating offense by a graduate student will be entered into their file, where it will be seen by the student's advisor, as well as their qual, prelim, and thesis committees. Several faculty members have publicly stated that they would refuse to advise or serve on a committee for a MS or PhD student who has committed even a single cheating offense, no matter how minor or how far in the past. In short, if you cheat, you are signing your own academic death warrant.
Regardless of whether it constitutes plagiarism, or whether you get caught, getting too much help on your homework will hurt your final grade. If you don't learn how to solve algorithmic problems on your own, you will perform poorly on the (closed-book, closed-notes) exams, which make up 70% of your final course average. At least once a year, a student with a 95% homework average fails the course.