An analysis of some computational structures

Abstract

In this dissertation we study some of the most conmen structures into which data is organised when solving a problem by means of a computer algorithm. We attempt to illustrate various different techniques involved in the development of computer programs, such as, the use of abstract data types as an extension of more primitive data types like integer and characters and as an important part of the modular development of the program; the analysis of the time complexity of an algorithm, particularly the average case analysis; the final implementation of the algorithms as a computer program. The main mathematical tool used in this analysis is the tree, which is a special type of graph. We see how trees can also model the decision making process of an algorithm, and we show how this gives lower bounds on the efficiency of algorithms which sort by comparisons. We also give full Pascal implementation of most of the algorithms we discuss, and we use some of these programs to give empirical data in support of the theoretical results we present.