CS 314: Algorithms
Fall 2013

Homework Assignments

Homework Instructions and FAQ

Logistics

• Submit your homework in class. Homeworks will be due at start of class. There will be separate stacks for each question near the front of the room, so turn in all papers to the appropriate pile.

• Turn in your homework on time. All homework must be received by the beginning of class on the posted due date. Absolutely no late homeworks will be accepted without the instructor's written (or emailed) permission, which must be obtained at least 24 hours before the due date. To offset this somewhat draconian measure, we will drop the lowest grade of all the homeworks; this should take care of any unforeseen circumstances.

Format

• Clearly print your name, the homework number, and the problem number at the top of every page. For example: "Erin Wolf Chambers HW0 #2". Without this information, the I may have no idea who you are or what problem you're supposedly solving, so you'll get no credit for your work.

• Start each numbered homework problem on a new sheet of paper. This keeps things much cleaner and easier during the grading process, and ensures that I don't miss any problems.

• Staple your entire solution 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.

How to schedule oral presentation homework

Form: How to write

• 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. (1337-5p33k = 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 via email.) 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 the recommended tetbook, the best solution you can submit is "See page 263 of the textbook." Period. Same with the lectures, the lecture notes, and previous exams or homeworks from the current semester.

  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 grader will 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 of the material, not just how to use Google and a printer.

• 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 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. If you try to fake it, you'll get nothing. Remember, though, that a course average of 50% or less is an automatic F.

Content: What to write

• 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(n²)." 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 parrticular 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.

Form: How To Present

• Aim to present your solutions in 5 minutes. This is probably a bit ambitious, especially during the first weeks. However, I will stop you after 10 minutes on one problem, so you should practice giving your solution quickly and accurately! Ideally, you will want to write out your solution, even if you don't need to turn it in. Very often you will only find a bug in the solution when trying to write it down, and even if it is correct, you will improve your presentation by first writing out the argument to clarify it in your own mind.
• The "I don't know" policy also works for oral homeworks. If you have no idea of a solution, then you might as well say "I don't know" and nothing else to the instructors, because they will give you a 0 if your solution is completely wrong.
• Don't dwell on the details! Assume that the listener, who is after all the instructor for the class, is familiar with the topics from class. If the solution only differs from something presented it class by a small detail, say that! For example, if the problem is dealing with minimum spanning trees, 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 quite sufficient! (Assuming, of course, that this is the correct solution to the problem.)
• Don't forget the proof of correctness and runtime analysis. Highlight the main points of these arguments. Your job is simply to convince me that you understand the proof. So (for example) don't worry too much about base cases in an oral presentation, unless they are somehow unusual or especially important. While they are necessary in a formal writeup, they are usually unimportant in an oral presentation.

Interaction with the instructor

During your presentation, I may interrupt, ask questions, provide or ask for clarifying comments, point out flaws or counterexamples, or any other similar behavior. (Don't worry, I won't usually throw anything to get your attention.) Usually this can be taken as an indication that either you haven't made things clear or there is an error. It might also be that you've assumed too much of your tired, stressed, and overworked instructor. In any case, don't panic, because I'm not out to get you; just answer the questions to the best of your ability.

Part of the value is that you can get immediate, real-time feedback on your solutions. However, at some point it is very likely that you will find out that something is incorrect or unclear in a problem you are presenting. Don't panic! You can still get partial credit for these problems, and may even be able to fix the solution. Part of the value of this experience is learning to think on your feet while communicating your solutions.

Within reason, the instructor may allow you to react and modify your solutions. However, full points for content will only be awarded when initial solutions are correct. Yes, we realize that this gives oral presentation an advantage over written homework, since you are more likely to fix errors and get partial credit. Enjoy it!

One last comment. If you are totally stuck and can't remember how to solve the problem, but your homework partner remembers, you are allowed to ask for help. However, you will lose points for this, so try to avoid it! Make sure you all know how to solve every problem, so that you can try for full credit. However, if your answer is wrong and you can't fix it, you are better off asking for help and getting partial credit if your partner can get it correct - you'll only lose a few points off the total, so that is better than a 0.