# Monthly Archives: October 2013

## Turn taking in human-computer dialogue

Turn-taking has had a brief moment in the press recently with the news that marmosets ‘take turns in conversation’. A blog post on the topic at National Geographic led me to a 2009 paper which examined turn-taking behaviour across 10 different … Continue reading

## The Knapsack Problem and Dynamic Programming

The knapsack problem is a key one in computer science, and has received a lot of attention over the years. The goal is to best fill a bag of capacity Mkg with items {1..N} that each have a weight and … Continue reading

## Dynamic programming for alignment

Dynamic programming is a technique that breaks a larger problem down into smaller sub-problems, solves those and caches the answers. In this way, solving the larger problem is more computationally efficient than a naive brute-force approach which tries all possible … Continue reading

## Graphs

A graph is a fundamental data structure that’s really useful for lots of different applications. It is a set of nodes with edges joining them; the edges may be directed or undirected. Examples of directed graphs are transport networks (e.g. … Continue reading

## Computational complexity and polynomial time

A key concept in computer science is computational complexity. That is, how the time taken to run an algorithm changes with the size of the input. Sorting a 100-dimensional array is obviously faster than sorting a 1,000,000-dimensional array, but how … Continue reading

## Divide-and-conquer sorting algorithms

Previously, I wrote about the simple sorting algorithms which have a computational complexity of O(n2). Better sort algorithms exist, and the particular class of divide-and-conquer algorithms are interesting in this era of big data as they lend themselves well to … Continue reading

## Simple sorting algorithms

If, like me, you studied some computer science at university, you were once intimately familiar with a number of sorting algorithms. But now the exact details are a bit fuzzy, and all that remains of that knowledge is a voice … Continue reading