Computer Science 431
Algorithms

Spring 2015, The College of Saint Rose

Home     Syllabus     Schedule

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 P=NP
• 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

• Simpsons Math