A lot of toast, with a side-order of roast (2002) [pdf]
www2.math.upenn.edu
www2.math.upenn.edu
As an undergraduate at Swarthmore College, I took an elective in combinatorial algorithms that he had agreed to travel from U Penn to teach. Up to this point I had only experienced harsh lessons that math / computer science was either / or.
He mused early on that choosing k distinct elements from the integers 1 to n must be k log k in complexity, because "sorting" is k log k in complexity. I showed up at around 5pm at his office hours, looking like George Harrison post-Beatles, probably smelling of pot smoke. He was undoubtedly questioning his judgment in agreeing to teach this course, about to face awful traffic to get home. I suggested that one could divide the integers 1 to n into k bins, and sort any way one liked, because the average occupancy would be one. I asserted that this was a linear algorithm. He blew me off, and headed home.
Around 10pm the dorm hall phone rung, with a professor of mine relaying his apologies. I learned a lot from Herb Wilf, rest of the semester, now that I had his attention.
This idea was of course in Knuth (Art of Computer Programming volume ??). I was briefly disillusioned, still believing adults had time to read everything. Hey, Don Knuth had time to write everything?
When, instead of dropping out of grad school, I decided to stay and computerize algebraic geometry, I can thank Herb Wilf for the perspective that took.