Computer Science 385

Design and Analysis of Algorithms

Spring 2024, Siena College

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^{3}*P=NP*

- the

Terminology

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

Links