**WHAT YOU SHOULD STUDY!** The easy answer is everything.
However, the main things you should look at are the previous exams,
the previous practice exam/study material, and the ``Since the 12-Week
Exam'' section below. Especially, look over the sample questions for
the ``Since the 12-Week'' material.

**Exponentiation**- We covered ``divide and conquer'' exponentiation early on in the semester, but we really started needing it with our RSA implementation. What additional improvements can you make when you want to compute ?
**GCD**- What's interesting about our GCD algorithm historically? Whom is it named after? Know the algorithm and how to use it!
**Extended GCD**- If the gcd of two numbers and is , then it turns out that there exist two numbers and such that . The extended GCD algorithm returns not only the gcd , but also and . If I give you psuedo-code to jog your memory, you should be able to perform the algorithm on small numbers. You should also know how this helps you to compute multiplicative inverses ``''.

**Key Generation**- How are keys generated?
**Encryption/Decryption**- How do we encrypt and decrypt?
**Security**- What is RSA's security based on? Why is it difficult to crack? What would you have to do to your implementation to foil Mr. Lemerande's RSA cracking program? Why can't we be sure that we may always rely on RSA to provide secure communications?
**Authenication**- How can RSA provide authenticated communication (i.e. a ``digital signature'')?
**Export Controls with Cryptology**- We talked about this stuff, and you should know the basics -- who controls this? what constitutes exporting? can you export cryptographic technology?

**P**- What's the definition of P?
**NP**- What's the definition of NP? Be able to show that a problem is in NP! What does ``NP'' stand for?
**P vs NP**- What's the big P vs. NP question? True/false/Nobody Knows: if a problem is in P it is also in NP? True/false/Nobody Knows: if a problem is in NP it is also in P?
**Reduction**- If I reduce problem to problem , which one is harder?
**NP-Complete**- What does it mean for a problem to be ``NP-Complete''? Give me an example of an NP-Complete problem. How could NP-Complete problems help you prove P = NP?

- True or false or nobody knows ;-) You have to be selling (i.e. recieving money for) a cryptography product overseas to fall under the export control regulations for cryptographic software? Explain!
- True or false or nobody knows - It is impossible to solve the 0/1 Knapsack problem in time polynomial in the input size of the problem. Explain!
- True or false or nobody knows - Since Dr. Brown can crack 32-bit RSA encryption in about a minute, he could crack 128-bit RSA in about four minutes. Explain!
- What does "NP" stand for in "P = NP"?
- Suppose I have a function
ZZ power(ZZ x, ZZ e);

That uses divide and conquer exponentiation. We know that this function only does recursive calls, so I think it should be able to compute`power(123456789,9876543210)`very quickly -- in about steps, which is about 33. Unfortunately, it takes forever. Where's the flaw in my logic? - Would I have to change anything in our RSA implementations if I wanted to encode 8 characters at a time, rather than 3? What would I do differently?
- Are there any problems that are so difficult that they're not even in NP?
- How do you prove that a problem is in NP?
- What do you have to do to prove that a problem is NP Complete?

Algorithm | Best | Worst | Average | technique |

Insertion Sort | ||||

Bubble Sort | ||||

Sequential Search | ||||

Binary Search | depends | Divide & Conquer | ||

D & C Exponentiation | Divide & Conquer | |||

MergeSort | Divide & Conquer | |||

QuickSort | Divide & Conquer | |||

QuickSelect | Divide & Conquer | |||

Matrix Chain Multiplication | Memoization/Dynamic Programming | |||

Longest Common Subsequence | Memoization/Dynamic Programming | |||

Simple Scheduling | Greedy Algorithms | |||

Superincreasing Knapsack | Greedy Algorithms | |||

Huffman Trees | Greedy Algorithms | |||

Prim's Algorithm | Greedy Algorithms | |||

Mulitpop Stack | Amortized Time | |||

Binary Counter | Amortized Time | |||

Extensible Array | Amortized Time | |||

Modular exponentiation | Number Theoretic Algs | |||

Euclidean GCD | Number Theoretic Algs | |||

Extended GCD | Number Theoretic Algs |

- Graph Algorithms -- Breadth-first, Depth-first, Shortest Path, Cycle Detection, Topological Sort.
- Huffman Encoding -- Uses greedy algorithms for tree
construction, DFA's (the tree
*is*a DFA!), expression trees and postfix as the basis for encoding the tree as a sequence of 0's and 1's. - 0/1 Knapsack-based public key cryptosystem
- RSA
- , , and -completeness