Information about the Final Exam

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