Princeton University
Computer Science Department

Computer Science 345
The Efficient Universe

Avi Wigderson

Spring 2006

Final Exam

General Information

No collaboration is permitted on the final. You may refer to your own notes, textbooks, and online references. You are not supposed, however, to search for solutions online.

Your solutions are due by 4:00pm on Friday, May 19. You may work on the exam for up to 24 consecutive hours. Since students will be taking the exam at different times, you should not discuss the final exam with others till that date. Please, return the exam to Donna O'Leary (410 CS Building), or email a pdf or word file to kmakaryc AT

Make your answers as clear, precise and brief as you can. No problem requires more than a page in clear handwriting (we recommend to write a draft first). You can give partial answers (or solve special cases) for possible partial credit. If you make any assumptions state them clearly. You can use theorems/lemmas/facts from the class, precept, textbook and recommended references. You should prove any other theorems/lemmas/facts you use.

You may ask questions about the course topics up until the time you start working on the exam. After that, you should only ask questions if you need a clarification about a problem on the final. We will try to answer all your questions.

Each of the problems below is worth 25 points. Your grade will be the total of the grades on your best 5 of the 6 problems.

Hint: Try to solve easy problems first and then proceed to more difficult ones.

Good luck!

Download the exam