tag:blogger.com,1999:blog-8890204.post6906682390636826935..comments2024-03-10T05:26:42.148-04:00Comments on My Biased Coin: Teaching SortingMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-8890204.post-65330726933189266712014-09-09T12:53:33.163-04:002014-09-09T12:53:33.163-04:00After explaining about introspection sorting - htt...After explaining about introspection sorting - http://en.wikipedia.org/wiki/Introsort you may want them to explore other hybrid sorts and whther they are useful/practical or not and explain why.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-35118436035926870892014-09-08T23:42:12.090-04:002014-09-08T23:42:12.090-04:00I have started to think that sorting is the most u...I have started to think that sorting is the most useful topic covered in a basic algorithms and data structures course.<br /><br />The traditional topics on such courses - dynamic data structures using pointers in the RAM model - work well when the data structures are not much bigger than the L3 cache. When the amount of data grows, the RAM model and the data structures and algorithms designed for it may no longer be that relevant. With larger datasets, using arrays of tuples as the fundamental data structure, with scanning, sorting, and joins as the basic operations, is often easier and more efficient.Jounihttps://www.blogger.com/profile/08868620962601644633noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-70071622987318541902014-09-08T00:36:42.521-04:002014-09-08T00:36:42.521-04:00Sorting remains valuable for other interesting rea...Sorting remains valuable for other interesting reasons: ask your students why Quicksort is often the preferred sorting method (e.g., in the C/C++ libraries) while it's only O(n log n) in the avg case -- over Heapsort, which is worst-case O(n log n) with small constants... there are some interesting lessons to learn there..Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-18609145002433067612014-09-07T22:47:46.332-04:002014-09-07T22:47:46.332-04:00Student here. The students in my immediate vicinit...Student here. The students in my immediate vicinity were chatting about VEB trees because we'd never seen them before and they were interesting, not because we were hopelessly lost. (On the whole, I for one think your presentation of them was excellent.) The discussion, of course, turned up a few things we realized that we didn't understand, which we were able to clear up after the break.<br /><br />If the structure of [ (1) present interesting novel topic (2) have short break (3) reconvene, and answer any questions that came to light over the break ] wasn't intentional, I would highly suggest trying it again. On Thursday, at least, it worked really well.Anonymousnoreply@blogger.com