based on weekly homework assignments. There will be no
examinations. The problem sets are due by noon on Thursdays.
Homework should be turned in to the Ma6 box outside of 253 Sloan.
- Please staple a blank page containing only your name at the front of the assignment.
- You are encouraged to work in groups on the assignments. However, you must do on your own problems that are marked "NO
COLLABORATION". Moreover, do not ask about these questions in office hours. You are of course allowed to ask for a clarification if the question is not clear, or if you think that it contains a mistake. It is also fine to ask about the material from class that is related to the problem.
- There is no need to formally prove anything, unless the question specifically asks for a proof. However, you do need to explain what you did. The grader needs to see that you did not just write an algorithm/answer without understanding how to get to it or why it works.
- Unless stated otherwise, every given graph is simple and undirected.
- There is no need to find the running time of the algorithms that you create in your homework. However, the running times must be polynomial in the size of the input.
- There is no need to write pseudocodes for algorithms - we even prefer a description in words.
- There is no need to reprove anything that was proven in class. On the other hand, you are not allowed to refer to any other sources, including the course's text book (answers of the form "The proof can be found in page X of the book" will receive no points).
- Make sure that you submit your assignments in the LOCKED 6a mailbox, and not in the open box for graded assignments.
No book covers all of the material, and we rely on several sources. One main textbook is Introduction to Graph Theory, 2nd edition, Douglas West. Another is Graph Theory, 4nd edition, Reinhard Diestel. A free online version of the book can be found here.