Example: Searching texts

Internet Search engines solve the problem of searching vast quantities of text for specified keywords (and then the separate problem of ranking these by relevance). Directly searching through billions of webpages on the Internet is not a realistic procedure for a query that needs to finish in microseconds. Instead, search engines employ sophisticated data structures to efficiently access the information.

A key idea behind search indexes is to organise the same collection in different ways depending on how we want to search it. Consider a simpler version of this problem. Suppose we have a collection of songs by different artists, and we want to search either by artist or by song title. If the collection is just a list, with new songs added at the end, both kinds of search will be slow. Grouping songs by artist could make artist searches faster, but it would not help us search by title. Instead, we can create two separate indexes: one in which all songs are ordered alphabetically by artist, and another in which they are ordered by title. Then anyone who knows the alphabet can quickly find a song or an artist using a variant of the binary search algorithm (see Section 1.3).

Example: Travel by train

The railroad is expanding to the new cities! Engineers want to build as little total rail length as possible, but still connect all cities. After the railway is constructed, travellers wants to find the fastest way of getting from city A to city B.

Both these problems can be modelled as graph problems, using a data structure where vertices (cities) are connected by edges (potential railroad tracks or train departures). Specifically, finding the smallest rail network is a minimal spanning tree problem (see Section 12.4) and travel planning is a shortest path problem (see Section 12.3).

Example: Simulating particles

Simulating various physical systems is a common software application. Suppose we are modelling particles that can collide with other particle or with a physical boundary, causing a change of direction and speed, or perhaps randomly splitting the particle in two. For each particle we can calculate when its next collision will occur.

To simulate the progression of this system, we can use a priority queue data structure (see Section 8.2) to store future collisions, and efficiently access them in the order they occur. When we calculate the outcome of a collision, we add new future collisions to the priority queue.

This generalises into any system with timed events where there is a main loop that repeatedly finds the next event and executes it, possibly spawning new future events.