Computer Science 385
Analysis of Algorithms
Spring 2011, Siena College
Lecture 27: NP-completeness; Wrapup
Date: Thursday, April 28, 2011
Agenda
- Announcements
- Problem set 7 due Monday at 4 PM
- Come to lunch on Tuesday
- Final exam
- Available Thursday morning 5/5, due back Friday
afternoon 5/6, scheduled slot available for questions
- Ground rules: permitted sources are your own notes,
problem sets, and other assignments, my online lecture pages
and topic notes, our textbook. All other sources are not
allowed. Obviously, you will work alone and may not discuss
the exam with your classmates (or anyone else except me)
until everyone has submitted the exam.
- Typeset and/or handwritten responses OK
- Focus on topics since exam 2
- dynamic programming
- graph algorithms
- Huffman codes
- limitations of algorithms
- Don't forget course evaluations
- Last lecture assignment submission
- Looking at a solution to the shortest path
- Revisit: problem reduction to establish a lower bound
- The Halting Problem
- NP-complete problems
- HOMER3 believes P=NP
Links