Saturday, January 20, 2018

Episode 30 - Treaps

This week's episode will cover the treaps. The main advantage of treaps is an easy to implement binary search tree data structure. I'll be discussing why I think they are a useful data structure and a handful of useful tricks that make them more powerful than segment trees.

Here are some useful notes for learning more about treaps:

See you live! (timestream)

Friday, December 15, 2017

Episode 29 - Rainbow Roads

I'm happy to announce Algorithms Live! will be returning tomorrow! I'm sorry to have been away for so long. With the amount of travel, reading and preparations for some research ideas, working on ICPC contests, and wanting to focus on my job search, it was difficult to reliably schedule episodes. Plans for the future of this show are exciting. I used some of this time to map out where I wanted these episodes to go. A few of the episodes are based on your requests.

So now for big changes! I recently started a new job at working as a simulation engineer. For those that don't know, my research background is in simulation and training in virtual environments. I'm happy to be applying some of this knowledge to self-driving cars and happy that is supportive of me continuing to run Algorithms Live!

The other piece of exciting news is I moved to California. I've finally met Lewin in person and hopefully will meet many other competitive programmers in the bay area and have them on the show. :)

Being in California allowed me to finally attend one of Donald Knuth's Christmas lectures in person. Many of you will remember my Christmas tree lecture from last year. This year was a bit different. Donald gave an exploratory lecture where he demonstrated the excitement of diving deep down rabbit holes while doing research and some combinatorial geometry. It was exciting and humorous but oddly enough, the lecture was not about trees!

I'm going to rectify this dilemma, as it wouldn't be Christmas without talking about one of my favorite classes of graphs. This week's episode will once again feature Lewin Gan. We will discuss his ACM ICPC problem "Rainbow Roads" that was used in several regions in the US. You can try the problem by solving one of the following regionals in Codeforces gym:
This will be my last episode of 2017 to ease back into things. I'll be going on holiday break this week, but will start running regular weekly episodes at the start of 2018. I've missed running this show and hope that many of you will like the future episodes to come!

See you live! (stream, time)

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)