Computer Science 385
Design and Analysis of Algorithms
Spring 2026, Siena University
Lecture 28: Dynamic Programming Wrapup; Greedy Algorithms
Date: Monday, April 13, 2026
Agenda
- Announcements
- Academic Showcase Project keep updating those progress report for each of the coming Fridays
- get your Lab 8: Dynamic Programming checks
- Problem Set 5: [PDF] due Wednesday
- Empirical Study 2: [PDF] due Friday
- Exam 2 quick recap
- Note: heaps and heapsort notes and practice sheet from data
structures in Canvas if you are unsure for the problem set questions
- Hashing Q&A
- Dynamic Programming
- Warshall's algorithm and Floyd's algorithm are covered on the
problem set
- 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
- (minimum) spanning tree
- Prim's algorithm
- Kruskal's algorithm