Computer Science 385
Design and Analysis of Algorithms

Spring 2019, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Academic Celebration Project: [HTML] [PDF]: get your proposals in today, we will discuss throughout the week
  • Problem Set 5: [PDF] due Thursday
  • Exam 2 a week from tomorrow, make arrangements this week if you have a conflict with both Tuesday offerings
  • please bring laptops and textbooks to labs this week
• Summer scholars METAL project: who's interested?
• Knapsack problem dynamic programming example wrapup
• A quick look at Warshall's algorithm (Floyd's is similar, will see in lab)
• Greedy algorithms
  • basic idea
  • Prim's algorithm
  • Kruskal's algorithm (will see in lab)

Terminology

• greedy algorithms
• (minimum) spanning tree
• Prim's algorithm
• Dijkstra's algorithm
• single-source shortest path problem