Episode 32 - Fracturing Search

It has been several months since I've created an episode of Algorithms Live! but I'm excited to restart the show. I'll be making some changes to the format of the show that I'm hoping some of you will really like. Before I get into all of that I want to share some personal updates and explain what I've been doing the past few months.

Sadly, things did not work out with drive.ai. I enjoyed the experience, met many interesting people, and learned a great many things. Not working while in the bay area is terrifying so I had to dedicate most of my time figuring out how to leave the bay area and setting up my next life steps.

During the last few months, I worked on making videos for Interview Kickstart. This has been interesting because I started to think about how I could change the format of Algorithms Live! so that it is more useful using some of the ideas from making IK videos. One difficulty in running the show is finding a guaranteed quiet place to schedule a live episode. When I originally ran the show, I would run the episodes late at night in my office at UCF. Not having a dedicated quiet office has hurt running the show live. So I've decided to run more polished pre-recorded episodes as an experiment. Let me know what you think of the new format!

So now on to more exciting and fun news. The first is I'll be attending the IOI this year as USA's deputy leader. So if you are attending IOI, please say hi! I'll also be presenting a paper on Tidal Flow this year at the IOI Conference (journal, paper). Tidal Flow is a maximum flow algorithm I invented while training for the ICPC World Finals in 2012. My team wanted an iterative fast flow algorithm that was also easy to implement and understand. The result was the Tidal Flow algorithm. I taught this technique, along with many other fast flow algorithms, while training teams at UCF for many years and the algorithm enjoyed popular usage among our teams. If you decide to read the paper or use the algorithm, I'd be interested to know what you think of it.

Earlier this summer, I helped coach at the USACO training camp. One problem I set during the camp was an enumeration problem. The problem is given a weighted graph, print the cost of the kth smallest spanning tree (where n <= 50, m <= (n choose 2), k <= 10,000). Give this problem a try. Can you get something that runs efficiently on random, fully connected graphs? After the contest I presented the concept of fracturing search as a method for solving this type of enumeration problem. The technique is generally applicable, and many of the USACO finalists found it interesting. The idea is based off Murty's assignment ranking algorithm (paper, altlink). There is even an paper that solve this same problem using the technique (paper). So I've decided to turn this technique and problem into an episode. I hope you enjoy the idea as much as I do.

So here is episode 32 (episode). I'd love to hear thoughts of the episode and the new format. Is this format better? What should be changed? I have many more episodes planned and will be releasing them regularly following this year's IOI.

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)

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:

• Jeff Erickson's treap notes
• Proving depth of a treap
• Randomized Reduction Lemma

See you live! (time, stream)

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 drive.ai 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 drive.ai 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:

• South East USA Regional Contest
• Pacific Northwest Regional Contest

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)

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)

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)

Episode 26 - Fibonacci Machine

This week's episode will cover the solution to an old segment tree problem I enjoy:

• Fibonacci Machine

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)