1. # From An Iterator of Iterators to Cantor's Paradise: A Deep Dive Into An Interview Question

A deep dive into flattening an iterator of iterators and a segue into set theory and some of its theorems based on the solutions to this problem, inspired by a coding interview question.

Tags:
2. # The Infinite In Haskell and Python

Exploring the use of coroutines and lazy evaluation to generate infinite structures in Haskell and Python.

Tags:
3. # Understanding Recurrence Relations Using Automata, Python Code, And Javascript Visualizations

Recurrence relations are very often taught in first- or second-year computer science and discrete mathematics courses. This post takes a somewhat different and more visual approach to understanding linear recurrences and solving them by drawing the link between linear recurrences, automata, and matrices, using the problem of generating all domino-tilings of a board as the springboard. Code in Python and visualizations in JavaScript are used to demonstrate the ideas.

Tags:
4. # Turing Recognizability of Turing Machines That Accept All Strings

A proof that the set of encodings of Turning machines that accept all strings is not Turing-recognizable.

Tags:
5. # It From Bit - A Brief Exploration Of Some Ideas and Results From The Theory of Computation

A presentation I gave to a group of physics graduate students, as an introduction to some ideas and results in theoretical computer science.

Tags:
6. # Understanding SAT by Implementing a Simple SAT Solver in Python

SAT is often described as the "mother of all NP-complete problems." This post goes over what SAT is and why it is considered to be so important. A simple SAT solver is implemented using Python in the process.

Tags:
7. # So How Do You Actually Calculate The Fibonacci Numbers?

You have seen it as an example a million times. But do you know how to do it efficiently?

Tags:
8. # Combinatorial Generation Using Coroutines With Examples in Python

Approaching combinatorial generation algorithms using coroutines, with examples in Python. Inspired by Knuth's work in his volume 4 of The Art of Computer Programming, as well as his "Deconstructing Coroutines" paper, co-written with Frank Ruskey.

Tags:
9. # Multilinear Representation of Boolean Functions

Algorithm to compute the multilinear representation of a boolean function given its truth table.

Tags:
10. # Line Intersecting Maximal Number of Circles (Circle "Stabbing" Problem)

Developing an algorithm to find a line that intersects a maximal number of circles, given a set of circles. Based on an ACM ICPC regional competition problem.

Tags:
11. # Finding the Tangent Line to Two Circles Demonstrated Using JSXGraph

An HTML5 applet demonstrating step by step how to find tangent lines to two circles, using the JSXGraph framework.

Tags:
12. # Thales Inscribed Angle Theorem Demonstrated Using JSXGraph

An HTML5 applet demonstrating the Thales inscribed angle theorem.

Tags:
13. # Pattern Matching in Fibonacci Words (ACM ICPC World Finals 2012)

A discussion of calculating the number of occurrences of a given pattern in Fibonacci words, with a Java solution. Problem from the 2012 ACM ICPC world finals.

Tags:
14. # Fibonacci Primitive Roots of Primes (Project Euler)

A problem on finding primes with Fibonacci primitive roots, from Project Euler and my Python solution.

Tags:
15. # Basics of Cryptography Part I: RSA Encryption and Decryption

An introduction to RSA cryptography, with accompanying Python code implementing the basic algorithms used. A quick review of the number theory and group theory involved is given as well.

Tags:
16. # Hundred Prisonors and a Room With a Light Switch

A hundred prisoners are given a challenge that might set them free. See if you can solve the puzzle involving a light switch and help them gain their freedom.

Tags:
17. # Interview Question: All Possible Products of a List of Primes

Interview question to list all possible products of a list of primes, with two Python solutions and a short discussion of the problem.

Tags:
18. # Problem-Solving Lessons From George Pólya

What I learned from Newman's selections of Pólya's How to Solve It, the influential and beautifully written book on problem-solving techniques and heuristics.

Tags:
19. # Interview Question: Fair and Unfair Coins and Bayes' Theorem

Interview question to infer the probability of an fair and unfair coins after a certain number of coin tosses using Bayes' theorem.

Tags:
20. # A Study of Python's More Advanced Features Part I: Iterators, Generators, itertools

A study of Python's iterators, generators and the itertools package, with ample (mostly) mathematical examples.

Tags:
21. # Interview Question: Fairness from Unfairness and Randomness Extraction

Interview question to use an unfair coin to simulate a fair one. The question is the same as extracting randomness from an unfair Bernoulli process. A Python implementation is given.

Tags: