Computer Science 431

Algorithms

Spring 2013, The College of Saint Rose

Agenda

- Announcements
- Final exam information
- Monday, May 6, 10:45-1:15, AH 205
- Ground rules: permitted sources are your own notes, problem sets, and other assignments, my online lecture pages and topic notes, our textbook. All other sources are not allowed.
- Focus on topics since exam 2
- hashing
- dynamic programming
- graph algorithms
- Huffman codes
- limitations of algorithms

- Lecture assignment 27 recap
- Limitations of Algorithms
- lower bounds
- trivial lower bounds
- decision trees
- adversary arguments
- problem reduction

- the
*P*and*NP*classes- tractability
- class
*P* - class
*NP* *NP*-complete problems- HOMER
believes^{3}*P=NP*

- lower bounds
- Course evaluations

No New Lecture Assignment

Links