Apr 302018One of the most important and overlooked parts of designing algorithms is choosing the right data types.
We often assume that the types of data an algorithm will use are determined by the inputs and the output — but it might help to use a temporary collection of some data, if that collection has useful operations.
Those operations are determined by the collection’s type.
In this post we’ll look at a couple of examples where using the right data types makes the problem simpler.
Apr 302018Perhaps the most difficult part of our process for writing algorithms is splitting a problem into subproblems.
This is more an art than a science — there’s no systematic way to identify subproblems, and each problem might be split into subproblems in many different ways.(1)
Apr 232018Before attempting these exercises, you should read the posts on points and vectors, simple shapes and polygons.
Apr 232018A polygon is any shape made of straight-line segments.
Polygons are especially important in computer graphics and games, since they’re used in vector image formats and 3D models.
Apr 232018The most primitive geometric objects are points and vectors.
But real geometric problems involve shapes like rectangles, triangles, circles, and polygons — or more complex collections of shapes, such as 3D models made of many polygons.
In this post we’ll consider how computers can represent some simple kinds of shapes, and solve problems using these representations.
Apr 232018Many computing applications deal with geometric or spatial data.
Here are some of the more obvious examples:
Apr 162018Before attempting these exercises, you should read the posts on comparisons and swaps, iterative sorting and recursive sorting.
Apr 162018In the previous post we saw two iterative sorting algorithms: selection sort and insertion sort both work using a loop to put the right values in the right places, one at a time.
They are two of the simplest sorting algorithms.
But they’re not very efficient — for long lists, they’re too slow.(1)
In this post we’ll see one of the simplest efficient sorting algorithms, called merge sort.
Rather than sorting items one-by-one, it works by recursively sorting shorter lists.
Apr 162018Before writing an algorithm, it’s always worth thinking about how you would solve the same problem “by hand”.
After all, you can’t write instructions for how to do something if you don’t know how to do it yourself.
The problem we’re currently interested in is sorting — given a list, put its values in order.
There are hundreds of algorithms which solve this problem, but ultimately every sorting algorithm does one of two things:
Apr 162018We have seen two search algorithms on lists — linear search and binary search.
Both algorithms find the index of a given target value in a list.
But they make different assumptions about the data in the list: linear search works on any list, whereas binary search only works if the list is in order.
