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

Tags:

Understanding Recurrence Relations Using Automata, Python Code, And Javascript Visualizations
Recurrence relations are very often taught in first or secondyear 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 dominotilings of a board as the springboard. Code in Python and visualizations in JavaScript are used to demonstrate the ideas.

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 Turingrecognizable.

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.

Understanding SAT by Implementing a Simple SAT Solver in Python
SAT is often described as the "mother of all NPcomplete 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: 
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: 
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, cowritten with Frank Ruskey.

Multilinear Representation of Boolean Functions
Algorithm to compute the multilinear representation of a boolean function given its truth table.
Tags: 
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.

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.

Thales Inscribed Angle Theorem Demonstrated Using JSXGraph
An HTML5 applet demonstrating the Thales inscribed angle theorem.

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.

Fibonacci Primitive Roots of Primes (Project Euler)
A problem on finding primes with Fibonacci primitive roots, from Project Euler and my Python solution.

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.

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.

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.

ProblemSolving 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 problemsolving techniques and heuristics.
Tags: 
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.

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: 
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.