Computer Science 385
Design and Analysis of Algorithms

Spring 2025, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Academic Showcase Project proposals are in, brief progress report due Friday
• Exam 2 update
• Problem Set 5: [PDF] out
• Hashing Q&A
• Dynamic Programming
  • the analysis of the binomial coefficients
  • wrapping up the Knapsack problem approaches (both top-down and bottom-up)
  • Warshall's algorithm and Floyd's algorithm: will study as part of PS 5
• Greedy algorithms
  • general idea: a greedy algorithm's steps must be
    • feasible
    • locally optimal
    • irrevocable

Terminology

• transitive closure
• Warshall's algorithm
• all-pairs shortest paths
• Floyd's algorithm
• greedy algorithms