Gee, I saw quicksort but not heap sort! Heap sort is O( n log(n) ) in all cases including worst, and quicksort is O( n^2 ) worst case. O( n log(n) ) is the Gle

Gee, I saw quicksort but not heap sort! Heap sort is O( n log(n) ) in all cases including worst, and quicksort is O( n^2 ) worst case. O( n log(n) ) is the Gleason bound, the fastest sort there can be on average from comparing pairs of keys so that in that sense heap sort is asymptotically the fastest possible. Dropping the technique of comparing pairs lets us consider radix sort which can be faster, still. The lecture does cover merge sort; good. For graphs, the min cost network flow problem is linear programming, and it turns out that if the arc capacities are integers and start with a basic integer feasible solution, then the simplex algorithm maintains integer solutions and, if merely an optimal solution exists, will find an optimal integer solution. It turns out that this fact is in practice one of the best tools for linear integer programming which generally is in NP-complete. This progress on integer programming is worth noting. For cycling in the simplex algorithm for the min cost flow problem on networks, W. Cunningham, long at Waterloo, has a nice solution based on what he calls strongly feasible basic solutions. For the simplex algorithm for the network flow problem, there are, compared with the simplex algorithm in general, some enormous simplifications -- e.g,. a feasible basis corresponds to a spanning tree of arcs -- and, thus, astoundingly high performance on astoundingly large problems -- this fact should be noted. Maybe I missed it, but I didn't see trees mentioned. Both AVL trees and red-black trees are good examples, that is, balanced binary trees good for collection classes. And B-trees, multi-way branched balanced trees, long important on hard disk (and likely now on solid state disks) for database should also be mentioned. Since need to teach heap sort, should also mention that the heap data structure is good for an easy implementation of fast priority queues, e.g., look at 1 billion numbers one at a time, in any order, and end up with the 100 largest, efficiently. Also there is a modification of the heap data structure that has good locality of reference when doing a lot of virtual memory paging. And for hashing, the clean solution is Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong, Extendible hashing-a fast access method for dynamic files', "ACM Transactions on Database Systems", ISSN 0362-5915, Volume 4, Issue 3, September 1979, Pages: 315 - 344. I'm not thrilled with recursion since in practice it can strain implementations of the call stack. Course over. Hope you enjoyed it!