CS255 Spring 2022 Practice Final

To study for the final I would suggest you:

1. Know how to do (by heart) all the practice problems.
2. Go over your notes at least three times. Second and third time try to see how much you can remember from the first time.
3. Go over the homework problems.
4. Try to create your own problems similar to the ones I have given and solve them.
5. Skim the relevant sections from the book.
6. If you want to study in groups, at this point you are ready to quiz each other.

Here are some facts about the actual final:

1. It is comprehensive.
2. It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test.
3. You should bring photo ID.
4. There will be more than one version of the test. Each version will be of comparable difficulty.
5. It is 10 problems (3pts each), 6 problems will be on materials since the second midterm, 4 problems will be from the topics of the midterm.
6. Two problems will be exactly (less typos) off of the practice final, and one will be off of the practice midterm.

The practice final is below:

1. Sketch the proof that LRU is a `k`-competitive paging algorithm.
2. Give pseudo-code for the Euclidean algorithm then use it to calculate (showing computation steps) the gcd of 125 and 45.
3. Prove the equation `ax=b mod n` either has no solutions or it has `d=gcd(a,n)` distinct solutions `mod n`.
4. How is the Chinese Remainder Theorem used in the proof of correctness of the RSA algorithm? Where in the proof of correctness of Miller Rabin do we use: The values of `n>1` for which `ZZ_n^\star` is cyclic (that is, generated by one element) are `2`, `4`, `p^e`, and `2p^e`, for all primes `p>2` and all positive integers `e`.
5. Define the complexity classes P, NP. Define the terms p-time reduction, NP-hard, and NP-complete. Give an example of a problem in `NP` that is not known to be in `P` or to be `NP`-complete.
6. Given a directed graph `G` a dominating set is a subset of vertices `D` of `G` such that for every edge `(u, v)` in `G` one has `v in D`. Let DS be the language `{langle G, k rangle | mbox( G has a dominating of size at most k)}`. Prove DS is NP-complete.
7. Give a 2-aproximation algorithm for Vertex Cover and show why it is a 2-approximation.
8. Prove there is no p-time approximation algorithm for general TSP.
9. Give a 128/127-approximation algorithm for MAX-7SAT and prove it works.
10. Support we had the list `L=langle 50,51,55,70,71,82,83,84,99 rangle`. Give the `TRIM(L, delta)` from class used in our APPROX-SUBSET-SUM algorithm. Then apply it to this list with `delta=0.1`.