{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;
\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;
\red192\green192\blue192;}{\stylesheet{\widctlpar\adjustright \fs20\cgrid \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{\s15\widctlpar\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid \sbasedon0 \snext15 header;}{\s16\widctlpar
\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid \sbasedon0 \snext16 footer;}{\*\cs17 \additive \sbasedon10 page number;}{\s18\widctlpar\adjustright \cgrid \sbasedon0 \snext18 Body Text;}}{\info{\title HUMBOLDT STATE UNIVERSITY}{\author Dr. Hal Campbell}
{\operator Tuttle}{\creatim\yr2000\mo5\dy5\hr13\min8}{\revtim\yr2000\mo5\dy5\hr13\min8}{\printim\yr2000\mo5\dy5\hr11\min59}{\version2}{\edmins0}{\nofpages2}{\nofwords454}{\nofchars2588}{\*\company CNRS - HSU}{\nofcharsws3178}{\vern113}}
\widowctrl\ftnbj\aenddoc\lytprtmet\formshade\viewkind1\viewscale75\pgbrdrhead\pgbrdrfoot \fet0\sectd \linex0\endnhere\sectdefaultcl {\header \pard\plain \s15\widctlpar\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid {\fs18 CIS 480 - Final Review Notes\tab 
\tab p. }{\field{\*\fldinst {\cs17\fs18  PAGE }}{\fldrslt {\cs17\fs18\lang1024 2}}}{\fs18 
\par Sharon Tuttle - Spring 2000
\par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}
{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \widctlpar\adjustright \fs20\cgrid {\b\fs24 Final Review Notes}{\fs24 
\par 
\par *   final is }{\b\fs24 comprehensive}{\fs24  --- covers the whole semester!
\par 
\par Remember:
\par *   if it was on the homework, it is fair game;
\par *   if we discussed it in class, it is fair game;
\par *   if it was in the reading and we "skipped" it, DON'T WORRY about that;
\par *   if it was in the reading and we discussed that topic, it is fair game;
\par }{\b\fs24 
\par }{\fs24 *   look at the kinds of questions that were on previous tests, and on the HW's --- similar questions are definitely possible on the test.
\par         *   use the Test 1, Test 2 study suggestions in studying for final, too;
\par }\pard\plain \s18\widctlpar\adjustright \cgrid {
\par *   questions could integrate topics from throughout the semester;
\par 
\par *   will provide a sheet of reference similar to that from test 2.
\par 
\par *   post-test-2 material high points:
\par 
\par         *   structural vs. computational complexity.
\par 
\par         *   computational complexity --- how much of a resource is needed?
\par                 *   usually as a function of the length of the input
\par 
\par         *   big-O notation
\par                 *   could give you a function, ask you for the big-O
\par                 notation with regard the time complexity;
\par 
\par                 *   could ask if the time complexity is polynomial or
\par                 exponential
\par 
\par         *   usually the resource of interest is time, or space (often
\par         can be traded off)
\par 
\par *   that brings us to P, NP, intractable ...
\par         *   remember: IN the set of }{\b decidable}{ problems, there are problems that are 
\par         considered }{\b intractable}{ --- there is an algorithm for them, but they are not considered 
\par         solvable in a practical sense, because they take "too much" of some resource; we've 
\par         been focusing mostly on those that take too much time.
\par 
\par         *   there are problems that have been }{\b proven}{ to take }{\b exponential}{ time --- it has been 
\par         proven that no polynomial time solution exists for them. They are decidable, yes, but 
\par         not solvable in a practical sense as the input size increases. These are intractable.
\par 
\par *   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 }{\b decidable}{ problems;)
\par 
\par *   some ramblings about possible questions
\par         *   what is P, what is NP, what is their general significance, how are they related to 
\par         one another?
\par 
\par         *   what does NP stand for?
\par 
\par         *   what is NP-complete?
\par                 *   in NP
\par                 *   ANY problem in NP can be reduced to it
\par                 *   "hardest"
\par 
\par         *   what was the 1st problem shown to be NP-complete
\par         (satisfiability!)
\par         *   what are some examples of NP-Complete problems?
\par 
\par         *   Given a problem, show that is in NP.
\par 
\par *   you could be given a simple NP-complete reduction to do;
\par         *   could also ask general questions ABOUT such reductions, also.
\par 
\par         *   How, in general, do you show that a problem is NP-complete?
\par         (1. show in NP, 2. show that a KNOWN NP-complete problem reduces to it)
\par 
\par *   Is P = NP?
\par *   what would it mean if a deterministic polynomial time solution was found to one of the NP-complete problems?
\par }}