CPSC 327, Spring 2004
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
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
    Plaintext and Ciphertext
    Secure communications
    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)