Homework Guidelines and Policies

 

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.

How to Submit Homework

Logistics

  • Submit your homework to either TA during the head-banging session or office hours. Do not submit homeworks to the instructor, for he is fond of losing important pieces of paper. If you'd like, you may also email your homework, as plain text or a pdf file.
  • Turn in your homework on time.
  • For most homeworks, there will be an automatic extension, typically of several days. You may turn in your written homework at any time between the official due date/time and the automatic extension due date/time for full credit, provided that you do not ask for the automatic extension. If you ask, it will be denied.

  • The time of day that hw is due will by default be NOON Champaign time. Specific times may be posted which supercede this default.

  • Requests for an extension beyond the automatic extension will typically be denied; this is akin to requesting a second extension, and the first question you'll be asked is "you were already given an extension for this reason - why do you need an additional extension?".

Format

 Homeworks that do not follow these formatting requirements risk receiving a grade of 0 or a severely reduced grade. Management of a large course requires compliance.

How to schedule oral presentation homework

For oral homeworks, the group should schedule a presentation time with the TAs. Watch Newsgroup for such schedule announcements. Each member in a group must present at least one of the problems. The assignment of who presents what will be done randomly by the TA at the beginning of the presentation session Refer to the newsgroup for more details.

Form: How to write

Please be nice to the graders! Make it easy for them to see what you're doing. If your answers are hard to read, the graders will be less sympathetic to your mistakes. All this goes for exam problems, too.

Content: What to write

Convince the grader that you understand exactly what you're doing.

  • Answer the right question. Duh. 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, lists, graphs, trees, etc. 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 and space usage. 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. (See the first point in this section.) 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.

Grading

Starting with the third homework, the 10 points assigned to a typical problem will be partitioned into 7 points for correctness, and 3 points for presentation. This will hold regardless of whether the presentation is written or oral. Technical communication is an extremely important aspect of what we do, and I am pleased to offer the incentive and arena for improving your skills.


Starting HW 3, the following policies are in place:


A grading rubric based on CONTENT is devised by the TA responsible for oral presentations, in consultation with the rest of the course staff. The rubric will be applied to written as well as oral presentation. The rubric will be posted along with solutions, or before hw are returned. Do not argue about whether giving only n points to attempted solutions of type x is fair or not; the allocation of partial-credit points for broad categories is a value-judgement made by course staff, in the context of the space of possible solutions, the level of understanding demonstrated, etc. etc. What we *are* willing to discuss is whether your attempted solution was mis-categorized unfairly. Of course, we can't anticipate every type of error, so a certain amount of interpolation and/or assigning points on the basis of analogy with other flawed solutions can be expected. Do not expect the TA during oral presentation to give you a grade, but do expect him to take notes.

The 3 points for presentation will be handled as follows for written and oral presentation:

  • WRITTEN: entirely decided by grader, with the following guidelines:
    • 3: this was a model submission. it was typed or written by a master draftsman. No chai stains, and no chewing gum was used to hold the pages together. It was a pleasure to read. I understood it completely. Intuitions were there when I needed them. Each step clearly followed from previous ones. There was no babbling... All in all, I have a greater sense of peace and harmony from having encountered this homework.
    • 2: good job, but a little sloppy here. a little confusing there. didn't quite follow what they were referring to in this other spot. Overall, I am psychically no better nor worse for having had this experience.
    • 1: significant presentation problems, including one or more of the following: parts were illegible, unreadable, poor documentation, didn't explain what the algorithm was completely, poor organization. Overall, reading this caused me some mental anguish.
    • 0: Feh. Why doesn't this group read the guidelines? It was a pain to go through and understand what their solutions are, because of all the obstacles they've put in my way. Why is the second problem on the first page, and continued on the last? What does this big smudge say? Was this supposed to be a proof, or a counterexample? Which of these was their answer...? While I was able to determine, to my best ability, what their CONTENT is worth, this was such an unpleasant experience that I will not give them a single of the discretionary points Professor Pitt has entrusted to me.
  • ORAL PRESENTATION points (3 of 10). So that each person in a group does not suffer for the sins of their partners, while the CONTENT will be group-graded, the presentation for the oral hw will be given per person. Your score(s) for oral presentation for the particular problems you present will be used also for the problems you did not present. Thus, if a group of 3 scored 5,6,7 points for three problems content (out of possible 7, 7, 7), and persons A,B,C received presentation scores of 3,2,1, respectively, then their grades for that HW will be: A:18+9 = 27 B:18+6 = 24 C:18+3 = 21. FINALLY, please note that the "I Don't Know" answer is not eligible for presentation points. Yes, I see the incentive for people to make up a bad answer, and present it very nicely, to achieve 30% instead of 25% that I don't know gives, but I am counting on your sense of pride and integrity not to do that. And, I'm also authorizing the grader to give 0 points for presentation if he suspects that you have momentarily lost your pride and integrity.

Returned Homeworks

  • Graded written homework problems can be retrieved from the TAs during office hours or head-banging sessions, or occasionally from the professor in class.

  • For information on regrade requests, please see the Grading Policy page.

How to present oral Homework

First, please read the two posted papers on giving presentations in CS. Neither is completely appropriate to the task at hand, and the Parberry article is dated, but both contain information that will serve you well not just for class presentations, but more importantly, in job talks, communications, presentations, etc.

That said, your homework presentation is much closer to the "technical details" part as described by Parberry, and the audience should be considered to be "experts."

The TA knows the problem you are solving, so you don't have to state it. They know the background material, so you don't need to introduce it. They don't need to hear the motivation for the problem, because (a) they already know it, and (b) your motivation for solving it is that we assigned it. They don't want to hear you explain what O() means, or define topics generally understood by a graduate student in CS.

Your goal should be approximately five minutes per problem, though I realize now that this is perhaps ridiculous.

Many of the same criteria apply to oral presentation as apply to written. You get 25% if you say simply "I don't know" and nothing more.

I said in the newsgroup that I believe the greatest danger is that you will spend more time thinking about oral presentation skills and not enough time thinking about the solution. My experience has been that when I thought I had proved a result, often trying to write the details down clearly is what showed me the logic errors. So, even for the oral presentation, I would urge you to write down a complete proof. This is also good presentation preparation.

What to say, guidelines

It is hard to describe what a good presentation is in general terms, beyond what the papers I've referenced say, and the advice/pointers extracted above for all work (oral/written). I will try to describe a generic good presentation.

  • How is the problem modeled? Our text has a variety of problem types. One such is "show how to modify the XYZ algorithm to handle negative vertex capacities...": As this type of problem is probably more straightforward, I will discuss the other type that appears more frequently and is more demanding from the standpoint of presentation... the "word" problems. In these, a problem is described that may not look, on the surface, like any particular abstract problem that we have studied (MST, shortest path, scheduling...). Typically, part of the challenge will be for you to figure out how known algorithms or techniques should apply. This means reformulating the given problem in some other way, or extracting the relevant parts and ignoring the irrelevant parts. This is in essence, the process of *reducing* your problem to a known one. (We'll talk a lot about reductions when we talk about NP-complete problems.) If the problem is like this (as opposed to, say, "show how to modify the XYZ algorithm to handle negative vertex capacities..."), then the first thing you should do is explain how you model the problem in relation to known algorithms/problems. For example:

    "In the goldrush problem, the fact that prospectors mine silver as well is a red herring, as this does not affect their daily intake. Thus, ignoring the silver haul, the problem as stated is the same as the well-known maximum weight rucksack problem, but with the added constraint that.... The added constraint comes from the fact that in the goldrush problem, each pick-axe contributes ..... but in the standard rucksack problem, ...."

    If this abstraction/reduction/reformulation is at all nontrivial, you should prove it. This means showing that a solution to the modified rucksack problem really is a solution to the goldrush problem.
  • Now that you've extracted a clear-cut algorithmic problem, perhaps in terms of some other known algorithm or well-studied problem, state algorithmically how you solved it. You shouldn't dwell on minutiae, but on what the listener needs to know to get a clear understanding of the algorithm, assuming the listener is a TA for this class. Thus, saying "the algorithm is identical to Kruskal's MST algorithm, except after each edge is chosen, we insert an extra step in which the maximum weight edge between any pair of distinct components is removed from the graph entirely- thus - it can never be used as an edge again" is sufficient (if that is what your algorithm does). If you are devising an algorithm that does not rely in any simple way as the above, then do describe the algorithm. Avoid "and so on..." For recursive algorithms, indeed, for *any* algorithm, make clear what the input and output are. Sometimes in an inductive proof to work, or for a recursive algorithm to perform properly, you may need to carry more information recursively/inductively throughout. Make this clear. As an example, the median finding algorithm presented in class actually returned the kth largest element of a set, and the value of k changed in each recursive call, based on what fraction of the data was to be "discarded". Another example is the bank-card problem for homework 3. A divide and conquer approach might require not just that one recursively determines whether a given subset of the cards contains a majority card-type, but also that the algorithm recursively returns a representative if there is one.
  • Now PROVE that it is correct. You don't need to even mention base cases for an inductive argument in an oral presentation.

    "Assume recursively that we have obtained an widget that is optimal for the first 13/19th of the data, and similarly for the 5/19th that form the second recursive call. Taking these two widgets, and..... with the remaining 1/19th of the data clearly results in an optimal widget for the entire data set because ...."
  • Analyze the running time and space, discussing only points that are not obvious.

    JARGON: Sometimes things are so cumbersome to say or write that it is a good strategy to introduce a new term. For example, call a vertex *sociable* if it has degree at least 3 times the average degree of its neigbors. Our algorithm finds all sociable vertices, and then..."

    Think of this as good proofwriting style, similar to good coding style. Introduce a macro if it will be used often, but not gratuitously to be used once.

    Your argument as a whole should be like good code as well.
    • Documentation (intuition as needed.. "the reason we are looking for the sociable vertices is that their degrees are sufficiently high that when we recurse on them, we'll cover at least 3/4 of the graph, and.... the remaining 1/4 of the graph is handled via this other technique...". )
    • Top down, modular (give high level, delve into detail as needed)
    • Good variable names
    • Clear understanding of I/O requirements, expectations, for each piece. (Exactly what does the lemma depend on? Exactly what is the conclusion of the theorem?)

Interaction

The TA randomly assigns to each person in your group a problem to present. Those not presenting should for the most part remain quiet, until at some point it appears that help is needed/requested.

During your presentation, the TA may interrupt, ask questions, provide or ask for clarifying comments, point out flaws or counterexamples. Usually this can be taken as an indication that either you haven't made things clear, or that there is an error. It might also be that you've assumed too much of the battle-weary TA. In any case, don't panic, just answer the questions... think of it as a tutoring session.

Part of the value is that you can get immediate, real-time feedback on your solutions. However, you also will likely find out that there are errors in your solution, you overlooked some cases, your proof is outright wrong, whatever.

Within reason, the TA will allow you to react and modify your solutions. However, only full points for content will be awarded when the initial solution presented was correct. Yes, we realize that this gives oral presentation an advantage over written. Yes, we realize that after we say it evens out you'll point out that because your group number is even (or odd), the luck of the draw made this unfair. No, we do not care, because allowing for this interaction is probably quite beneficial in the learning process, and to simply say "nope, wrong. move on" would blow some really good teaching/learning moments.