Episode 5 - Geometric Sweeps

Exciting news! Algorithms Live! is now eligible for a custom URL:
https://www.youtube.com/c/AlgorithmsLive

A special thank you to everyone that subscribed and viewed episodes to make this possible!

This week's episode will feature a special guest, Lewin Gan. Lewin writes problems regularly for Topcoder, Codeforces, and USACO. He is also judge and problem writer for the ICPC contests: NAIPC and Pacific Northwest Regional Contest. He was also an ICPC World Finalist in 2014 competing for University of California, Berkeley.

We will be discussing geometric sweeps. During the discussion, we will cover solutions for two of Lewin's interesting problems and a solution for a problem I set for NAIPC'15. We'll also take a segue into inversive geometry as an alternative method to solving one of his problems.

You can view all of Lewin's Topcoder problems here and Codeforces problems here. I'm sure you will find several of his problems interesting.

Here are the problems we will be discussing and a few more using related techniques:

• Segment Cutting
• Hongcow Draws a Circle
• Area of Effect
• Logging
• Cell Phone

See you live! (time, stream, channel)

Update: Lewin wanted to pass on the discussion of the O(log log P) optimization for the binary search in Hongcow Draws a Circle. You can find that here.

Episode 4 - Segment Trees

By popular request, this week's episode will cover segment trees. This data structure is a bit of a strange one. When I first learned them, the structure was referred to as an interval tree. Academic literature has a very different data structure called interval tree. Later on, I heard the data structure referred to as segment tree, but once again theoretical computer science has a different data structure called segment tree. The Croatian Open Competition in Informatics (COCI) refers to them as a tournament tree, but this name is also a bit misleading. Despite the confusion on the name, this data structure technique is extremely useful and flexible in competitive programming.

I recommend reviewing the merge sort algorithm before viewing this episode as the structure of segment tree closely mirrors the structure of merge sort's recursion. I'll be thorough in both the theoretical and implementation basics of this wonderful data structure.

See you live! (time, stream, channel)

Episode 3 - Rolling Hashes and Bloom Filters

For this week, you should try this problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1370

In Episode 3, I will cover the natural marriage of two ideas: rolling hashes and bloom filters. I'll be covering the idea behind the rolling hash technique, how Rabin-Karp works using this technique, and how the hashes can be stored in a bloom filter. I'll also show how a bloom filter is faster in practice than using the usual hash table when storing string hashes.

See you live! (time, stream, channel)

Episode 2 - Fancy Antiques

Try solving this problem.

This week's episode will feature our first guest, Deon Nicholas. Deon is an ICPC World Finalist from the University of Waterloo placing 13th in 2015. He is also a judge for NAIPC and the author of "Fancy Antiques", the problem we will cover this week.

This problem is particularly interesting to me. Despite being solved by only two teams, it has a remarkably simple solution. Moreover, the analysis of why the solution works, and is efficient, is beautiful. I believe such techniques are not well known given the low solve rate and should make for an interesting discussion. We'll be discussing the problem in detail, techniques for solving the problem more efficiently than the bounds require, and ideas for attacking similar problems. We'll also discuss an alternative solution by another judge from the contest, Lewin Gan.

This is our first week in the talk show format. Over the next few weeks, I hope to have many more guests. If you would like to see someone in particular on the show, please give their name in the comments. :)

See you live! (time, stream, channel)

Edit: For those interested in implementations of the discussed solutions, they can be found on David Van Brackle's judging blog: http://serjudging.vanb.org/?p=924.

Episode 1 - Trees and Diameters

If you haven't seen a lecture from Donald Knuth's lecture series on trees, I suggest watching this video. Every year, at the end of the fall semester at Stanford, Donald Knuth gives a lecture on trees, a sort of Christmas tree lecture series. In honor of this, I've decided to give my own Christmas tree lecture, though my treatment will be much less advanced than Knuth's. Instead, I will focus on the basics.

This week I'll cover some fundamental properties of trees. Some of these properties I will prove during the episode; while others I will leave for you to attempt. I'll present a proof sketch of each property to make each proof easier to digest. I still recommend reviewing proof by contradiction and other useful proof techniques.

One technique covered will be finding the diameter of a tree. There are two well-known techniques for finding diameters. But why do they work? Tune in to find out!

See you live! (time, stream, channel)

Episode 0 - Fenwick Trees

Welcome to Algorithms Live! I'll be hosting a new live talk show on algorithms in competitive programming. Often I find, when competitive programmers get together, the discussions are interesting. These kinds of conversations only seem to happen at training camps or contests themselves. I believe a talk show will be another good place to capture such discussions.

I suppose I should introduce myself. Hello! My name is Matt Fontaine and I'm teaching faculty at the University of Central Florida. I've been involved in programming contests for many years but behind the scenes. Here are a few contributions:

• Judge and problem writer for the North American Invitational Programming Contest (NAIPC)
• An ICPC coach and competitor
• Cow artist for USACO
• Topcoder SRMs

I love teaching algorithms and I hope that some of you will find my talk show interesting and useful.

The first broadcast will take place 9pm EST on December 23rd, but you can find the time in your timezone here. The first two broadcasts will be hosted at this time, but adjustments will be made based on interest and guests. :) The broadcast will take place here as a YouTube live stream and will be available for later viewing. The YouTube channel for the show is available here.

This week I will cover an elegant data structure popular in competitive programming, the Fenwick Tree (also known as a binary indexed tree or BIT). I believe this data structure is a good starting place given both its simplicity and its commonplace in contests. If you want to understand how this data structure works, this episode is for you!

In future weeks I'll be covering a variety of topics. Sometimes I'll review a problem I find interesting or an algorithmic technique useful in contests. I hope to invite guests on future episodes to discuss techniques and problems they find interesting. Please suggest guests you would like to see on the show!