======= Final Exam Exclusion List =======

Remarks:
A) Materials before mid term will be covered too. But significantly more weight will be put on 
the material after midterm and on material not covered by the mid term. 

B) The following list intend to provide a list of things that WILL NOT be covered in the final exam. 
All others not mentioned in this list are possible final exam questions.

C) VERY IMPORTANT: If a PROOF of a theorem is listed as not required, unless otherwise mentioned, 
you still NEED TO KNOW the main conclusion of the theorem, AS WELL AS the related algorithm or data 
structure. For example, although the proof of the optimality of the MIN algorithm is not required,
you still need to know MIN algorithm is offline optimal, and how MIN algorithm works.

1. Review.
- none is excluded.

2. Online algorithms
- Proof of offline optimality of MIN algorithm. 
- Proof of performance of MARKING algorithm. 
- Three types of adversaries.

3. Randomization
- Proof of the performance of Better-Cut algorithm.
- The primality test algorithm.

4. Amortized Analysis
- The proof of O(n log*n) complexity for union-find.

5. Approximation Algorithm
- The detailed approximation ratio of the PTAS for TSP.
- The PTAS for the furthest string.

6. Parameterized Algorithms
- The time complexity O(1.2738^k n^c). 
- As a general rule, you do not need to remember such numbers as 1.2738, unless they are simple values such as 2 or log n.