Thursday, February 23, 2017

Episode 9 - Solution Bags

Give these problems a try:

This week's episode of Algorithms Live! will cover solution bags. This is less of an algorithm or data structure and instead a different way of thinking of problems involving data structures. You can also view it as a different approach to dynamic programming that naturally yields itself to data structure optimizations.

During the discussion, I'll be going over maintaining an invariant on a data structure and how this can make basic data structures more powerful. My goal will be to change your way of thinking about data structure problems. Instead of guessing of what data structures might be relevant, we will list what our data structure needs to do and design our data structure from there. The data structure will reveal itself naturally from this analysis. I find this technique leads to simpler data structures.

Consider this problem: https://open.kattis.com/problems/whiteboard

Many solvers during this contest used segment trees, but a simple solution using only an ordered set (TreeSet in Java, multiset in C++) also exists. Finding solutions using this type of simple data structure will be easier after learning this way of thinking.

Also during this episode, I will discuss the min queues and their relationship with maintaining an invariant on a data structure. Using this data structure, we will solve the problem of finding the diameter of an almost tree.

See you live! (time, stream, channel)

Other news: This Saturday UCF will compete in this joint north american practice: https://open.kattis.com/contests/naipc17-p02. The practice is open to anyone to join. I'll be competing as UCF Death Valley.

1 comment:

  1. Another problem for practice: http://codeforces.com/contest/797/problem/F

    ReplyDelete