Computer Science 431
Algorithms

Spring 2013, The College of Saint Rose

Home     Syllabus     Schedule

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

No New Lecture Assignment

Links

• Simpsons Math