COS 522 - Complexity - Take home final

Read these instructions carefully before starting to work on the exam. If any of them are not clear, please email me before you start to work on the exam.

Schedule: You can work on this exam in a period of 72 hours of your choice between May 4th to May 18th 5pm. You may submit the exam earlier. You should type the exam, and submit me the file by email when you're finished with it. Please also put a copy of the exam in my mailbox (though you can do it also a day or two after the deadline.)

Restrictions , honor code: You should work on the exam alone. You can use the textbook, your own notes from the class, and the homework exercises. You can also use any personal summaries and notes of the material that you prepare before starting to work on the exam. You should not use any other material while solving this exam. You should write and sign the honor pledge on your submitted exam (the pledge is ``I pledge my honor that I did not violate the honor code during this exam and followed all instructions'').

Writing: You should answer all questions fully, clearly and precisely. When describing an algorithm or protocol, state clearly what are the inputs, operation, outputs, and running time. When writing a proof, provide clear statements of the theorem you are proving and any intermediate lemmas or claims. I recommend that you first write a draft solution of all questions before writing (or preferably, typing) up your final submitted exam.

Partial solutions: If there is a question you can not solve fully, but you can solve a partial/relaxed version or a special case, then please state clearly what is the special case that you can solve, and the solution for this case. You will be given partial credit for such solutions, as long as I feel that this special case captures a significant part of the question's spirit.

Quoting results: You can quote without proof standard mathematical tools such as Chernoff bounds, and concepts from linear algebra (inner product, eigenvalues etc.). However, you should quote the results precisely, and give a reference to the place in the textbook where the result is stated. Regarding complexity results, you can quote without proof results that have been proven in class or that have full proof in the book. However, if a result is stated in the book, but without a full proof (or part of the proof is given as exercise) then you must provide a proof if you use this result.

Clarifications: I have made an effort to make the questions as clear and unambiguous as possible. In case any clarifications are needed, you can contact me by email or phone: 609-981-4982 between 11am and 10pm EST. If there are any unresolved doubts, please write your confusion as part of the answer and maybe you will get partial credit.

When you are ready to work on the exam, you can download it from this link.