Some assignments are individual while others can be done in teams. The maximum number of people in a team will be stated in the handout of the respective assignment. All the team members must be enrolled in the course at submission time. A single joint solution must be submitted for each team. All submissions must include the names and student numbers of all the collaborators.
Mixed teams or undergraduate and graduate students are perfectly acceptable, but in this case the undergraduate collaborators will be marked only for the undergraduate deliverable (if different).
Late submissions will be accepted subject to a penalty of 10% per day late until my solutions (if applicable) are posted on the course’s Web site. Note that solutions may be posted as soon as four days after the due date of the respective assignment. No submissions will be accepted afterward under any circumstance.
Here are my solutions for the first examination.
Recall that the examination will be open book, meaning that you are allowed to use any kind of printed documentation. Electronic devices are not permitted and you are not allowed to share any material with your colleagues. Here you can find some generic information about open book exams. I strongly recommend that you (a) index well your material so that you can find the information you seek in short order and (b) ignore your material as much as possible (ideally, completely). If you stop every time to look things up you will most likely run out of time. My best recommendation is to bring your lecture notes and a few cheat sheets (no more than 4 pages) summarizing key concepts; this is going to save you considerable time during the exam.
The first exam covers P, NP, and NP-completeness, approximation algorithms, linear programming, and computational geometry to the extent that we covered in class up to Lecture 11 inclusive (basic operations and segment manipulation but not more complex algorithms such as the convex hull). I will not test directly anything from models of computation (and the Turing machine in particular).
Here are the kind of questions that you should expect to see.
For the complexity section I might ask the odd question about membership in P, but the main matter of this section are the classes NP and NPC. Questions asking for whole proofs of membership in NP may appear, but NPC membership proofs are generally too complex for a time limited exam. Expect therefore questions that ask to complete a reduction that will be started in the question itself (this kind of questions will be hereinafter called “fill in the blanks” questions), that ask for criticisms of reductions, or that explore the consequences of the existence or absence of a reduction. If a question asks for a complete reduction then that reduction will be simple to trivial.
Questions on approximation algorithms will likely not ask you to construct approximation algorithms (which is again too long a task for an exam), but will explore instead the existence or absence of such algorithms. Fill in the blank questions are also possible. I might also give you an approximation algorithm and ask what kind of an approximation scheme it represents. Again, if I ask for a complete approximation algorithm (or scheme) then that algorithm is simple to trivial. Questions about backtracking and branch and bound may ask how these algorithms run on certain problems (with the tree of sub-problems having a particular shape), or may ask you to comment on variations.
For linear programming I will not ask you to solve linear programs by hand. Questions that formulate some problem as a linear program on the other hand may appear. Other possible questions include questions about various properties of the simplex algorithm, and questions about various shapes of linear programs.
For computational geometry you should expect basic questions related to the algorithms discussed in class. There is an outside chance that I will be able to squeeze in a small question about segment intersection.
Trying to solve the following exercises from Cormen et. al. (page and exercise numbers are with respect to the 3rd edition) would be good practice for the exam: (p. 1065) 34.2-1, 34.2-3, 34.2-10 (you’ll have to understand the meaning of co-NP by yourself); (p. 1077) 34.3-5; (p. 1085) 34.4-3, 34.4-6; (p. 1100) 34.5-2, 34.5-7, 34.5-8; (p. 1111) 35.1-4, 35.1-5; (p. 1116) 35.2-1, 35.2-3, 35.2-5; (p. 857) 29.1-6, 29.1-7, 29.1-8, (p. 863) 29.2-3; (p. 878) 29.3-2, 29.3-4; (p. 1020) 33.1-2, 33.1-3, 33.1-5, (p. 1028) 33.2-1, 33.2-2, 33.2-3, and 33.2-8. Note however that these exercises are not meant to cover everything discussed in the course and are not necessarily a good indicator of the degree of difficulty of the questions that will appear on the exam.
Finally, you may want to take a look at the following practice exam ( without answers and with answers). This sample exam is kind of unbalanced, for indeed in the actual exam you will likely spend more time on NP-complete problems, less time on approximation algorithms, and possibly slightly more time on computational geometry. However, it should give you a good yardstick for the kind of questions that you will receive and roughly the time you are expected to spend while answering each of these questions. Obviously the actual exam will look different, so preparing for that exam based exclusively on the practice exam is a bad idea. I have however tried to illustrate in the practice exam the degree of difficulty that you will encounter in the real thing. Whether I succeeded is open to interpretation, since no two problems are the same and their degree of difficulty is to a certain degree a matter of personal opinion. I will also try to balance the questions in the actual exam better.