Data Structures and Algorithms: Introduction

Data Structures and Algorithms

1. Introduction

This course is designed to teach you how to program efficiently. It assumes that

you know the basics of programming in C,
can write, debug and run simple programs in C, and
have some simple understanding of object-oriented design.

An introduction to object-oriented programming using ANSI standard C may be found in the companion Object First course.

Good Programs

There are a number of facets to good programs: they must

run correctly
run efficiently
be easy to read and understand
be easy to debug and
be easy to modify.

What does correct mean?

We need to have some formal notion of the meaning of correct: thus we define it to mean

"run in accordance with the specifications".

The first of these is obvious - programs which don't run correctly are clearly of little use. "Efficiently" is usually understood to mean in the minimum time - but occasionally there will be other constraints, such as memory use, which will be paramount. As will be demonstrated later, better running times will generally be obtained from use of the most appropriate data structures and algorithms, rather than through "hacking", i.e. removing a few statements by some clever coding - or even worse, programming in assembler!

This course will focus on solving problems efficiently: you will be introduced to a number of fundamental data structures and algorithms (or procedures) for manipulating them.

The importance of the other points is less obvious. The early history of many computer installations is, however, testimony to their importance. Many studies have quantified the enormous costs of failing to build software systems that had all the characteristics listed. (A classic reference is Boehm's text.) Unfortunately, much recent evidence suggests that these principles are still not well understood! Any perusal of Risks forum will soon convince you that there is an enormous amount of poor software in use. The discipline of software engineering is concerned with building large software systems which perform as their users expected, are reliable and easy to maintain. This course will introduce some software engineering principles but we will concentrate on the creation of small programs only. By using well-known, efficient techniques for solving problems, not only do you produce correct and fast programs in the minimum time, but you make your programs easier to modify. Another software engineer will find it much simpler to work with a well-known solution than something that has been hacked together and "looks a bit like" some textbook algorithm.

Key terms

correct: A correct program runs in accordance with its specifications
algorithm: A precisely specified procedure for solving a problem.