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!