Tag Archives: log

Data structure challenge: application

Posted on April 6, 2020 by Brent

I forgot to mention this in my previous post, but the thing which got me thinking about the predecessor problem in the first place was this competitive programming problem on Open Kattis: Profitable Pizzas I challenge you to go and … Continue reading →

Posted in data structures | Tagged , , , , , , , , , , , , , , | Leave a comment

Data structure challenge: solutions

Posted on April 6, 2020 by Brent

In my previous post I challenged you to find a way to keep track of a sequence of slots in such a way that we can quickly (in or better) either mark any empty slot as full, or find the … Continue reading →

Posted in data structures | Tagged , , , , , , , , , , , , | 3 Comments

Data structure challenge: finding the rightmost empty slot

Posted on March 23, 2020 by Brent

Suppose we have a sequence of slots indexed from 1 to . Each slot can be either empty or full, and all start out empty. We want to repeatedly do the following operation: Given an index , find the rightmost … Continue reading →

Posted in data structures | Tagged , , , , , , , | 16 Comments

Test your intuition: logarithmic time

Posted on February 28, 2018 by Brent

Here is a question to test your intuition for logarithms. NO CALCULATORS allowed, and don’t take a long time to work out an answer in your head! Just go with your gut. After you have committed to a choice (say, … Continue reading →

Posted in teaching | Tagged , , , | 16 Comments

Sum of heights in a binary tree

Posted on November 3, 2017 by Brent

Executive summary: every year when teaching data structures I always forget how to analyze the cost of building a binary heap, which amounts to summing the heights of all the nodes in a full binary tree. So I’m writing down … Continue reading →

Posted in math, teaching | Tagged , , , , , , , | 2 Comments