Lecture 21

Lecture 21: More Graph Algorithms
Date: Friday, April 13, 2018

Agenda

Announcements
- It's high school programming contest day!
  - do your volunteer slot for your 20 bonus problem set points!
  - the alternate method for earning bonus points for those who can't volunteer is also now available: write a method that removes a value and corresponding tests for the binary search tree code from Lab 8, due a week from Monday by demonstration
- Hackathon update: 10 bonus quiz points if you volunteer, 20 bonus quiz points if you participate in at least part of it
- Lab 10: Greedy Algorithms and Heaps [PDF] due at your April 17/18 lab meetings
- Problem Set 6 due Monday
  - however, I will not apply late penalties for a week
  - as the next (and last) problem set will be out Monday, you might still want to keep plugging away to avoid overload next week
- Schedule for last two quizzes:
  - Monday, April 16 (yes, our next class meeting) on a smallish heapsort example and Prim's and Kruskal's algorithms
  - Friday, April 27 on topics TBA
- I will be at a conference on Friday, April 20, so we will not have a class meeting that day
- Looking ahead but surprisingly or perhaps frighteningly not too far ahead, we'll be having our final exam on May 2 at 4:00
More graph algorithms
- reachability
- transitive closure: Warshall's algorithm
- all-sources shortest paths: Floyd's algorithm
If there's time, the gadget testing problem

Terminology