Computer Science 385
Design and Analysis of Algorithms

Spring 2024, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Please do your next Academic Showcase Project: [HTML] [PDF] progress update by this afternoon
  • grading update
  • Reminder: no class Monday for eclipse day - get in the shadow! You might use the time to work on the new problem sets.
  • Lab 8: Dynamic Programming: finish up by lab next week
  • Problem Set 6: [PDF] due in one week
  • Problem Set 7: [PDF] not due until 4/24
• Quiz 3
• RB is clearly earthquake proof
• Wrapping up the Dynamic Programming approaches to the Knapsack Problem
• Greedy Algorithms
  • general idea: a greedy algorithm's steps must be
    • feasible
    • locally optimal
    • irrevocable
  • making change (or stamp totals, or chicken nugget totals)
  • The Muddy City
  • Prim's algorithm

Terminology

• greedy algorithms
• (minimum) spanning tree
• Prim's algorithm