Final Review Notes

*   final is comprehensive --- covers the whole semester!

Remember:
*   if it was on the homework, it is fair game;
*   if we discussed it in class, it is fair game;
*   if it was in the reading and we "skipped" it, DON'T WORRY about that;
*   if it was in the reading and we discussed that topic, it is fair game;

*   look at the kinds of questions that were on previous tests, and on 
the HW's --- similar questions are definitely possible on the test.
        *   use the Test 1, Test 2 study suggestions in studying for 
	final, too;

*   questions could integrate topics from throughout the semester;

*   will provide a sheet of reference similar to that from test 2.

*   post-test-2 material high points:

        *   structural vs. computational complexity.

        *   computational complexity --- how much of a resource is needed?
                *   usually as a function of the length of the input

        *   big-O notation
                *   could give you a function, ask you for the big-O
                notation with regard the time complexity;

                *   could ask if the time complexity is polynomial or
                exponential

        *   usually the resource of interest is time, or space (often
        can be traded off)

*   that brings us to P, NP, intractable ...
        *   remember: IN the set of decidable problems, there are 
	problems that are 
        considered intractable --- there is an algorithm for them, but 
	they are not considered 
        solvable in a practical sense, because they take "too much" of 
	some resource; we've 
        been focusing mostly on those that take too much time.

        *   there are problems that have been proven to take exponential 
	time --- it has been 
        proven that no polynomial time solution exists for them. They are 
	decidable, yes, but 
        not solvable in a practical sense as the input size increases. 
	These are intractable.

*   But besides the class of exponential problems, there are also the 
classes of problems P and NP; (remember that problems in P, problems in 
NP, and exponential problems, are all subsets of the set of decidable 
problems;)

*   some ramblings about possible questions
        *   what is P, what is NP, what is their general significance, 
	how are they related to 
        one another?

        *   what does NP stand for?

        *   what is NP-complete?
                *   in NP
                *   ANY problem in NP can be reduced to it
                *   "hardest"

        *   what was the 1st problem shown to be NP-complete
        (satisfiability!)
        *   what are some examples of NP-Complete problems?

        *   Given a problem, show that is in NP.

*   you could be given a simple NP-complete reduction to do;
        *   could also ask general questions ABOUT such reductions, also.

        *   How, in general, do you show that a problem is NP-complete?
        (1. show in NP, 2. show that a KNOWN NP-complete problem reduces 
	to it)

*   Is P = NP?
*   what would it mean if a deterministic polynomial time solution was 
found to one of the NP-complete problems?