CS 666, Fall 2009

Exam Guidelines

(link to CS466/666 home page)

Midterm and written final

The midterm takes place on October 27, 2009, in class.
The final takes place on December 9, 2009, 12:30-3, in RCH 211.
You are allowed to bring one 8.5x11 paper with anything written or typed on it.
You should study the material from class, as well as assignments. Past exams and assignments might also give useful questions to try, but previous offerings did not cover the exact same material, so not all questions are suitable.
For the final, strong emphasis will be on the second half.

Oral final

Available time slots

Regrets, I have no more space for oral exams for undergraduate students.

Other info

All graduate students must take the oral final, not the written one.

Undergraduate students may take an oral final, but should ask permission to do so before December 8. (I will agree unless too many students have asked and I don't have enough time slots left.) Any student that wrote the written final will not be allowed to take the oral final.

The exam should take approximately 30 minutes, but leave some more time just in case.

Please email me with your preferred day and time for the exam.

You are allowed to bring a cheat sheet (8.5x11, anything written or printed), though experience has shown that it would be easier to ask me than to search for the answer on the cheat sheet.

During the exam, I will provide pencils and paper. You should use these liberally to explain your answers. This is (a) because a picture says more than a thousand words and (b) st so that I have a bit of a record what we covered, in case I want to compare your performance with that of other students. I might also scribble on the paper; please ignore this (this is for my own records of what we talked about.) Contents:

All material covered in class and on assignments is subject to questioning.
I will start by asking you to explain some (easier) assignment questions. You need not explain every detail of a correct answer, but you should give enough ideas to show that you know how to solve it. (It's ok to give an answer based on my solution-sketches, as long as you fully understand why this works.)
I will follow up with related questions that cover course content. See below for some typical questions.
For the harder proofs and algorithms covered in class: Try to have an idea of how one would prove/do such a thing, but you don't need to know all the precise details.

Some typical questions:

What is the definition of problem P?
Is this problem NP-hard? If no, give a simple polynomial algorithm (it can be slow.) If yes, give an idea of what to reduce from and how.
For polynomial problems: Tell me some results as to how fast we can solve it. What techniques have been used? Any lower bounds? What remains open?
For NP-hard problems: Which of the standard-techniques of attacking NP-hard problems have we used? Can you sketch some algorithm ideas?
I may ask you to do the above for problems we've not seen in class, but these would then be quite similar (and I will provide plenty of help to get you in the right direction.)
For graduate students, I will also include questions on your project report, if I have any.

Some hints:

The most important part is to get the overall picture of what was going on in class. Go through the course material again, and at each step, ask yourself "Why did we do this?"
I recommend to draw a diagram with the different problems and the different problem solving techniques, indicating which was used when.
Realize that I'm not your enemy; I only want to know whether you've understood the ideas of the course.
In particular, you are allowed to ask questions during the exam. So if your mind blocks some definition during the exam, do not panic. Just admit to it, and I'll help you along.
Precise notation is not important, ideas are. A lot of definitions can easily be done in pictures, and you are allowed (in fact, invited) to do so during the exam.
Be prepared to say "I don't know the answer to this" at some point during the exam. This is perfectly acceptable, as long as it doesn't happen too much. It is much better to admit to not knowing something (so that we have time to move to another topic where hopefully you'll do better) than to waste time stumbling along trying to piece it together.
In fact, almost expect to say "I don't know the answer to this" at some point. I will adapt the questions I ask you to the answers you give me; the more good answers, the harder the questions (and the better the grade, obviously).
You can volunteer knowledge. If you know more about a topic than what I ask, mention what you know, and with any luck I'll go into that direction next.
I'll likely request to know your favorite part of the course and ask some questions from there. Know which part of the course you're best prepared for.