Category Archives: Algorithms

Generating a random variable by coin tossing


1. Coin tossing Suppose we are given a sequence of independent fair bits (meaning take and with probabily ) we want to produce with them a discrete random variable that takes the values with probabilities . The objective, of course, … Continue reading

Posted in Algorithms, Number Theory, Probability | Leave a comment

Higher order Newton-Raphson


In this post we shall see one way to look at the Newton–Raphson formula, and the extensions this produces. Actually, I came up with this idea a few years back, while I was studying for a Numerical Analysis exam. Introduction. … Continue reading

Posted in Algorithms, Computation | Tagged , | Leave a comment

Looking for the largest palindrome


Exercise 1 Let a string of characters be given, find the length of the largest palindrome contained in it. Let us start with the naive way of doing it, what would that be? Well, for each position, and possible length, … Continue reading

Posted in Algorithms | Leave a comment

Computing Pi


I have been a bit busy lately, but here is a rather interesting idea I thought some months ago: Suppose we wanted to approximate with rational numbers, how would you proceed? Of course, one way to go would be to … Continue reading

Posted in Algorithms, Computation | Leave a comment

Graph Colouring


This post will be dedicated to graph-colouring, inspired by a recent problem from TopCoder ( SRM 484 DIV2 problem 3). A proper colouring of a labeled graph is a function   , where is the set of colours, such that … Continue reading

Posted in Algorithms, Combinatorics, Graph Theory | Leave a comment