Computer Science 385
Design and Analysis of Algorithms

Spring 2024, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Problem Set 8: [PDF] due this afternoon, firm 4 PM deadline
  • Please come by to get any other missing labs taken care of
  • Reminder and update about course eval bonus opportunity
  • Join us for a CS lunch tomorrow at noon - RSVP form in the email from Dr. Lim
• Limitations of Algorithms
  • the P and NP classes
    • tractability
    • class P
    • class NP
    • NP-complete problems
    • HOMER³ believes P=NP

Terminology

• tractable problems
• intractable problems
• undecidability
• halting problem
• Class NP
• NP-complete
• NP-hard
• CNF-satisfiability problem
• independent set problem
• Hamiltonian cycle problem

Links

• P vs. NP - The Biggest Unsolved Problem in Computer Science
• Simpsons Math
• Homer 3D (see 2:00 or so)