Computer Science 385
Design and Analysis of Algorithms

Spring 2018, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Problem Set 6 late clock starts tonight
  • Problem Set 7: [HTML] [PDF] due Friday
  • Lab 11: Backtracking [PDF] due as usual at the start of your lab this week
  • One more quiz to take place on Friday: a few questions related to Lab 11: Backtracking [PDF]
  • Last lab this week is all pencil and paper
  • Reading day lunch: watch for an email from Dr. Breimer and be there next Tuesday
• About course evaluations
  • they're important!
  • I'll drop everyone's lowest quiz grade if we get 95% or better response rate
• Quick quiz 4 recap
• Limitations of Algorithms
  • lower bounds
    • trivial lower bounds
    • decision trees
    • adversary arguments
    • problem reduction

Terminology

• lower bounds
• tight bounds
• trivial lower bounds
• information-theoretic lower bound
• decision trees
• adversary argument
• problem reduction/transformation