Computer Science 385

Design and Analysis of Algorithms

Spring 2019, Siena College

Agenda

- Announcements
- Reminder: everyone gets 15 quiz bonus points if we get 95% or better response rate on course evaluations - do them today!!
- Academic Showcase Project: [HTML] [PDF] code submissions and final writeups due this afternoon by commiting and pushing to GitHub
- Get any remaining Lab 11: Limitations of Algorithm Power submissions to me today

- Final exam reminders
- Wednesday, May 1, 8:30-10:30 AM, RB 202, but I will plan to be there early for anyone who wants to start and have some extra time
- You will be provided with all needed summation and log formulas, and you will be permitted up to three double-sided sheets of handwritten notes as a reference
- Exam is cumulative but there is more of an emphasis on topics since Exam 2: backtracking and limitations of algorithm power
- Reviewing all labs and problem sets and checking out the practice questions would be a good way to prepare
- Review times: this afternoon and tomorrow afternoon, 4-5 PM, locations TBD

- Limitations of Algorithms
- the
*P*and*NP*classes- tractability
- class
*P* - class
*NP* *NP*-complete problems- HOMER
believes^{3}*P=NP*

- the
- Quiz 5

Terminology

- 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
- Homer 3D (see 2:00 or so)