When presenting an algorithm, it can be non-obvious that the algorithm does output the desired result, and also that it does it in the desired runtime. Sometimes it is convenient to present the algorithm at two levels:
-at the correctness level, put in just enough detail to enable the proof of correctness;
-at the runtime level, add just enough data structure and implementation details to enable the proof of runtime.
For example, at the correctness level Prim's algorithm is very similar to Kruskal's algorithm and can be presented using Tarjan's red-blue coloring approach in his green-blue book. At the runtime level Prim's algorithm is very similar to Dijkstra's algorithm (they both use heaps).
Mixing the two levels is frustrating: when proving correctness, one has to deal with low-level details that unnecessarily clutter one's understanding.
I second that this is good approach more often than not! If I have ever seen any algorithm where it makes sense to do both at once, I don't remember it
ReplyDelete