Assignments:
- Homework 0 is due on July 19
- Homework 1 is due on July 27
- Homework 2 is due on August 02
- Homework 3 is due on August 09
- Homework 4 is due on August 16
- Homework 5 is due on August 23
Read these guidelines carefully and keep them in mind when doing your homework assignments.
Format
Print you name clearly on the front page. Number each page and staple them together. You will loose points if you don't do this.
Nicely typeset homework will get extra credit. If you want to use Latex, the homework style file can make your life easier.
Don't turn in the piece of paper you used to derive your answer, neatly copy the relevant information onto a new empty page.
Content
Think about how to best present your ideas; always try to simplify things as much as possible. For example, suppose you are to find a graph example with a certain property; you find one with 20 nodes and 50 edges. You should ask yourself this question: is such a big graph really necessary?
When presenting your algorithms give pseudocode and a short description of the main ideas. Never turn in source code: Don't assume the grader knows your favorite programming language! English prose by itself is insufficient, as it is usually ambiguous. See the textbook and handouts for examples of the type of presentation we want.
In addition to its description you should always provide the analysis of your algorithm: justify its correctness, derive running time and space requirements. Always try to find the most efficient algorithm you can; partial credit will be given to less efficient solutions.
Unless otherwise stated always justify your answers, i.e., provide a proof for every true claim and a counter example for every false claim.
If you make use of material in the book or presented in class you don't need to copy all the details. For example, if your algorithm uses DFS as a subroutine don't repeat the DFS lecture, rather write "Step 1: Perform DFS. // for every vertex u, d[u] (discovery time) and f[u] (finishing time) are known" and then work with d[u] and f[u]
Grading
Any grading related questions or regrading requests should be directed to the TA. After the homeworks are returned you have one week to ask for a regrade request, after this all requests will be ignored.
If you don't know the solution to a problem don't expect to get partial credit for writing something that superficially resembles a proper answer but on a closer look it is just unintelligible ramble; such answers will get no credit. Answering "I don't know" (and nothing else) to any homework question is worth 20% of the points. It is important to be able to tell (and acknowdledge) when one doesn't know something.