Data Structures and the Java Collections Framework, Third Edition

APPENDIX 2

Mathematical Background

A2.1 Introduction

Mathematics is one of the outstanding accomplishments of the human mind. Its abstract models of real-life phenomena have fostered advances in every field of science and engineering. Most of computer science is based on mathematics, and this book is no exception. This appendix provides an introduction to those mathematical concepts referred to in the chapters. Some exercises are given at the end of the appendix, so that you can practice the skills while you are learning them.

A2.2 Functions and Sequences

An amazing aspect of mathematics, first revealed by Whitehead and Russell [1910], is that only two basic concepts are required. Every other mathematical term can be built up from the primitives set and element. For example, an ordered pair < a, b > can be defined as a set with two elements:

< a, b > = {a, {a, b}}

The element a is called the first component of the ordered pair, and b is called the second component. Given two sets A and B, we can define a function f from A to B, written

f : A → B

as a set of ordered pairs < a, b >, where a is an element of A, b is an element of B, and each element in A is the first component of exactly one ordered pair in f. Thus no two ordered pairs in a function have the same first element. The sets A and B are called the domain and co-domain, respectively.

For example,

f = {< −2,4 >, < −1,1 >, < 0,0 >, < 1,1 >, < 2,4 >}

defines the "square" function with domain { −2, −1, 0, 1, 2 } and co-domain ...