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.

Since the 12-Week Exam

Number Theoretic Algorithms

Essentially we have three ``number theoretic'' algorithms that we covered:
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 $x^e \mbox{mod} n$?
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 $u$ and $v$ is $g$, then it turns out that there exist two numbers $s$ and $t$ such that $g = su + tv$. The extended GCD algorithm returns not only the gcd $g$, but also $s$ and $t$. 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 ``$\mbox{mod} n$''.

RSA Algorithm

You should know this algorithm!
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, NP, Reduction, NP-Completeness

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 $A$ to problem $B$, 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?

Some Sample Questions

  1. 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!
  2. 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!
  3. 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!
  4. What does "NP" stand for in "P = NP"?
  5. Suppose I have a function
    
    ZZ power(ZZ x, ZZ e);
    
    That uses divide and conquer exponentiation. We know that this function only does $\log e$ recursive calls, so I think it should be able to compute power(123456789,9876543210) very quickly -- in about $\log (9876543210)$ steps, which is about 33. Unfortunately, it takes forever. Where's the flaw in my logic?
  6. 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?
  7. Are there any problems that are so difficult that they're not even in NP?
  8. How do you prove that a problem is in NP?
  9. What do you have to do to prove that a problem is NP Complete?

Before the 12-Week Exam

Asymptotic Analysis

What do $\Theta$, $O$, and $\Omega$ mean? What does it mean when I say, for example, that Quicksort is $\Theta(n^2)$ in the worst case? What's the difference between saying ``Algorithm $A$ is $\Theta(n^2)$ in the worst case'' and saying ``Algorithm $A$ is $O(n^2)$ in the worst case?

Algorithms you should know

Algorithm Best Worst Average technique
Insertion Sort $\Theta(n)$ $\Theta(n^2)$ $\Theta(n^2)$  
Bubble Sort $\Theta(n)$ $\Theta(n^2)$ $\Theta(n^2)$  
Sequential Search $\Theta(1)$ $\Theta(n)$ $\Theta(n)$  
Binary Search depends $\Theta(\mbox{lg} n)$ $\Theta(\mbox{lg} n)$ Divide & Conquer
D & C Exponentiation $\Theta(\mbox{lg} n)$ $\Theta(\mbox{lg} n)$ $\Theta(\mbox{lg} n)$ Divide & Conquer
MergeSort $\Theta(n \mbox{lg} n)$ $\Theta(n \mbox{lg} n)$ $\Theta(n \mbox{lg} n)$ Divide & Conquer
QuickSort $\Theta(n \mbox{lg} n)$ $\Theta(n^2)$ $\Theta(n \mbox{lg} n)$ Divide & Conquer
QuickSelect $\Theta(n)$ $\Theta(n^2)$ $\Theta(n)$ Divide & Conquer
Matrix Chain Multiplication $\Theta(n^3)$ $\Theta(n^3)$ $\Theta(n^3)$ Memoization/Dynamic Programming
Longest Common Subsequence $\Theta(n^3)$ $\Theta(n^3)$ $\Theta(n^3)$ Memoization/Dynamic Programming
Simple Scheduling       Greedy Algorithms
Superincreasing Knapsack       Greedy Algorithms
Huffman Trees       Greedy Algorithms
Prim's Algorithm       Greedy Algorithms
Mulitpop Stack       $\Theta(1)$ Amortized Time
Binary Counter       $\Theta(1)$ Amortized Time
Extensible Array       $\Theta(1)$ Amortized Time
Modular exponentiation       Number Theoretic Algs
Euclidean GCD       Number Theoretic Algs
Extended GCD       Number Theoretic Algs



Christopher W Brown
2001-04-26