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.
-
-
The Infinite In Haskell and Python
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 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.
-
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.
-
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 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: -
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, co-written 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.
-
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: -
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.