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)
|