Exam 1 study guide

This exam will be covering lectures 1-13 (up to and including October 5).
You should be familiar with all the terminology we have defined.
You should know the correct statements of the results we have proved so far, so that you can apply them properly.
You should have an idea of how the smaller results are proved. You do not need to memorize the following proofs:
- Characterization of trees
- Correctness of BFS, DFS and Dijkstra
- Characteriztion of bipartite graphs
- All the little DFS lemmas
- Cook's Theorem
- Reduction of SAT to 3-SAT, of 3-SAT to 3-COL, and VC to DHP.
You don't have to memorize the pseudo-code for any of the algorithms we have discussed, and I will not ask you to write any code. However, I may ask you to analyze some code for what it does and what its running time is.
Be familiar with the "Big Oh" notation.
You should DEFINITELY know which problems are in P, NP, NPC. You will have to use this information, but you can only use what we proved up to this point: for example you may NOT use that TSP is NPC.
You will be mainly asked to prove some new results, so make sure you have your "tool box" ready.
Some problems on the exam may throw you off at first. Make sure that you get a good nights sleep, so that you are fresh, rested and ready to go!