DSABook – Motivation and core concepts

1.1 Motivation and core concepts

How many cities with more than 100,000 people lie within 200 kilometres of Paris, France? How many people in Swedish towns with less than 50,000 people earn less than 50% of the average income of people in Sweden? How much more CO₂ will be emitted if I travel by plane from Gothenburg, Sweden, to Düsseldorf, Germany, compared to if I take the train? How can I see if a text contains plagiarism, that is, if it copied some parts from another existing text?

Gathering the necessary information is not sufficient to answer questions like these, the information must be organised to allow efficient access and analysis. To organise our data we use different data structures, and to update or analyse our data we use algorithms on these data structures. The subjects of data structures and algorithms are deeply intertwined: Efficient data structures are used when designing and implementing algorithms, and algorithms are used to design efficient data structures.

A university course on data structures and algorithms is essential to anyone who intends to do any substantial programming in their line of work. Often, choosing the right data structure for a task is half the battle of solving it, and conversely using the wrong data structure is an easy way to end up with an inefficient or error-prone mess. Hopefully, by the time you have read this book you can look back at your earlier solutions to programming exercises and realise how much you can improve them by using a set instead of a list, or a priority queue instead of a sorted array.

Apart from using the right data structure for the job, analysing an algorithm is another essential skill. If two algorithms solve the same problem, which one is better? Will the performance of your program scale to thousands of users? Which part of a piece of code is going to use all the processing power (and is thus the only part worth optimising)?

Suppose you have an algorithm for finding someone in a list of names. Let us say that it is very fast when searching among 1000 names, for example your social media friends. Can you use the same algorithm to search among all 10 million people living in Sweden? That problem is 10,000 times larger, is it still feasible to do it using your old laptop or do you need a supercomputer? These questions can be answered by algorithm analysis, and it is not certain that it takes 10,000 times longer to solve a 10,000 times larger problem – it depends on the algorithm. (The specific example of searching in a list is discussed in more detail in Section 1.3.)

The subjects in this book fall into one of four categories:

Data structures: A data structure describes how we can organise our data so that it can be retrieved and updated efficiently. We explain the fundamental ideas of various data structures, and present the most common implementations. Examples of data structures that you may be familiar with are arrays, linked lists, search trees and hash tables.
Abstract data types: An abstract data type (ADT) describes the capabilities of a data structure. In other words, what operations can we use on a given data structure? Are there different data structures that have the same capabilities? We use ADTs to categorise the different use cases. Examples of ADTs include lists, queues, sets and maps. Slightly simplified using programming terms: An ADT is an interface, and a data structure is the full implementation with all the technical details.
Algorithms: An algorithm is a process for solving a specific problem, taking an input and producing a correct output. This can include operations on data structures, such as querying, iterating or updating them. We describe algorithms using natural language, explain how to analyze them, and how to implement them as programs.
Analysis: The main purpose of analysing data structures and algorithms is to know how efficient they are. We focus on theoretical algorithm analysis, and in particular asymptotic complexity analysis, where we mathematically can derive how an algorithm behaves when the size of the input grows.

We also show how to describe algorithms and data structures to others, using well-established technical terms and structures, such as pseudocode and diagrams. We abstract away from technical details of a particular programming language, and focus on explaining the underlying ideas of a data structure or algorithm. We aim to provide you, the reader, with the means to write a good implementation in your favourite programming language.