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)
Wednesday, July 26, 2017
Sunday, July 23, 2017
Episode 27 - Topological Sort and Kosaraju's Algorithm
Today is a surprise bonus episode of Algorithms Live! If viewers recall, I missed an episode due to some scheduling problems a few weeks ago. This episode will make up for that.
In this episode, I will cover two techniques that relate well to each other. In the first half of the episode, I will discuss two methods for finding the topological sort of a graph. In the second half, I will cover Kosaraju's algorithm for finding strongly connected components.
See you live! (stream, time)
In this episode, I will cover two techniques that relate well to each other. In the first half of the episode, I will discuss two methods for finding the topological sort of a graph. In the second half, I will cover Kosaraju's algorithm for finding strongly connected components.
See you live! (stream, time)
Friday, July 21, 2017
Episode 26 - Fibonacci Machine
This week's episode will cover the solution to an old segment tree problem I enjoy:
In episode 4, I covered segment trees. This problem requires a segment tree modified for an interesting purpose. I truly love Polish problems and this problem is a nice augmented segment tree problem. I recommend giving it a try before seeing the solution.
Saturday, July 15, 2017
Episode 25 - Desert Wind
One of the viewers, Mikhail Goncharov, has happily contributed time links to an old episode of algorithms live. You can see the links in the description of the knapsack episode. It is now way easier to navigate the episode to find a useful subtopic being discussed. This expanded description also gives a nice outline so you get an overview of an old episode. Thank you so much! If anyone else would like to contribute similar time links, just send me an overview of the episode in this form (either PM through Codeforces or YouTube):
00:00 Introduction
03:23 Technique 1
5:31 Problem Name
13:21 Technique 2
14:30 Coding
I really appreciate this type of contribution. If you can contribute to even one episode, please do!
In this week's episode, I will be discussing an old problem that I find interesting, Desert Wind. You can the problem statement here:
The episode should be a bit shorter than usual but I hope you will all still enjoy it. I should be done right before the start of this week's Codeforces Educational Round.
00:00 Introduction
03:23 Technique 1
5:31 Problem Name
13:21 Technique 2
14:30 Coding
I really appreciate this type of contribution. If you can contribute to even one episode, please do!
In this week's episode, I will be discussing an old problem that I find interesting, Desert Wind. You can the problem statement here:
The episode should be a bit shorter than usual but I hope you will all still enjoy it. I should be done right before the start of this week's Codeforces Educational Round.
Friday, July 7, 2017
Episode 24 - 2SAT
Sadly, due to some personal matters, I had trouble scheduling a time for last week's episode. So I'll be running that episode tonight. I'll make a surprise bonus episode sometime in the future to make up for it.
This week's episode will cover 2SAT (2-satisfiability). You can attempt these problems:
This topic is a bit tricky to explain depending on your background and knowledge base. To make things a bit easier, I'll be using concepts taught in the first chapter of Rosen's Discrete Mathematics. I'll be aligning with the notation and assume some basic familiarity with propositional logic and deductions.
This week's episode will cover 2SAT (2-satisfiability). You can attempt these problems:
This topic is a bit tricky to explain depending on your background and knowledge base. To make things a bit easier, I'll be using concepts taught in the first chapter of Rosen's Discrete Mathematics. I'll be aligning with the notation and assume some basic familiarity with propositional logic and deductions.
Subscribe to:
Posts (Atom)