Sketchy Polytopes | Sketchy Polytopes

Algorithms

2-butterfly derangement

2-butterfly derangement — The hallmark of the Cooley-Tukey algorithm for Fast Fourier Transform is the butterfly network, which helps reduce $O(n^2)$ computations to $O(n log n)$. Butterflies are

Maximum weighted independent set - connected component

Maximum weighted independent set - connected component — Given a weighted connected component, what is the weight of the maximum independent set, and how many different sets have this weight? A Petersen graph

Maximum weighted independent set - singletons and forest

Maximum weighted independent set - singletons and forest — Gus wants to open franchises of his restaurant, Los Pollos Hermanos, along Central Avenue. There are $n$ possible locations for franchises, where location i is

Rational numbers in decimal

Rational numbers in decimal — In decimal representation, rational numbers either terminate after a finite number of digits or produce a repeating sequence. Conversely, any repeating decimal can be converted

Generalized heaps

Generalized heaps —

Fibonacci Numbers

Fibonacci Numbers — Two notes from Jiřì Matoušek’s book Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra 1, 2.

Congestion control as optimization, 1

Congestion control as optimization, 1 — Why transmission control?

Estimating uniques - sampling with replacement — While exploring ways to estimate multiset union and intersection cardinalities, I discovered an interesting result mentioned in a paper by Shukla [1], who in turn