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
My Computer Doesn't Listen 