Author Archives: nolfonzo

Dynamic Programming – basic examples

Posted on March 29, 2020 by nolfonzo

The key idea in Dynamic Programming (DP) is to generate a set of subproblems from a larger problem, and then use recursion or a bottoms up approach to combine the subproblem results to solve the original problem. Recursion lends itself … Continue reading →

Posted in programming | Tagged | 16 Comments

A simple Monte Carlo simulation in Python

Posted on November 13, 2011 by nolfonzo

Monte Carlo is a simulation method that can be useful in solving problems that are difficult to solve analytically. Here’s an interesting application of the technique to estimate the value of pi. Consider a circular dartboard placed against a square … Continue reading →

Posted in programming | Tagged , | 3 Comments

Generating prime numbers using Numpy

Posted on August 27, 2010 by nolfonzo

I’ve been looking at generating primes, and using various element-wise operations in Numpy arrays to do so. To cut the the chase, prime6 below is the fastest implementation. The ones before that tell the story of how I got there. … Continue reading →

Posted in programming | Tagged , , | 12 Comments

Birthday simulations using Python and Numpy

Posted on August 26, 2010 by nolfonzo

I’ve written previously about the probability of finding a shared birthday in a room full of people. I wanted to run some simulations on this using Python. As an aside, you’ll find some of the techniques below bear a similarity … Continue reading →

Posted in programming | Tagged , , , | Leave a comment

Dijkstra Shortest Path using Python

Posted on August 24, 2010 by nolfonzo

This post uses python and Dijkstra’s algorithm to calculate the shortest path given a start node (or vertex), an end node and a graph. The function will return the distance from the start node to the end node, as well … Continue reading →

Posted in programming | Tagged , , , | 7 Comments

Cyclic Linked List – finding the start of the loop using Python

Posted on July 18, 2010 by nolfonzo

I’d blogged previously about writing a python function to find out whether a linked list is cyclic or acyclic – it’s worth a read before tackling this one. The challenge here is to return the node that is at the … Continue reading →

Posted in programming | Tagged , , , | Leave a comment

Anagrams using Python

Posted on June 4, 2010 by nolfonzo

Python can be an elegant language. This is an example – a Python function that finds the anagrams for a supplied word. For the word dictionary I found one in OS X at /usr/share/dict/words.

Posted in programming | Tagged , , | 2 Comments

Birthday pairings

Posted on April 30, 2010 by nolfonzo

Here’s two classic birthday puzzles: How many people do you need in a room to have a better than 50% chance of finding at least one shared birthday among them? How many people do you need in a room with … Continue reading →

Posted in puzzles | Tagged , , , | 1 Comment

A perfect hand, with some combinatorial tricks

Posted on April 29, 2010 by nolfonzo

Question: You deal the first 13 cards from a well shuffled, 52-card deck. What are the chances the 13 cards you deal are of the same suit? There’s a couple of ways to do this – both incorporate useful techniques … Continue reading →

Posted in puzzles | Tagged , | 1 Comment

Puzzle – A safe place to drop an egg

Posted on April 11, 2010 by nolfonzo

This is a problem where it’s fairly easy to find the solution via trial and error, but not so easy to generalize. Question Let’s say you need to find out the highest floor in a 100 story building from which … Continue reading →

Posted in puzzles | Tagged | 1 Comment