Computer Science 385
Design and Analysis of Algorithms

Spring 2024, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • One more Academic Showcase Project: [HTML] [PDF] progress update today
  • If your group hasn't registered for our Academic Showcase Project: [HTML] [PDF] session, please do so now (yes, now)
  • Problem Set 7: [PDF] due Wednesday
  • Lab 10: Backtracking wrap up before the next lab (note fix in the IsLegal pseudocode
• Lab 10: Backtracking Question 18 discussion
• Problem Set 6: [PDF] quick recap (delay to Monday)
• Limitations of Algorithms
  • lower bounds
    • trivial lower bounds
    • decision trees
    • adversary arguments
    • problem reduction
• Quiz 3 redo

Terminology

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