The final exam for this course is scheduled for Monday, May 10, from 8:30 until 11:30 AM. It will be held in our regular classroom. The exam will be five or six pages long, and you will probably not need the entire three-hour exam period to complete it. The exam is cumulative, with emphasis on the material that has been covered since the second test. Questions on earlier material will not require a very detailed knowledge of specific algorithms, data structures, or their implementations. Material covered since the second test includes: the graph algorithms in sections 3 and 4 of Chapter 9; NP algorithms and NP complete problems; Chapter 10 on dynamic programming; and cryptography. You can expect to be asked to apply by hand some of the algorithms that we have covered, such as Kruskal's, Dijkstra's, Niff, and Edit Distance.
The final assignment is due at our final class period, Monday, May 3. Please remember that this is an individual assignment and that you are not permitted to work on or discuss the assignment with other people in the class. If you have not finished the assignment by class time on Monday, turn in what you have. I am reserving the right to ask you to come in during reading period to explain your work to me before you grade it; you won't get any points if you can't demonstrate that you understand the material that you turned in.
Earlier in the term, I agreed that I would accept a revised version of your hash table assignment, which was originally due March 1. That offer is still open. However, at this point, I will not offer any further help on this assignment, and I will only accept your work if you explain it to me during reading week and can answer questions about it.
Important terms and ideas covered since the second test include:
Tree (connected, acyclic, undirected) Spanning tree Making a random maze Minimal spanning tree Kruskal's algorithm UNION/FIND Dijkstra's shortest path algorithm The classes P and NP Decision problem Optimization problem Non-deterministic algorithm When is a decision problem in P? When is a decision problem in NP? The unsolved problem: Is P = NP ? Polynomial reduction NP-complete problem Some NP-hard problems: Hamiltonian cycle problem Traveling salesman problem Vertex cover problem Clique problem Bin packing problem Graph coloring Circuit satisfiability Why is Circuit Satisfiability NP-complete? Approximation algorithms Approximate bin packing (Niff) Approximate graph coloring
Representing sparse graphs and matrices Dynamic programming When is it useful? Relation to recursion Fibonacci numbers Edit Distance Cryptography Plaintext and Ciphertext Secure communications Confidentiality Integrity Authentication Non-repudiation Keys Secret key (or Symmetric key) algorithms Public key (or Asymmetric key) algorithms Public and private keys Confidentiality in a public key system Authentication in a public key system Certificates and certificate authorities Public key infrastructure Secure hash function Session key RSA public key cryptography system Nature of the public and private keys Encryption and decryption functions Computing x^p (mod p)