Category Archives: programming

Dynamic Programming – basic examples

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

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

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

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

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

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

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

Mth to last – a recursive approach in Python

A collegue of mine was pondering the mthToLast problem for a LinkedList I’d blogged about previously and sent me the following IM message: just a guess – but can you use recursion to solve your link list m problem? a … Continue reading

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

Reverse a string using recursion in Python

I’ve always found recursion somewhat unnatural to think about, but somehow satisfying when I can see it unfolding in my mind – this simple exercise in reversing a string using recursion is a case in point… >>> def reverse(str): if … Continue reading

Posted in programming | Tagged , , | Leave a comment

Deep copy and recursive references

Quick one about coding a deep copy and avoiding recursive references… Let’s say we have an instance a which has a reference to an instance b and we have to do a deep copy of a. To do this, we … Continue reading

Posted in programming | Tagged , , | 3 Comments