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)

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! (streamtime)

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.

See you live! (stream, time)

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.

See you live! (time, stream)

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.

The goals of this episode are to demonstrate how to make 2SAT problems easier to implement, pull the answer out, find the lexicographically first answer, and discuss the problem's relationship to strongly connected components.

See you live! (time, stream)

Thursday, June 22, 2017

Episode 23 - Strongly Connected Components

This week's episode will expand upon the technique involving low links to directed graphs. The result is Tarjan's strongly connected components algorithm. I'll be addressing how to extract these components and some additional helpful properties that are implicit to the algorithm.

Here are a few problems you can try solving involving SCC's:
See you live! (time, stream)

Friday, June 16, 2017

Episode 22 - Biconnected Decompositions

In this week's episode I will be discussing the types of meta-graphs that can be formed from 2-edge-connected and 2-vertex-connected components.

Here are a few problems that are relevant to this technique:

I will only be discussing a subset of these problems. You may find the others useful to solve on your own to practice this technique.

See you live! (time, stream)