Wednesday, July 26, 2017

Episode 28 - Sparse Tables and LCA

In this week's episode, I will be discussing the relationship between the lowest common ancestor problem of a rooted tree and range minimum query. Tree traversals can be saved as a sequence and the idea is the foundation behind Euler tour trees. This idea is also how you relate lowest common ancestor queries to range minimum query.

Though segment trees are a nice solution to range minimum query, I'll be coding the sparse table solution, which is closely related to the binary lifting technique. This gives another lens to view this problem through. Sparse table has the added benefits of an O(1) query.

On the personal life side of things, I had some issues where my PhD adviser backed out of moving to the university I was planning to attend this fall. This is what caused the scheduling issue for the episode a few weeks ago. I've decided to go back into industry and am looking for jobs and staying with friends over the next few weeks. What this means for Algorithms Live! is episodes will be at strange times for a bit. I'll try to run at least one episode a week with less notice until my life balances back out. Thank you for being understanding!

See you live! (stream, channel)


  1. please more lecures. There have been no live sessions from past 2 weeks. Hope you will do a live session soon :)

    1. Sorry about that! I've been traveling (couch hopping) and the issue has been finding a quiet place to record the show. My plan is to run the next episode on Thursday. Hopefully I can run multiple episodes the following week.

  2. Hi Matt, I just saw this. We're looking for instructors to teach CS Data Structures and Algorithms. Please let me know if I am able to interest you. I really like your teaching. .