If you're interested in Data Structures classes, I also strongly recommend Keith Schwartz's CS166. Unfortunately there are no public video recordings afaik, but slides and handouts are available, and also of exceptional quality: http://web.stanford.edu/class/archive/cs/cs166/cs166.1196/
That is a nice set of materials, can confirm. I loved the range-minimum-query parts, amongst others.
RMQ is cool because there's a bunch of different approaches, there's different tradeoffs to make (time, memory, implementation effort, pratical and theoretical efficiency, etc.), and some of the results are surprising.
Nice link. I've been learning more about string processing for search via research papers, but began with Suffix Trees. I just started looking at the slides here and looks easily digestible: http://web.stanford.edu/class/archive/cs/cs166/cs166.1196/le...
This is a really interesting class, and Erik Demaine is a top notch lecturer. If you're interested in algorithms I can easily recommend this class.
This isn't intro material though, and most of it is fairly niche in terms of usage. Your average programmer probably won't use any of this knowledge.
The most generally useful bits I remember were on the different types of persistence in data structures, which is legitimately cool and occasionally useful, especially in purely fuctional programming.
I also found the link-cut trees to be about the most interesting data structure I know of, they're cool as hell. You start with a pretty simple DS (splay trees), add some interesting analysis that's also related to heavy-light decomposition, and extend them to do something impressive. It's just a fun mix of analysis and implementation towards a goal. The moment it clicked for me was one of those once-a-year satisfaction events.
If any of that somehow talked you into doing this class, I'd recommend the Intro to Algorithms class also in MIT OCW first, at least one of the years is partially taught by Erik Demaine as well.
I found the hash table lecture really interesting, somewhat practical, and it made me sound really smart when I got the inevitable hash table questions during interviews.
7 comments
[ 2.2 ms ] story [ 27.4 ms ] threadRMQ is cool because there's a bunch of different approaches, there's different tradeoffs to make (time, memory, implementation effort, pratical and theoretical efficiency, etc.), and some of the results are surprising.
This isn't intro material though, and most of it is fairly niche in terms of usage. Your average programmer probably won't use any of this knowledge.
The most generally useful bits I remember were on the different types of persistence in data structures, which is legitimately cool and occasionally useful, especially in purely fuctional programming.
I also found the link-cut trees to be about the most interesting data structure I know of, they're cool as hell. You start with a pretty simple DS (splay trees), add some interesting analysis that's also related to heavy-light decomposition, and extend them to do something impressive. It's just a fun mix of analysis and implementation towards a goal. The moment it clicked for me was one of those once-a-year satisfaction events.
If any of that somehow talked you into doing this class, I'd recommend the Intro to Algorithms class also in MIT OCW first, at least one of the years is partially taught by Erik Demaine as well.