BCB 5300: Algorithms in Computational Biology
Fall 2018

Homework Assignments

Homework Instructions and FAQ

Logistics

• Submit your homework in class. Unless otherwise specified, homeworks will ALWAYS be due at start of class. Please print or handwrite a paper copy, and bring it with you the day of class.

• Turn in your homework on time. All homework must be received by the beginning of class on the posted due date. 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, 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.

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!!)

• In general, use pseudocode or outline format to describe any 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's a bad strategy in any algorithms course. Part of what you're supposed to learn here is how to tell when you don't know the answer, so come see me if you have questions.

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, or you may be asked to find a counterexample or work through an example of an algorithm. (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.