CS573:
Graduate Algorithms  Fall 2012
Homework Instructions and FAQ
In all issues the outline is the last
word as far as policy.
If you have any questions or concerns about these course policies,
please don't hesitate to ask in lecture, during office hours, on the
course newsgroup, or by email.
Over 90 students are taking CS573 this semester. The graders
will have to critically examine billion pages (or similar
nubmer, I am no good with numbers) of homework submissions before the
end of semester! We desperately need your help to make sure homeworks
are graded and returned quickly.
Logistics
 Submit your homework in the homework boxes in the basement
of Siebel Center. They are in the lowerlevel next to the snack
machines.
 Start each numbered homework problem on a new sheet of
paper. You would need to submit every question in a separate box.
 Turn in your homework on time. Absolutely no late
homeworks will be accepted for any reason. To offset this somewhat
draconian measure, we will drop the lowest grade of all the
homeworks; this should take care of most unforeseen circumstances.
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. Such creative grading would only be used
in some exceptional cases. Contact Sariel in such cases.
 Each student must submit their own solutions for Homework
0.
Format
 Readiblity  due to budget situation, we have no special grader
for this class. As such, make sure your homework is clearly written
and readble. You will lose up to 20% of the homework grade if your
solution is hard to read. Solutions that are unreadble will get zero
points. Submitting printed homeworks in a step in the right
direction... (See below for details.)
 Use standard US Letter paper (8.5" × 11") or a close
approximation. Most US notebook paper is close enough. Use both
sides of the page whenever possible.
 Clearly print your name(s), your NetID(s), the homework
number, and the problem number at the top of every page. For
example: "Bogi Shogi (shogi@uiuc.edu) 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.
 If a problem requires more than one page, staple those
pages together once in the upper left corner. Please do not use
paper clips, tape, glue, spit, or rubber bands. Please do not try
to keep pages together by folding or tearing. It is not necessary
to staple singlepage solutions.
Please DO staple your entire homework together.
 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 (i.e., probably the TA in this
case) get to decide what "nicely" means. I strongly
recommend using LaTeX, which is 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, TeX Live for
UNIX/Linux (already included in many distributions), and MiKTeX for all you poor victims of
the Gates Virus.
Homeworks that do not follow these formatting requirements will
automatically receive a grade of zero. This is not a joke.
Please be nice to the graders! Make it easy for them to
understand what you're doing. If your answers are hard to read, the
graders will be less sympathetic to your mistakes. If your answers
are impossible to read, we'll just ignore them. All this goes for
exam problems, too.
 Write concise, legible, and correct solutions. You
will lose points for bad handwriting, spelling, grammar,
arithmetic, algebra, logic, and so on. If we can't decipher what you
wrote, you will get no credit. This is especially important for
students whose first language is not English. If your handwriting is
bad, it's time to learn LaTeX. (13375p33k = teh 5uxx0r!!)
 Use pseudocode or outline format to describe your algorithms. Do not turn in source code! Too much syntactic sugar distracts the reader (and the writer!) from what's the algorithm is really doing. On the other hand, raw English prose is also usually insufficient. See the textbooks and lecture notes 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.

Make the punch line obvious. Emphasize your final answers by
putting a box around them, or using a highlighter, or some similar
trick.
 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 abstract data types.
 Include relevant details. 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 regurgitate! If your answer is a simple modification
of something we've seen in class, just say so and (carefully!)
describe the changes. If the complete and correct answer is on page
263 of Jeff's lecture notes, the best solution you can submit
is "See page 263 of Jeff's lecture notes." Period. Same with
previous exams or homeworks from the current semester. You
will lose points for vomiting.
However, if you find a solution from any other source,
such as a web page, a journal paper, a different algorithms textbook,
an official homework solution from some earlier semester, or your mom,
you must rewrite the solution in your own words, and
you must properly cite your sources. Assume the graders have
access to all the official course material, but nothing else. While
we strongly encourge you to use any outside source at your
disposal, please remember that the homework is supposed to demonstrate
that you understand the material, not just how to use Google and a
printer.
IDK  I dont know points
Don't babble! If you don't know the answer, don't do a brain
dump, hoping to get partial credit for including a few key words.
That will never work in this class. Part of what you're supposed to
learn here is how to tell when you don't know the answer.
Answering "I don't know" (and nothing else) to
any homework or exam question is automatically worth 25%
partial credit for that question. (We will also accept "WTF?")
If you try to fake it, you'll get nothing. A course average of 30% or
less, or a homework average of 50% or less, is an automatic F.
Important: IDK points will not exceed 10% of the given homework or
exam.
Convince the grader that you understand exactly what you're doing.
 Answer the right question. No matter how clear and polished your solution is, it's worth absolutely nothing 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 all your answers. Unless the problem specifically says otherwise, every homework and exam problem requires a proof. Without a proof, even a perfectly correct answer is worth nothing. In particular, the sentence "It's obvious!" is not a proof—many 'obvious' things are actually false!

By default, if a homework or exam problem asks you to give/show/describe/develop 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(n^{2})." 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. (See the first point in this section.) Some problems may ask you to analyze the space used by your algorithm in addition to the runing time. Exam problems will rarely ask for proofs of correctness.

Don't make the reader extrapolate. It is never enough to explain what happens during the first one or two iterations of an algorithm, and then say "and so on". If we can't immediately tell just by looking what happens during the 17th, 42nd, or 31337th iteration, your description is incomplete. 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.
 Graded homework problems and midterms can be retrieved from the
TA office during office hours (or whenever the TAs are around).
Under normal circumstances, your graded work should be ready to pick
up no more than 10 days after you submit it.
 Homework solutions will be posted a few days after the
submission deadline; exam solutions will be posted immediately after
the exam ends. All 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
the grade is complete.
 Homeworks can be regraded by submitting them to any of the TAs;
exams can be regraded by submitting them to the instructor. If the
graders have made a simple arithmetic mistake, we will fix it
immediately. Otherwise, you must also submit a brief written
explanation why you think you were graded unfairly. (For example,
"My answer to problem 2 is correct; see the posted solutions.")
Don't revise or explain your answer; we can only grade what you
submitted the first time.
If you submit a regrade request, your entire homework or
exam will then be regraded from scratch. Yes, this means
your grade can actually go down. In fact, it would probably go down.
All 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.
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.
Finally, please remember that each homework point is worth less
than 0.1% of your grade. Frivolous regrade requests will be met
with the scorn they deserve.
The following is just a sketch of how the final grade computation
would be done. The instructor reserves the right to change this
algorithm in any way he/she/it sees fit when the actual grading is
done. In any case, grading would be done in a consistent and fair way
and would try to follow the algorithm described below.
Homework and exam grades will be reported on moodle. (We may
also use the campus Gradebook program.) For privacy reasons, your
alias (if we ask for it) should not resemble your name or NetID. By
providing an alias, you 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.
Final course grades are assigned using the following algorithm.
(What do you expect from an algorithms course?)
 Drop each student's lowest homework grade.
 Compute everyone's raw average, which excludes all extra
credit points. Course work is weighted as follows:
 Clicker 5% (only for on campus students)
 Quizzes 5%
 homework 15%,
 midterm 25%.
 final is 50%.
(Online students would probably be automatically given the clicker
questions points. TBD.)
 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 below 30% or an adjusted
homework average below 50% automatically gets an F. (These are
not the only ways to fail!)
 Determine letter grade cutoffs, excluding outliers from steps 4
and 5. The mean is a borderline B+/A, and each standard deviation is
worth 2/3 letter grade.
 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 system 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 roughly 50% of the students get an
A or better.
This final section is unfortunately necessary, thanks to the
actions of a very small 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 sources. 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 for 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 proper credit is plagiarism. Verbatim duplication
of any source is plagiarism, including official homework
solutions from previous semesters of 473/573, 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
other people to copy your work is also a violation of academic
integrity. For more information, see the university's Policy
on Academic Integrity, especially the section on
plagiarism.
Violations of academic integrity will not be tolerated. The
default penalty for a first offense is a grade of zero on the homework
or exam, plus a 10% penalty on the final course average. The penalty
for a second offense, or a particularly egregious first offense, is an
F in the course. (These are the department's recommended
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 573.
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 perform poorly on the (closedbook, closednotes) exams,
which make up 70% of your final course average.
It is quite OK to use a solution you found online/papers/book/etc,
with the following restriction. You have to write the solution in
your own words and understand the solution (i.e., do not just
cut and paste whatever you found  this would be considered
cheating). Similarly, you must understand the solution you
submit. Failing to understand the solution you submit is cheating.
In any case, you must give clear credit in the text: "the solution
is taken from http://www.theunion.com/", etc.
You will not lose points for using outside sources for your solutions.
 Dont ask on online forums to solve your homework questions. Just
dont.
Last modified: Wed Aug 28 16:30:12 CDT 2013