Friday, February 9, 2018

Episode 31 - Orchestra

This week's episode will feature a special guest, Scott Wu. Scott is the top ranked Codeforces member in the US. He helped Harvard earn a gold medal in ICPC World Finals 2016. He also achieved three gold medals at the IOI 2012-2014, achieving a perfect score in 2014.

We will be discussing his problem, Orchestra, from 8VC Venture Cup 2016. We'll be taking a deep dive into this problem and learning several tricks to bringing the runtime down gradually. If you have any questions you would like answered by Scott in the broadcast, please leave them in the comments on this post!

See you live! (time, stream)

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)