Data Structures and Algorithms
An algorithm for a particular task can be defined as “a finite sequence of instructions, each of which has a clear meaning and can be performed with a finite amount of effort in a finite length of time”. As such, an algorithm must be precise enough to be understood by human beings. However, in order to be executed by a computer, we will generally need a program that is written in a rigorous formal language; and since computers are quite inflexible compared to the human mind, programs usually need to contain more details than algorithms. Here we shall ignore most of those programming details and concentrate on the design of algorithms rather than programs.
Fundamental questions about algorithms
Given an algorithm to solve a particular problem, we are naturally led to ask:
- What is it supposed to do?
- Does it really do what it is supposed to do?
- How efficiently does it do it?
The technical terms normally used for these three aspects are:
- Performance analysis
For many problems, the ability to formulate an efficient algorithm depends on being able to organize the data in an appropriate manner. The term data structure is used to denote a particular way of organizing data for particular types of operation. These concepts will look at numerous data structures ranging from familiar arrays and lists to more complex structures such as trees, heaps and graphs, and we will see how their choice affects the efficiency of the algorithms based upon them.
We will start by studying some key data structures, such as arrays, lists, queues, stacks and trees, and then move on to explore their use in a range of different searching and sorting algorithms. This leads on to the consideration of approaches for more efficient storage of data in hash tables. Finally, we will look at graph based representations and cover the kinds of algorithms needed to work efficiently with them. Throughout, we will investigate the computational efficiency of the algorithms we develop, and gain intuitions about the pros and cons of the various potential approaches for each task.