1. ## A Review of Basic Algorithms and Data Structures in Python - Part 1: Graph Algorithms

A quick review of basic graph algorithms and related data structures, with minimal implementations and unit tests provided in Python.

Tagged as
2. ## Fun With Python Coroutines: Generating Permutations

A very short post on having fun with coroutines to generate all permutations of a given list.

Tagged as
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.

Tagged as
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.

Tagged as
5. ## 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.

Tagged as
6. ## Multilinear Representation of Boolean Functions

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

Tagged as
7. ## 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.

Tagged as
8. ## Expected Running Time of Two Randomized Sort Algorithms (ACM ICPC 2013 PACNW Regional)

Computing the expected running time of two randomized sort algorithms for a given input array. This problem appeared in ACM ICPC 2013 PACNW regional competition.

Tagged as
9. ## 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.

Tagged as
10. ## Fibonacci Primitve Roots of Primes (Project Euler)

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

Tagged as
11. ## Common Substring Permutation

Short post on a simple problem on common subsequence permutations with a neat one-line Python solution.

Tagged as
12. ## 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.

Tagged as
13. ## 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.

Tagged as
14. ## Interview Question: Fair and Unfair Coins and Bayes' Theorem (Groupon)

Groupon interview question to infer the probability of an event using Bayes' theorem.

Tagged as
15. ## Interview Question: Fairness from Unfairness (Groupon)

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

Tagged as