Computer Science 431

Algorithms

Spring 2015, The College of Saint Rose

Agenda

- Course evaluations
- Announcements
- Wraup up Problem Set 8: Dijkstra's Road Trip and More [HTML] [PDF] by tomorrow
- Final exam: 1:30-4:00, Tuesday, May 5. Focus on topics
since Exam 2, but a little of everything.
- hashing
- dynamic programming
- graph algorithms
- Huffman codes
- limitations of algorithms (can't ask much...)

- I will be available to go over problems from the last problem set and to answer other questions around 8 PM on Monday, May 4, in AH 205

- Lecture 24 assignment recap
- Lecture 25 assignment 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
- Thank you for a most enjoyable semester!

No New Lecture Assignment

Hey, we're done!

Terminology

- lower bounds
- tight bounds
- trivial lower bounds
- information-theoretic lower bound
- decision trees
- adversary argument
- problem reduction/transformation
- tractable problems
- intractable problems
- undecidability
- halting problem
- Class NP
- NP-complete
- NP-hard
- CNF-satisfiability problem
- independent set problem
- Hamiltonian cycle problem

Links