Computer Science 385
Analysis of Algorithms

Spring 2011, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Problem set 6 late clock started at 9 AM
  • Final exam: available Thursday morning of exam week, due back Friday afternoon, scheduled slot available for questions
  • Don't forget course evaluations
• Lecture assignment recap
• Problem set 7 out
• Limitations of Algorithms
  • lower bounds
    • trivial lower bounds
    • decisions trees
    • adversary arguments
    • problem reduction
  • the P and NP classes
    • tractability
    • class P
    • class NP
    • NP-complete problems

Lecture Assignment 26

Due at the start of class, Thursday, April 28.

Please submit answers to these questions either as a hard copy (typeset or handwritten are OK) or by email to jteresco AT siena.edu by the start of class. Please use a clear subject line when submitting by email (e.g., CS 385 Lecture Assignment 26, Joe Student). We will discuss these questions at the start of class, so no late submissions are accepted.

1. Read section 10.4 and the notes on Iterative Improvement, then answer Levitin Exercise 10.4.4, p. 375.