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.