Friday, December 14, 2018

Episode 34 - Educational Streaming w/ Errichto

This week's episode will feature Errichto and will take place on Sunday, December 16th. If you are interested in viewing the live stream, you can find the link here or view the video after the stream following the same link.
Many of you know Errichto as a prolific problem writer and his recent appearances in TCO, Google Code Jam, Facebook Hacker Cup, and many other programming contest finals. He represented the University of Warsaw in the 2018 ACM ICPC World Finals, where his team placed 14th. This year he started an educational stream for competitive programming that is growing in popularity.
In this episode, we will discuss the benefits of educational streaming in competitive programming and ideas for making competitive programming more popular. Topics will include: how programming contests relate to e-sports, broadcasts for programming competition finals and how they can be improved, and algorithms videos on YouTube and what we would like to see in the future for popularizing the sport. I think this will be a fun podcast style stream. Please ask questions on this post for ideas that you would like to see discussed.
As with all Algorithms Live! episodes, we will be discussing an interesting algorithmic programming challenge. In this episode, we will discuss Errichto's problem Disjoint Triangles. As build up to this problem, we will also be discussing Interstellar Battle from Bubble Cup earlier this year. This is sure to be an exciting episode with many interesting topics and ideas.
See you live!

Friday, November 30, 2018

Episode 33 - Maximum Flow Intuition

During September I attended the IOI as the USA team's deputy leader. The event was lots of fun and I met many new friends, some of which will be future episode guests. While attending I also presented my paper on Tidal Flow, an algorithm I invented while training for ICPC contests. The paper also served as an extensive study on maximum flow algorithms. During testing I implemented many new flow algorithms and decided it would be fun to share some of these algorithms in an extended flow series.

The first episode of this series is now available here. I'll be going over terminology, proofs, algorithms, and patterns as the series expands. There is much to talk about. I'll be interspersing the episodes with some guest episodes I've been planning. Hopefully this variety will keep the episodes exciting for all viewers.

In other news, I've received many requests to start a GitHub repository to store all of the code I write during episodes. Such a repository is now available here.

Sunday, August 19, 2018

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 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.

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)