htiek
Joined 9 years ago
Karma
800
Submissions
30
Member since
Jul 11
Recent submissions
Comment · 7 months ago
The range minimum query problem (RMQ) used to solve LCA is a really fun one. I spend two lectures on it in my advanced data structures course. The approach covered in the slides linked here is perhaps the best-known way to solve LCA via RMQ, but I personally prefer one developed by Fischer and Heun in 2006. Check the first two lectures of my course (https://web.stanford.edu/class/archive/cs/cs166/cs166.1256/) for details.
Comment · 4 years ago
This is something I created many, many years back for Stanford’s CS103 course as a lecture demo. Apologies for the lack of mobile support - I’ve always presented this from my laptop. :-)
Comment · 6 years ago
I like this approach to describing B-trees! I recently taught B-trees for a data structures course and presented them using a similar method. Thought I'd leave the link in case it was useful: http://web.stanford.edu/class/cs166/lectures/05/Slides05.pdf
Comment · 7 years ago
You can use lowest common ancestor queries in conjunction with suffix trees to solve a lot of interesting string problems. For example, take two indices within a string, find their corresponding suffixes in the suffix tree, and then take their LCA. That gives you an internal node corresponding to the longest string that appears starting at both indices (this is called their "longest common extension.") You can use this as a subroutine in a bunch of genomics applications.