Posts tagged with "Algorithms"

• 2025.11.09

  Heuristics for Minimum Euclidean Skeletons

  Disclaimer: This blog post is a rehash of some exploration I did as part of the Mathematics and Statistics Vacation Scholarship program at the University of Melbourne in January 2021. It’s been a while since then, so please forgive any inaccuracies that are almost assuredly present.

  The poster I presented at the conclusion of the program was hosted on the UniMelb website but has suffered the demise of linkrot. I think it’s an interesting problem, though; so I’m reposting my notes here for posterity and as a reminder to myself to revisit this topic and provide a more polished and accurate treatment (with code samples).

• 2025.08.31

  Can a regex match valid card numbers?

  Sometimes the mere existence of a question is dangerous. A colleague recently asked me whether it’s possible to validate credit card numbers in regex using the Luhn algorithm, and, well, I was thoroughly nerd-sniped. I’ll outline the problem briefly and we’ll try to explicate a solution together.

  For what follows, it’ll be helpful if you’ve encountered concepts such as Deterministic Finite Automata (DFA), Regular languages and modular arithmetic before. If you haven’t, I think a quick skim through the Wikipedia pages should be sufficient to follow. I’ll also pair the mathematical formalisms with Python code in the exposition to make it easier to follow.