Introduction

This course is about computing. The notion of computing is much more fundamental than the notion of a computer, because computing can be done even without one. In fact, we have been computing ever since we entered primary school, mainly using pencil and paper. Since then, we have been adding, subtracting, multiplying, dividing, computing lengths, areas, volumes and many many other things. In all these computations we follow some definite, unambiguous set of rules. This course is about studying these rules for a variety of problems and writing them down explicitly.

When we explicitly write down the rules (or instructions) for solving a given computing problem, we call it an algorithm. Thus algorithms are primarily vehicles for communication; for specifying solutions to computational problems, unambiguously, so that others (or even computers) can understand the solutions. When an algorithm is written according to a particular syntax of a language which can be interpreted by a digital computer, we call it a program. This last step is necessary when we wish to carry out our computations using a computer.

While writing down algorithms, it is important to choose an underlying model of computation, i.e., to choose appropriate primitives to describe an algorithm. This choice determines the kind of computations that can be carried out in the model. For example, if our computational model consists of only ruler and compass constructions, then we can write down explicit rules (algorithms) for bisecting a line segment, bisecting an angle, constructing lengths equal to given irrational numbers and a plethora of other things. We cannot, however, trisect an angle. For trisecting an angle, we require additional primitives like, for example, a protractor. For arithmetic computations we can use various computing models like calculators, slide rules or even an abacus (as we believe our ancestors have been using). With each of these models of computing, the rules for specifying a solution (algorithms) are different, and the precision of the solution also differs. Thus, in our study of algorithms and programs, it becomes important to first choose a reasonable model of computation. Soon in these notes we will describe our choice of computational models which are widely used in modern computing using digital computers.

Once a computational model is available, and we can specify an algorithm (or a program) to solve a given problem, we have to ensure that the algorithm is correct. We would also wish that our algorithms are efficient. Correctness and efficiency of algorithm design are central issues in this course. In what follows, we will endeavour to develop methodologies for the design of correct algorithms.

Thus, the major vehicles for problem solving using computers are:

Algorithm

An Algorithm is a finite specification of the solution to a given problem (definite input and output). It is unambiguous and specifies a solution in terms of a finite process (finite number of steps in execution).

Effective Algorithm

When the solution is specified according to a model of computation (particular primitives).

Program

Encoding of an effective algorithm in the syntax of a programming language. This is necessary for machine execution of an algorithm.

In the two subsequent chapters we will establish two widely used models of computation and develop methodologies for algorithm design and proving correctness of algorithms in these models. The two models that we will introduce are the functional and the imperative models of computation. We will use the programming languages ML and Java to write programs in these two models respectively. We will devote the remaining part of this chapter to discuss some mathematical preliminaries necessary for programming.