htiek
Re:The LCA problem revisited [pdf]
on Monday March 23, 2026 @09:41AM (#47489424)
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.
Chegg Integrates ChatGPT4
Parts of Twitter source leaked online
Re:Buttons as Finite Automata
on Thursday March 24, 2022 @10:42AM (#30790531)
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. :-)
A Mathematical Foundation for Foundation Paper Pieceable Quilts
Mining Magnets: Arctic island finds green power can be a curse
Re:Let’s Invent B(+)-Trees
on Tuesday April 28, 2020 @12:39AM (#23003434)
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
Levandowski agrees to plea deal over Google secrets
Sometimes, data are avocados. Sometimes, data is wine
Re:Topics in Advanced Data Structures [pdf]
on Monday April 29, 2019 @02:30PM (#19781145)
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.