Computer Science 385
Design and Analysis of Algorithms
Spring 2018, Siena College
Lecture 24: Tractability
Date: Friday, April 27, 2018
Agenda
- Announcements
- Problem Set 7: [HTML] [PDF] will be accepted without late penalty
through Monday 9 AM, but no late submissions will be eligible for
credit
- Reading day lunch: be there!
- Course evaluations: get to 95% response rate to drop a quiz grade!
- In class on Monday: 5 points of the final exam will be
determined by your responses to a set of departmental assessment
questions - please be on time since we'll probably do them at the
start of class
- Informal talk about METAL/HDX implementation at 2:00 Saturday
afternoon as part of the hackathon - all are welcome
- Final exam details
- Wednesday, May 2, start between 4:00 and 5:30, end no earlier
than 5:30 and no later than about 8:30
- Sarazen Great Room
- 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 a bit more of an emphasis on
topics since Exam 2: backtracking and limitations of algorithm
power
- Reviewing all labs and problem sets would be a good way to prepare
- Also: some practice problems (handout)
- METAL survey
- Limitations of Algorithms
- the P and NP classes
- tractability
- class P
- class NP
- NP-complete problems
- HOMER3 believes P=NP
- 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