Author Archives: Brent

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Data structure challenge: application

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

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

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 , , , , , , , | 15 Comments

Competitive Programming in Haskell: modular arithmetic, part 2

In my last post I wrote about modular exponentiation and egcd. In this post, I consider the problem of solving modular equivalences, building on code from the previous post. Solving linear congruences A linear congruence is a modular equivalence of … Continue reading

Posted in haskell | Tagged , , , , | 4 Comments

What would Dijkstra do? Proving the associativity of min

This semester I’m teaching a Discrete Mathematics course. Recently, I assigned them a homework problem from the textbook that asked them to prove that the binary operator on the real numbers is associative, that is, for all real numbers , … Continue reading

Posted in math | Tagged , , , , , , | 16 Comments

Competitive Programming in Haskell: modular arithmetic, part 1

Modular arithmetic comes up a lot in computer science, and so it’s no surprise that it is featured, either explicitly or implicitly, in many competitive programming problems. As a brief aside, to be good at competitive programming it’s not enough … Continue reading

Posted in haskell | Tagged , , , , | 6 Comments

Unexpected benefits of version control

Last night I dreamed that I had shaved off my mustache, and my wife was not happy about it. But in the dream, I couldn’t remember when or why I had shaved. Suddenly, it occurred to me: when I merged … Continue reading

Posted in humor | Tagged , , , | 1 Comment

Competitive Programming in Haskell: primes and factoring

Number theory is a topic that comes up fairly regularly in competitive programming, and it’s a very nice fit for Haskell. I’ve developed a bunch of code over the years that regularly comes in handy. None of this is particularly … Continue reading

Posted in haskell | Tagged , , , , | 5 Comments

Counting inversions via rank queries

In a post from about a year ago, I explained an algorithm for counting the number of inversions of a sequence in time. As a reminder, given a sequence , an inversion is a pair of positions such that and … Continue reading

Posted in haskell | Tagged , , , , , , , , , | 4 Comments

Computing Eulerian paths is harder than you think

Everyone who has studied any graph theory at all knows the celebrated story of the Seven Bridges of Königsberg, and how Euler gave birth to modern graph theory while solving the problem. Euler’s proof is clever, incisive, not hard to … Continue reading

Posted in learning | Tagged , , , , | 5 Comments