1921
Topics /
Math & Algorithms
The most popular blog posts about math & algorithms on Hacker News. 2,394 posts.
1922
Probably Approximately Correct – A Formal Theory of Learning (2014)
In tackling machine learning (and computer science in general) we face some deep philosophical questions. Questions like, “What does it mean to learn?” and, “Can a computer learn?” and, “How do you define simplicity?” and, “Why does Occam’s Razor work? (Why do simple hypotheses do well at modelling reality?)” In a…
1923
Prospecting for Hash Functions
Update 2022 : TheIronBorn has found even better permutations using a smarter technique. That thread completely eclipses my efforts in this article.
1924
The Fast Fourier Transform
It’s often said that the Age of Information began on August 17, 1964 with the publication of Cooley and Tukey’s paper, “An Algorithm for the Machine Calculation of Complex Fourier…
1925
Visualizing dynamic programming
I’ve always thought dynamic programming was a pretty crummy name for the practice of storing sub-calculations to be used later. Why not call it table-filling algorithms , because indeed, thinking of a dynamic programming algorithm as one that fills in a table is a quite good way of thinking about it.
1926
1927
Rotating Quine
My Quines are sometimes specialized for Japanese. But to attend RubyConf, I should write "global" Quines. v=0000;eval$s=%q~d=%!^Lcf<LK8, ...
1928
Graph Theory Applications in Video Games
A detailed look at Graph Theory and how it can be applied to video games.
1929
On the Computational Complexity of MapReduce
I recently wrapped up a fun paper with my coauthors Ben Fish, Adam Lelkes, Lev Reyzin, and Gyorgy Turan in which we analyzed the computational complexity of a model of the popular MapReduce framework. Check out the preprint on the arXiv. Update: this paper is now published in the proceedings of DISC2015. As usual I’ll…
1930
1931
How to Teach Math?
The only way to learn mathematics is to do mathematics—Paul Halmos Angie Hodge is an Associate Professor of mathematics at Northern Arizona University. Her interests as stated on her website …
1932
Why 'gallons per mile' is better than 'miles per gallon'
Why we should really be quoting fuel consumption figures as 'gallons per mile' and not 'miles per gallon'.
1933
Milton Friedman’s Interest Rate Fallacy
Milton Friedman’s interest rate fallacy is one of the most mystifying and counterintuitive facts in modern finance.
1934
NP-complete isn't always hard
A common assumption I see on the ‘net is that NP-complete problems are impossible to solve. I recently read that dependency management in Python is hard because package resolution is NP-complete. This is true in principle, but the reality is more complicated. When we say “NP-complete is hard” we’re talking about…
1935
1936
Make a "Magic Eye" image using Excel
I’ve been on a weird kick lately making images using Excel. [Here’s one post. I hope to post more soon.] If you add a background color to each cell in a spreadsheet and resize the cell …
1937
Entropy in the Universe
If you click on this picture, you’ll see a zoomable image of the Milky Way with 84 million stars: But stars contribute only a tiny fraction of the total entropy in the observable Universe. If…
1938
Solving “Two Sum” in C with a tiny hash table
I came across a question: How does one efficiently solve Two Sum in C? There’s a naive quadratic time solution, but also an amortized linear time solution using a hash table. Without a built-in or standard library hash table, the latter sounds onerous. However, a mask-step-index table , a hash table construction…
1939
Traveling Salesman: the most misunderstood problem
Whenever people start talking about NP-Complete problems, or even NP problems, one of the first examples they reach for is the classic Traveling Salesperson Problem. TSP makes sense because it int...
1940
PID Controller: A Simple Control Loop Mechanism
A mid-depth cap with classic style for any occasion, this Nike Club Cap comes in smooth cotton twill that's been softly washed for casual, daily comfort. Soft and unstructured, the precurved bill makes for easy styling, and the adjustable back-strap lets you find the right fit. Nike Hat Size 6 1/2 6 5/8 6 3/4 6 7/8 7…
1941
1942
Turing Machines
An interactive introduction to Turing machines, the theoretical foundation of modern computing.
1943
How to Be Wrong (2016)
“To be wrong, or not to be wrong?” That is the wrong question. You are going to spend a lot of your time being wrong, especially if you become a scientist or mathematician. The question…
1944
The Median-of-Medians Algorithm
In this post, we consider the problem of selecting the \(i\)-th smallest element from an unsorted list of \(n\) elements. Somewhat surprisingly, there is an algorithm that solves this problem in linea
1945
Linear Algebra of Types (2019)
It gives my brain a pleasant thrum to learn new mathematics which mimics the algebra I learned in middle school. Basically this means that the new system has operations with properties that match those of regular numbers as much as possible. Two pretty important operations are addition and multiplication with the…
1946
Kolmogorov Complicity and the Parable of Lightning (2017)
A good scientist, in other words, does not merely ignore conventional wisdom, but makes a special effort to break it. Scientists go looking for trouble. — Paul Graham, What You Can’t Sa…
1947
1948
Correlation is usually not causation. But why not?
Correlations are oft interpreted as evidence for causation; this is oft falsified; do causal graphs explain why this is so common, because the number of possible indirect paths greatly exceeds the direct paths necessary for useful manipulation?
1949
Ten Ways to Check if an Integer Is a Power Of Two in C
To write a program to check if an integer is a power of two, you could follow two basic strategies: check the number based on its decimal value, or check it based on its binary representation. The former approach is more human-friendly but generally less efficient; the latter approach is more machine-friendly but…
1950
A fast alternative to the modulo reduction (2016)
Suppose you want to pick an integer at random in a set of N elements. Your computer has functions to generate random 32-bit integers, how do you transform such numbers into indexes no larger than N? Suppose you have a hash table with a capacity N. Again, you need to transform your hash values (typically 32-bit ……