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.
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!