12 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples properties that make it useful to think of them as one object.The notation eS is read "element e is a member of set S"or,briefiy,"e is in S."Notice that e and S are different types in this case.For example.if e is an integer,S is a set of integers,which is different from being an integer. A particular set is defined by listing or describing its elements between a pair of curly braces.Examples of this notation are SI=(a,b,c},S2=[x x is an integer power of 2,S3={1,...,n) The expression for S2 is read"the set of all elementsx such that x is an integer power of 2."The""symbot is read "such that"in this context.Sometimes a colon (""is used in this place.The ellipsis"..."may be used when the implicit elements are clear. If all elements of one set,S1,are also in another set,S2,then S is said to be a subset of S2 and S2 is said to be a superset of St.The notations are SS2 and S2 S1.To denote that S is a subset of S and is not equal to S2,we write SIC S2 or S2S1.It is important not to confuse "e"with"C."The former means"is an element in"and the latter means "is a set of elements contained within."The empty set,denoted by 0,has no elements,so it is a subset of every set. A set has no inherent order.Thus,in the above examples,S could have been defined as (b,c,u)and S3 could have been defined as (i1 <isn)when it is understood that i is an integer. A group of elements in a specified order is called a sequence.Besides order,another important difference between sets and sequences is that sequences can have repeated elements.Sequences are denoted by listing their elements in order,enclosed in parentheses. Thus (a,b,c),(b,c,a),and (a,b.c,a)are distinct sequences.The ellipsis can also be used for sequences,as in (1....,n). A set S is finire if there is an integer n such that the elements of S can be placed in a one-to-one correspondence with {1,...,n);in this case we write S=n.In general,S denotes the number of elements in set S,also called the cardinality of S.A sequence is finite if there is an integer n such that the elements of the sequence can be placed in a one- to-one correspondence with (1,....n).A set or sequence that is not finite is infinite.If all the elements of a finite sequence are distinct,that sequence is said to be a permation of the finite set consisting of the same elements.This again underscores the difference between a set and a sequence.One set of n elements has n!distinct permutations (see Section 1.3.2). How many distinct subsets does a finite set of n elements have?Keep in mind that the empty set and the entire set are subsets.To construct any subset we have n binary choices: to include or exclude each element of the given set.There are 2 distinct ways to make these choices,so there are 2"subsets. How many distinct subsets of cardinaliry k does a finite set of n elements have?There is a special notation for this quantity:()read"n choose k"or,more verbosely,"number of combinations of n items taken k at a time."The notation C(n,k)is also used,and these quantities are called binomial coefficients. To find an expression for),oC(nk),we focuson choices in the subset of k instead of choices in the original set,say S.We can make a sequence of k distinct elements of as
1.3 Mathematical Background 13 follows:The first element of the sequence can be chosen from any element of S,so there are n choices.Then the second element of the sequence can be chosen from any remaining element of S,so there are (n-I)choices for this,and so on until k elements are chosen. (If k >n it is impossible to make k distinct choices,so the result is 0.)Therefore there are n(n -1)...(n-k+1)distinct sequences of k distinct elements.But we saw that a specific set of k elements can be represented as k'sequences.So the number of distinct subsets of k,drawn from a set of n,is Cn,k)三 n(n-)…(n-k+1)n! (n-k)!k! forn≥k之0.(1.1) Since every subset must have some size from 0 through n,we arrive at the identity 2 1.2) k=0 Tuples and the Cross Product A tuple is a finite sequence whose elements often do not have the same type.For example, in a two-dimensional plane,a point can be represented by the ordered pair (x,y).If it is a geometric plane,x and y are both"length."But if it is a plot of running time vs.problem size,then y might be seconds and x might be an integer.Short tuples have special names: pair,triple,quadruple,quintuple,and so on.In the context of"tuple"these are understood to be ordered:in other contexts"pair"might mean"set of two"instead of "sequence of two,"and so on.A k-tuple is a tuple of k elements. The cross producr of two sets,say S and T,is the set of pairs that can be formed by choosing an element of S as the first element of the tuple and an element of T as the second. In mathematical notation we have S×T={(x,y)lx∈S,y∈T} 1.3) Therefore [S x TI =[SI[TI.It often happens that S and T are the same set,but this is not necessary.We can define the iterated cross product to produce longer tuples.For example, S x T x U is the set of all triples formed hy taking an element of S,followed by an element of T,followed by an element of U. Relations and Functions A relation is simply some subset of a(possibly iterated)cross product.This subset might be finite or infinite,and can be empty or the entire cross product.The most important case is a binary relation,which is simply some subset of a simple cross product.We are all familiar with many examples of binary relations,such as "less than"on the reals Letting R denote the set of all reals,the "less than"relation can be defined formally as (x.y)xER,y eR,x<y).As we see,this is a subset of R x R.As another example,if P is the set of all people,then P x P is the set of all pairs of people.We can define"parent of"as (x,y)such that x is a parent of y."ancestor of"as (x,y)such that x is an ancestor of y,and these are subsets of P x P
14 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples Although many relations are pairs in which both elements are the same type,this is not required by the definition.A set of pairs ((x.y)xeS,y T)is a hinary relation Going back to our earlier example of a tuple in a plot,such a rclation might represent the relationship between problem size and running time for some program.For another example,we might let F be the set of all female people,and then"x is mother of y"would be a subsct of Fx P. Although relations may be arbitrary subscts,there are certain common properties of interest that a relation R might have when botb elements are drawn from the same underiying set,say S.Also,in these cases,because many standard relations have an infix notation (such as x <y),the notation x Ry is often used to mean (x,y)E R. Definition 1.2 Important properties of relations Let RCS x S.Note the meanings of the following terms: refexive for all xe S.(xx)E R. symmetric whenever (x,y)E R.(y,x)is also in R. antisymmetric whenever (x,y)ER,(y,x)is not in R transitive whenever(x,y)∈Rand(y.z)∈R,then(x,z)∈R. A relation that is reflexive,symmetric,and transitive is called an equivalence relation, often denoted with“=”.■ Note that "less than"is transitive and antisymmetric,while "less than or equal"is transitive and reflexive,but not antisymmetric (becausex<x). Equivalence relations are important in many problems because such a relation parti- tions the underlying set S;that is,it divides into a collection of disjoint subsets (called equivalence classes)S1,S2....,such that all elements in S are"equivalent"to each other. all elements in S2 are equivalent to eachi other,and so on.For example,if S is some set of nonnegative integers and R is defined as(x.y)Ix eS,yeS,(x-y)is divisible by 3. then R is an equivalence relation on S.Clearly,(x-x)is divisible by 3.If (x-y)is di- visible by 3,so is (y-x).Finally,if (x-y)and (y -z)are divisible by 3,so is (x-z). So R satisfies the properties that define an equivalence relation.How does R partition S? There are three groups,each with a different nonnegative remainder when divided by 3. All clements with the same remainder are equivalent to each other. Since a binary relation is a set whose elements are ordered pairs,it is often convenient to think of the relation as a two-column table in which each row contains one tuple.A function is simply a relation in which no element of the first column is repeated within the relation. Many problems that involve binary relations can be cast as problems on graphs.Graph problems constitute a rich class of challenging algorithmic problems.For example,in a big project involving many interdependent tasks,we might have many facts of the form"task x depends on task y having been completed."With a fixed set of people to perform the tasks. how should they be scheduled to minimize the elapsed time?We will study many problems like this in later chapters
1.3 Mathematical Background 15 1.3.2 Algebra and Calculus Tools This section provides some definitions and elementary properties about logarithms,proba- bility,permutations,summation formulas,and common mathematical sequences and se- ries.(A series is the sum of a sequence in this context.)We will introduce additional mathematical tools for recurrence equations in Cbapter 3.You can find formulas not de- rived here by consuiting the sources in Notes and References at the end of the chapter. Floor and Ceiling Functions For any real number x,x](read"floor of x")is the largest integer less than or equal to x.[x](read "ceiling ofx")is the smallest integer greater than or equal to x.For example, L2.9=2,andf6.11=7. Logarithms The logarithm function,usually to the base 2.is the mathematical tool used most exten- sively in this book.Although logarithms do not occur very frequently in natural sciences, they are prevalent in computer science. Definition 1.3 Logarithm function and logarithmic base Forb>I andx>0.log(read"log to the base b of x")is that real number L such that x;that is,logx is the power to which b must be raised to get x. The following properties of logarithms follow easily from the definition. Lemma 1.1 Letx and y be arbitrary positive real numbers,let a be any real number,and let b 1 and c>I be real numbers. 1.log,is a strictly increasing function,that is,if x>y,then log x>log y. 2.log is a one-to-one function,that is,if logx=logb y,then x=y. 3.log1=0. 4.l0g影b=a. 5.log(xy)=log x +logb y. 6.log(xa)=alogn x. 7.xlogsy ylogo x. 8.To convert from one base to another:logx=(log x)/(log c). Since the log to the base 2 is used most often in computational complexity,there is a special notation for it:"lg";that is,Ig x=log2 x.The natural logarithm (log to the base e) is denoted by "In";that is,In x log.x.When log(x)is used without any base being mentioned,it means the statement is true for any base. Sometimes the logarithm function is applied to itself.The notation Ig Ig(x)means Ig(lg(x)).The notation Ig(x)means p applications.so lg()is the same as gIg(x). Note that Ig3)(65536)=2,which is quite different from (1g(65536))=4096
16 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples Throughout the text we almost always take logs of integers,not arbitrary positive numbers,and we often need an integer value close to the log rather than its exact value. Let n be a positive integer.If n is a power of 2,say n=2,for some integer k.then Ig n=k.If n is not a power of 2,then there is an integer k such that2<n2+1.In this case,[ig n]=k and ng n=k+1.The expressions [lg nJ and flg nl are used often. You should verify these inequalities: n≤2lgm]<2n 号<2≤n. Finally,here are a few more useful facts:Ig e1.443 and Ig 103.32.The derivative of In(x)is 1/x.Using part 8 of Lemma 1.1,the derivative of Ig(x)is lg(e)/x. Permutations A permutation of n distinct objects is a sequence that contains each object once.Let S=(s1,S2.....s).Note that tbe elements of S are ordered by their indexes;that is,s is the first element,s2 the second,and so on.A permutation of S is a one-to-one function x from the set (1,2....,n onto itself.We think of as rearranging S by moving the ith element,s;,to the r(i)th position.We may describe a simply by listing its values,that is, (π(1)，π(2)，..，π(n).For example,forn=5,π=(4,3，l,5,2)rearranges the elements of S as follows:S3,$5.52,51,54. The number of permutations of n distinct objects is n!.To see this,observe that the first element can be moved to any of the n positions;then that position is filled and the second element can be moved to any of the n-I remaining positions;the third element can be moved to any of the remaining n-2 positions.and so on.So the total number of possible rearrangements is nx(t-l)×(n-2)×..X2×1=n. Probability Suppose that in a given situation an event,or experiment,may have any one,and only one,of k outcomes,s1.52,....sk.These outcomes are called elementary events.The set of all elementary events is called the universe and is denoted U.With each outcome s;we associate a real number Pr(si),called the probability of si,such that 0≤Pr(s)≤1forI≤i≤k; Pr(s1)+Pr(s2)+...+Pr(sk)=1. It is natural to interpret Pr(s;)as the ratio of the number of times si is expected to occur to the total number of times the experiment is repeated.(Note,however,that the definition does not require that the probabilities correspond to anything in the real world.)The events s1,....S&are said to be mutually exclusive because at most one of them can occur. The examples most frequently used to illustrate the meaning of probability are flip- ping coins,throwing dice,and various events with playing cards.In fact the origin of probability theory is thought to be in the study of gambling games by Blaise Pascal,a French mathematician.If the "experiment"is the flip of a coin,then the coin may land