Computer Science 385
Design and Analysis of Algorithms

Spring 2019, Siena College

Home     Syllabus     Schedule

Agenda

• Thank you to our substitute instructor, Dr. Flatland!
• Announcements
  • Problem Set 6: [PDF] continues
  • There will be no new lab next week as you wrap up Problem Set 6: [PDF] and continue work on the Academic Showcase Project: [HTML] [PDF]
  • Lab 10: Greedy Algorithms and Backtracking is not due until your final lab meeting when we get back from Easter break
• 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