xvi Preliminaries and Notation fred,blue}CS {-23,-345,-9999,-12}CS2 fred,white,black}S fred,yellow}Cfred,yellow} Intersection Set S is the intersection of sets S'and S"if every member of S is a member of S' and also a member of S".This is denoted as:S=S'nS". fred,blue)=fred,yellow,blue,whitenblue,black,red} Union Set S is the union of sets S'and S"if every member of S is either a member of S'or it is a member of S"or it is a member of both S'and S".This is denoted as: S=S'US". fred,blue,white,black}=fred,blue,white}Ufblue,black,red} Set Difference Set S is the set difference of sets S'and S"if every member of S is a member of S'but is not a member of S".This is denoted as:S=S'-S". fred,blue}=fred,yellow,blue,white}-(black,yellow,white} Cartesian product The cartesian product of two sets S and S'is defined as a set of ordered pairs (x,y)(x,y)(y,x))such that x is a member of S and y is a member of S'; that is S*S'={(x,y)lx∈S andy∈S'}. For instance {red,blue}*{4,8}={(red,4),(red,8),(blue,4),(blue,8)} It can be shown that IS S'l =ISIx IS'l for finite sets.Similarly,the cartesian product of n sets S1,S2,...,Sn can be defined as S1 S2 *...Sn={(a1,a2,...,an)l aE S:for every i Each (v1,v2,...,vn)ES*S2 *...*Sn is called an n-ary tuple. Sets of Sets Sets can be members of other sets.For instance,a set of families is a set of sets
Preliminaries and Notation xvii where each member set is the names of people in a family: {{Fred,Mary,John},{Alf,Claire,Sue,Joe},...,{Jim,Anne}} Relations A relation R on S1,S2,...,Sn is defined as a subset of the cartesian product of these sets: TCS1 *S2*...*Sn R is called an n-ary relation.When n =2,R is called a binary relation.When n 3,R is called a ternary relation.For example relation age ={(Fred,25),(Jim,16),(Mary,25)} where S1={Fred,Jim,Mary}and S2 ={25,16}. Mappings (or Functions) A mapping or a function,F,from set Si to set S2 is a binary relation on S and S2 such that for every element x in S1 there is at most one element y in S2 such that (x,y)e F.This is denoted as F(x)=y.In other words,if F(x)=y and F(x)=z,then y must be equal to z.For instance,age is a function from the set {Fred,Jim,Mary}to the set {16,25}.Set S1 is called the domain of the map- ping F and set S2 is called the range of F.This is usually represented as F:S1→S2 Thus age {Fred,Jim,Mary}{16,25} An injective or one-to-one mapping,F,is one such that F(a)=F(b)if and only if a =b.If F is not injective,it is called a many-to-one function. A surjective mapping,F,is one such that for each y e S2,there exists an x∈S1 such that F(x)=y. A bijective mapping,F,is one which is both injective and surjective. Permutation and Combinations A permutation of m-ary tuples on a set S={a1,a2,...,an}is a set of ordered tuples(xi,x2,.·,xm)such thatxi∈S(for all)andx:≠x if i≠i A combination of m-ary tuples on a set S={a1,a,....an}is a set of un- ordered tuples(x1,x2,,,xm)such thatx∈S,x≠x if i≠i.For example, for S={1,2,3)and m=2:
xviii Preliminaries and Notation Permutation on S={(1,2),(1,3),(2,3),(2,1),(3,1),(3,2)} Combination on S={(1,2),(1,3),(2,3)} The number of permutations of m values out of n values is denoted by Pm and the number of combinations of m values out of n values is denoted by Cm.It can be shown that Pm=n!/(n-m)!and Cm =n!/(n-m)!m!. Sequences A sequence is a linear and ordered list of objects usually of the same type: a1,a2,a3,...an.A sub-sequence of this sequence is a sequence:ai,,... aim where (i,i,...,im)is a combination of m values from{1,2,...,n} such that if>ik ifj>k. Logical Operators and Quantifiers A n-ary predictate P(a1,a2,...,an)is a property which is true for some n-ary tuples and false for other tuples.For example person(Mary)is true person(chair)is false age(Mary,40)is true age(Mary,54)is false Predicates can be combined to form complex properties by using logical opera- tions:and,or,not,(implies),=(equivalent).Properties can have quantifiers: for all y and there exists 3.For example x number(x)=positive(xxx+1):For all x,ifx is a number,its square plus 1 is a positive number x3y greater(x,y): For all x,there exists a value of y such thatx>y Programming Language:Notations and Assumptions The language used in this book is primarily standard Pascal with a few minor variations.However,the algorithms can be expressed in Modula-2 or any other similar language with little difficulty.Now a few examples of the notation and assumptions made in the book regarding Pascal programs will be given. Throughout the book the existence of the procedure error is assumed: procedure error; begin
Preliminaries and Notation xix writeln(There has been an error.); goto 999 end; 999 is assumed to be a label at the end of the program.This procedure is called every time an error condition has occurred and therefore the program is term- inated.In a few places,this procedure is explicitly given a parameter to describe the nature of the error that has occurred. The data type 'elemtype'is used in the book and refers to a Pascal definable type.The assignment operation is supported for variables of type 'elemtype'. Usually 'elemtype'is used as the type of the individual elements of a structure. In a few places elemtype can only refer to a record structure of Pascal,but this is evident from the context.When appropriate,the values of type elemtype are assumed to be ordered such that the relations >,<'etc.can be applied to them. The identifiers used in the Pascal programs are allowed to have underscore characters_'and also may have subscripts or superscripts.(This is intended for improving the readability of programs.To run these programs,such decorations should be omitted.) var a_or_b:boolean; a1,a2:integer; A major notational extension is the use of an abstract control construct.This is primarily a means for traversing all the members of a set: for all s∈SdoP(s); where S is a set and P is a procedure.This statement is equivalent to executing P for every member of the set S.In Pascal,this control structure will be imple- mented as procedure process_all(var S:zet;procedure P(var s:elemtype)); (This procedure would execute P(s)for all elements s in the set S * process_all(S,P); Note that the type 'zet'refers to abstract data type 'set'as discussed in chapter 5.Pascal'set'data types are not allowed to participate as variable parameters of sub-programs.A similar control construct will be used for traversing members of a relation R: for all(a,x)∈RdoP(x)i where a is an element (constant)and x is a variable.This is equivalent to execut- ing P for every x such that the pair(a,x)is in R. Finally,the symbols and 'are used to denote sets and the symbols (*and'*)'are exclusively used to denote comments in Pascal programs
PART I DESIGN AND ANALYSIS OF DATA TYPES