Computer Science 385
Design and Analysis of Algorithms

Spring 2017, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Please bring laptops to lab tomorrow
• Review problems out
• Limitations of Algorithms
  • lower bounds
    • trivial lower bounds
    • adversary arguments
    • problem reduction
  • the P and NP classes
    • tractability
    • class P
    • class NP
    • NP-complete problems