Computer Science 385
Design and Analysis of Algorithms

Spring 2025, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Academic Showcase Project
    • today is the deadline to get your group signed up for our session (see my email of April 2)
    • second progress report due Friday next week
  • Problem Set 5: [PDF] due Wednesday, but the late clock will be suspended during the break (it will start running at 9 AM on Tuesday, April 22)
  • Lab 9: Prim's Algorithm, Dijkstra's Algorithm, Traversals available early for those interested, lab as usual tomorrow if you have not completed by then
  • We will meet for lab the day back from break as usual to do some backtracking
• 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
  • Kruskal's algorithm
  • Dijkstra's algorithm

Terminology

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