Get the latest tech news

Algorithms for the 21st Century (2006)

The algorithms taught to computer science students haven't changed all that much in the last several decades, but the machines that these algorithms run on have changed a great deal. Each of these algorithms is analyzed and justified based on a model of the machine running the algorithm.

I hope to awaken a doubt in you that such traditional techniques as linked lists, structures, binary trees, and "divide and conquer" algorithms are always good for large problems on today's machines. Here are the results for the AMD 64-bit machine, with the programs compiled unoptimized: Note that using unit stride with separate arrays is significanly faster than the structure cases, by tens of percents. History shows that computing systems are often designed by engineers more motivated by cost, chip and board area, cooling, and other considerations than programmability.

Get the Android app