CSC 364H Summer 2002

Final Exam Information

What is the format of the exam?
The exam will consist of 8 questions. You will have 3 hours to complete the exam. There will be 75 points available.
The first 6 questions will be on various topics from the course and will be required. For each of the last 2 questions, you will be able to choose from two options. You will be able to choose either 7A or 7B as your 7th question to answer, and choose either 8A or 8B as your 8th question to answer.
The style of the questions will be similar to those you have seen on the homework, quizzes and term tests. Questions might come directly from the homework, or they might be completely new. Regardless, I believe you will be able to solve any of the questions if you know how to do all the homework questions (including those not for hand-in).

What is on the exam?
The exam will cover the entire course, with some exceptions.

Not on the exam:

• explicit constructions of Turing machines. You must be able to manipulate TMs at a high level for reductions, etc.
• linear programming
• polynomial hierarchy, other related complexity classes
• randomization and nontrivial approximation algorithms
• and some other minor things not covered in detail

You need to know for the exam:

• the standard models of computation
• languages and decision problems
• decidability/recognizability/undecidability and reductions
• greedy technique
• divide and conquer technique
• dynamic programming technique
• max-flow/min-cut problems and algorithms
• classes of P, NP, NP-complete
• NP-completeness problems, polynomial reductions
• ... and anything else you think I think is important (i.e., anything I might have forgotten when writing this list)

What should I study to prepare for the exam?
I would suggest working on the homework questions as your first priority, including those questions that were not for hand-in. If you understand these questions, I have confidence that you will do quite well on the final.

What NP-complete problems should I be familiar with for use in my reductions?

• 3SAT (3-CNF-SAT)
• SUBSET-SUM (KNAPSACK)
• CLIQUE
• VERTEX COVER (VC)
• HAMILTONIAN CYCLE (HC)
• 3-COLORABILITY (3-COL, 3-COLOR)

What mark do I need to pass the course?
The course outline says you must get a minimum of 35% on the exam to pass the course. Generally, if you answer one 10-point question completely correctly, one question half-right, and say "I don't know the answer" to the rest of the questions, you will meet this requirement. I don't think it will be a problem for anyone in this class.

How will the exam be graded?
Each question will be graded independently, in a style similar to how each homework, quiz and test was graded. Be precise and concise.